语法分析和语法分析程序.

1三、SLR(1)分析表的构造常见程序设计语言都不是LR(0)的,所以LR(0)分析表实用性较差.例如,典型的分程序结构:B’→BB→bD;SeD→D;d|dS→s;S|s不是LR(0)文法.甚至常见的简单表达式文法G[E]也不是LR(0)文法.2B’→BB→bD;SeD→D;d|dS→s;S|s3不过,常见的程序设计语言相应的LR(0)分析表冲突项目较少,可以对分析表做一定的修改,消除“移进-归约”或“归约-归约”冲突.4SLR(1)分析表的构造（续）考虑LR(0)分析表的造表算法规则(2),对于Ii中归约项目A→·,不管下一输入符号是谁,均进行归约.若Ii中同时含有B→·b及C→·两类项目时,上述填表方法必然得到冲突的分析表.一般地,Ii={A1→·a11,…,Am→·amm,B1→·,…,Bn→·}如果能根据下一输入符号a对上述冲突加以区分,则冲突可解决.当集合FOLLOW(Bk)(1≦k≦n)与{a1,a2,…,am}两两互不相交时,则可按下述方法解决冲突:aVT{#},IFa{a1,a2,…,am}THENACTION[i,a]=sjELSEIFaFOLLOW(Bj)THENACTION[i,a]=rBjELSEACTION[i,a]=“ERR”5SLR(1)分析表的构造（续）上述方法就是SLR(1)(SimpleLR(1))规则.按照SLR(1)规则,只须将LR(0)分析表的填表规则(2)修改为:(2’)若归约项目A→属于Ii,且A→是P中第j产生式,则对于aFOLLOW(A),置ACTION[i,a]=rj注:其它规则不变!对于给定的文法G,若其相应的SLR(1)分析表无冲突项,则称G是SLR(1)文法.7四、LR(1)分析表的构造尽管SLR(1)分析表简单实用,但还不能解决所有问题;例如,文法S’→SS→CbBAA→Aab|abB→C|DbC→aD→a相应的DFA见下页。–其中项目集I10={S→CbBA·,A→A·ab}中存在“移进-归约”冲突,由FOLLOW(S)={#}≠{a},冲突是可解决的.–但项目集I8={C→a·,D→a·}中,FOLLOW(C)={a,b},FOLLOW(D)={b},存在公共元素b，不能解决此冲突.还需考虑另一个条件：归约后得到的符号串应该是一个规范句型的前缀，即当分析栈内容为#,输入符为a时,若将归约为A,则#Aa必须是某一规范句型的前缀,否则这个归约就是无效的.89LR(1)分析表的构造（续）例如,对于上述文法的规范句型Cbabab,分析达到格局：I0I2I4I8bab#Cba时,由于输入符b∈FOLLOW(C),若用C来归约,得到I0I2I4I6bab#CbC但CbCb不是任何规范句型的前缀!因此应该用D来归约，得到规范句型的前缀CbDb.因此,将#a归约成#Aa…的前提条件不仅仅是要求a∈FOLLOW(A),还必须要求Aa是某规范句型的前缀.–在原来的每个LR(0)项目[A]中放置一向前搜索符号a:[A,a],称为LR(1)项目.11求LR(1)项目集闭包算法类似于LR(0)分析,识别文法全部活前缀的DFA的状态是由LR(1)项目集表示的.对每个LR(1)项目集I,相应的闭包CLOSURE(I)的定义为(1)ICLOSURE(I);(2)设项目[AB,a]CLOSURE(I),对所有形如B的产生式,及每个bFIRST(a),将[B,b]=CLOSURE(I);(3)重复(2),直到CLOSURE(I)不再增大.13GO函数及DFA的构造方法为求GO(I,X),其中I为LR(1)项目集,X∈V,类似于LR(0)方法,有:GO(I,X)=CLOSURE(J)其中,J={[AX,a]|[AX,a]I}注意,每个LR(1)项目与其后继项目有相同的搜索符号采用与LR(0)类似的方法,可构造出文法G的LR(1)项目集族C及状态转换图(DFA).14I0:S’→·S,#S→·CbBA,#C→·a,bI1:S’→S·,#SI3:C→a·,baI2:S→C·bBA,#CI4:S→Cb·BA,#B→·C,aB→·Db,aC→·a,aD→·a,bbI5:S→CbB·A,#A→·Aab,#/aA→·ab,#/aI6:B→C·,aBCI8:C→a·,aD→a·,baI7:B→D·b,aI9:B→Db·,aDbI11:A→a·b,#/aI12:A→ab·,#/aabI10:S→CbBA·,#A→A·ab#/aAI13:A→Aa·b,#/aI14:A→Aab·,#/aab图4-19文法G[S]的LR(1)项目集及DFA15LR(1)分析表的构造利用LR(1)项目集族C和GO函数构造LR(1)分析表:(1)对于每个项目集Ii中的项目[AX,a],并且GO(Ii,X)=Ij,IFX∈VTTHENACTION(i,X)=sjELSE(X∈VN)GOTO(i,X)=j;(2)若归约项目[A,a]∈Ii,A是第j产生式,则ACTION(i,a)=rj;(3)若[S’→S,#]∈Ii,则ACTION(i,#)=“acc”;(4)其它:ERROR.对于一文法G而言,若按上述方法所构造的分析表不含多重定义的元素,则称此分析表为LR(1)分析表.凡具有LR(1)分析表的文法称为LR(1)文法16状态ACTIONGOTOab#SABCD0s3121acc2s43r64s85675s11106r47s98r6r79r510s13r111s1212r3r313s1414r2r2分析表实例17五、LALR(1)分析简介从前面的介绍可知,每个LR(1)项目均由两部分组成,一是LR(0)项目,称为LR(1)项目的核;一是向前搜索符号集.对于移进项目,搜索符集无作用;对于归约项目,它指明了在扫描到不同的符号时用不同的产生式进行归约.上述原理解决了SLR(1)分析中所不能解决的冲突,使LR(1)分析比SLR(1)分析的能力有明显的提高.LR(1)也有缺点:分析表状态数过大,使分析的效率降低.为解决二者之间的能力与效率之矛盾,LALR(1)分析是最佳方案.LALR(1)方法的分析能力介于LR(1)与SLR(1)之间.是目前最流行的分析技术.18LALR(1)分析简介(续)LALR(1)分析(LookAhead-LR)是由F.DeRemer提出的.其基本思想就是将LR(1)项目集中的同心集合并,将其压缩为较小的DFA,若压缩过程并未带来新的冲突,则分析表可大大地简化(状态数与SLR(1),LR(0)的DFA相同).核相同的LR(1)项目集称为同心集，合并同心集是将其中对应的LR(1)项目的向前搜索符号集合并到一起。19文法G[E]的LR(1)项目集.合并前该文法有22个状态。2021文法G[E]的LALR(1)项目集.合并后只有12个状态。2223关于各类文法的一些结论1.任何LR(K),LL(K)及简单优先文法类都是无二义性文法;2.任何二义性的文法不可能是LR(K)文法,但借助其它方法,可对某些二义性文法建立无冲突的LR(K)分析表;3.每个SLR(K)文法必是LR(K)的,存在LR(1)文法,对任何K,它不是SLR(K)的.4.各文法类之间的关系见图4-24