编译原理第4章语法分析自下而上LR分析法.ppt

4.3 LR分析法,图 1,语法分析概述,LR分析法是一种自下而上进行规范归约的语法分析方法,L指自左向右扫描输入串,R指最右推导(规范归约)。LR分析法比递归下降分析法、LL(1)分析法对文法的限制要少得多,大多数无二义性CFG语言都可用LR分析器识别,且速度快,并能准确、指出输入串的语法错误及出错位置。LR分析法的主要缺点:手工构造工作量相当大,必须求助自动产生工具。,LR分析程序(器)：自左向右扫描，识别句柄，自下而上归约的语法分析程序。LR分析程序生成器：自动生成LR分析程序的程序。,LR分析器（分析表）的分类：LR(0)表构造法。这种方法的局限性较大、但它是建立其它较一般的LR分析法的基础。简单LR（简称SLR）表构造法。虽然一些文法不能构造SLR分析表，但是，它是一种比较容易实现又很有使用价值的方法。规范LR表构造法。这种分析表能力最强，能够适用一大类文法，但实现代价高，或者说，分析表的体积非常大。向前LR表构造法（简称LALR）。这种分析表的能力介于SIR和规范LR之间，可以高效地实现。,LR分析器的工作原理 规范归约(最右推导逆过程)的关键是寻找句柄。LR分析法的基本思想:在规范归约过程中,一方面记住已移进和归约出的符号串,即记住“历史”(栈);另一方面根据所用产生式推测未来可能遇到的输入符,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈栈顶时,希望能根据所记载的“历史”、“展望”及“现实”材料来确定栈顶符号是否构成句柄。,分析表产生器,文法,分析表,LR分析程序结构,一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。我们将把“历史”和“展望”材料综合地抽象成某些“状态”（自动机）。分析栈（先进后出存储器）用来存放状态。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。因此，在任何时候都可从栈顶状态得知所想了解的文法的一切信息，而没有必要从底而上翻阅整个栈。LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。,4.3.1 LR分析过程,LR分析的核心分析表,分析表由ACTION表和GOTO表两部分组成。ACTION(s，a)：表示当状态s面临输入a时的动作GOTO(s，x)：规定了状态s面对文法符号X(非终结符）时的下一状态,文法G(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,分析表（图）,分析表中记号的含义sj：把下一状态 j 和现行输入符号 a 移进栈；rj：按第 j 个产生式进行归约；acc：接受；空白格：出错标志，报错,给出下述文法G的LR分析表,幻灯片 11,ACTIONk,a的动作:(1)移进:设表中ACTIONk，a=Sj，当S栈顶状态为k，现行输入符号为a，总控程序根据“k”和“a”查LR(0)分析表，得：ACTIONk，a=Sj此时，Sj 表示j状态进S栈，a进T栈（文法符号栈）。,(2)归约:设LR(0)分析表中的ACTIONmn，a=rj，其中rj表示使用文法的第j个产生式Ax1x2xp归约；mn表示LR分析表的一个状态。假设总控程序按S栈顶状态mn和现行输入符号a查LR分析表，得ACTIONmn，a=rj此时，S栈的状态为：m1,mn-p+1,mn文法符号T栈的符号为：x1x2xp按ACTIONmn，a=rj 的要求：,S栈应删除栈顶p个状态：mn-p+1,mn删除后，S栈成为：m1,mn-p T栈中x1x2xp归约成A，即T栈栈顶删除p个文法符号，非终极符A进T栈；若GOTOmn-p，A=j，则状态j进S栈。,(3)接受:宣布分析成功,分析器停止工作。当S栈顶状态为k，现行输入符号为a，总控程序根据“k”和“a”查LR分析表得：ACTIONk，a=accacc说明语法分析成功。(4)报错:报告发现源程序有错,调用出错处 理程序。总控程序若按“k”和“a”查表得：ACTIONk，a=空白说明语法分析出错，所给输入串不是本文法的句子。,LR分析器总 控 程 序 的工作十分简单,它的任一步只需按分析栈栈顶状态s和现行输入符a执行ACTIONs,a所规定的动作。LR分析器的工作过 程 可看成是栈中状态序列、已归约串和输入串构成的三元式的变化过程。,2.句型分析过程,设所给输入串为#i*i+i#，则总控程序分析此输入串的过程，如表4-11所示，通过分析，说明i*i+i是文法例4.4的句子。,例 利用上述分析表，假定输入串为 i*i+i，描述LR分析器的工作过程。,状 态,符 号,输入串,（1）0#i*i+i#（2）05#i*i+i#（3）03#F*i+i#（4）02#T*i+i#（5）027#T*i+i#（6）0275#T*i+i#（7）02710#T*F+i#（8）02#T+i#（9）01#E+i#,ACTION 0,i=s5移进 5 和 i,ACTION 5,*=r6按第6个产生式进行归约，即：(6)Fi,GOTO0,F=3移进状态3,ACTION 10,+=r3按第3个产生式进行归约，即(3)TT*F,GOTO0,T=2移进状态2,例 利用上述分析表，假定输入串为 i*i+i，描述LR分析器的工作过程。(续),状 态,符 号,输入串,（10）016#E+i#（11）0165#E+i#（12）0163#E+F#（13）0169#E+T#（14）01#E#,ACTION1,#=acc接受输入串！,LR文法,LR（k）文法：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。,定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们把这个文法称为LR文法。,存在不是LR的上下文无关文法若一个文法的任何“移进-归约”分析器都存在下述情况:尽管栈的内容和下一输入符都已了解,但仍无法确定是“移进”还是“归约”,或无法从几种可能的归约中确定其一,则该文法为非LR文法。注意:(1)LR文法肯定是无二义的,一个二义文法不会是LR文法。(2)LR分析技术可适当修改以适于一定的二义文法。,LR分析法的主要任务：构造一张LR分析表 首先讨论一种只概括“历史”资料而不包含推测性“展望”材料的“状态”。希望仅由这种简单状态就能识别呈现在栈顶的某些句柄。LR(0)项目集就是这样一种简单状态。,、LR(0)项目集规范族和LR(0)分析表,两种LR(0)分析表的构造算法：方法一：先构造识别文法的活前缀非确定有限自动机，然后确定化，再构造LR(0)分析表；方法二：是直接构造LR(0)项目集规范族，再构造LR(0)分析表。,方法一：LR(0)分析表的构造步骤 确定G的LR(0)项目 以LR(0)项目为状态,构造一个能识别文法G的所有活前缀的NFA 利用子集法,将NFA确定化,成为以项目集合为状态的DFA根据 上述DFA可直接构造出LR分析表,定义：文法G每一个产生式的右部添加一个圆点，称为 G的一个LR(0)项目。设文法G的某一产生式为Ax1x2xn，则Ax1xi.xi+1xn称为文法G的LR(0)项目。如：AXY对应三个项目：AXY AXY AXY 而:A的项目 A,B、句型的活前缀及文法的LR(0)分析表,项目的意义：指明在分析过程的某时刻，我们看到产生式多大一部分项目在计算机中的表示：（m，n）int m，n m：代表产生式编号 n：指出圆点的位置,如：abc前缀：，a，ab，abc活前缀：规范句型的一个前缀，该前缀是不含句柄之后 的任何符号。,C、字的前缀：指该字的任意首部,例4.5 文法为：（1）SE（2）EaA（3）AcA（4）Ad其句型“acd”，d是句柄，活前缀为：；a；ac；acd同理，在句型“acA”中，句柄是“cA”活前缀为：；a；ac；acA,称为活前缀原因：在右边增添一些终结符号就可以使它成为一个规范句型。在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2.Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。,D、对文法G，构造能识别G的所有活前缀的NFA,识别文法句型活前缀的非确定有限自动机(NFA M)包括：状态、状态转换、初态、终态NFA的状态：是一个LR(0)项目,一个项目指明了在分析过程的某时刻看到产生式多大一部分 构造方法：a.文法开始符号的形如SS的项目为NFA的唯一初态；文法的所有LR(0)项目构成的状态都是识别文法的规范句型的活前缀的终态。活前缀识别态,b.若状态i和j出自同一个产生式，而且j的圆点只落后于i的圆点一个位置，就从i画一条标志为Xi的弧到j。（即，i：XX1Xi-1XiXn j：XX1 Xi-1XiXn）c.若状态i的圆点之后的符号为非终结符，如i为 XA，其中A属于VN，就从状态i画弧到所有A状态。,例.构造以下文法的NFA,文法G的所有LR(0)项目,文法 G S E E aA|bB A cA|d B cB|d,1.S E 2.S E 3.E aA 4.E a A 5.E aA 6.A cA 7.A c A 8.A cA 9.A d 10.A d 11.E bB 12.E b B 13.E bB 14.B cB 15.B c B 16.B cB 17.B d 18.B d,利用上述规则a，b，c构造NFA，如图所示：,E,E、使用子集方法，将NFA确定化，使之成为一个以项目集合为状态的DFA。（1）SE（2）EaA（3）AcA（4）Ad,可将文法的LR(0)项目分成如下四类：A 归约项目S 接收项目，其中，S是开始符号Aa 移进项目，其中，aVTAB 待归约项目，其中，BVN识别例4.5的文法的句型“acd”的过程,先构造识别句型的活前缀NFA M，然后确定化太繁琐，下面给出一种直接构造DFA M的方法,3.LR(0)项目集规范族（方法二）相关定义：定义 4.12 若I是一个LR(0)项目集，则项目集Closure(I)的定义如下：（a）Closure(I)=I；（b）若项目ABClosure(I)，BVN，则Closure(I)=Closure(I)B；（c）重复(b)，直至Closure(I)不再扩大为止。,定义 4.13 设I为LR(0)项目集，X是一文法符号，LR(0)状态转换函数GO(I，X)的定义如下：GO(I，X)=Closure(J)其中：J=任何形如AX的项目|AXI,文法（1）SE（2）EaA（3）AcA（4）Ad若S EI，则Closure(I)=S E，E aA，令I0=SE，EaA，则GO(I0，E)=SE=I1GO(I0，a)=EaA，AcA，Ad=I2 从项目集I0开始，将I0定义成一个状态，按照状态转换函数GO(I，X)的定义可以找出所有的项目集（状态），由GO(I，X)所产生的项目集（状态）全体称为LR(0)项目集规范族。,构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，而这个S是G的开始符号。称G是G的拓广文法。把文法G进行拓广为了使“接受”状态易于识别，有一个仅含项目SS的状态，这就是唯一的“接受”态。,拓广文法,步骤一:令NFA的初态为I,求其CLOSURE(I),得到初态项目集。即:求CLOSURE（SS)步骤二:对所得项目集I和文法G的每个文法符号X(包括VT和VN)计算GO（I，X）=CLOSURE（J），得到新的项目集。其中J=任何形如A X 的项目|A X 属于I 步骤三:重复步骤二，直至没有新的项目集出现。经过以上步骤构造出的项目集的全体即为LR(0)项目集规范族。,利用LR(0)项目集规范族和GO函数画出DFA,构造项目集规范族方法,构造LR(0)项目集规范族的,例如，文法G为：SaBCBbCc拓广文法G为：（1）SS（2）SaBC（3）Bb（4）Cc句子“abc”的规范归约过程如下：abc，aBc，aBC，S，S运用图识别输入串“abc”的过程,有效项目（课本P86类似）,项目A 1.2对活前缀1是有效的，存在规范推导,在任何时候，分析栈中的活前缀X1X2 Xm的有效项目集正是状态栈顶Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 Xm后到达的那个项目集(状态)。(LR分析的基本定理，陈火旺P108),*,文法G(S)SE EaA|bB AcA|d BcB|d 考虑：项目：B c.BB.cB B.d 活前缀：bcS E bB bc.B(项目B c.B)S E bB bcB bccB(项目B.cB)S E bB bcB bcd(项目B.d),项目A 1.2对活前缀1是有效的，其条件是存在规范推导:,相关定义：LR(0)文法：不存在以下两种冲突的文法 移进归约冲突 归约归约冲突 LR(0)表：由LR(0)文法得到的分析表 LR(0)分析器：使用LR(0)表的分析器,LR（0）分析表的构造,给定文法G，设文法G拓广为文法G，假若文法G的项目集规范族（识别句型的活前缀确定有限自动机）已经给出;其状态（项目集）为I0，I1In，则分析表的构造算法如下（算法中，Ii状态用右下角标i表示，Sj、rk的意义同前）：,分析表的构造方法 如下：（1）设GO(Ii，X)=Ij，若XVT，则置Action(i，X)=Sj，表示将状态j和终结符X移进栈；若XVN，则置GOTO(i，X)=j，表示将状态转换为j进栈。（2）设项目AIi，若A不是文法的开始符号，则置Action(i，a)=rk，rk表示用文法的第k个产生式进行归约，“a”表示集合VT#的所有符号，若A是文法的开始符号，则置Action(i，#)=“acc”，符号“#”表示句子右界符。（3）分析表中的空白表示出错。,（1）SS（2）SaBC（3）Bb（4）Cc,练习：假定文法的各个产生式的编号如下，构造其LR(0)项目集规范族 和LR(0)分析表：0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,DFA构造：（部分）,CLOSURE(S-E)=S-E,E-aA,E-bB 此即为DFA的状态0,令I=S-E,E-aA,E-bB GO(I,a)=CLOSURE(E-aA)/即I中所有圆点之后紧跟a的=E-aA,A-cA,A-d GO(I,b)=CLOSURE(E-bB)=E-bB,B-cB,B-d GO(I,E)=CLOSURE(S-E)=S-E,同上步骤，依次对各项目集进行计算（略）LR(0)分析表构造,（DFA部分图，全图见下页）,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,E,a,b,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,E,该文法的LR(0)分析表？,该文法的LR(0)分析表如下所示：,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,试对acccd进行分析？,例:按上表对acccd进行分析步骤 状态栈 符号栈输入串10#acccd#202#acccd#3024#acccd#40244#acccd#502444#acccd#60244410#acccd#7024448#acccA#802448#accA#90248#acA#10026#aA#1101#E#,文法 G 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,LR(0)分析法的局限性-语法动作冲突,LR(0)分析法的关键:由项目集规范族构造LR(0)分析表 任给一状态（项目集）和任一符号“a”（aVT#），使得Action(i，a)的值是唯一的（无冲突）。若Action(i，a)值不唯一，我们称为语法动作冲突。分情况讨论：,（1）无冲突：若一个项目集Ii中仅含移进项目或仅含一个规约项目，则Action(i，a)的值是唯一的，其中，aVT。,（2）移进归约冲突：若一个项目集Ii中，既含有移进项目，又含有归约项目，此时，Action(i，a)值不唯一，其中，aVT，i表示状态Ii。,（3）归约归约冲突：若一个项目集Ii中，存在两个或两个以上的归约项目，则Action(i，a)的值不唯一 上述（2）、（3）两种情况中的动作冲突，有一部分可以使用FOLLOW集 解决,即SLR(1)分析法。,例4.6 设文法为：（0）SS（1）SabdD（2）SaBc（3）Bb（4）Dd LR(0)项目集规范族 应按如下规则填写，cFOLLOW(B)：Action(3，c)=r3 Action(3,d)=S4，d不属于FOLLOW(B)所以：Action(3,d)r3,、SLR（1）表的构造方法,SLR是LR(0)的一种改进，它在归约时除了考虑历史情况之外还考虑了现实输入。,（0）SS（1）SabdD（2）SaBc（3）Bb（4）Dd,对于I3 SLR(1)填写规则：cFOLLOW(B)：Action(3，c)=r3 Action(3,d)=S4，,为什么当xFOLLOW(B)时，SLR(1)分析表填Action(3，x)=r3,而Action(3，d)=s4呢？因为 SaBdD不成立，而S SabdD成立，也就是说，“aBdD”不是句型，B后面只能出现“x”，不能出现“d”，,（0）SS（1）SabdD（2）SaBc（3）Bb（4）Dd,归约归约冲突例 若I=Xb，A，B 若当前输入符号为b，则含有移进归约冲突；而A和B，又含有归约归约冲突。,则当 I 面临任何输入符号a时，可做出如下“移进归约”决策：若a=b，移进；若a属于FOLLOW（A），则用A归约；若a属于FOLLOW（B），则用B归约；此外，报错。,I=Xb，A，B,2、SLR（1）表的构造方法 若项目Aa属于Ik且GO(Ik,a)Ij，a为终结符，且置 ACTIONk，a为“把状态j和符号a移进栈”，简记为“sj”；若项目A属于Ik，那么，对任何输入符号a，aFOLLOW(A)，置ACTIONk，a为“用产生式A进 行归约”，简记为“rj”；其中，假定A为文法G的第j个 产生式；若项目SS属于Ik，则置ACTIONk，为“接受”，简 为“acc”；若GO(Ik，A)=Ij，A为非终结符，则置GOTOk，A=j；分析表中凡不能使用规则1至4填入信息的空白格均置上“出 错标志”。,只在归约时 展望,即已到产生式末尾,则去判断FOLLOW(A),SLR(1)分析表 项目集,（0）SS（1）SabdD（2）SaBc（3）Bb（4）Dd,文法 G：(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,练习：对如下文法构造其SLR（1）分析表。,FOLLOW集如下：FOLLOW(S)=#FOLLOW(E）=+，），#FOLLOW(T)=+,*,),#FOLLOW(F)=+,*,),#,该文法的LR(0)项目集规范族由这些项目集的转换函数GO表示成的DFA文法G的非终结符的FOLLOW集如下：FOLLOW(S)=#FOLLOW(E）=+，），#FOLLOW(T)=+,*,),#FOLLOW(F)=+,*,),#SLR分析表,I0：S E E E+T E T T T*F T F F(E)F i,I2：E T T T*F,I1：S E E E+T,I4：F(E)E E+T E T T T*F T F F(E)F i,I7：T T*F F(E)F i,I10：T T*F,I6：E E+T T T*F T F F(E)F i,I8：F(E)E E+T,I11：F(E),I9：E E+T TT*F,I5：F i,I3：T F,T,E,(,i,i,F,F,*,+,(,(,E,T,I2,),T,F,i,I3,I5,F,(,*,I4,i,I5,FOLLOW(S)=#FOLLOW(E）=+，），#FOLLOW(T)=+,*,),#FOLLOW(F)=+,*,),#,文法 G 的SLR分析表如下所示：,FOLLOW(S)=#FOLLOW(E)=+，)，#FOLLOW(T)=+,*,),#FOLLOW(F)=+,*,),#,任一文法，可按上述算法构造一张表，若表无多重定义入口，则此表称为SLR(1)分析表。具有SLR(1)分析表的文法，称为SLR(1)文法。具有SLR(1)分析表的分析器（SLR(1)分析表+总控程序）称为SLR(1)分析器；,1.非SLR(1)文法举例例4.7 文法：（0）SS（1）SaCaCb（2）SaDb（3）Ca（4）Da,、LR（1）分析表的构造,I3有归约冲突，用C、D的后继符号：FOLLOW(C)=a，bFOLLOW(D)=b解决不了冲突，因为：FOLLOW(C)FOLLOW(D)=b 完整 LR(0)项目集规范族见课本,（0）SS（1）SaCaCb（2）SaDb（3）Ca（4）Da,问题：有些无二义文法会产生“移进/归约”冲突 或“归约/归约”冲突产生原因：SLR(1)分析法未包含足够多的“展望”信息解决办法：让每个状态含有更多的“展望”信息方法：重新定义项目，使得每个项目都附带有k个终结符；即每个项目的形式为：A-,a1a2ak,LR（1）分析表的构造,LR(0)项目A加上k个搜索符a1a2ak，就构成一个LR(k)项目：A，a1a2ak其中，aiVT（i=1，2，k），此项目要求存在规范推导SA a1a2aka1a2ak这里仅考虑LR(1)项目A，a，LR(0)项目与LR(1)项目之间的区别是后者多了一个搜索符。,2.LR(k)项目与LR(1)有效项目,向前搜索符a仅对归约项目A-,a有意义；归约项目A-,a意味着：当它所属的状态呈现在栈顶且后续的输入符号为a时，才可以把栈顶上的归约为A只研究k1的情形,说明：,定义4.15 我们称一个LR(1)项目A，a对活前缀是有效的，如果存在规范推导SAWW其中，=，aFIRST(W)，若W=，则a=“#”。,SAWW其中，=，aFIRST(W)例4.8（0）SS（1）SBB（2）BaB（3）BbLR(1)项目BaB，a对活前缀=aaa是有效的，这里，=aa，=a，=B。对于活前缀=aaa，下面给出规范推导证明：SSBBBabaBabaaBabaaaBab即：SaaBabaaaBab“aaaBab”中，“aaa”是规范句型的前缀，而且不含句柄（aB）之后的符号，所以是活前缀。,3.LR(1)项目集规范族的构造算法,算法与构造LR(0)项目集规范族类似。对任意LR(1)项目集I,需定义 Closure(I)和GO(I，X)，其中，X(VNVT)定义4.16(a)若I是一个LR(1)项目集，则置Closure(I):=I；(b)若项目AB，aClosure(I)，且B是一产生式，则对于bFIRST(a)的每个符号，做：Closure(I):=Closure(I)B，b(c)重复(b),直至Closure(I)不再扩大为止。（对于A有：SAWBW，同理对于B也符合定义）,例如，文法SABAaBb假设I=SAB，#，则Closure(I)=SAB，#，Aa，b,定义4.17:令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为：GO(I，X)CLOSURE(J)其中 J形如AX,a的项目|AX,a I 注意：搜索符号a不改变。例如项目集I0=SAB，#，Aa，b，则 GO(I0，A)=SAB，#，Bb，#,LR(1)项目集规范族算法设所给文法G,定义拓广文法G S：void intemsetsb(G)C=closureSS，#;do for(C中的每个项目集I和G中的每个文法 符号X）if(GO(I,X)非空且不属于G)将GO(I,X)加入G;while(!(G不扩大为止),例4.7（0）SS（1）SaCaCb（2）SaDb（3）Ca（4）Da,练习：例4.8（0）SS（1）SBB（2）BaB（3）Bb构造 LR(1)项目集规范族,（0）SS（1）SBB（2）BaB（3）Bb,4、构造LR（1）分析表的步骤：,确定LR(1)项目；利用函数CLOSURE和GO求DFA（即：构造 LR(1)项目集规范族）;根据DFA，构造LR(1)分析表。,根据DFA,构造LR(1)分析表,设文法G的LR(1)项目集为：I0，I1，In。在分析表中，用状态i表示第i个项目集Ii，分析表的构造算法如下：（1）若LR(1)项目AX，aIi，且GO(Ii，X)=Ij，则当XVT时，置ACTION(i，X)=Sj；当XVN时，置GOTO(Ii，X)=j。（2）若A，aIi，且A是文法的第k个产生式，则当AVn-S时，置ACTION(i，a)=rk，rk 表示使用第k个产生式的归约；当A=Sa=“#”时，置ACTION(i，#)=“acc”。（3）空白表示出错。,例4.8拓广文法的规范LR分析表,(0)S-S(2)B-aB(1)S-BB(3)B-b,LR(1)分析法小结,LR(1)分析表的构造,状态集的计算方法和 LR(0)基本相同,分析表的构造方法和 LR(0)基本相同,构造方法的不同点：归约动作的选择,SLR(1)分析参考 FOLLOW 集归约,LR(1)分析仅考虑 LR(1)项目中的后继符,LR(1)方法的优缺点：解决了SLR(1)分析所难以解决的“移进-归约”或“归约-归约”冲突。LR(1)分析表状态多，规模大。算法适用范围广。,4.3.5 LALR(1)方法,LALR(lookahead-LR)技术。这种方法在实际中是经常使用的。LALR(1)和SLR(LR(0)的分析表有同样多的状态，而规范LR分析表要大得多。LALR(1)的能力介于SLR(1)和规范LR(1)之间。,LALR(1)分析表的构造,问题：对于一般的语言，规范LR分析表要用几千个状态，实际应用很困难分析：由例4.8中可以看到，有些状态集除了搜索符不同外是两两相同的解决办法：合并同心集，构造LALR(1)分析表,我们称两个LR(1)项目集具有相同的心，如果除去搜索符之后，这两个集合是相同的(LR(0)项目相同)。,将所有同心的LR(1)项目集合并后，得到一个心就是一个LR(0)项目集。,说明：,I3:B a B,a/bB aB,a/bB b,a/b,I6:B a B,#B aB,#B b,#,I36:B a B,a/b/#B aB,a/b/#B b,a/b/#,合并为,合并项目集时要修改转换函数，即GO(I,X)；动作ACTION应进行修改，使得能够反映各被合并的集合的既定动作。,LR(1)项目集导入同心集I i0，Ii1，Iik的弧，现导入合并后的项目集JP，弧上标记不变；由同心集I i0，Ii1，Iik导出的弧，改由JP导出，弧上标记不变。,根据图413 I3和I6，I4和I7，I8和I9分别为同心集,I3:B a B,a/bB aB,a/bB b,a/b,I6:B a B,#B aB,#B b,#,I4:B b,a/b,I7:B b,#,I8:B a B,a/b,I9:B a B,#,I36:B a B,a/b/#B aB,a/b/#B b,a/b/#,I47:B b,a/b/#,I89:B a B,a/b/#,合并为,合并为,合并为,合并同心集不会产生新的移进-归约冲突，但有可能产生新的“归约-归约”冲突。,若同心集合并前，任一同心集无移进、归约冲突，则合并后，不可能引起归约、移进冲突。若 a1，amX1，Xn则 有语法分析动作冲突；反之无冲突。,合并同心集，可能引起归约与归约冲突。例：下面文法是LR(1)的，但不是LALR(1)的。S S S aAd bBd aBe bAe A c B c,S S，#S aAd,#S bBd,#S aBe,#S bAe,#,S S，#,S a Ad,#S a Be,#A c,dB c,e,a,S,S b Bd,#S b Ae,#A c,eB c,d,b,A,S a A d,#,B,S a B e,#,c,A c,d B c,e,A c,eB c,d,c,引起归约与归约冲突。,I3和I5合并得：,对于同一个文法，LALR分析表和SLR分析表具有相同数目的状态，却能处理一些SLR所不能分析的文法。思考：文法：S-L=R(2)S-R(3)L-*R(4)L-i(5)R-L(0)S-S判断该文法是否是LR(0)、SLR(1)、LR(1)、LALR(1)文法？,文法：S-L=R(2)S-R(3)L-*R(4)L-i(5)R-L(0)S-S,S-L=RR-L,LR(0)项目,S-L=R,#R-L,#,LALR(1)项目,A、构造LALR分析表的第一个算法,步骤：构造文法G的LR(1)项目集族C=I0,I1,In把所有的同心集合并在一起，记C=J0,J1,Jm为合并后的新族。那个含有项目S-S,#的Jk为分析表的初态从C构造ACTION表构造GOTO表分析表空白格均填上“出错标志”,a、若项目Aa,b属于Jk且GO(Jk,a)Jj，a为终结符，则置ACTIONk，a为“sj”；b、若项目A,a属于Jk，则置ACTIONk，a为“用产生式A归约”，简记为“rj”；其中，假定A为文法G的第j个产生式；c、若项目SS,#属于Jk，则置ACTIONk，为“接受”，简记为“acc”；,从C构造ACTION表,根据图413 I3和I6，I4和I7，I8和I9分别为同心集,I3:B a B,a/bB aB,a/bB b,a/b,I6:B a B,#B aB,#B b,#,I4:B b,a/b,I7:B b,#,I8:B a B,a/b,I9:B a B,#,I36:B a B,a/b/#B aB,a/b/#B b,a/b/#,I47:B b,a/b/#,I89:B a B,a/b/#,合并为,合并为,合并为,由合并后的集族所构成的LALR分析表,结论：LALR(1)分析法比LR(1)分析法对某些错误发现的时间推迟-合并同心集后多做了规约.,一个文法是LALR(1)文法，也是LR(1)文法，但不一定是SLR(1)，LR(0)文法。,一个文法是LR(1)文法，不一定是LALR(1)文法。,LR(1)分析方法和LL(1)分析方法的比较,LR分析方法和LL(1)分析方法的比较,LR(1)分析方法和LL(1)分析方法的比较,4.3.6 二义文法的应用,任何二义文法不是一个LR文法,因而也不是SLR(1)或LALR(1)文法。但二义文法的问题是因其没有定义算符优先级和结合规则而产生了二义性。因此,下面讨论使用LR分析法的基本思想,凭借一些其它条件分析二义文法。,二义文法G1：E E+E|E*E|(E)|i非二义的文法G2：E E+T|T T T*F|F F(E)|i 对比可以发现G1有两个优点：1)、若需要改变算符的优先级或结合规则，不需要改变文法G1本身；2)、文法G1的分析表所包含的状态肯定比G2的状态要少得多。因为，在文法G2中含有单个非终结符的产生式，这些产生式是用来定义算符的优先级和结合规则的，它们要占用不少状态和消耗不少时间。,二义文法分析,使用LR分析法的基本思想，凭借其他一些条件，来分析二义文法所定义的语言。可以根据二义文法构造出LR分析表。其步骤是：1、构造LR(0)分析表；2、对于发生冲突的项目用SLR方法解决；3、对于SLR方法解决不了的冲突借助于其它条件解决。,使用算符的优先级和结合规则的有关信息解决“移进(或接受)”/“归约(或接受)”冲突。赋予每个终结符和产生式以一定的优先级。假定在面临输入符号a时碰到移进/归约(假定用A归约)的冲突,则比较终结符a和产生式A的优先级。若A的优先级高于a的优先级,则执行归约,反之则执行移进。,EEE|E*E|(E)|i 1)构造LR(0)分析表（部分）,EEE E+EE E*E E(E)E i,EEE E+EE E*E,E,E(E)E E+EE E*E E(E)E i,(,E i,i,i,(,+,E E+EE E+EE E*E E(E)E i,E,E E+E E E+EE E*E,I7,E E+E|E*E|(E)|i2)用SLR方法解决部分冲突例如：状态I1，E E E E+E E E*i其中存在接受移进冲突，它可以用SLR方法解决。3)用SLR方法解决不了的冲突例如：状态I7，E EE E E+E E E*E其中存在归约移进冲突。此时，只能采取加入附加条件的办法。,对状态7，读到“*”，究竟应该先做加法的归约呢还是应该先做乘号的移进，由于我们认为乘法的优先级高于加法，所以这里应该做乘法的移进；对状态7，读到“+”，究竟应该先做加法的归约呢还是应该先做加号的移进，由于我们认为相同优先级的算符服从左结合，所以这里应该做加法的归约；,例4.9 设描述两种条件语句的文法为：（0）SS（1）SiSeS（2）SiS（3）SaFOLLOW(S)=e，#按照算法语言的习惯要求，我们规定Action(4，e)=S5，相当于有“else”的条件语句优先。图4-16的项目集除了“I4”以外无动作冲突，所以，人为地解决LR项目集的动作冲突，可构造出LR分析表。,一、基本含义 Yet Another Compiler-compiler Steve Johnson在1975年为Unix系统编写的 Yacc 的 GNU（GNUs Not Unix 自由软件）版叫做 Bison 二、基本功能 接受用户提供的文法（可能是二义性的）、优先级、结合性质等附加信息，自动产生这个文法的LALR分析表。有些YACC甚至可包括接受语义描述和目标机器描述，并完成源语言到目标代码的翻译。,分析表的自动生成YACC,用生成器Yacc构造翻译器的过程,Yacc编译器,yacc源程序translate.y,C编译器,a.out,a.out,源程序,输出,语法分析小结,语法分析,自上而下语法分析,自下而上语法分析,LL(1)分析法,递归下降分析法,优先分析法,LR分析法,LR（0）SLR（1）LR(1)LALR（1）,直观算符优先分析法,算符优先分析法,参考资料,陈火旺，程序设计语言编译原理（第三版）,国防工业出版社，83129冯博琴译，现代编译程序设计，邮电出版社，Kenneth C.Louden,冯博琴 等译，编译原理与实践，机械工业出版社Alfred V.Aho,Ravi SethiJeffrey D.Ullman,Compilers:Principles,Techniques,and Tools,Addison-Wesly,1986。,