最新【考研计算机专业课】天津大学 编译原理讲义 LR(0)分析表(共22张PPT课件).pptx

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

1、4.3.2 LR(0)项目集规范项目集规范(gufn)族和族和LR(0)分析表分析表LR(0)项目集描述了一种只概括项目集描述了一种只概括“历史历史”资料而不包含资料而不包含(bohn)推测性推测性“展望展望”材料的材料的“状态状态”。LR(0)分析分析(fnx)表的构造表的构造:I. 先构造识别文法的活前缀的非确定有限自动机，然后确定化，得到先构造识别文法的活前缀的非确定有限自动机，然后确定化，得到LR(0)项目集规范族，再构造项目集规范族，再构造LR(0)分析表。分析表。II. 直接构造直接构造LR(0)项目集规范族，再构造项目集规范族，再构造LR(0)分析表。分析表。第一页，共二十二页。

2、(1) 规范句型规范句型(j xn)的活前的活前缀缀 所谓所谓(suwi)(suwi)活前缀活前缀是指规范句型的一个前缀，这种前缀不含是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。句柄之后的任何符号。 之所以称为活前缀，是因为在右边增添之所以称为活前缀，是因为在右边增添(zngtin)一些终结符之后，就可一些终结符之后，就可以使它成为一个规范句型。以使它成为一个规范句型。例例，文法，文法G的产生式的产生式为为: : ET| |E+TTF| |T*FF(E)| |iT*i2+i3 T*F+i3 T+i3 E+i3 E+F E+T E句型句型T*i2+i3的活前缀为的活前缀为: ；T；T

3、*；T*i2因为因为i2是句柄。是句柄。I 字的前缀字的前缀是指该字的任意首部。是指该字的任意首部。第二页，共二十二页。(2) 文法文法(wnf)的的LR(0)项目项目设文法设文法G的某一产生式为的某一产生式为Ax1x2xn，则，则Ax1xi xi+1xn 称为称为(chn wi)文法文法G的的LR(0)项目项目。 其中，其中，“”或在文法或在文法(wnf)符号符号xi和和xi+1之间，之间，i=1,2,n-1；或；或在在x1之前；或在之前；或在xn之后。之后。 (1) EaA (2) AcA (3) Ad 例例，文法，文法GAd有两个有两个LR(0)项目项目: : Ad Ad EaA有三个有

4、三个LR(0)项目项目: : EaA EaA EaA 第三页，共二十二页。文法的文法的LR(0)(0)项目分成项目分成(fn chn)(fn chn)如下四类如下四类: : AB 待归约项目待归约项目(xingm)(xingm)，其中，其中，BVN A 归约项目归约项目(xingm) S 接收项目，其中，接收项目，其中，S是根符号是根符号 Aa 移进项目，其中，移进项目，其中，aVT第四页，共二十二页。(3) 识别文法句型识别文法句型(j xn)活前缀的活前缀的NFA识别文法句型活前缀的非确定有限识别文法句型活前缀的非确定有限(yuxin)(yuxin)自动机自动机( (NFA M) )包括包

5、括( (状状态、字母表、状态转换、初态、终态态、字母表、状态转换、初态、终态) )，定义如下，定义如下: : 1.1.对文法对文法(wnf)(wnf)进行拓广，增加新的开始结点进行拓广，增加新的开始结点( (SE) )，定义文法，定义文法的每一个项目。的每一个项目。SE SE EaA EaA EaA (1) SE (2) EaA (2) (3) AcA (4) Ad 例例，文法，文法GAd Ad AcA AcA AcA 第五页，共二十二页。2. 定义文法定义文法(wnf)(wnf)的每一个项目作为的每一个项目作为NFA M的一个状态；字母表的一个状态；字母表= VNVT。 a.如果状态如果状态

6、 i 和和 j 出自同一产生式，而且状态出自同一产生式，而且状态 j 的圆点的圆点只落后于状态只落后于状态 i 的圆点一个位置，的圆点一个位置，如状态如状态 i 为为: Ax1xi-1 xixn状态状态 j 为为: Ax1xi xi+1xn就从状态就从状态 i 画一条标志为画一条标志为xi 的弧到的弧到状态状态 j。3.b.若状态若状态(zhungti)(zhungti)为为AB，BVN，则需从该状态画，则需从该状态画弧弧到所有到所有Br r状态。状态。 4. 文法的根符号产生式文法的根符号产生式SE定义定义(dngy)(dngy)的项目的项目SE E作为初态。作为初态。 5. 文法的所有型如

7、文法的所有型如AA的的LR(0)项目构成的状态都是识别文法项目构成的状态都是识别文法的规范句型的句柄的终态。的规范句型的句柄的终态。 第六页，共二十二页。例例，文法，文法(wnf)(wnf)G的识别规范句型活前缀的的识别规范句型活前缀的NFA M 第七页，共二十二页。(4) NFA DFAI0=1,3 ，I1=2， I2=4,6,9， I3=5， I4=6,7,9 ，I5=8， I6=10 第八页，共二十二页。(5) 构造构造LR(0)项目项目(xingm)集规范族集规范族构成识别一个文法活前缀的构成识别一个文法活前缀的DFA的项目集的项目集(状态状态)的全体的全体(qunt)称称为该文法的为

8、该文法的LR(0)项目集规范族项目集规范族。例例，句型，句型(j xn)(j xn)“acd”的识别过程的识别过程 状态栈状态栈活前缀栈活前缀栈现行输入符号现行输入符号输入串输入串0#(初值初值)Acd#02#aCd#024#acD#0246#acd# 0245#acA# 023#aA# 01#E# 第九页，共二十二页。II. 直接直接(zhji)构造构造(1) 定义两个重要定义两个重要(zhngyo)运算运算:项目项目(xingm)集闭包集闭包Closure(I) : 1. 若一个若一个LR(0)项目项目I，则此项目，则此项目Closure(I)； 2. 若项目若项目ABClosure(I)

9、，则，则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 = I1 GO（I0，a ）= EaA，AcA，Ad = I2 SE SE EaA EaA EaA Ad Ad AcA

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

11、目集规范族的算法如下: 第十二页，共二十二页。Closure( SS )加入加入(jir)C中；中；for (C中的每个项目集中的每个项目集I和和G中的每个文法符号中的每个文法符号X)if ( GO (I，X) 非空且不属于非空且不属于C )将将GO (I，X)加入加入Cdowhile (C不扩大为止不扩大为止)void intemsets(G)第十三页，共二十二页。例例，文法，文法(wnf)G为为:拓广文法拓广文法(wnf)G为为:(1) SS (2) SaBC(3) Bb (4) CcSaBCBb CcI0 = Closure( SS ) = SS，SaBC ；GO（I0，S）= SS =

12、 I1 GO（I0，a）= SaBC，Bb = I2 GO（I2，B）= SaBC，Cc = I3 GO（I2，b）= Bb = I4 GO（I3，C）= SaBC = I6 GO（I3，c）= Cc = I5 第十四页，共二十二页。第十五页，共二十二页。(1) SS (2) SaBC(3) Bb (4) CcI0S SS aBCI1S S SaI2B bS a BCBI3C c S a B CCI6S aBC bcI4B b I5C c 第十六页，共二十二页。给了文法给了文法G，将文法，将文法G拓广为文法拓广为文法G，假若文法，假若文法G的项目集规的项目集规范范(gufn)族已经给出，其状态

13、（项目集）为族已经给出，其状态（项目集）为I0，I1In，则，则分析表的分析表的构造算法构造算法如下如下: 1. 若若GO (Ii，a) =Ij，aVT，则置，则置Action (i，a) = Sj； 2. 若若GO (Ii，X) =Ij，若，若XVN，则置，则置Goto (i，X) = j； 3. 若项目若项目A Ii，A为文法的非根符号，则置为文法的非根符号，则置Action（i，a）=rk，rk表示用文法的第表示用文法的第k个产生式个产生式A进行归约，进行归约，“a”表示集合表示集合(jh)VT#的所有符号；的所有符号； 4. 若项目若项目SS Ii，则置，则置Action（i，#）=“

14、acc”，符号，符号(fho)“#”表示句子右界符。表示句子右界符。 5. 分析表中的空白表示出错。分析表中的空白表示出错。 第十七页，共二十二页。状态状态ACTION表表GOTO表表 abc#SBC0S2 1 1 acc 2 S4 3 3 S5 64r3r3r3r3 5r4r4r4r4 6r2r2r2r2 第十八页，共二十二页。LR(0)分析法的要求分析法的要求: LR(0)(0)分析表要求不含重入口。因此我们希望分析表要求不含重入口。因此我们希望LR(0)(0)分析法分析法在在造表之前，就能够从文法的造表之前，就能够从文法的LR(0)(0)项目集规范族中判定所项目集规范族中判定所造分析表入

15、口定义唯一，即任给一状态造分析表入口定义唯一，即任给一状态( (项目集项目集) )和任一符号和任一符号“a” (” (aVT# ) )，使得，使得Action( (i，a) )的值是唯一的。的值是唯一的。任给一文法，可按上述算法构造一张分析表，若表无任给一文法，可按上述算法构造一张分析表，若表无重入口重入口，则此，则此分析表称为分析表称为(chn wi)LR(0)分析表分析表，所给文法称为，所给文法称为LR(0)文法文法，具有具有LR(0)分析表的分析器，称为分析表的分析器，称为LR(0)分析器分析器。 第十九页，共二十二页。a.a. 一个项目集一个项目集Ii中，既含有移进项目，又含有归约项目

16、，此中，既含有移进项目，又含有归约项目，此种情况，种情况，Action( (i，a) )值不唯一值不唯一(wi y)(wi y)。其中，。其中，aVT，i表示表示状态状态Ii。 Action(i，a)=Sj，同时，同时(tngsh)(tngsh)，Action(i，a)=rk，冲突。，冲突。 例例，若若Action( (i，a) )值不唯一，我们值不唯一，我们(w men)(w men)称为称为语法动作冲突语法动作冲突。通。通常为以下两种情况常为以下两种情况: :第二十页，共二十二页。b.b. 一个项目集一个项目集I Ii i中，存在两个或两个以上中，存在两个或两个以上(yshng)(yshn

17、g)的归约项目，则的归约项目，则Action(i，a)的值不唯一，其中，的值不唯一，其中，i i表示状态表示状态I Ii i。 例例，Action(i，a)= rk1或或rk2，冲突，冲突(chngt)(chngt)。 上述两种情况，有一部分动作冲突上述两种情况，有一部分动作冲突(chngt)(chngt)可用非终极符的后继符号可用非终极符的后继符号集合集合FOLLOW(A)解决。为此，下面介绍解决。为此，下面介绍SLR(1)分析表分析表。 第二十一页，共二十二页。内容(nirng)总结4.3.2 LR(0)项目集规范族和LR(0)分析表。LR(0)项目集描述了一种只概括“历史”资料而不包含(bohn)推测性“展望”材料的“状态”。所谓活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在右边增添一些终结符之后，就可以使它成为一个规范句型。TF|T*F。字的前缀是指该字的任意首部。AcA。例，文法G的识别规范句型活前缀的NFA M。为此，下面介绍SLR(1)分析表第二十二页，共二十二页。