编译原理实用教程教学课件杨德芳第6章 LR分析技术.ppt

《编译原理实用教程教学课件杨德芳第6章 LR分析技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章LR分析技术本章学习目标LR(k)分析器是这样一种分析程序：它总是按从左到右的方式扫描输入串，并按照自底向上的方式进行归约。在这种分析过程中，它至多向前查看k个输入符号就能确定当前的动作是移进还是归约。本章要点：LR分析的基本原理LR（0）分析表的构造SLR（1）分析表的构造LR（1）分析表的构造LALR（1）分析表的构造6.1LR分析器的工作原理自底向上分析方法是一种移进—归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析方法的关键问题是在分析过程中如何确定句柄。L

2、R分析方法根据当前分析栈中的符号串（通常用状态来表示）和向右顺序查看输入串的k（k≥0）个符号就能惟一确定句柄。LR分析方法的归约过程正是规范推导的逆过程，所以LR分析过程是一种规范归约。LR(k)分析方法是1965年Knuth提出的。括号中的k表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（k）分析方法和自底向上的优先分析对文法的限制要少得多。也就是说对于大多数无二义性上下文无关文法描述的语言都可以用相应的LR分析器识别。而且这种方法还具有分析速度快，能准确、及时地指出出错位置等优点

3、。它的主要缺点是对于一个实用语言文法分析器的构造工作量相当大，实现比较困难。1．LR分析的概述一个LR分析器由三部分组成：（1）总控程序，也称为驱动程序。对所有的LR分析器总控程序是相同的。（2）分析表或分析函数。不同的文法其分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两部分,，们都用二维数组表示。（3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作由栈顶状态和当前输入符号所决定。其中SP为栈顶指

4、针，S[i]为状态栈，X[i]为文法符号栈。状态栈的内容按关系GOTO[Si，X]=Sj。其中X为终结符或非终结符。输入串abcdefg#总控程序输出S0#S1X1……SnXnSPACTION表GOTO表图6-1LR分析器的工作过程ACTION[Si,a]规定了栈顶状态为Si时遇到输入符号a应该执行的动作。动作有4种可能：（1）移进：当Sj=GOTO[Si,a]成立，则把Sj移入到状态栈，把a移到文法符号栈，其中i和j表示状态。（2）归约：当在栈顶形成句柄为时，则用归约为相应的非终结符A，即

5、当文法中有A的产生式，当的长度为（即

6、

7、=）时，则从状态栈和文法符号栈中自栈顶向下去掉个符号，即栈指针SP减去；并把A移入文法符号栈，再把满足Sj=GOTO[Si,A]的状态移进状态栈，其中Si为修改后指针的栈顶状态。（3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则分析成功。（4）报错：当遇到状态为某一个状态下出现不该遇到的文法符号栈时，则报错。说明输入串不是该文法能接受的句子。2．LR分析举例表达式文法G[E]如下所示，

8、它对应的LR分析表如表6-1所示。（1）EE+T（2）ET（3）TT*F（4）TF（5）F（E）（6）Fi状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION[0,i]=S5,将状态5压栈205#i+i*i#r6：用Fi归约，GOTO(0，

9、F)=3入栈303#F+i*i#r4：用TF归约，GOTO(0，T)=2入栈402#T+i*i#r2：用ET归约，GOTO(0，E)=1入栈501#E+i*i#ACTION[1,+]=S6，将状态6压栈6016#E+i*i#ACTION[6,i]=S5，将状态5压栈70165#E+i*i#r6：用Fi归约，GOTO(6，F)=3入栈80163#E+F*i#r4：用TF归约，GOTO(6，T)=9入栈90169#E+T*i#ACTION[9,*]=S7，将状态7压栈1001697#E+T*

10、i#ACTION[7,i]=S5，将状态5压栈11016975#E+T*i#r6：用Fi归约，GOTO(7，F)=10入栈120169710#E+T*F#r3：用TT*F归约，GOTO(6，T)=9入栈130169#E+T#r1：用EE+T归约，GOTO(0，E)=1入栈1401#E#ACC：分析成功我们主要是关心的问题是如何由文法构造LR分析表。对于一个文法，如果能构造一张分析表，使得它的每一个入口均是惟一确定的，则称这个文法是LR文法。对于一个LR文法，当分析器对输入串进行自左向右扫描