ppt编译原理5章66

《ppt编译原理5章66》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.3LR分析方法LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向前看的符号个数。LR分析法与其它语法分析方法相比，应用更广泛，具有更强的吸引力，主要原因有：(1)应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的结构；(2)能有效实现：是最一般的无回溯的移进—归约方法，能够象其它的移进—归约方法一样有效的实现；

2、(3)容易查错：LR分析器能够及时发现语法错误和准确指出错误位置。二、LR分析器的逻辑结构：1.整体结构：总控程序a1a2…aiai+1…an#动作表状态转换表Sm...S1S0Xm...X1#分析表输出sp(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；(2)分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作；(3)分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分(状态是指能识别活前缀的自动机状态)，

3、LR分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。2.分析表的组成：分析表由两部分组成，这就是分析动作表和状态转换表：(1)分析动作表以一个二维数组表示，行代表分析栈栈顶状态，列代表当前的输入符号，数组元素表示当前栈顶为状态为Si，而输入符号为aj时，所执行的分析动作Action[Si,aj]。输入符号状态a1…an#S0S1Sm…共有4种动作：移进：新状态进状态栈，输入符号进符号栈；s归约：用相应的产生式进行归约；r5接受：当文法符号归约到只剩下识别符号，且输入串结束时(当前输入为#)，分析成功；acc出错：当状态栈顶为某一状态下

4、，出现了不该出现的文法符号时，报错。执行移进动作元素为产生式或产生式编号表示用它进行归约元素为acc表示接受元素为空白表示出错(2)状态转换表也用一个二维数组表示，行代表分析栈栈顶状态，列代表文法符号，数组元素表示当前栈顶为状态为Si面对文法符号为Xj时，应转去的新状态Goto[Si,Xj]。输入符号状态X1X2…XpS0S3S1S2S5Sm文法符号包括终结符号和非终结符号三、LR分析过程：1.LR分析算法：(1)将初始状态S0和输入串的左边界(#)分别进分析栈；(2)根据状态栈栈顶和当前输入符号查动作表进行如下工作：移进:若动作表中对应“移进

5、”，那么当前输入符号进符号栈，并据状态转换表查得输入符号所对应的新的状态进状态栈，继续扫描，即下一个输入符号变成当前得输入符号；归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的符号串长度为n，则符号栈栈顶的n个符号为句柄，所以符号栈栈顶n个符号出栈，同时，状态栈顶的n个元素也出栈，归约后的文法符号(非终结符)进符号栈，并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。(3)重复以上(2)的工作直到接受或出错为止。2.举例，有文法G[L

6、](1)LE,L(2)LE(3)Ea(4)Eb要求对输入串a,b,a进行分析，即分析#a,b,a#为了分析方便，给文法的产生式进行了编号，文法中非终结符有L、E终结符有a、b和,它们共同组成文法符号首先直接给出LR分析表为了节省空间，在实际应用中，将动作表和状态转换表中关于终结符的各列对应进行合并。ActionGotoab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1例如，本来Action(S0,a)=“移进”，表示在状态S0下输入a时，执行“移进”动作。而Goto(S0,a)=S

7、3表示在状态S0下遇到a时，应转去的状态。现在，Action(S0,a)=S3表示在状态S0下输入a时，移进符号栈并转去新的状态S3。r1~r4表示文法的产生式(1)~(4),即应采用此产生式进行归约数字表示要转去的新状态的编号，如：Goto(S5,L)=6表示要转去新状态S6分析过程：ActionGotoab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1(1)LE,L(2)LE(3)Ea(4)Eb步骤状态栈S符号栈X产生式输入符号1S0#a,b,a#2S0S3#a,b,a#3S0S

8、2#Er3(Ea),b,a#4S0S2S5#E,b,a#5S0S2S5S4#E,b,a#6S0S2S5S2#E,Er4(Eb),a#7S0S2S5