编译原理(清华)第七章LR分析法.ppt

《编译原理(清华)第七章LR分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章LR分析法学习目标：掌握：LR（0）分析，SLR（1）分析理解：活前缀，可归前缀了解：LR(1)、LALR(1)分析思想7.1LR分析概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)、LALR(1)分析思想回顾：自底向上分析实现的基本思想——“移进－归约”方法(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde

2、##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤LR分析法：根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K>=0）符号就可唯一地确定句柄。LR(K)的含义：L表示从左到右扫描输入串R表示最左规约（即最右推导的逆过程）K表示向右查看输入串符号的个数当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0),SLR(1),LR(1),LALR(1)方法7.1LR分析概述LR分析的特点：是规范归约适用范围广，适用于大多数上下

3、文无关文法描述的语言分析速度快，能准确定位错误缺点：LR分析器的构造工作量大LR分析器的组成总控程序：所有LR分析器总控程序相同。分析表：不同文法有不同的分析表同一文法采用的LR分析器不同，分析表也不同分析表分为ACTION表（动作表）和GOTO表（状态转换表）。分析栈：包括状态栈S和文法符号栈X。分析表是LR分析器的核心LR分析表：列标题为状态，行标题为文法符号GOTO表示当前状态面临文法符号时应转向的下一个状态。ACTION表示当前状态面临输入符号时应采取的动作ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r

4、2r2为了节省空间，将ACTION和GOTO中关于终结符号的各列合并起来ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r2r2ACTIONGOTOacebd#SAB0S211acc2S1S33r2r2r2r2r2r2ACTION表中的动作有4种：移进(Sk)：把状态k移入状态栈，若当前状态是i，且k=GOTO[i,a]，把a移入符号栈归约(rk)：用第k条产生式进行归约，此时栈顶形成了句柄β，文法中第k条产生式为A->β，且

5、β

6、=r，归约时从状态栈和符号栈中弹出r个符号，把A移入符号栈，j=GOTO[i,A]移

7、入状态栈，其中状态i为修改指针后的栈顶状态接受(acc)：当符号栈只剩文法开始符S，并且当前输入符为‘＃’，则分析成功报错：当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子LR分析器的工作过程示意图输入串a1a2…an#总控程序ACTION表GOTO表nXn。。。。10X1#SP输出状态栈文法符号栈栈指针LR分析器：在分析的每一步，通用的总控程序按照状态栈栈顶状态i和当前输入符号a查LR分析表，并执行其中ACTION和GOTO规定的操作。LR分析例（LR(0)分析）文法G[S]：(1)S->aAcBe(2)A->b(3)A->Ab

8、(4)B->d对输入串abbede＃进行LR分析ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR(0)分析表为：对输入串abbcde#的分析过程(1)S->aAcBe(2)A->b(3)A->Ab(4)B->dacc##011R1##aAcBe02357910S9e##aAc02359R4e##aAcd023588S8de##aAc02357S5cde##a026R3cde##aAb02365S6bcde##a024

9、R2bcde##ab0243S4bbcde##a022S2abbcde##01GOTOACTION输入串符号栈状态栈步骤A333A37B71S17.2LR(0)分析使用LR(0)分析表的LR分析器称为LR(0)分析器。LR(0)分析器在分析的过程中只根据符号栈的内容就能确定句柄，不需要向右查看输入符号对文法的限制较大，对绝大多数高级语言的语法分析器不适用构造LR(0)分析表的思想和方法是构造其他LR分析表的基础。例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子归约（S→aAcBe）##aAcBe10）

10、接受##S11）移进ee##aAcB9