LR法分析kang.ppt

编译原理 第7章ＬＲ分析 主要内容 本章学习目标 7.1 自下而上分析及LR分析概述 7.2 LR分析算法 PPT 1-36 7.3 SLR(1) 分析 7.4 LR（1）分析 7.5 LALR分析 7.6 使用二义文法 本章小结 重点习题解析 作业 相关术语的回顾（英文版） 本章学习目标 　一．学习目标 掌握LR分析器 二．课程安排 2学时 本章知识结构 自下而上分析算法 能力强 构造复杂 最常用和最有效的模型----移进归约(动作） 将输入分成两部分：未消化和半消化的 S – E E – T | E + T T – int | (E) Reduce: 如能找到一产生式 A – w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA.即倒过来用这个产生式. 如上例, 若栈中内容是 (int ，我们使用产生式 T– int柄把栈中内容归约为(T Shift: 如不能执行一个归约且在未消化的输入中还有 token ，就把它从输入移到栈中. 如上例,假定栈中内容是 ( ,输入中还有 int+int)#.不能对( 执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)# . Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S – w） ，且没有余留输入了，意味着已成功分析了整个输入串. 移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误. STACK REMAINING INPUT PARSER ACTION 1 (int + int)# Shift 2 ( int + int)# Shift 3 (int + int)# Reduce: T – int 4 (T + int)# Reduce: E – T 5 (E + int)# Shift 6 (E + int)# Shift 7 (E + int )# Reduce: T – int 8 (E + T )# Reduce: E – E + T 9 (E )# Shift 10 (E) # Reduce: T – (E) 11 T # Reduce: E – T 12 E # Reduce: S – E 13 S # 冲突 (E + T )# Reduce:E – E + T why?不用 E – T (E ) # 若使用了E – T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes） （E+E不能和任何产生式的右端匹配 （E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但不超过句柄 移进归约分析的栈中出现的内容加上余留输入构成规范句型 冲突及解决方法 冲突： 移进-归约 冲突 归约-归约 冲突 解决方法： Conflict Solutions 改写文法 根据产生式出现的顺序来选择 根据算符的优先级 特定的一种shift-reduce实现技