归约与移进归约法 ■归约 ◆推导的逆过程当A→Y是文法G的一个产生 式，且a、B∈V*,则aYB能直接归 约到aAB ◆例如E+T==>E+T*F,那么E+T*F可以归约到E+T ■移进归约法 ◆把输入符号一个一个地移进栈里，当栈顶形 成某个产生式的一个候选式时，就把栈顶的这 一 可归约串替换成（归约为)该产生式的左部 符号 ■归约举例 2025/4/3 可)11
2025/4/3 11 归约与移进归约法 ◼归约 ◆推导的逆过程 当Ａ→γ是文法Ｇ的一个产生 式，且α、β∈Ｖ*，则αγβ能直接归 约到αＡβ ◆例如 E+T==>E+T*F,那么E+T*F可以归约到E+T ◼移进归约法 ◆把输入符号一个一个地移进栈里，当栈顶形 成某个产生式的一个候选式时，就把栈顶的这 一可归约串替换成（归约为）该产生式的左部 符号 ◼归约举例
例文法G[S] 输入串为：abbcde 移进归约法举例 S-aAcBe最右推导：S=>aAcBe=>aAc@e A→Abb ==>aAbcde==>abbcde B→d 说明 步骤栈 输入缓冲区 动作 0# abbcde# 移进a 1 #a bbcde# 移进b 栈中串+余留输入串 2 #ab bcde# 归约A→b =当前句型 3 #aA bcde# 移进b 栈顶可归约串 4 #aAb cde# 归约A→Ab =当前句型的句柄 5 #aA cde# 移进c 6 #aAc de# 移进d 右句型中句 7 #aAcd e# 归约B→d 柄的后面只能出 8 #aAcB e# 移进e 现终结符 9 #aAcBe # 归约S→aAcBe 颜理拉痢柄 10 #S # 接受 2025/4/3 分析成功结束 12
2025/4/3 12 例文法G[S] 移进归约法举例 S→aAcBe A→Ab|b B→d 输入串为：abbcde S a A c B e A b d b 步骤 栈 输入缓冲区 动作 0 # abbcde# 1 #a bbcde# 2 #ab bcde# 3 #aA bcde# 4 #aAb cde# 5 #aA cde# 6 #aAc de# 7 #aAcd e# 8 #aAcB e# 9 #aAcBe # 10 #S # 分析成功结束 移进a 移进b 归约 A→b 移进b 归约 A→Ab 移进c 移进d 归约 B→d 移进e 归约S→aAcBe 接受 栈中串+余留输入串 =当前句型 栈顶可归约串 =当前句型的句柄 语法树 分析过程 说明 最右推导：S ==>aAcBe ==>aAcde ==>aAbcde==>abbcde 右句型中句 柄的后面只能出 现终结符 当前句型的句柄 修剪语法树
例文法G[S]: S→aAcBe 语法分析树的生成（输出) A→Abb B→d 产生式序列： S4.S→aAcBe 1.A→b 2.A→Ab 3.B→d 4.S→aAcBe 、2.A→Ab B 1.A→b 3.B→d a C d e 2025/4/3 节目录 ☑D13
2025/4/3 13 语法分析树的生成（输出） a b b c d e A A B S 1.A→b 2.A→Ab 3.B→d 4.S→aAcBe 例文法G[S]： S→aAcBe A→Ab|b B→d 产生式序列： 1.A→b 2.A→Ab 3.B→d 4.S→aAcBe 节目录
规范推导与规范归约 ■规范推导一最右推导 ■规范句型一如果文法G无二义性， 由规范推 导所得的句型（也称为右句型） ■规范归约一规范推导的逆过程，即最左归约 a 规范归约的实质一在移进过程中， 当发现栈 顶呈现句柄时就用相应产生式的左部符号进行 替换 ■对于规范句型来说，句柄的后面不会出现非 终结符，只能出现终结符 2025/4/3 节目录 ☒14
2025/4/3 14 规范推导与规范归约 ◼规范推导——最右推导 ◼规范句型——如果文法G无二义性，由规范推 导所得的句型(也称为右句型) ◼规范归约——规范推导的逆过程，即最左归约 ◼规范归约的实质——在移进过程中，当发现栈 顶呈现句柄时就用相应产生式的左部符号进行 替换 ◼对于规范句型来说，句柄的后面不会出现非 终结符，只能出现终结符 节目录
移进归约分析器 输入缓冲区 i火i# 分析栈 移进归约 产生式 E 控制程序 序列 # 栈内容+输入缓冲区内容=#句型# 分析过程中 符号栈 输入串 初态 # w# 。. 终态 #S 井 分析成功 2025/4/3 D☒15
2025/4/3 15 移进归约分析器 i ＊ i # ＋ Ｅ # 移进归约 控制程序 产生式 序列 栈内容 + 输入缓冲区内容 ＝ # 句型 # 分析过程中 符号栈 输入串 初态 # w # . . . 终态 #S # 分析成功 分 析 栈 输入缓冲区