《编译原理》课程教学课件（PPT讲稿）chp5 自底向上优先分析

第5章自底而上优先分析 ■引言 ◆简介 相关概念 ■自下而上分析基本问题 ◆归约 规范归约 ■算符优先分析 ◆算符优先关系表的构造和分析过程 ■小结 ■作业 2025-4-2 课程目录 ☑

2025-4-2 1 第5章 自底而上优先分析 n引言 u简介 相关概念 n自下而上分析基本问题 u归约 规范归约 n算符优先分析 u算符优先关系表的构造和分析过程 n小结 n作业 课程目录

引言 ■自下而上分析简介 ■相关概念 ◆短语、直接短语和句柄 ◆素短语和最左素短语 ◆利用语法树寻找短语、句柄的方法 2025-4-2 章节目录 □2

2025-4-2 2 引 言 章节目录

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

2025-4-2 3

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

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

相关概念 ■短语 若S==*>aAδ，且A==+>B,则称 B是句型αBδ相对于非终结符号A的短语。 ■直接短语 若S→*aAδ且A→B,则称B是句型 aBδ相对于非终结符号A的直接短语。 ■句柄一个句型的最左直接短语。 S A 2025-4-2 节目录 ☑5

2025-4-2 5 相关概念 n短语 若Ｓ==*>αＡδ，且A==+>β，则称 β是句型αβδ相对于非终结符号A的短语。 节目录 n直接短语 若Ｓ* αＡδ 且 A β，则称β是句型 αβδ 相对于非终结符号A的直接短语

素短语 素短语最左素短语p116 (1)是一个短语 (2)至少包含一个终结符 (3)且除自身外不再包含其它素短语 ◆句型E+T*i的短语有三个：E+T*iT*ii 其中：i是句型E+T*i的素短语 T*i不是句型E+T*i的素短语 不满足条件(3)，包含素短语1 E+T*1不是句型E+T*i的素短语 不满足条件(3)，包含素短语1 ■最左素短语 处于句型最左边的素短语 ◆句型E+T*i的最左素短语是：i 2025-4-2 节目录 6

2025-4-2 6 素短语 最左素短语p116 u句型E+T*i的最左素短语是：i u句型E+T*i的短语有三个：E+T*i T*i i 其中：i是句型E+T*i的素短语 T*i不是句型E+T*i的素短语 E+T*i不是句型E+T*i的素短语 不满足条件(3)，包含素短语i 不满足条件(3)，包含素短语i n素短语 (1)是一个短语 (2)至少包含一个终结符 (3)且除自身外不再包含其它素短语 n最左素短语 处于句型最左边的素短语 节目录

利用语法树寻找句型的短语、句柄等 句型n=E+T*i ■寻找方法 E① 句型n的语法树有： ◆n个内部节点一n棵子树 ◆n棵子树n个短语 每颗子树的叶结点从左至右排 列组成一个短语 ◆m棵直接子树- m个直接短语 只有父子两代 3个短语E+T*iT*i1 1个直接短语 i ◆最左直接子树—句柄 句柄i 素短语i 最左素短语 i 2025-4-2 ☑7

2025-4-2 7 利用语法树寻找句型的短语、句柄等

利用语法树寻找短语、句柄举例 例文法GE:E→E+TTT→TFFF→(E)i 句型1=T+T郑+i的语法树 6个内部节点6棵子树 E② 句型1有6个短语： T+TF+i是句型n相对于的短语 E④+T⑤ T+TF是句型n相对于必的短语 T是句型n相对于E4的短语 TF是句型1相对于T的短语 i,1是句型n相对于T3,F6的短语 3个直接短语：T,TF,1 句柄：T2个素短语：TF,1 最左素短语：T*却 2025-4-2 8

2025-4-2 8 利用语法树寻找短语、句柄举例 例 文法G[E]：

利用语法树寻找短语、句柄课堂练习 例文法GE]:E→E+TTT→T郑FF→(E)|i 句型1=i1*i2ti3的语法树 BEGIN 8个内部节点 一8棵子树 E2 T3 句型n有8个短语： i1*i2+i3是句型n相对于E1的短语 T4 F5 i1*i2是句型1相对于2，T的短语 i1是句型n相对于T6,F8的短语 T6 米 F7 13 i2是句型1相对于7的短语 F8 i3是句型n相对于T3,的短语 12 直接短语3个：i1,i2,i3 i1 句柄：i1 素短语3个：i1,i2,i3 最左素短语： i 2025-4-2 节目录

2025-4-2 9 利用语法树寻找短语、句柄课堂练习 例 文法G[E]： 节目录

自下而上分析基本问题 ■归约与移进归约法 规范推导与规范归约 移进归约分析器 要解决的基本问题？ 2025-4-2 章节目录 ☑)10

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