《编译原理》课程教学资源：第二章 语言描述与实现 Language Description and Implementation 2.5 语法分析——自下而上分析

2.5语法分析自下而上分析 25.1.1归约( Reduce) ●自下而上( Bottom-Up)分析采用“移进一归 约”( shift-reduce)的基本思想 把输入符号逐个移进到一个符号栈,当栈顶形成某 个产生式的候选式时,即把栈顶的这一部分替换成 (归约为)该产生式的左部符号

2.5.1.1 归约(Reduce) 自下而上(Bottom-Up)分析采用“移进－归 约”(shift-reduce)的基本思想 ⚫ 把输入符号逐个移进到一个符号栈，当栈顶形成某 个产生式的候选式时，即把栈顶的这一部分替换成 (归约为)该产生式的左部符号。 2.5 语法分析——自下而上分析

●例:设文法GS): (1)s+aAcBe (2)A→b (3)A→Ab (4)B→d 试对 abbcde进行“移进一归约”分析 eBeAa abin

例：设文法G(S)： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 试对abbcde进行“移进－归约”分析。 a bbcde b bcde A b cde c de d abbcdee e B c A Sa B c A a e

步骤:12345678910 动作:进a进b归(2)进b归(3)进c进d归(4)进e归(1 bAAa cAa dcAa BcAa BcAa S

步骤: 1 2 3 4 5 6 7 8 9 10 动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1) e d B B b c c c c b A A A A A A A a a a a a a a a a S

a B′e b d 自下而上分析过程:边输入单词符号,边 归约。 核心问题:识别可归约串

b b d a c e S A B A 自下而上分析过程：边输入单词符号，边 归约。 核心问题：识别可归约串

25.1.2规范归约 定义:令G是一个文法,S是文法的开始符号,假 定aB8是文法G的一个句型,如果有 且 S→ aA8 A=B 则β称是句型aB86相对于非终结符A的短语。 特别是,如果有A→B,则称β是句型aB8相对 于规则A→>β的直接短语。一个句型的最左 直接短语称为该句型的句柄

2.5.1.2 规范归约 定义：令G是一个文法，S是文法的开始符号，假 定是文法G的一个句型，如果有 且 S A *   + A 则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对 于规则A→ 的直接短语。一个句型的最左 直接短语称为该句型的句柄

考虑文法G(E):E→T|E+T T今F|TF F→>(E 和句型+2+3 E→ET→E+F→E+i3→T+ →TF+3→T2+3→F*i2+i3 →i1i2 问题:对于句型i2+i3而言,有哪些短语、 直接短语和句柄?

考虑文法G(E)： E → T | E+T T → F | T*F F → (E) | i 和句型i1 *i2+i3： E  E+T  E+F  E+i3  T+i3  T*F+i3  T*i2+i3  F*i2+i3  i1 *i2+i3 问题：对于句型i1 *i2+i3而言，有哪些短语、 直接短语和句柄？

因为 E*→F2+13→料2+3所以1是句型相对于非终结符F 的短语和直接短语。 E→*F+3→1+2+i3,所以2是句型相对于非终结符F的 短语和直接短语。 E*→1i2+F→i*2+i3,所以i3是句型相对于非终结符F的 短语和直接短语 E*→E+i3+→i1*2+i3,所以i2是句型相对于非终结符E 的短语。 E*→E→i12+3所以i12+i3是句型相对于非终结符E 的短语。 结论:对于句型1*2+3而言: 短语:i1,i2,i3,i1*i2,i1*2+3 直接短语:i1,i2,i3 句柄:i1

因为 E * F*i2+i3  i1 *i2+i3 ,所以i1是句型相对于非终结符F 的短语和直接短语。 E* i1 *F+i3  i1 *i2+i3 ,所以i2是句型相对于非终结符F的 短语和直接短语。 E*  i1 *i2+F i1 *i2+i3 ,所以i3是句型相对于非终结符F的 短语和直接短语。 E* E+i3 + i1 *i2+i3 ,所以i1 *i2是句型相对于非终结符E 的短语。 E *  E i1 *i2+i3 ,所以i1 *i2+i3是句型相对于非终结符E 的短语。 结论：对于句型i1 *i2+i3而言： ⚫ 短语： i1，i2，i3， i1 *i2， i1 *i2+i3 ⚫ 直接短语： i1，i2，i3 ⚫ 句柄： i1

根据语法树找短语、直接短语、句柄 ●在一个句型对应的语法 树中,以某非终结符为 根的两代以上的子树的 所有末端结点从左到右 排列就是相对于该非终 F 结符的一个短语,如果 子树只有两代,则该短 语就是直接短语。而最 左直接短语就是句柄

在一个句型对应的语法 树中，以某非终结符为 根的两代以上的子树的 所有末端结点从左到右 排列就是相对于该非终 结符的一个短语，如果 子树只有两代，则该短 语就是直接短语。而最 左直接短语就是句柄。 E F F T T T i1 + * E F i3 i2 根据语法树找短语、直接短语、句柄

可用句柄来对句子进行归约 句型归约规则 abbcde(2)A→b aBode(3)A→Ab aAcde (4)B>d aAcBe(1)s→ aAcBe s

可用句柄来对句子进行归约 句型 归约规则 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1) S → aAcBe S

●定义:假定α是文法G的一个句子,我们称序列 a 0 是一个规范归约,如果此序列满足: On- a 2a为文法的开始符号,即a=S 3对任何i,0≤isn,a;-1是从a1经把句 柄替换成为相应产生式左部符号而得到的

定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是一个规范归约，如果此序列满足： 1 n=  2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句 柄替换成为相应产生式左部符号而得到的