编译原理课件chap06(陈火旺)

《编译原理课件chap06(陈火旺)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章语法分析——LR分析第六章语法分析--LR分析第五章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法与第5章介绍的算符优先分析一样，LR方法也是通过求句柄逐步归约进行语法分析。在运算符优先分析中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。第六章语法分析--LR分析LR分析概述LR（k）分析是根据当前分析栈中的符号串和向右顺序查看输入串的k(k≥0)个符号就可以唯一确定分析的动作是移进还是归约以及用哪个产生式归约。从左到右扫描(L)自底向上进行规约(R)(是规范规约）第六章语法分析

2、--LR分析LR分析的优缺点1)适合文法类足够大,适用于大多数上下文无关文法2)分析效率高3)报错及时4)手工实现工作量大5)可以自动生成美国Bell实验室推出的编译程序自动构造工具——YACC：能接受一个用BNF描述的满足LALR（1）上下文无关文法并对其自动构造出LALR（1）分析器。第六章语法分析--LR分析第六章LR分析法一、LR分析概述（基本构造原理与方法）二、LR(0)分析三、SLR(1)分析四、LR(1)分析五、LALR(1)分析第六章语法分析--LR分析ＬＲ分析器模型总控程序outputInput#S1Xm…S1…X1S

3、0#栈状态文法符号ACTIONGOTOLR分析表产生式表第六章语法分析--LR分析逻辑上说，一个LR分析器由3个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。2、LR分析方法的逻辑结构第六章语法分析--

4、LR分析总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。LR分析过程的思想是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。第六章语法分析--LR分析LR分析过程的思想：记住历史：记住已移进和归约的整个符号串。（即栈中的内容）立足现实：输入串读头下的符号展望未来：根据所用的产生式推测未来可能碰到的输入符号。（也通过栈识别）第六章语法分析--LR分析分析表的组成：(1)分析动作表

5、Action符号状态a1a2…atS0action[S0,a1]action[S0,a2]…action[S0,at]S1action[S1,a1]action[S1,a2]…action[S1,at]……………Snaction[Sn,a1]action[Sn,a2]…action[Sn,at]第六章语法分析--LR分析表中action[Si,aj]为二维数组，指出当前栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。(2)状态转换表goto第六章语法分析-

6、-LR分析符号状态x1x2…xtS0goto[S0,x1]goto[S0,x2]…goto[S0,xt]S1goto[S1,x1]goto[S1,x2]…goto[S1,xt]……………Sngoto[Sn,x1]goto[Sn,x2]…goto[Sn,xt]表中goto[Si,xj]指出栈顶状态为Si，文法符号为xj时应转到的下一状态。第六章语法分析--LR分析1313分析表种类的不同决定使用不同的LR分析方法a)SLR分析表(简单LR分析表)b)LR（1）分析表(规范LR分析表)构造简单,最易实现,大多数上下文无关文法都可以构造出SL

7、R分析表,所以具有较高的实用价值。使用SLR分析表进行语法分析的分析器叫SLR分析器适用文法类最大,大多数上下文无关文法都能构造出LR分析表,但其分析表体积太大.暂时实用价值不大.a‘)LR（0）分析表第六章语法分析--LR分析1414c)LALR分析表(超前LR分析表)这种表适用的文法类及其实现上难易在上面两种之间,在实用上很吸引人.使用LALR分析表进行语法分析的分析器叫LALR分析器。例：YACC文法规则文件YACC源文件YACC某语言的LALR分析器第六章语法分析--LR分析15151.四种分析表对应四类文法几点说明2.一个SL

8、R文法必定是LALR文法和LR（1）文法第六章语法分析--LR分析3、LR分析过程：LR分析步骤：(a)将初始状态S0和句子的左界符#分别进分析栈。(b)根据栈顶状态和当前输入符号查动作表，进行如下的工作。