第6章 LR分析程序及其自动构造 6.1自下而上分析及其LR分析概述 6.2LR(0)分析 6.3SLR(1)分析 6.4LR(1)分析 6.5LAR分析 6.6使用二义文法
第6章 ＬＲ分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析 6.4 LR（1）分析 6.5 LALR分析 6.6 使用二义文法
自下而上分析算法能力强构造复杂 最常用和最有效的模型-移进归约(动作) 将输入分成两部分:未消化和半消化的 半 Inpu#未消化 的 总控程序 output 分析表 生式表
自下而上分析算法 能力强 构造复杂 最常用和最有效的模型----移进归约(动作） 总控程序 output Input# … 栈 状态 文法符号 分析表 产 生 式 表 将输入分成两部分：未消化和半消化的 总控程序 output 半 Input#未消化 消 化 的 分析表 产 生 式 表
S→>EE>T|E+T 多T→i1 Reduce:如能找到一产生式A_>W且栈中的内容是qW (q可能为空,则可以将其归约为qA即倒过来用这个 产生式 如上例若栈中内容是(nt,我们使用产生式T->nt 柄把栈中内容归约为(T Sh:如不能执行一个归约且在未消化的输入中还有 token,就把它从输入移到栈中 如上例假定栈中内容是(输入中还有m+m诛不能 对(执行一个归约,因为它不和任何产生式的右端匹 配所以把输入的第一个符号移到栈中,于是栈中内容 是nt,而余留的输入是+int#
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+)时就会发生错误
Reduce的一个特殊情况：栈中的全部内容 w归约为开始符号S （即施用 S –> w） ， 且没有余留输入了，意味着已成功分析 了整个输入串. 移进归约分析中还会出现一种情况，就是 出错，比如当前的token不能构成一个合 法句子的一部分，例如上面的文法，试 分析 int+)时就会发生错误
STACK REMAINING INPUT PARSER ACTION (int int# Shift>多 2(2int+int)# 2 Shift 3(int int)# Reduce:T-> int 4(T t int)# Reduce:E-> T 5(E int)# Shift 6(E+ int# Shift Z(E+int )# Reduce:T-> int t 8(E+ 进进# Reduce:E→>E+T 9(E Shift 10(E) Reduce: T->(E) 11 Reduce:E-> T 12E # Reduce:S->E 13S#
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 #