《编译原理》课程教学课件（2023讲稿）cha05 自底而上语法分析

第5章自底而上优先分析 n自底向上分析简介 n短语、直接短语和句柄（第2章2.6) n自下而上分析基本问题 u归约 规范归约 u举例p103 2023/2/28 课程目录 ☑21

2023/2/28 1 第5章 自底而上优先分析 n 自底向上分析简介 n 短语、直接短语和句柄（第2章 2.6） n 自下而上分析基本问题 u 归约 规范归约 u 举例 p103 课程目录

文法G: 自下而上分析简介 E→E+TT E T→TFF F→(E)|i 输入串：w=i*i+i E 输入串最终能归约到 开始符号，说明输入串是 文法的一个句子，分析成 功结束。 2023/2/28 ☒D2

2023/2/28 2 文法G： 自下而上分析简介 E→E+T|T T→T*F|F F→(E)|i 输入串：w=i*i+i 最 右 推 导 E E + T F i T T * F F i i 最 左 归 约 E==>E+T ==>E+F ==>E+i ==>T*F+i ==>T*i+i ==>F*i+i ==>i*i+i ==>T+i 输入串最终能归约到 开始符号，说明输入串是 文法的一个句子，分析成 功结束

自下而上分析基本思想p103 n从输入串出发，逐步进行归约，直至归约 到文法的开始符号，那么输入串是文法的 句子，否则输入串有语法错误 n或者说，从语法树的末端开始，步步向上 归约，修剪语法树，直到只剩根结点 n归约一一用产生式的左部替代右部 n关键 寻找每步句型中可归约串 寻找方式不同，分析方法不同 n效率更高，对语法限制更少 2023/2/28 章节目录 ☑3

2023/2/28 3 自下而上分析基本思想 p103 n 从输入串出发，逐步进行归约，直至归约 到文法的开始符号，那么输入串是文法的 句子，否则输入串有语法错误 n 或者说，从语法树的末端开始，步步向上 归约，修剪语法树，直到只剩根结点 n 归约——用产生式的左部替代右部 n 关键——寻找每步句型中可归约串 寻找方式不同，分析方法不同 n 效率更高，对语法限制更少 章节目录

利用语法树寻找句型的短语、句柄等 句型n=E+T*i n寻找方法 E① 句型n的语法树有： un个内部节点一n棵子树 un棵子树一n个短语 每颗子树的叶结点从左至右排 列组成一个短语 um棵直接子树一m个直接短语 只有父子两代 3个短语E+T*iT*i1 1个直接短语i u最左直接子树一句柄 句柄i 2023/2/28 章节目录 可4

2023/2/28 4 利用语法树寻找句型的短语、句柄等 句型η=E+T*i E E + T T * F i n寻找方法 句型η的语法树有： un棵子树——n个短语 um棵直接子树——m个直接短语 u最左直接子树——句柄 ① ② ③ 3个短语 1个直接短语 i 句柄 i E+T*i T*i i 只有父子两代 un个内部节点——n棵子树 每颗子树的叶结点从左至右排 列组成一个短语 章节目录

自下而上分析基本问题 n归约与移进归约法 n规范推导与规范归约 n移进归约分析器 n要解决的基本问题？ 2023/2/28 章节目录 ☒5

2023/2/28 5 自下而上分析基本问题 n 归约与移进归约法 n 规范推导与规范归约 n 移进归约分析器 n 要解决的基本问题? 章节目录

归约与移进归约法 n归约 u推导的逆过程当A→Y是文法G的一个产生 式，且a、B∈V*,则aYB能直接归 约到aAB u例如E+T=>E+T*F,那么E+T*F可以归约到E+T n移进归约法 u把输入符号一个一个地移进栈里，当栈顶形成 某个产生式的一个候选式时，就把栈顶的这一 可归约串替换成（归约为)该产生式的左部符 号 n归约举例 2023/2/28 ☒D6

2023/2/28 6 归约与移进归约法 n 归约 u 推导的逆过程 当Ａ→γ是文法Ｇ的一个产生 式，且α、β∈Ｖ*，则αγβ能直接归 约到αＡβ u 例如 E+T==>E+T*F,那么E+T*F可以归约到E+T n 移进归约法 u 把输入符号一个一个地移进栈里，当栈顶形成 某个产生式的一个候选式时，就把栈顶的这一 可归约串替换成（归约为）该产生式的左部符 号 n 归约举例

例文法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 # 接受 2023/2/28 分析成功结束 ☒D 7

2023/2/28 7 例文法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 d e 2023/2/28 节目录

2023/2/28 8 语法分析树的生成（输出） 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 节目录

规范推导与规范归约 n规范推导一一 最右推导 n规范句型一一如果文法G无二义性， 由规范推 导所得的句型（也称为右句型） n规范归约一一规范推导的逆过程，即最左归约 n规范归约的实质一一在移进过程中， 当发现栈 顶呈现句柄时就用相应产生式的左部符号进行 替换 n对于规范句型来说，句柄的后面不会出现非 终结符，只能出现终结符 2023/2/28 节目录 ☒D9

2023/2/28 9 规范推导与规范归约 n 规范推导——最右推导 n 规范句型——如果文法G无二义性，由规范推 导所得的句型(也称为右句型) n 规范归约——规范推导的逆过程，即最左归约 n 规范归约的实质——在移进过程中，当发现栈 顶呈现句柄时就用相应产生式的左部符号进行 替换 n 对于规范句型来说，句柄的后面不会出现非 终结符，只能出现终结符 节目录

移进归约分析器 输入缓冲区 i火i# 分析栈 + 移进归约 产生式 控制程序 序列 # 栈内容+输入缓冲区内容=#句型# 分析过程中 符号栈 输入串 初态 # w# 终态 #S # 分析成功 2023/2/28 ☑D0

2023/2/28 10 移进归约分析器 i ＊ i # ＋ Ｅ # 移进归约 控制程序 产生式 序列 栈内容 + 输入缓冲区内容 ＝ # 句型 # 分析过程中 符号栈 输入串 初态 # w # . . . 终态 #S # 分析成功 分 析 栈 输入缓冲区