编译原理 第13讲(第七章).ppt

《编译原理 第13讲(第七章).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章ＬＲ分析7.1LR概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)分析7.5LALR(1)分析7.6二义文法在LR分析中的应用7.1LR分析概述自下而上的语法分析，特定的一种shift-reduce实现技术特点能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器自下而上的语法分析SAAcabdcabdcd归约过程构造的推导：cAdcabdScAd例：文法G：S→cAdA→abA→a识别输入串w=cabd是否该文法的句子归约的例子(1)S→cAd(2)A→ab(3

2、)A→a识别输入串w=cabd是否为该文法的句子自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2)，而是选择a用产生式(3)，将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子。在自下而上的分析方法中如何识别可归约的串？cabdcAbda刻画“可归约串”在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）选择“可归约串”是句型的句柄，

3、又称规范归约例子G[E]：E→E+T

4、TT→T*F

5、FF→(E)

6、i求句型i*i+i短语：i1*i2+i3，i1*i2，i1，i2，i3直接短语：i1，i2，i3句柄：i1句型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+iEE+TT+TT+FT+iT*F+iF*F+iF*i+ii*i+iEE

7、+TTFT*Fi3Fi2i1LR分析器模型(一种shift-reduce实现技术)总控程序outputInput$(#)…栈LR分析表（移进归约依据表）产生式表L－从左到右扫描输入串R－构造最右推导ACTION表和GOTO表ACTION表告诉分析器：栈顶状态为S,当前输入符号是a时做什麽1.ACTION[S,a]=Sj(由状态S转移到状态Sj)2.ACTION[S,a]=rj(根据第j条产生式为A，进行归约)3.ACTION[S,a]=acc(分析结束，分析器接受符号串)4.ACTION[S,a]=error(分析结束，分析器拒绝符号串)GOTO表G

8、OTO[S,A]。栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态ACTION表和GOTO表是如何生成的呢？根据文法构造的DFA来生成LR分析算法置ip指向输入串w的第一个符号令S为栈顶状态,a是ip指向的符号重复beginifACTION[S,a]=SjthenbeginPUSHj(进栈)ip前进(指向下一输入符号)endelseifACTION[S,a]=rj(第j条产生式为A)thenbeginpop

9、

10、项令当前栈顶状态为S’pushGOTO[S’,A]endelseifACTION[s,a]=accthenreturn(成功）el

11、sereturn(error)end.重复LR分析的例子G[S]:(1)SaAcBe(2)Ab(3)AAb(4)Bd符号串w=abbcde#是否是G[S]的句子ACTIONGOTO状态acebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR分析表生成DFAx235789641AbaSbcBed*这个DFA怎么构造的？LR分析过程Stepstates..Therestofinputactiongoto10abbcde#s2202bb

12、cde#s43024bcde#r2goto(2,A)4023bcde#s650236cde#r3goto(2,A)6023cde#s570235de#s8802358e#r4goto(5,B)902357e#s910023579#r1goto(0,S)1101#acc(带符号栈的）LR分析器模型总控程序outputInput#S1Xm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表(带符号栈的）LR分析过程Stepstates.Syms.Therestofinputactiongoto10#abbcde#s2202#abbcde#s

13、43024#abbcde#r234023#aAs650236#aAbcde#r3