编译原理 第6-1章(清华大学).ppt

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

1、第6章ＬＲ分析程序及其自动构造6.1自下而上分析及其LR分析概述6.2LR(0)分析6.3SLR(1)分析6.4LR（1）分析6.5LALR分析6.6使用二义文法自下而上分析算法能力强构造复杂最常用和最有效的模型----移进归约(动作）总控程序outputInput#…栈状态文法符号分析表产生式表将输入分成两部分：未消化和半消化的总控程序outputInput#未消化半消化的分析表产生式表S–>EE–>T

2、E+TT–>int

3、(E)Reduce:如能找到一产生式A–>w且栈中的内容是qw(q可能为空),则可以将其归约为qA.

4、即倒过来用这个产生式.如上例,若栈中内容是(int，我们使用产生式T–>int并把栈中内容归约为(TShift:如不能执行一个归约且在未消化的输入中还有token，就把它从输入移到栈中.如上例,假定栈中内容是(,输入中还有int+int)#.不能对(执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是(int，而余留的输入是+int)#.Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S（即施用S–>w），且没有余留输入了，意味着已成功分析了整个输入串.移进归约分析中还会出现

5、一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析int+)时就会发生错误.移进-归约模型分析(int+int)的过程STACKREMAININGINPUTPARSERACTION1(int+int)#Shift2(int+int)#Shift3(int+int)#Reduce:T–>int4(T+int)#Reduce:E–>T5(E+int)#Shift6(E+int)#Shift7(E+int)#Reduce:T–>int8(E+T)#Reduce:E–>E+T9(E)#Shi

6、ft10(E)#Reduce:T–>(E)11T#Reduce:E–>T12E#Reduce:S–>E13S#(E+T)#Reduce:E–>E+Twhy?不用E–>T(E)#若使用了E–>T，在栈中形成的(E+E不是规范句型的活前缀（viableprefixes）（E+E不能和任何产生式的右端匹配（E+E）不是规范句型活前缀是规范句型（右句型）的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导规范句型规范归约最右推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最右非终结符进行替换最

7、右推导被称为规范推导。由规范推导所得的句型称为规范句型G[S]：S→EE→E+T

8、TT→(E)

9、intSET(E)(E+T)(E+int)(T+int)(int+int)规范归约假定α是G的一个句子，称序列αn,αn-1…,α0是α的一个规范归约如果该序列满足：（1）αn=α（2）α0为文法的开始符号（3）对任何j,0

10、ce或者分析程序归约时有多个产生式可选例子（danglingelse）：S–>ifEthenS

11、ifEthenSelseS如输入ifEthenifEthenSelseS分析某一时刻，栈的内容:ifEthenifEthenS而else是下一token归约还是移进？特定的一种shift-reduce实现技术ＬＲ分析LR最右推导分析器模型和分析算法ＬＲ　分析特征讨论ＬＲ分析器模型总控程序outputInput#S1Xm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表ACTIONGOTOacebd#SAB0S

12、211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR分析算法置ip指向输入串w的第一个符号令S为栈顶状态a是ip指向的符号重复beginifACTION[S,a]=SjthenbeginPUSHj,a(进栈)ip前进(指向下一输入符号)endelseifACTION[S,a]=rj(第j条产生式为A)ＬＲ分析程序thenbeginpop

13、

14、项令当前栈顶状态为S’pushGOTO[S’,A]和A(进栈)endelseifA

15、CTION[s,a]=accthenreturn(成功）elseerrorend.重复例6.1:G[S]:SaAcBe[1]Ab[2]AAb[3]Bd[4]w=abbcde#Stepstates.Syms.Therestofinputactiongoto10#abbcde#s220