【精品】【考研计算机专业课】天津大学 编译原理讲义 lr(0)分析表（可编辑.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 lr(0)分析表（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 lr(0)分析表（可编辑.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 LR(0)分析表(1)规范句型的活前缀规范句型的活前缀 所谓所谓活前缀活前缀是指规范句型的一个前缀，这种前缀不含句是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。柄之后的任何符号。之所以称为活前缀，是因为在右边增添一些终结符之后，之所以称为活前缀，是因为在右边增添一些终结符之后，就可以使它成为一个规范句型。就可以使它成为一个规范句型。例例，文法，文法G的产生式的产生式为为:ET|E+TTF|T*FF(E)|iT*i2+i3T*F+i3T+i3E+i3E+FE+T E句型句型T*i2+i3的活前缀为的活前缀为:；T；T*；T*i2因为因为i2是

2、句柄。是句柄。I字的前缀字的前缀是指该字的任意首部。是指该字的任意首部。(2)文法的文法的LR(0)项目项目设文法设文法G的某一产生式为的某一产生式为Ax1x2xn，则，则Ax1xixi+1xn称为文法称为文法G的的LR(0)项目项目。其中，其中，“”或在文法符号或在文法符号xi和和xi+1之间，之间，i=1,2,n-1；或在；或在x1之前；或在之前；或在xn之后。之后。(1)EaA(2)AcA(3)Ad例例，文法，文法GAd有两个有两个LR(0)项目项目:AdAdEaA有三个有三个LR(0)项目项目:EaAEaAEaA文法的文法的LR(0)(0)项目分成如下四类项目分成如下四类:AB 待归约

3、项目，其中，待归约项目，其中，BVNA归约项目归约项目S接收项目，其中，接收项目，其中，S是根符号是根符号Aa移进项目，其中，移进项目，其中，aVT(3)识别文法句型活前缀的识别文法句型活前缀的NFA识别文法句型活前缀的非确定有限自动机识别文法句型活前缀的非确定有限自动机(NFAM)包括包括(状状态、字母表、状态转换、初态、终态态、字母表、状态转换、初态、终态)，定义如下，定义如下:1.1.对文法进行拓广，增加新的开始结点对文法进行拓广，增加新的开始结点(SE)，定义文，定义文法的每一个项目。法的每一个项目。SESEEaAEaAEaA(1)SE(2)EaA(2)(3)AcA(4)Ad例例，文法

4、，文法GAdAdAcAAcAAcA(4)NFADFAI0=1,3，I1=2，I2=4,6,9，I3=5，I4=6,7,9，I5=8，I6=10(5)构造构造LR(0)项目集规范族项目集规范族构成识别一个文法活前缀的构成识别一个文法活前缀的DFA的项目集的项目集(状态状态)的全体的全体称为该文法的称为该文法的LR(0)项目集规范族项目集规范族。例例，句型，句型“acd”的识别过程的识别过程状态栈状态栈活前缀栈活前缀栈现行输入符号现行输入符号输入串输入串0#(初值初值)Acd#02#aCd#024#acD#0246#acd#0245#acA#023#aA#01#E#II.直接构造直接构造(1)定义

5、两个重要运算定义两个重要运算:项目集闭包项目集闭包Closure(I):1.若一个若一个LR(0)项目项目I，则此项目，则此项目Closure(I)；2.若项目若项目ABClosure(I)，则，则BClosure(I)，其，其中中BVN；3.重复重复(2)，直至，直至Closure(I)不扩大为止。不扩大为止。状态转换函数状态转换函数GO(I，X):GO(I，X)=Closure(J)其中，其中，J=任何形如任何形如AX的项目的项目|AXI(1)SE(2)EaA(2)(3)AcA(4)Ad例例，文法，文法GI0=Closure(I)=SE，EaA设设I=SE，则，则GO（I0，E）=SE=I

6、1GO（I0，a）=EaA，AcA，Ad=I2SESEEaAEaAEaAAdAdAcAAcAAcA思想思想:从项目集从项目集I0开始，将开始，将I0定义成一个状态，按照定义成一个状态，按照状态转换函数状态转换函数GO（I，X）的定义可以找出所有的项）的定义可以找出所有的项目集（状态），由目集（状态），由GO（I，X）所产生的项目集（状）所产生的项目集（状态）全体称为项目集规范族。态）全体称为项目集规范族。(2)设所给文法为设所给文法为GS=(Vn，Vt，P，S)，我们定义，我们定义一个拓广文法一个拓广文法GS=(VnS，Vt，PSS，S)，产生拓广文法，产生拓广文法LR(0)项目集规范族的算法

7、如下项目集规范族的算法如下:Closure(SS)加入加入C中；中；for(C中的每个项目集中的每个项目集I和和G中的每个文法符号中的每个文法符号X)if(GO(I，X)非空且不属于非空且不属于C)将将GO(I，X)加入加入Cdowhile(C不扩大为止不扩大为止)voidintemsets(G)例例，文法，文法G为为:拓广文法拓广文法G为为:(1)SS(2)SaBC(3)Bb(4)CcSaBCBbCcI0=Closure(SS)=SS，SaBC；GO（I0，S）=SS=I1GO（I0，a）=SaBC，Bb=I2GO（I2，B）=SaBC，Cc=I3GO（I2，b）=Bb=I4GO（I3，C）

8、=SaBC=I6GO（I3，c）=Cc=I5(1)SS(2)SaBC(3)Bb(4)CcI0SSSaBCI1SSSaI2BbSaBCBI3CcSaBCCI6SaBCbcI4BbI5Cc给了文法给了文法G，将文法，将文法G拓广为文法拓广为文法G，假若文法，假若文法G的项目的项目集规范族已经给出，其状态（项目集）为集规范族已经给出，其状态（项目集）为I0，I1In，则，则分析表的构造算法分析表的构造算法如下如下:1.若若GO(Ii，a)=Ij，aVT，则置，则置Action(i，a)=Sj；2.若若GO(Ii，X)=Ij，若，若XVN，则置，则置Goto(i，X)=j；3.若项目若项目AIi，A为

9、文法的非根符号，则置为文法的非根符号，则置Action（i，a）=rk，rk表示用文法的第表示用文法的第k个产生式个产生式A进行归约，进行归约，“a”表示表示集合集合VT#的所有符号；的所有符号；4.若项目若项目SSIi，则置，则置Action（i，#）=“acc”，符号，符号“#”表示句子右界符。表示句子右界符。5.分析表中的空白表示出错。分析表中的空白表示出错。状态状态ACTION表表GOTO表表abc#SBC0S211acc2S433S564r3r3r3r35r4r4r4r46r2r2r2r2LR(0)分析法的要求分析法的要求:LR(0)(0)分析表要求不含重入口。因此我们希望分析表要求

10、不含重入口。因此我们希望LR(0)(0)分析法在分析法在造表之前，就能够从文法的造表之前，就能够从文法的LR(0)(0)项目集规范族中判定所造分项目集规范族中判定所造分析表入口定义唯一，即任给一状态析表入口定义唯一，即任给一状态(项目集项目集)和任一符号和任一符号“a”(aVT#)，使得，使得Action(i，a)的值是唯一的。的值是唯一的。任给一文法，可按上述算法构造一张分析表，若表无任给一文法，可按上述算法构造一张分析表，若表无重重入口入口，则此分析表称为，则此分析表称为LR(0)分析表分析表，所给文法称为，所给文法称为LR(0)文法文法，具有，具有LR(0)分析表的分析器，称为分析表的分

11、析器，称为LR(0)分析分析器器。a.a.一个项目集一个项目集Ii中，既含有移进项目，又含有归约项目，中，既含有移进项目，又含有归约项目，此种情况，此种情况，Action(i，a)值不唯一。其中，值不唯一。其中，aVT，i表示表示状态状态Ii。Action(i，a)=Sj，同时，同时，Action(i，a)=rk，冲突。，冲突。例例，若若Action(i，a)值不唯一，我们称为值不唯一，我们称为语法动作冲突语法动作冲突。通常。通常为以下两种情况为以下两种情况:b.b.一个项目集一个项目集I Ii i中，存在两个或两个以上的归约项目，则中，存在两个或两个以上的归约项目，则Action(i，a)的值不唯一，其中，的值不唯一，其中，i i表示状态表示状态I Ii i。例例，Action(i，a)=rk1或或rk2，冲突。，冲突。上述两种情况，有一部分动作冲突可用非终极符的后继符号上述两种情况，有一部分动作冲突可用非终极符的后继符号集合集合FOLLOW(A)解决。为此，下面介绍解决。为此，下面介绍SLR(1)分析表分析表。