《编译原理实践及应用》第4章(3)LR分析方法.ppt

《编译原理实践及应用》第4章(3)LR分析方法.ppt

《《编译原理实践及应用》第4章(3)LR分析方法.ppt》由会员分享，可在线阅读，更多相关《《编译原理实践及应用》第4章(3)LR分析方法.ppt（66页珍藏版）》请在冰点文库上搜索。

LR分析方法,第四章（3）,本章要求,主要内容：

LR分析方法及其相关概念，语法分析器的自动生成，各种语法分析中的错误处理重点掌握：

LR分析方法与分析过程，活前缀、LR（0）项目、Closure和go函数的定义，项目集规范族及识别活前缀的有穷自动机的构造，LR（0）分析表的构造，SLR文法及其分析表的构造。

LR分析概述,LR分析法：

L从左向右扫描输入串，R构造最右推导的逆过程大多数用上下文无关文法描述的高级语言的语法成分可以用LR分析器来识别。

LR分析：

采用移进-归约分析，严格的规范归约。

LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K（K0）个符号就可以唯一确定分析的动作是移进还是归约。

向前查看0个符号，就是LR（0）分析方法，向前查看1个符号，就是LR

（1）方法。

LR分析的优缺点,优点：

比其他“移进-归约”方法使用广泛，识别率高能用LL

（1）分析法分析的所有文法都能使用LR方法来进行分析。

LR分析法在扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。

缺点：

手工构造分析表工作量太大。

必须使用自动生成器。

自底向上分析法的关键问题是如何确定句柄。

LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。

在算符优先分析中，通过算符的优先关系得到句柄“最左素短语”，LR方法中句柄是通过识别活前缀而求得。

LR分析方法的基本思想是：

在规范归约过程中，一方面记住已移进和归约出的整个符号串（历史），另一方面又根据所用产生式推测未来可能碰到的输入符号（对未来的展望）。

当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。

一个LR分析器的组成见下图。

1、LR分析方法的逻辑结构,一个LR分析器由3个部分组成：

LR分析程序，又称总控程序。

所有的LR分析器都是相同的。

分析表（分析函数），不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

状态栈：

（S0,#）为预先放到栈中的初始状态和符号。

文法符号：

X1X2Xm是目前已移进并归约出的句型部分。

其实它是多余的，已经概括到状态里。

分析器实际上是一个带有先进后出栈的确定的有穷自动机。

将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。

只需根据栈顶状态和输入符号就可以唯一决定下一个动作。

总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。

LR方法：

根据具体文法的分析表对输入串进行分析处理。

LR分析过程：

在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。

2.分析表的组成：

表中actionSi,aj，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。

其动作有四种可能，分别为：

移进（S）、归约（r）、接受（acc）、出错（error）。

（1）分析动作表Action是一个二维数组,表中gotoSi,xj指出状态为Si，遇到Xj时应转到的下一状态。

显然：

分析表定义了一个以文法符号为字母表的DFA,

（2）状态转换表goto也是一个二维数组,ri表示按第i个产生式进行归约,Si表示把当前输入符号移进栈，第i个状态进状态栈。

i表示转第i个状态，即第i个状态进状态栈。

空白表示分析动作出错,例：

LR的Action和GoTo表,

（1）EE+T

（2）ET（3）TT*F（4）TF（5）F（F）（6）Fi,产生式的序号,设文法为GL：

用三元式:

（状态栈，符号栈，输入符号串）表示分析过程中状态栈，符号栈，输入符号串的变化初始时，将状态S0和#进分析栈。

三元式为：

（S0,#,a1a2an#）任一时刻的三元式为：

（S0S1Sm,#X1X2Xm,aiai+1an#）分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。

3、LR分析过程：

移进：

当前输入符号ai移进符号栈，将action表中指出的状态S进状态栈。

（S0S1SmS,#X1X2Xmai,ai+1an#）,根据Sm和ai查action表,actionSm,ai有4种情况：

出错：

报告出错信息。

三元式的变化过程终止。

接受：

分析成功，终止分析。

三元式不再变化。

归约：

若产生式A的右端长度为r，则两个栈顶的r个元素同时出栈，A进符号栈;再根据Sm-r和A查goto表，S=gotoSm-r,A进状态栈。

三元式变为：

（S0S1Sm-rS,#X1X2Xm-rA,aiai+1an#）,为了介绍LR分析过程，直接给出该文法的分析表，以后再介绍如何生成,例：

LR的具体分析过程：

（1）EE+T

（2）ET（3）TT*F（4）TF（5）F（F）（6）Fi,设文法为GL：

根据上述分析表，对输入串i*i+i的分析过程如下：

LR文法：

对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的如何构造LR分析表？

1）基本概念字的前缀：

指该字的任意首部。

活前缀：

规范句型的一个前缀，不含句柄之后的任何符号。

在它之后增添一些终结符号后，就成为规范句型。

即：

对于文法G，若S，Vt*，称为活前缀。

在LR分析的过程中，假定输入串是一个句子，任何时候符号栈里的文法符号都构成活前缀，配上输入串的剩余部分，就成为规范句型。

构造一个有穷自动机来识别文法G的所有活前缀，这样就可以自动生成LR分析表。

4、LR（0）项目集族,*,LR（0）项目：

在文法G中每个产生式的右部适当位置添加一个圆点构成项目。

例如：

产生式SXYZ对应有4个项目：

0SXYZ1SXYZ2SXYZ3SXYZ产生式A只对应一个项目：

A项目指明了在分析过程的某时刻，已看到的产生式部分项目集：

若干个项目组成的集合。

例如：

对于上述产生式的4个项目即构成一个项目集。

练习,求文法：

SaS|bS|a的LR（0）项目集,SaSSbSSa,SaSSaSSaSSbSSbSSbSSaSa,后继符号有多种，据此将项目分为多种：

移进项目：

后继符号为终结符：

Aa待约项目：

后继符号为非终结符：

AB归约项目：

后继符号为空：

即圆点在最右边A接受项目：

归约项目的左边是文法开始符号S,后继符号：

在项目中紧跟在符号“”后面的符号称为该项目的后继符号。

表示下一时刻遇到的符号。

后继符号集：

项目集中各项目的后继符号所组成的集合称为后继符号集。

项目集EET,Fi的后继符号集为,i,写出文法的所有项目，每个项目是一个状态规定项目1为NFA的唯一初态若状态i和状态j出自同一产生式，而且状态j的圆点只落后于状态i一个位置:

若i的圆点后是a，从i到j画一条弧，标记为a若i的圆点后是A，则连两种弧：

（1）从状态i画弧到所有的A的状态。

（2）从状态i到j画弧，标记为A归约项目表示结束状态，用双圈表示,2）构造NFA的方法：

例：

求文法对应的NFA,SEEaA|bBAcA|dBcB|d,1.SE2.SE3.EaA4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,1）该文法的项目有：

识别活前缀的NFA,2）画出NFA,LR（0）项目集规范族的定义：

构成识别一个文法活前缀的DFA的项目集的全体构造方法有两种：

1）先构造NFA，使用第三章的子集法将NFA确定化2）直接使用闭包和状态转换函数进行计算,5、LR（0）项目集规范族的构造：

1）使用第三章的子集法将NFA确定化，得到一个识别该文法的确定的有穷自动机，其每个状态是项目集,识别活前缀的DFA,一个项目集I的闭包Closure（I）的计算：

（1）I中的任何项目都Closure（I）

（2）若ABClosure（I）,且BVN，则对任何关于B的产生式：

BrClosure（I），r为任意符号串（3）重复

（2）直到Closure（I）不再增加为止。

2）LR（0）项目集规范族的构造：

注意：

（2）的条件表示所有项目集中右边为B的状态与B的状态是等价的，因此，只要B进入Closure（I）中,则所有B的圆点在左边的项目B都应进入同一个Closure（I）中。

例：

对于文法5.7有下列项目：

1.SE2.SE3.EaA4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,若项目集I=EaA,则Closure（I）=EaA,AcA,Ad若项目集I=BcB,求Closure（I）=？

Closure（I）=BcB，BcB，Bd,状态转换函数GO（I,X）的计算：

GO（I,X）=Closure（J）I是一个项目集，X是一个文法符号其中J=任何形如AX的项目|AXIGO函数实际就是检查I中的每一个后继符号为X的项目，将这个圆点向后移动一个位置，得到项目集J，再对项目集J求闭包。

例：

对于上面的例题文法5.7有下列项目,1.SE2.SE3.EaA4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,已知I=EaA,AcA,Ad求go（I,A）和go（I,c）go（I,A）=EaAgo（I,c）=AcA,AcA,Ad已知I=BcB，BcB，Bd求go（I,B）和go（I,c）,go（I,B）=BcBgo（I,c）=EcB,BcB,Bd,1.拓广文法：

在原文法GS上增加一个产生式SS，这是为了得到唯一的接受状态SS2.设项目集规范族C只包含第一个状态SS的闭包，即C=Closure（SS）3.利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO（I,X）加入到C中，直到C中状态数不再增加C即为文法G的LR（0）项目集规范族,LR（0）项目集规范族的构造算法：

前述的例子中，是已经拓广了的文法,1.SE2.SE3.EaA4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,初始时，设置C=Closure（SE）,是一个状态,即C=SE,EaA,EbB再根据C中的每个状态的go函数，求出更多的状态，直到状态数不再增多为止,例：

设文法G为：

EaAbBAcAdBcBd求该文法的LR（0）分析表。

（0）SE

（1）EaA

（2）EbB（3）AcA（4）Ad（5）BcB（6）Bd,第步：

拓广文法，并对产生式给予序号：

第步：

写出拓广后的文法的项目集：

1.SE2.SE3.EaA4.EaA5.EaA6.EbB7.EbB8.EbB9.AcA10.AcA11.AcA12.Ad13.Ad14.BcB15.BcB16.BcB17.Bd18.Bd,第3步：

从SE开始求项目集规范族,由S0=SE知：

Closure（S0）=SE,EaA,EbB,由此初值CClosure（S0）再根据GO函数计算后继状态,由此表明显看出：

Go（状态，后继符号）后继状态,最后得到LR（0）的项目集规范族,算法描述：

PROCEDUREitemsets（G）;C:

=CLOSURE（SS）;doforC中的每个项目集I和每个文法符号XdoifGO（I,X）非空且不属于C把GO（I,X）加入C中;在I和GO（I，X）之间画标记为X的弧;while（C的元素再增加）,有效项目：

项目A1.2对活前缀=1是有效的条件是：

存在规范推导SAw12w根据定义可知，若归约项目A1对活前缀1是有效的，则应把符号串1归约为A，即把活前缀1变为A若移进项目A12对活前缀1是有效的，则知，句柄尚为形成，下一步动作应是移进一个活前缀的有效项目集就是从构造的DFA的初态出发，经读取后而能到达的那个项目集（状态）。

ie.分析栈中的活前缀X1X2Xm的有效项目集是栈顶状态Sm所代表的状态,*,若文法G=（Vt,Vn,S,），则识别G的项目集规范族的自动机为DFAM=（=VtVn，Q=G的LR（0）项目集规范族,q0=closure（SS），F=所有含归约项目的有效项目集组成的集合，=go）,LR（0）文法：

若一个文法G的拓广文法G的活前缀识别自动机中的每个状态不存在下述情况：

既含移进又含归约的项目；含有多个归约项目。

对LR（0）文法可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数构造出LR分析表,6、LR（0）分析表的构造,设有文法G，则LR（0）分析表的构造原则为：

对于AXIk，GO（Ik,X）=Ij若XVt，则置actionk,X=Sj,即把（j,a）移进栈若XVn，则置gotoIk,X=j对于AIk，则对所有的xVt和#，均置actionk,x=rj（设A是第j个产生式），即用A归约若SSIk，则置actionk,#=acc，即接受其他均置出错。

根据该原则，上述例题中得到LR（0）的项目集规范族的DFA如图，求LR（0）分析表,（0）SE

（1）EaA

（2）EbB（3）AcA（4）Ad（5）BcB（6）Bd,得到最后的LR（0）分析表,练习,给定文法：

SaS|bS|c

（1）构造的LR（0）项目集规范族，

（2）构造识别该文法所产生的活前缀的DFA（3）该文法是否是LR（0）的，若是，构造LR（0）分析表,三.求项目集规范族,四.画出DFA,每个项目集中的各个项目不冲突,则是LR（0）文法。

五.构造LR（0）分析表,非LR（0）文法,项目集规范族中I1，I2，I9中存在移进-归约冲突，不能构造LR（0）分析表,考查文法：

（0）SE

（1）EE+T

（2）ET（3）TT*F（4）TF（5）F（E）（6）Fi,只有当一个文法G是LR（0）文法，即G的每一个状态不出现冲突时，才能构造出LR（0）分析表。

由于大多数实用的程序设计语言的文法不能满足LR（0）文法的条件，因此使用向前查看一个符号的办法来处理冲突。

只对有冲突的状态向前查看一个符号，即查看follow集，以确定做哪个动作，这种分析方法为简单的LR分析法，用SLR表示。

如果每个项目都附上k个终结符号，表示要对它进行归约时，后续的k个输入符号与这k个符号相同时，才能对栈顶进行归约。

这就是LR（k）分析。

SLR分析方法,SLR

（1）冲突的解决办法,若一个项目集中同时含有移进和归约项目，出现了冲突。

解决冲突的办法是：

考察非终结符A、B的的follow集，此时要求b,follow（A）,follow（B）不相交。

当面临的输入符号a为：

当a=b，则b应移进；当afollow（A），则用产生式A进行归约；当afollow（B），则用产生式A进行归约.,I=XbAAB,（0）SE

（1）EE+T

（2）ET（3）TT*F（4）TF（5）F（F）（6）Fi,移进-归约冲突,冲突的解决方法：

在I1中，Follow（S）=#，而SE是唯一的接受项目，所以当且仅当遇到句子的结束符#号时，句子才被接受。

又因#+，因此I1中的冲突可解决。

SEEE+T,在I2中，Follow（E）=#,）,+Follow（E）*=+,）,#*，所以如果当前输入符号为#,）,+时，就使用ET进行归约；如果当前输入符号为*时，就移进；当面临其他输入符号时，出错。

ETTT*F,在I9中，Follow（E）*=+,）,#*，因此面临输入符为+，）或#时，用产生式EE+T进行归约；当面临输入符为*时，移进；其它情况则报错。

EE+TTT*F,SLR

（1）分析表的构造算法,设有文法G，则SLR

（1）分析表的构造方法为：

对于AXIk，GOTO（Ik,X）=Ij若XVt，则置actionk,X=Sj,即把（j,a）移进栈若XVn，则置gotoIk,X=j对于AIk，则对所有的x，xfollow（A），则置actionk,x=rj（设A是第j个产生式），即用A归约若SSIk，则置actionk,#=acc，即接受其他均置出错。

如果分析表的每个入口不含多重定义，则称为SLR表，文法G称为SLR

（1）文法。

例：

下述文法的SLR分析表,（0）SE

（1）EE+T

（2）ET（3）TT*F（4）TF（5）F（F）（6）Fi,SLR不能解决的问题,拓广文法G为：

（0）SS

（1）SaAd

（2）SbAc（3）Saec（4）Sbed（5）Ae,得到项目集规范族,项目集I5和I7中的冲突，不能用SLR

（1）方法解决。

Follow（A）=c，d,LR

（1）分析,LR（0）项目：

为A,a1a2ak，A是一个LR（0）项目，aiVT*。

a1a2ak称为它的向前搜索字符串。

一个项目集的闭包Closure（I）：

（1）将I中的所有项目都加入Closure（I）。

（2）若项目AB,aClosure（I），B是一个产生式，那么对于任何bFirst（a），如果B,b原来不在Closure（I）中，则把它加进去。

重复执行该过程，直到Closure（I）不再增大为止。

I是一个项目集，X是一个文法符号，则转换函数GO（I,X）定义为：

GO（I,X）=Closure（J），J=任何形如AX,a的项目|AX,aI。

构造LR

（1）项目集规范族及识别活前缀的DFA,

（1）C:

=Closure（SS,#）;

（2）重复执行（3）的动作，直到C不再增大;（3）FORC中的每个项目集I和G的每个符号XDOIFGO（I,X）非空且不属于C把GO（I,X）加入C中;在I和Go（I,X）之间画标记为X的弧线;,上面的例子的LR

（1）项目集规范族,LR

（1）分析表的构造,

（1）若项目Aa,bIk，且GO（Ik,a）=Ij，其中aVT，则置actionk,a=Sj。

即把输入符号a和状态j分别移入文法符号栈和状态栈。

（2）若项目A,aIk，其中aVT，则置actionk,a=rj，即用产生式A进行归约，j是在文法中对产生式A的编号。

（3）若项目SS,#Ik，则置actionk,#acc，表示接受。

（4）若GO（Ik,A）Ij，其中AVN，则置gotok,Aj。

表示当栈顶符号为A时，从状态k转换到状态j。

（5）凡不能用规则

（1）（4）填入分析表中的元素，均置报错标志。

上面的分析表为：

LALR

（1）分析,LALR方法是一种折衷方法，它的分析表比LR

（1）分析表要小得多，能力也弱一些，但它能应用在一些SLR

（1）不能应用的场合。

实际的编译器经常使用这种方法，大多数程序设计语言的语法结构能方便地由LALR文法表示。

在LR

（1）分析表中，若存在两个状态（项目集）除向前搜索符不同外，其它部分都是相同的，称这样的两个LR

（1）项目集是同心的。

如果把同心的LR

（1）项目集合并，心仍相同（心就是一个LR（0）项目集），超前搜索符集为各同心集超前搜索符的并集，合并同心集后go函数自动合并。

称为LALR方法。

构造LALR分析表的算法：

（1）构造LR

（1）项目集规范族，C=I0，I1，In。

（2）合并所有的同心集，得到LALR

（1）的项目集族C=J0，J1，Jm。

含有项目SS,#为初态。

（3）由C构造动作（action）表。

若Aa,bJk，且GO（Jk,a）Jj，其中aVT，则置actionk,a=Sj，若项目A,aJk，其中aVT，则置actionk,a=rj，rj的含义是按产生式A进行归约若项目SS,#Ik，则置actionk,#=acc，表示分析成功，接受。

（4）goto表的构造。

若不是同心集的项目集，转换函数的构造与LR

（1）的相同；假定Ii1,Ii2，Iin是同心集，合并后的新集为Jk，转换函数GO（Ii1,X），GO（Ii2,X），GO（Iin,X）也为同心集，将其合并后记作Ji，因此，有GO（Jk,X）=Ji，所以当X为非终结符时，GO（Jk,X）=Ji，则置gotok,X=i，表示在k状态下遇到非终结符X时，把X和i分别移到文法符号栈和状态栈。

（5）分析表中凡不能用（3）、（4）填入信息的空白均填上“出错标志”。

该文法的LR

（1）项目集规范族,例：

文法（0）SS

（1）SBB

（2）BbB（3）Ba,LR

（1）分析表为：

I3和I6，I4和I7，I8和I9分别为同心集，将同心集合并后为：

I36：

BaB,a/b/#BaB,a/b/#Bb,a/b/#I47：

Bb，a/b/#I89：

BaB，a/b/#同心集合并后仍不包含冲突，因此该文法是LALR文法。

得到LALR分析表：