第6章自底而上优先分析 ■引言 ◆简介相关概念 ■自下而上分析基本问题 ◆归约规范归约 ■算符优先分析 ◆算符优先关系表的构造和分析过程 ■小结 ■作业 2025/4/3 课程目录 ☑)1
2025/4/3 1 第6章 自底而上优先分析 ◼引言 ◆简介 相关概念 ◼自下而上分析基本问题 ◆归约 规范归约 ◼算符优先分析 ◆算符优先关系表的构造和分析过程 ◼小结 ◼作业 课程目录
引言 ■自下而上分析简介 ■相关概念 ◆短语、直接短语和句柄 ◆素短语和最左素短语 ◆利用语法树寻找短语、句柄的方法 2025/4/3 章节目录 ☒☑2
2025/4/3 2 引 言 ◼自下而上分析简介 ◼相关概念 ◆短语、直接短语和句柄 ◆素短语和最左素短语 ◆利用语法树寻找短语、句柄的方法 章节目录
文法G: 自下而上分析简介 E→E+TT E T→T*FF F→(E)i 输入串： w=i*i+i E 输入串最终能归约到 开始符号，说明输入串是 文法的一个句子，分析成 功结束。 2025/4/3 ☒D3
2025/4/3 3 文法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 输入串最终能归约到 开始符号，说明输入串是 文法的一个句子，分析成 功结束
自下而上分析基本思想p102 ■从输入串出发，逐步进行归约，直至归约 到文法的开始符号，那么输入串是文法的 句子，否则输入串有语法错误 ■i 或者说，从语法树的末端开始，步步向上 归约，修剪语法树，直到只剩根结点 ■归约一用产生式的左部替代右部 ■关键一 寻找每步句型中可归约串 寻找方式不同，分析方法不同 ■效率更高，对语法限制更少 2025/4/3 节目录 ☒D4
2025/4/3 4 自下而上分析基本思想 p102 ◼从输入串出发，逐步进行归约，直至归约 到文法的开始符号，那么输入串是文法的 句子，否则输入串有语法错误 ◼或者说，从语法树的末端开始，步步向上 归约，修剪语法树，直到只剩根结点 ◼归约——用产生式的左部替代右部 ◼关键——寻找每步句型中可归约串 寻找方式不同，分析方法不同 ◼效率更高，对语法限制更少 节目录
相关概念 ■短语 若S==*>aAδ，且A=+>B,则称 B是句型αBδ相对于非终结符号A的短语。 ■直接短语 若S→*αAδ且A→B,则称B是句型 αBδ相对于非终结符号A的直接短语。 口句柄一个句型的最左直接短语。 Q A B 2025/4/3 节目绿 ☒D5
2025/4/3 5 相关概念 Ｓ α Ａ δ β ◼短语 若Ｓ== *>αＡδ，且A==+>β，则称 β是句型αβδ相对于非终结符号A的短语。 节目录 ◼直接短语 若Ｓ * αＡδ 且 A β，则称β是句型 αβδ 相对于非终结符号A的直接短语。 句柄 一个句型的最左直接短语
素短语 素短语： 最左素短语p115 （1)是一个短语 (2)至少包含一个终结符 (3)且除自身外不再包含其它素短语 句型E+T*i的短语有三个：E+T*iT*i1 其中：i是句型E+T*i的素短语 T*i不是句型E+T*i的素短语 不满足条件(3)，包含素短语1 E+T*i不是句型E+T*i的素短语 不满足条件(3)，包含素短语1 最左素短语处于句型最左边的素短语 句型E+T*1的最左素短语是：i 2025/4/3 节目绿 D6
2025/4/3 6 素短语 最左素短语p115 句型E+T*i的最左素短语是：i 句型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 ◼素短语 (1)是一个短语 (2)至少包含一个终结符 (3)且除自身外不再包含其它素短语 最左素短语 处于句型最左边的素短语 节目录
利用语法树寻找句型的短语、句柄等 句型n=E+T*i ■寻找方法 E① 句型n的语法树有： on个内部节点一n棵子树 0n棵子树一n个短语 每颗子树的叶结点从左至右排 米 列组成一个短语 om棵直接子树 m个直接短语 只有父子两代 3个短语E+T*iT*ii 1个直接短语i 加最左直接子树一句柄 句柄1 素短语i 最左素短语i 2025/4/3 ☒D7
2025/4/3 7 利用语法树寻找句型的短语、句柄等 句型η=E+T*i E E + T T * F i ◼寻找方法 句型η的语法树有： n棵子树——n个短语 m棵直接子树——m个直接短语 最左直接子树——句柄 ① ② ③ 3个短语 1个直接短语 i 句柄 i E+T*i T*i i 只有父子两代 素短语 i 最左素短语 i n个内部节点——n棵子树 每颗子树的叶结点从左至右排 列组成一个短语
利用语法树寻找短语、句柄举例 例文法GE]:E→E+TTT→TFFF→(E)|i 句型1=T+TF+i的语法树 6个内部节点—6棵子树 E② 句型n有6个短语： T+TF+i是句型n相对于的短语 E④+T⑤ T+TF是句型1相对于E2的短语 T是句型n相对于E4的短语 T米 T*F是句型n相对于T5的短语 i,i是句型n相对于T3,6的短语 3个直接短语：T,TP,i 句柄：T2个素短语：T*F,1 最左素短语：T*F 2025/4/3 8
2025/4/3 8 利用语法树寻找短语、句柄举例 句型 η=T+T*F+i 的语法树 例 文法G[E]： E→E+T|T T→T*F|F F→(E)|i E E + T F i E + T T T * F ① ② ③ ④ ⑤ ⑥ 句型η有6个短语： T+T*F+i 是句型η相对于E 1的短语 T+T*F 是句型η相对于E 2的短语 T 是句型η相对于E 4的短语 T*F 是句型η相对于T 5的短语 i，i 是句型η相对于T 3 ，F 6的短语 3个直接短语： T ,T*F，i 句柄：T 2个素短语：T*F ，i 最左素短语：T*F 6个内部节点——6棵子树
利用语法树寻找短语、句柄课堂练习 例文法GE]:E→E+T|TT→TFFF→(E)|i 句型n=i1*i2+i3的语法树 BEGIN 8个内部节点 一8棵子树 E2 T3 句型n有8个短语： i1*i2+i3是句型n相对于E的短语 T4 F5 i1*i2是句型1相对于E2,T4的短语 i1是句型n相对于T6,F8的短语 T6 米 F7 is 12是句型n相对于F7的短语 F8 i3是句型n相对于T3,F5的短语 ig 直接短语3个：i1,12,3 句柄：i1素短语3个：i1,2,i3 最左素短语： 2025/4/3 节目录
2025/4/3 9 利用语法树寻找短语、句柄课堂练习 句型 η=i1*i2+i3 的语法树 8个内部节点—— 8棵子树 句型η有8个短语： i1*i2+i3是句型η相对于E 1的短语 i1*i2是句型η相对于E 2 ,T4的短语 i1是句型η相对于T 6 ，F 8的短语 i2是句型η相对于F 7的短语 i3是句型η相对于T 3,F5的短语 例 文法G[E]： E→E+T|T T→T*F|F F→(E)|i 直接短语 3个： i1, i2，i3 句柄：i1 素短语3个：i1,i2，i3 最左素短语： i1 E1 E 2 + T3 F 5 T 6 * F7 T 4 F 8 i2 i3 i1 节目录 BEGIN
自下而上分析基本问题 归约与移进归约法 规范推导与规范归约 移进归约分析器 要解决的基本问题？ 2025/4/3 章节目绿 ☒10
2025/4/3 10 自下而上分析基本问题 ◼归约与移进归约法 ◼规范推导与规范归约 ◼移进归约分析器 ◼要解决的基本问题? 章节目录