1、 编译设计和开发技术编译设计和开发技术 浙江科技学院计算机与电子工程学系浙江科技学院计算机与电子工程学系*LR分析法q 掌握： LR（ 0） 分析， SLR（ 1） 分析q 理解：活前缀，可归前缀q 了解： LR(1)、 LALR(1)分析思想1回顾：自底向上分析实现的基本思想 “ 移进归约 ” 方法 (1) S aAcBe (2) A b (3) A Ab (4) B d 判断输入串 abbcde# 是否为该文法的句子归约（ S aAcBe）#aAcBe10）接受#S11）移进 ee#aAcB9）归约（ Bd ）e#aAcd8）移进 dde#aAc7）归约（ A Ab）cde#aAb5）移进
2、 ccde#aA6）移进 bbcde#aA4）归约（ Ab ）bcde#ab3）移进 bbbcde#a2）移进 aabbcde#1）动作输入符号串符号栈步骤2编译设计和开发技术编译设计和开发技术 浙江科技学院计算机与电子工程学系浙江科技学院计算机与电子工程学系*q LR分析法 ：根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的 K个（ K=0） 符号就可唯一地确定句柄。q LR(K)的含义： L表示从左到右扫描输入串 R表示最左规约（即最右推导的逆过程） K表示向右查看输入串符号的个数当 K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0),SLR(1),
3、LR(1),LALR(1)方法$1 LR分析概述3编译设计和开发技术编译设计和开发技术 浙江科技学院计算机与电子工程学系浙江科技学院计算机与电子工程学系*q LR分析的特点：是规范归约适用范围广，适用于大多数上下文无关文法描述的语言分析速度快，能准确定位错误 缺点： LR分析器的构造工作量大4编译设计和开发技术编译设计和开发技术 浙江科技学院计算机与电子工程学系浙江科技学院计算机与电子工程学系*q LR分析器的组成q 总控程序：所有 LR分析器总控程序相同。q 分析表：不同文法有不同的分析表同一文法采用的 LR分析器不同，分析表也不同分析表分为 ACTION表 （动作表）和 GOTO表 （状态
4、转换表）。q 分析栈：包括 状态栈 S和 文法符号栈 X。分析表是 LR分析器的核心5q LR分析表：行标题为状态，列标题为文法符号GOTO表示当前状态面临文法符号时应转向的下一个状态。ACTION表示当前状态面临输入符号时应采取的动作ACTION GOTOa c e b d # a c e b d # S A B0 S 2 11 acc2 S S 1 33 r2 r2 r2 r2 r2 r26为了节省空间，将 ACTION和 GOTO中关于终结符号的各列合并起来ACTION GOTOa c e b d # a c e b d # S A B0 S 2 11 acc2 S S 1 33 r2
5、r2 r2 r2 r2 r2ACTION GOTOa c e b d # S A B0 S2 11 acc2 S1 S33 r2 r2 r2 r2 r2 r27q ACTION表中的动作有 4种：q 移进 (Sk)：把状态 k移入状态栈，若当前状态是 i， 且 k=GOTOi,a， 把a移入符号栈q 归约 (rk)：用第 k条产生式进行归约，此时栈顶形成了句柄 ， 文法中第 k条产生式为 A- ， 且 |=r ， 归约时从 状态栈 和 符号栈 中弹出 r个符号，把 A移入符号栈， j=GOTOi,A移入状态栈，其中状态 i为修改指针后的栈顶状态q 接受 (acc)：当符号栈只剩文法开始符 S，
6、 并且当前输入符为 ，则分析成功q 报错：当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子8q LR分析器的工作过程示意图输入串 a1a2a n #总 控 程 序ACTION表 GOTO表Sn Xn。 。S1S0X1#SP 输出状态栈 文法符号栈栈指针LR分析器：在分析的每一步，通用的 总控程序 按照 状态栈 栈顶状态 Si和当前输入符号 a查 LR分析表 ，并执行其中 ACTION和 GOTO规定的操作。9LR分析例（ LR(0)分析）文法 GS： (1)S-aAcBe (2)A-b (3)A-Ab (4)B-d对输入串 abbcde进行 LR分析ACTION GOTOa c e b d # S A B0 S2 11 acc2 S4 33 S5 S64 r2 r2 r2 r2 r2 r25 S8 76 r3 r3 r3 r3 r3 r37 S98 r4 r4 r4 r4 r4 r49 r1 r1 r1 r1 r1 r1LR(0)分析表为：10
