清华大学：《编译原理》课程教学资源_第六章 LR分析 6.1 概述 自下而上的语法分析 LR分析器 6.2 LR（0）分析

第六章LR分析 自下而上的语法分析 特定的一种h+ reduce实现技术 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件 难点 几乎不可能用手工编写LR分析器 现实 有LR分析器的生成器

第六章ＬＲ分析 自下而上的语法分析 特定的一种shift-reduce实现技术 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件 难点 几乎不可能用手工编写LR分析器 现实 有LR分析器的生成器

第六章LR分析 61概述 自下而上的语法分析 LR分析器 62LR(0)分析 63SLR(1)分析技术,二义文法的应用 64LR(1)和LALR(1)分析

第六章ＬＲ分析 6.1 概述 自下而上的语法分析 LR分析器 6.2 LR(0)分析 6.3 SLR(1)分析技术，二义文法的应用 6.4 LR(1)和LALR(1)分析

61概既述 自下而上的语法分析 例:文法G:S→cAd A→ab A 识别输入串w=cabd是否该文法的句子 归约过程构造的推导:cAd→ cabd S→cAd

6.1 概述 自下而上的语法分析 例：文法G： S → cAd A → ab A → a 识别输入串w=cabd是否该文法的句子 S A A c a b d c a b d c d 归约过程构造的推导： cAd  cabd S  cAd

(1)S→cAd(2)A→ab(3)A→a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中,如果不是 选择ab用产生式(2)而是选 择a用产生式(3)将a归约到 c abd 了A,那么在cAb 中无法找到一个可归约串 最终就达不到归约到S的结 果,因而也无从知道cabd是cAbd 在自下而上的分析方法中如何 识别可归约的串? 在分析程序工作的每一步, 都是从当前串中选择一个 子串,将它归约到某个非 终结符号,该子串称为 可岿约串

(1)S → cAd (2) A → ab (3)A → a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中，如果不是 选择ab用产生式(2),而是选 择a用产生式(3)将a归约到 了A，那么在c A b d 中无法找到一个可归约串了， 最终就达不到归约到S的结 果，因而也无从知道cabd是 一个句子 在自下而上的分析方法中如何 识别可归约的串？ 在分析程序工作的每一步， 都是从当前串中选择一个 子串，将它归约到某个非 终结符号，该子串称为 “可归约串” c a b d c A b d a

刻画“可归约串” 文法G|S 句型的短语 S=*aA6且A=+β,则称β是句型aB8 相对于非终结符A的短语 句型的直接短语 若有A→β,则称β是句型aβ8相对于非终结 符A的直接短语 句型的句柄 个句型的最左直接短语称为该句型的句柄

刻画“可归约串” 文法G[S] 句型的短语 S =>* αAδ且 A =>+ β，则称β是句型αβδ 相对于非终结符A的短语 句型的直接短语 若有A β，则称β是句型αβδ相对于非终结 符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄

例:i*i+i的短语、直接短语和句柄 E G[E]:E→E+TT E T→T*F|F F→(E)i 句型:i*i+i T* F 短语:i*i2+i3,i*i2 直接短语:i1,,,句柄:

例 ：i*i+i 的短语、直接短语和句柄 E E + T T F T * F i3 短语：i1* i2+ i3， i1* i2， F i2 i1 ， i2， i3 。 i1 直接短语： i1， i2， i3 。句柄： i1 G[E]：E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i

自下而上的语法分析 在分析程序工作的每一步,都是从当前串中选择一 个子串,将它归约到某个非终结符号,该子串称为 “可归约串” 选择“可归约串”是最左素短语(至少 含有一个终结符的最左边的短语,且这 个短语不包含别的短语) 选择“可归约串”是句型的句柄一规范 归约

自下而上的语法分析 在分析程序工作的每一步，都是从当前串中选择一 个子串，将它归约到某个非终结符号，该子串称为 “可归约串” • 选择“可归约串”是最左素短语（至少 含有一个终结符的最左边的短语，且这 个短语不包含别的短语） • 选择“可归约串”是句型的句柄－规范 归约

G[E|:E→E+TT T→T*F|F F→→(E川i 句型的自下而上分析,总是归约当前句型的句柄形成的规 范推导序列: E→E+T→E十F→E+i→Ti→T*+i→T*+→F*+i→iii 句型i计的自下而上分析总是归约当前句型的最左素短语形成 的推导: E→T+F→Ti→→F*F+i→F*计+i→→ii+i

G[E]：E→E+T|T T→T*F|F F→(E)|i • 句型 i*i+i 的自下而上分析，总是归约当前句型的句柄形成的规 范推导序列： EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i • 句型 i*i+i 的自下而上分析总是归约当前句型的最左素短语形成 的推导： ET+FT+iF*F+iF*i+ii*i+i

自下而上的分析模式移进-归约模式 Shif:移进,输入符进栈 reduce:归约,用第个产生式归约 Input$(#) 总控程序 output 移进归约 生 依据表 式 表

自下而上的分析模式 移进－归约模式 Shift:移进，输入符进栈 reduce:归约，用第i个产生式归约 总控程序 output … 产 生 式 表 Input$(#) … 移进归约 依据表

文法G[S]: 步骤找 余留輸入符号串动作 (1) s→ QAcBe 1)# abbcdetf 移进 (2)A→b 2)#a bbcde#f 移进 (3)A→Ab 3)# badelt 归约(A→b (4)B→d 4)#aA bcdf 移进 5)*aAb coeff 归约(A→Ab) s 6)#aA cdet 移进 7)#aAc dett 移进 8)#aAcd 归约(B→d) 9)#aAcB 移进 10)*aAcBe # 归约(→ aAc Be 11)#S # 接受 对输入串 abbcde#的移进-归约分析过程 bb c d 符号串 abode是看是G[S]的句子 s→ aAcBe→ qAcde→ aBode→ abbcde

文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e 步骤 栈 余留输入符号串 动作 1） # abbcde# 移进 2） #a bbcde# 移进 A 3） #ab bcde# 归约(A→b) 4） #aA bcde# 移进 A 5） #aAb cde# 归约(A→Ab) 6） #aA cde# 移进 7） #aAc de# 移进 B 8） # aAcd e# 归约(B→d) 9） #aAcB e# 移进 11） #S # 接受 S 10） #aAcBe # 归约(S →aAcBe) 符号串abbcde是否是G[S]的句子 对输入串abbcde#的移进-归约分析过程 SaAcBe aAcde aAbcde  abbcde