LR(0)文法分析

1、实验名称：LR(0)文法分析一、实验目的：输入：任意的压缩了的上下文无关文法。输出：相应的LR(0)分析表。二、实验原理：对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念一一文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号(自栈底而上)X1X2Xm应该构成活前缀，把输入用的剩余部分配上之后即应成为规范句型(如果整个输入用确实构成一个句子)。因此，只要输入用的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G,我们可以构造一个有限自动机，它能识别G的所有活

2、前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号(自栈底而上)始终构成活前缀。假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：(1)既含移进项目又含归约项目；(2)含有多个归约项目，则称G是一个LR(0)文法。该自动机的状态集合即为该文法的LR(0)项目集规范族。构造识别文法活前缀DFA有3种方法：(1)根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA;(2)求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA;(3)使用闭包函数(

3、CLOSURE)和转向函数(GO(I,X)构造文法G的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号用的前缀是指该符号用的任意首部，包括空用一例如，对于符号用abc,其前缀有e,a,ab,abc。如果输入用没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号用可以构成一个规范句型。活前缀与句柄的关系如下：(1)活前缀已含有句柄的全部符号，表明产生式A-B的右部B已出现在栈顶。(2)活前缀只含句柄的一部分符号，表明A-B1B2的右部子用B1已出现在栈顶，期待从输入用中看到

4、B2推出的符号。(3)活前缀不含有句柄的任何符号，此时期望A-B的右部所推出的符号用。在文法G的每个产生式的右部(候选式)的任何位置上添加一个圆点，所构成的每个产生式称为LR(0)项目。如产生式Axyz有如下项目：A.xyz,Ax.yz,Axy.z,Axyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)，可以用这种标有圆点的产生式来确(1) A-B.刻划产生式A-B的右部B已出现在栈顶。(2) A-B1.B2刻划A-B102的右部子用B1已出现在栈顶，期待从输入用中看到B2推出的符号。(3) A-.B刻划没有句柄的任何符号在栈顶，此时期望A-B的右部所推出

5、的符号用。(4)对于A-e的LR(0)项目只有A一.。设文法G=(Vt,Vn,S,P)是一个上下文无关文法，若存在一个规范推导SAw12w(其中A12P),则称项目A1?2对活前缀=1是有rmrm效的，即LR(0)有效项目。从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入用的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号用。不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类：(1)归约项目：表现形式：A-a.这类LR(0)项目表示句柄a恰好

6、包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按A-a进行归约。(2)接受项目：表现形式：S-a.其中S是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a,用S-a进行归约，则整个分析成功。(3)移进项目：表现形式：Aa.b(bVt)这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。(4)待约项目：表现形式：A-a.BB(BVn)这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出LR(0)项目的定义和分类之后，我们从这些L

7、R(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法：(1)规定含有文法开始符号的产生式(设S-A)的第一个LR(0)项目(即S-.A)为NFA的惟一初态。(2)令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。(3)若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置，即：若i为X-X1X2Xi-1XiXn,j为X-X1X2XiXi+1

8、Xn,则从状态i引一条标记为Xi的弧到状态j0(4)若状态i为待约项目(设X-aAB),则从状态i弓屋弧到所有A一-r的状态。为了使“接受”状态易于识别，我们通常将文法G进行拓广。假定文法G是一个以S为开始符号的文法，我们构造一个G,它包含了整个G,但它引进了一个不出现在G中的非终结符S,并加进一个新产生式S-S,以S一SG为开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目S-S的状态，这就是惟一的“接受”态。如果I是文法G/的一个项目集，定义和构造I的闭包CLOSURE(I)如下：(1) I的项目者B在CLOSURE(I)中。(2) 若A-.B属于CLOSURE(I),则每一

9、形如Bf的项目也属于CLOSURE(I)。(3) 重复(2)直至iJCLOSURE(I)不再扩大。定义转换函数如下：GO(I,X)=CLOSURE(J)其中：I为包含某一项目集的状态，X为一文法符号，J=A-X.|A-.XI。圆点不在产生式右部最左边的项目称为核，惟一的例外是S'一.S,因此用GOTO(I,X)状态转换函数得到的J为转向后状态闭包项目集的核。使用闭包函数(CLOSURE)和转换函数(GO(I,X)构造文法G的LR(0)的项目集规范族，步骤如下：(1) 置项目S'一.S为初态集的核，然后对核求闭包CLOSURE(S'一.S)得到初态的闭包项目集。(2) 对

10、初态集或其他所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)求出新状态J的闭包项目集。(3) 重复(2)直到不出现新的项目集为止。计算LR(0)项目集规范族C=I0,Ii,.In的算法伪代码如下：Procedureitemsets(G');BeginC:=CLOSURE(S'.S)RepeatFor C中每一项目集I和每一文法符号XDo if GO(I,X)非空且不属于CThen把GO(I,X)放入C中UntilC不再增大End;一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约冲突，若归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的

11、例子：我们希望能根据识别文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集(状态)中的项目的不同作用。我们说项目A-B1邛2对活前缀aB1是有效的，具条件是存在规范推导SA12o一般而言，同一项目可能对几个活前缀都是有效的(当一个项目出现在几个不同的集合中时便是这种情形)。若归约项目A-B1.对活前缀1是有效的，则它告诉我们应把符号用1归约为A,即把活前缀1变成aA。若移进项目A-01.02对活前缀1是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲

12、突。这种冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀丫的有效项目集正是从上述的DFA的初态出发，经读出丫后而到达的那个项目集(状态)。换言之，在任何时候，分析栈中的活前缀X1X2Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈顶的项目集(状态)体现了栈里的一切有用信息一一历史。前面我们已经对LR(0)文法进彳T了定义，下面我们来看一下LR(0)分析表是如何构造的。对于LR(0)文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR(0

13、)分析表的算法。假定C=I0,I1，In,令每个项目集Ik的下标k为分析器的一个状态，因此，G'的LR(0)分析表含有状态0,1,，n。令那个含有项目S'一.S的Ik的下标k为初态。ACTION子表和GOTO子表可按如下方法构造：(1)若项目A-a.aB属于Ik且GO(Ik,a)=Ij,a为终结符,则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“s”；(2)若项目A-a.属于Ik,那么，对任何终结符a,置ACTIONk,a为“用产生式A-a进行规约”，简记为“；其中，假定A-a为文法G'的第j个产生式；(3)若项目S'-S.属于Ik,则置ACTION

14、k,#为“接受”，简记为“acc”；(4)若GO(Ik,A)=Ij,A为非终结符,则置GOTOk,A=j;(5)分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个人口不含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR(0)文法，LR(0)文法是无二义的。例如，文法G(E)的拓广文法如下：(0)S'一E(1)E-aA(2)E一bBA一cAA一d(5)B一cB三、实验内容及其代码如下所示:#include<iostream>#include<stdio.h&

15、gt;#include<fstream>#include<malloc.h>usingnamespacestd;# defineOK1# defineERROR0# defineN50# defineY20intvtnum,vnnum,pronum;/依次是终结符个数，非终结符个数，产生式个数charvtN;终结符集charvnN;/非终结符集charoldNN=70'/用于存储文法charoldzNN='/0'/用于存储增广文法intACTIONNN=0;/动作表intGOTONN=0;/状态转换表typedefstructSqEintt;/状

16、态编号charc1;SqE;/堆栈元素typedefstructitemintf;/项目前部，表示产生式编号intl;/项目后部，表示停顿点在产生式的位置item;/定义项目typedefstructlinkintf；/连接前部，表小所用符号的编号，非终结符编号=在vn口中的下标+100intl;/连接后部，即状态编号link;/定义状态之间的连接typedefstructcdintitem_num;状态中的项目数intlink_num;/状态的连接数itemwN;/项目集linkuN;/连接集cd;/定义状态typedefstructDFAintcd_num;/状态个数cdsN+1;/状态集

17、DFA;/定义规范LR(0)项目族,D.sN用作状态转换函数go_switch()的存储空间DFAD;voiddfa();求规范LR(0)项目族voidclosure(int);/求闭包voidgo_switch(int,int);/求转换inttest_go_switch();voidadd_go_switch();增力口新状态voiddel_go_switch();/清空状态转换函数的存储空间voidaction。;/构造ACTION表voidgo_answer();/昭造GOTO表intcontrol。，总控程序intlength(int);/返回增广文法产生式右部的长度inttest(

18、char);voidprintf_ag();输出ACTION表和GOTO表booltest_link(inti,intnum);voidmain()inti,j;ifstreamin("input1.txt",ios_base:in);/读文件，从文件中读入pronum,vtnum,vnnum以及产生式in>>pronum>>vnnum>>vtnum;in>>vn;in>>vt;for(i=1;i<=pronum;i+)in>>oldi;/将产生式存入01d,old1为第一个产生式for(i=1;

19、i<=pronum;i+)for(j=0;oldij!='/0'j+)oldz皿=oldij;/将产生式从01d加录入oldz叩o1dz00='P'01dz01=o1d10;/加入P->S,将原文法扩充，使其变为增广文法vtvtnum='$'/把结束符'$'加入终结符集D.cd_num=0;for(i=0;i<=N;i+)D.si.item_num=0;D.si.1ink_num=0;初始化状态个数、连接个数、项目个数dfa();action();go_answer();printf_ag();control。；

20、/求一个状态的闭包voidc1osure(inti)intj,k,m,x,f1ag;doj=D.si.item_num;/j是本轮循环开始前的项目数for(k=0;k<D.si.item_num;k+)for(m=0;m<=pronum;m+)if(oldzm0=01dzD.si.wk.fD.si.wk.l)/对当前状态i中的每个项目，查询每个产生式，例如：A->a.Ab应找到A->flag=0;/判断该项是否在当前状态i中，即检查(m,1)是否存在于状态i中保证求闭包时加入的新项目和原项目集不重合for(x=0;x<D.si.item_num;x+).if(D.

21、si.wx.f=m&&D.si.wx.l=1)flag=1;break;if(flag=0)如果该项不在当前状态i中，将其加入状态iD.si.wD.si.item_num.f=m;D.si.wD.si.item_num.l=1;D.si.item_num+;.while(j!=D.si.item_num);/当一轮没有新的项目加入i时，结束循环/状态转换函数，i是状态编号，num是符号编号，状态转换函数的结果存于sNvoidgo_switch(inti,intnum)intj；for(j=0;j<D.si.item_num;j+).if(test(oldzD.si.wj.

22、fD.si.wj.l)=num)D.sN.wD.sN.item_num.f=D.si.wj.f;D.sN.wD.sN.item_num.l=D.si.wj.l+1;D.sN.item_num+;closure(N);/返回终结符和非终结符的标号，判断符号的类型，0<二终结符返回值<100,100<=非终结符返回值<200，错误符号返回值二200inttest(charc)inti,j;for(i=0;i<vtnum;i+)if(vti二二c)break;if(i<vtnum)returni;elsefor(j=0;j<vnnum;j+)if(vnj=c

23、)break;if(jvvtnum)return(100+j);elsereturn200;/检验状态转换函数的结果inttest_go_switch()inti,j,k,flag;if(D.sN.item_num=0)判断状态转换的结果是否为空，即当前状态可否接return0;elsefor(i=0;i<D.cd_num;i+)选定一状态，对sN中的每个项目进行循环，如果存在一个项目在当前状态中未找到，即flag=0,立即跳至下一状态flag=1;/判断状态转换函数的结果是否已经完全包含于某一现有状态中，例如go_switch(状态4,符号a)依然存在于状态4中，go_switch(状

24、态4,符号c)已经存在于状态5for(j=0;j<D.sN.item_num;j+)/如果在当前状态i中找不到sN的当前项目j,就跳至下一状态for(k=0;k<D.si.item_num;k+)if(D.si.wk.f=D.sN.wj.f&&D.si.wk.l=D.sN.wj.l)break;if(k>=D.si.item_num)flag=0;break;if(flag=1)return1000+i;return1;/状态转换函数的结果未被任何现有状态完全包含，完全满足建立新状态的条件/把状态转换函数的结果加入DFA,即当建立新状态的条件符合时，建立新的状

25、态sD.cd_numvoidadd_go_switch()inti;for(i=0;i<D.sN.item_num;i+).D.sD.cd_num.wD.sD.cd_num.item_num.f=D.sN.wi.f;D.sD.cd_num.wD.sD.cd_num.item_num.l=D.sN.wi.l;D.sD.cd_num.item_num+;D.cd_num+;./清空状态转换函数的存储空间voiddel_go_switch()一一D.sN.item_num=0;./构造规范LR(0)项目族voiddfa()inti,j,k;D.s0.w0.f=0;D.s0.w0.l=1;D.c

26、d_num+;D.s0.item_num+;closure(0);/f巴P->S加入初状态，并求其闭包doi=D.cd_num;/本轮循环开始时状态数for(j=0;j<D.cd_num;j+)/对每个状态进行循环for(k=0;k<vnnum;k+)/对当前状态，每个非终结符if(!test_link(j,k+100)/检验当前状态用当前非终结符构造的连接是否已经存在，若存在，则跳至下一非终结符，这样可以防止do_while()二次执行时，将连接集重新加入当前状态，比如s0go_switch(j,k+100);/对当前状态，当前符号调用状态转换if(test_go_swit

27、ch()=1)如果符合建立新状态的条件一一add_go_switch();D.sj.uD.sj.link_num.f=k+100;/建立当前状态和新状态的连接D.sj.uD.sj.link_num.l=D.cd_num-1;D.sj.link_num+;.elseif(test_go_switch()>=1000)/如果状态转换的结果包含于某一现有状态一一D.sj.uD.sj.link_num.f=k+100;/建立当前状态和该现有状态的连接D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.sj.link_num+;.del_go_switch(

28、);/清空一一for(k=0;k<vtnum;k+)对当前状态，每个终结符if(!test_link(j,k)go_switch(j,k);if(test_go_switch()=1)一一add_go_switch();D.sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=D.cd_num-1;D.sj.link_num+;.elseif(test_go_switch()>=1000)一一D.sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.sj.link_n

29、um+;.del_go_switch()；.while(i!=D.cd_num);/当一轮没有新的状态产生时，结束/构造ACTION表voidaction()inti,j,k;for(i=0;i<D.cd_num;i+)/对每个状态循环.for(j=0;j<D.si.link_num;j+)/S,对每个状态的每个连接循环，如果找到当前状态用终结符建立的注接，则ACTION当前状态号北对应终结符编号产连接另一端状态号if(D.si.uj.f<100)ACTIONiD.si.uj.f=D.si.uj.l;for(j=0;j<D.si.item_num;j+)/r,对每个状态

30、的每个项目循环，如果找到一个终结项目，例如A->c.则ACTION当前状态北所有vt和$=产生式A->c的编if(oldzD.si.wj.fD.si.wj.l='/0')for(k=0;k<=vtnum;k+)ACTIONik=D.si.wj.f+100;for(j=0;j<D.si.item_num;j+)/acc,对每个状态的每个项目循环，如果找到P->S.所在状态，则ACTION当前状态$=300,即accif(D.si.wj.f=0&&D.si.wj.l=2)ACTIONivtnum=300;break;/构造GOTO表vo

31、idgo_answer()inti,j;for(i=0;i<D.cd_num;i+).for(j=0;j<D.si.link_num;j+)/对每个状态的每个连接循环，如果找到当前状态用非终结符建立的连叁，则GOTO当前状态号北对应非终结符编号二连接另一端状态号if(D.si.uj.f>=100)GOTOiD.si.uj.f-100=D.si.uj.l;/总控程序intcontrol。inti,j,num;charcY='/0'/初始化带分析字符串的存储空间SqEstackN;intp1=0,p2=0;/p1是待分析字符串指针，p2是栈顶下一位元素的指针，st

32、ack0是栈底vtnum+;/6EJ'$'加入终结符集for(i=0;i<N;i+)stacki.c1='/0'/初始化符号栈stackp2.t=0;stackp2.c1='$'/把(0,$)压栈p2+;/指针更新printf("/n请输入要分析的字符串(以$结尾):")；cin>>c;printf("/n栈中状态栈中符号输入用分析动作/n");while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION栈顶状态号当前字符编号for(i=0,j=0;stack

33、i.c1!='/0'i+)printf("%d",stacki.t);j+;for(i=0;i<14-j;i+)printf("");/输出栈中状态for(i=0,j=0;stacki.c1!='/0'i+)printf("%c",stacki.c1);j+;for(i=0;i<14-j;i+)printf("");/输出栈中符号for(i=p1,j=0;ci!=70'i+)printf("%c",ci);j+;for(i=0;i<14-

34、j;i+)printf("");/输出剩余字符串if(ACTIONstackp2-1.ttest(cp1)>0&&ACTIONstackp2-1.ttest(cp1)<100)/Sprintf("S%d/n”,ACTIONstackp2-1.ttest(cp1);/输出分析动作stackp2.t=ACTIONstackp2-1.ttest(cp1);/将状态压栈stackp2.c1=cp1;将当前与符压栈p2+;p1+;/更新两个指针elseif(ACTIONstackp2-1.ttest(cp1)>100&&AC

35、TIONstackp2-1.ttest(cp1)<200)/r,num=ACTIONstackp2-1.ttest(cp1)-100;/num是归约所用的产生式编号printf("r%d/n",num);p2=p2-length(num);/弹出length(num)个元素stackp2.t=GOTOstackp2-1.ttest(oldznum0)-100;/若T是弹出后的栈顶元素中的状态号，把GOTOToldznum0压栈，注意-100stackp2.c1=oldznum0;/把oldznum0压栈p2+;stackp2.c1=70'封顶elseif(ACTIONstackp2-1.ttest(cp1)=0)/Errorprintf("Error/n/nError,您输入的句型和文法不符！/n");returnERROR;printf("01$%c$acc/n”,oldz10);printf("/nSucceed,您输入句型和文法匹配!/n");returnOK;/返回增广文法产生式右部的长度intlength(inti)intj;for(j=1;oldzij!='