《编译原理6-lr0》由会员分享，可在线阅读，更多相关《编译原理6-lr0（53页珍藏版）》请在金锄头文库上搜索。
1、 第六章分析 自下而上的语法分析 特定的一种shift-reduce实现技术能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件 难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器第六章分析6.1 概述自下而上的语法分析LR分析器 6.2 LR(0)分析 6.3 SLR(1)分析技术，二义文法的应用 6.4 LR(1)和LALR(1)分析6.1 概述 自下而上的语法分析例：文法G： S cAdA abA a 识别输入串w=cabd是否该文法的句子SAAc a b d c a b d c d 归约过程构造的推导： cAd cabd S cAd(1)S cAd (2) A ab
2、 (3)A a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析对串cabd的分析中，如果不是 选择ab用产生式(2),而是选 择a用产生式(3)将a归约到 了A，那么在c A b d 中无法找到一个可归约串了， 最终就达不到归约到S的结 果，因而也无从知道cabd是 一个句子 在自下而上的分析方法中如何 识别可归约的串？ 在分析程序工作的每一步 ，都是从当前串中选择一 个子串，将它归约到某个 非终结符号，该子串称为“ 可归约串”c a b dc A b da刻画“可归约串”文法GS句型的短语 S =* A且 A =+ ，则称是句型 相对于非终结符A的短语句型的直接短语 若有A ，
3、则称是句型相对于非终结 符A 的直接短语句型的句柄 一个句型的最左直接短语称为该句型的句柄例 ：i*i+i 的短语、直接短语和句 柄E E + TT F T * F i3 短语：i1* i2+ i3， i1* i2 ，F i2 i1 ， i2 ， i3 。 i1 直接短语： i1 ， i2 ， i3 。句柄： i1 GE：EE+T|TTT*F|FF(E)|i 句型：i*i+i自下而上的语法分析 在分析程序工作的每一步，都是从当前串中选 择一个子串，将它归约到某个非终结符号，该 子串称为“可归约串” 选择“可归约串”是最左素短语（至少含 有一个终结符的最左边的短语，且这个 短语不包含别的短语）
4、选择“可归约串”是句型的句柄规范归 约GE：EE+T|TTT*F|FF(E)|i句型 i*i+i 的自下而上分析，总是归约当前句型的句柄形成的规范 推导序列： EE+TE+FE+iT+iT*F+iT*i+iF*i+i i*i+i句型 i*i+i 的自下而上分析总是归约当前句型的最左素短语形成的 推导：ET+FT+iF*F+iF*i+i i*i+i自下而上的分析模式 移进归约模式 Shift:移进，输入符进栈 reduce:归约，用第i个产生式归约总控程序output产 生 式 表Input$(#)移进归约 依据表文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B
5、da b b c de步骤栈余留输入符号串动作1） # abbcde# 移进2） #a bbcde# 移进A3） #ab bcde# 归约(Ab)4） #aA bcde# 移进A5） #aAb cde# 归约(AAb)6） #aA cde# 移进7） #aAc de# 移进B8） # aAcd e# 归约(Bd)9） #aAcB e# 移进11） #S # 接受S10） #aAcBe # 归约(S aAcBe)符号串abbcde是否是GS的句子对输入串abbcde#的移进-归约分析过程SaAcBe aAcde aAbcde abbcde6.1 概述 分析 特定的一种shift-reduce实现
6、 技术L 从左到右扫描输入串 R 构造最右推导分析器模型总控程序outputInput$(#)栈LR分析表产 生 式 表LR分析表(1)S a A c B e (2)A b (3)A Ab (4)B dLR分析表ACTION GOTOa c e b d # S A B 0 S2 1 1 acc 2 S4 3 3 S5 S6 4 r2 r2 r2 r2 r2 r2 5 S8 7 6 r3 r3 r3 r3 r3 r3 7 S9 8 r4 r4 r4 r4 r4 r4 9 r1 r1 r1 r1 r1 r1LR分析使用两张表ACTION表 告诉分析器：栈顶状态为S, 当前输入符号是a时做什 麽 1
7、. ACTIONS,a= Sj2. ACTIONS,a=rj (第j条产生式为A) 3. ACTIONS,a=acc 4. ACTIONS,a= error GOTO表GOTOS,A栈顶状态为S，归约之后的非终结符為A时 ，要放到栈顶的新状态分析 GS: (1)S a A c B e (2)A b (3)A Ab (4)B d w=abbcde# Step states. . The rest of input action goto 1 0 abbcde# s2 2 02 bbcde# s4 3 024 bcde# r2 goto(2,A) 4 023 bcde# s6 5 0236 cde
8、# r3 goto(2,A) 6 023 cde# s5 7 0235 de# s8 8 02358 e# r4 goto(5,B) 9 02357 e# s9 10 023579 # r1 goto(0,S) 11 01 # acc1) E E + T 2) E T 3) T (E) 4) T idid + (id)LR分析算法置ip指向输入串w的第一个符号 令S为栈顶状态a是ip指向的符号 重复 begin if ACTIONS,a=Sjthen begin PUSH j(进栈)ip 前进(指向下一输入符号)end else if ACTIONS,a=rj (第j条产生式为A)分析算法(c
9、ontinue)then begin pop | 项 令当前栈顶状态为S push GOTOS,A end else if ACTIONs,a=acc then return (成功） else error end.重复 分析特征 栈顶状态为S, 当前输入符号是a时 做什麽-?有穷狀态自动机 规范推导进一步讨论分析特征 GS: (1)S a A c B e (2)A b (3)A Ab (4)B d w=abbcde#(带符号栈的）分析器模型总控程序outputInput#S1 Xm S1 X1S0 #栈状态文法符号ACTION GOTOLR分析表产 生 式 表 Step states. Syms. The rest of inputaction goto 1 0 # abbcde# s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 4 023
