LR(0)文法分析

实验名称：LR（0）文法分析一、 实验目的：输入：任意的压缩了的上下文无关文法。输出：相应的LR（0）分析表。二、实验原理：对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一种重要概念文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2Xm应当构成活前缀，把输入串的剩余部分派上之后即应成为规范句型（如果整个输入串的确构成一种句子）。因此，只要输入串的已扫描部分保持可归约成一种活前缀，那就意味着所扫描过的部分没有错误。对于一种文法G，我们可以构造一种有限自动机，它能辨认G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是对的的，栈里的文法符号（自栈底而上）始终构成活前缀。假若一种文法G的拓广文法的活前缀辨认自动机中的每个状态（项目集）不存在下述状况：（1）既含移进项目又含归约项目；（2）具有多种归约项目，则称G是一种LR（0）文法。该自动机的状态集合即为该文法的LR（0）项目集规范族。构造辨认文法活前缀DFA有3种措施：（1）根据形式定义求出活前缀的正则体现式，然后由此正则体现式构造NFA再拟定为DFA；（2）求出文法的所有项目，按一定规则构造辨认活前缀的NFA再拟定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X)构造文法G的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到辨认活前缀的DFA。符号串的前缀是指该符号串的任意首部，涉及空串。例如，对于符号串abc，其前缀有，a，ab，abc。如果输入串没有错误的话，一种规范句型的活前缀是该句型的一种前缀，但它不含句柄之后的任何符号。之因此称为活前缀，是由于在该前缀后联接尚未输入的符号串可以构成一种规范句型。活前缀与句柄的关系如下：（1）活前缀已具有句柄的所有符号，表白产生式A的右部已出目前栈顶。（2）活前缀只含句柄的一部分符号，表白A12的右部子串1已出目前栈顶，期待从输入串中看到2推出的符号。（3）活前缀不具有句柄的任何符号，此时盼望A的右部所推出的符号串。在文法G的每个产生式的右部（候选式）的任何位置上添加一种圆点，所构成的每个产生式称为LR（0）项目。如产生式A xyz有如下项目：A.xyz，Ax.yz，Axy.z，Axyz.。为刻划分析过程中的文法的每一种产生式的右部符号已有多大一部分被辨认（出目前栈顶），可以用这种标有圆点的产生式来拟定。（1）A.刻划产生式A的右部已出目前栈顶。 （2）A1.2 刻划A12的右部子串1已出目前栈顶，期待从输入串中看到2推出的符号。 （3）A. 刻划没有句柄的任何符号在栈顶，此时盼望A的右部所推出的符号串。（4）对于A的LR(0)项目只有A。设文法G=（VT，VN，S，P）是一种上下文无关文法，若存在一种规范推导SAw12w（其中A12P），则称项目A12对活前缀=1是有效的，即LR(0) 有效项目。从直观意义上讲，一种LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被辨认，LR(0)项目中的圆点可当作是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是目前输入或继续扫描的符号串。不同的LR(0)项目，反映了分析栈顶的不同状况。我们根据LR(0)项目的作用不同，将其分为四类：（1）归约项目：体现形式：Aa.此类LR(0)项目表达句柄a正好涉及在栈中，即目前栈顶的部分内容构成了所盼望的句柄，应按Aa进行归约。（2）接受项目：体现形式：a.其中是文法惟一的开始符号。此类LR(0)项目实际是特殊的归约项目，表达分析栈中内容正好为a，用a进行归约，则整个分析成功。（3）移进项目：体现形式：Aa.（bVT）此类LR(0)项目表达分析栈中是不完全涉及句柄的活前缀，为构成正好有句柄的活前级，需将b移进分析栈。（4）待约项目：体现形式：A.B （BVN）此类LR(0)项目表达分析栈中是不完全涉及句柄的活前缀，为构成正好有句柄的活前缀，应把目前输入字符串中的相应内容先归约到B。在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能辨认文法所有前缀的有限自动机。其环节是：一方面构造能辨认文法所有活前缀的非拟定的有限自动机，再将其拟定化和最小化，最后得到所需的拟定的有限自动机。由文法G的LR(0)项目构造辨认文法G的所有活前缀的非拟定有限自动机的措施：（1）规定具有文法开始符号的产生式（设A）的第一种LR(0)项目（即.A）为NFA的惟一初态。（2）令所有LR(0)项目分别相应NFA的一种状态且LR(0)项目为归约项目的相应状态为终态。（3）若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一种位置，即：若i为XX1X2Xi-1XiXn， j为 XX1X2XiXi+1Xn，则从状态i引一条标记为Xi的弧到状态j。（4）若状态i为待约项目（设XA），则从状态i引弧到所有Ar的状态。为了使“接受”状态易于辨认，我们一般将文法G进行拓广。假定文法G是一种以S为开始符号的文法，我们构造一种，它涉及了整个G，但它引进了一种不出目前G中的非终结符，并加进一种新产生式S，以S为开始符号。那么，我们称是G的拓广文法。这样，便会有一种仅含项目S的状态，这就是惟一的“接受”态。如果I是文法G的一种项目集，定义和构造I的闭包CLOSURE(I)如下：（1） I的项目都在CLOSURE(I)中。（2） 若Aa.Bb属于CLOSURE(I)，则每一形如B.g的项目也属于CLOSURE(I)。（3） 反复（2）直到CLOSURE(I)不再扩大。定义转换函数如下：GO（I，X）= CLOSURE（J）其中：I为涉及某一项目集的状态，X为一文法符号，J= AaX .b | Aa.X bI。圆点不在产生式右部最左边的项目称为核，惟一的例外是S.S，因此用GOTO（I，X）状态转换函数得到的J为转向后状态闭包项目集的核。使用闭包函数（CLOSURE）和转换函数(GO(I,X)构造文法G的LR(0)的项目集规范族，环节如下：（1） 置项目S.S为初态集的核，然后对核求闭包CLOSURE（S.S）得到初态的闭包项目集。（2） 对初态集或其她所构造的项目集应用转换函数GO(I，X)= CLOSURE(J)求出新状态J的闭包项目集。（3） 反复（2）直到不浮现新的项目集为止。计算LR（0）项目集规范族C=I0，I1 , . In 的算法伪代码如下： Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一项目集I和每一文法符号X Do if GO(I,X) 非空且不属于C Then 把 GO(I,X) 放入C中 Until C 不再增大End;一种项目集也许涉及多种项目，若移进和归约项目同步存在，则称移进-归约冲突，若归约和归约项目同步存在，则称归约-归约冲突。下面看一种具体的例子：我们但愿能根据辨认文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集（状态）中的项目的不同作用。我们说项目A1.2对活前缀1是有效的，其条件是存在规范推导。一般而言，同一项目也许对几种活前缀都是有效的（当一种项目出目前几种不同的集合中时便是这种情形）。若归约项目A1.对活前缀是有效的，则它告诉我们应把符号串归约为A，即把活前缀变成A。若移进项目A1.2对活前缀是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应是移进。但是，也许存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。并且它们告诉我们应做的事情各不相似，互相冲突。这种冲突通过向前多看几种输入符号，或许可以获得解决。对于每个活前缀，我们可以构造它的有效项目集。事实上，一种活前缀的有效项目集正是从上述的DFA的初态出发，经读出后而达到的那个项目集（状态）。换言之，在任何时候，分析栈中的活前缀X1X2Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。事实上，栈顶的项目集（状态）体现了栈里的一切有用信息历史。 前面我们已经对LR（0）文法进行了定义,下面我们来看一下LR（0）分析表是如何构造的。对于LR（0）文法，我们可以直接从它的项目集规范族C和活前缀辨认自动机的状态转换函数GO构造出LR分析表。下面是构造LR（0）分析表的算法。假定C=I0, I1,，In，令每个项目集Ik的下标k为分析器的一种状态，因此，G的LR(0)分析表具有状态0，1，n。令那个具有项目SS的Ik的下标k为初态。ACTION子表和GOTO子表可按如下措施构造：（1）若项目A.a属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”；（2）若项目A属于Ik，那么，对任何终结符a，置ACTIONk，a为“用产生式A进行规约”，简记为“rj”；其中，假定A为文法G的第j个产生式；（3）若项目SS属于Ik, 则置ACTIONk, #为“接受”，简记为“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)SE(1)EaA(2)EbB(3)AcA(4)Ad(5)BcB三、实验内容及其代码如下所示：#include#include#include#includeusing namespace std;#define OK 1#define ERROR 0#define N 50#define Y 20int vtnum,vnnum,pronum;/依次是终结符个数，非终结符个数，产生式个数 char vtN;/终结符集 char vnN;/非终结符集char oldNN=/0;/用于存储文法char oldzNN=/0;/用于存储增广文法int ACTIONNN=0;/动作表int GOTONN=0;/状态转换表typedef struct SqE int t;/状态编号 char c1;SqE;/堆栈元素typedef struct item int f;/项目前部，表达产生式编号 int l;/项目后部，表达停止点在产生式的位置item;/定义项目typedef struct link int f;/连接前部，表达所用符号的编号，非终结符编号=在vn中的下标+100 int l;/连接后部，即状态编号link;/定义状态之间的连接typedef struct cd int item_num;/状态中的项目数 int link_num;/状态的连接数 item wN;/项目集 link uN;/连接集cd;/定义状态typedef struct DFA int cd_num;/状态个数 cd sN+1;/状态集DFA;/定义规范LR(0)项目族,D.sN用作状态转换函数go_switch()的存储空间DFA D;void dfa();/求规范LR(0)项目族void closure(int);/求闭包void go_switch(int,int);/求转换int test_go_switch();void add_go_switch();/增长新状态void del_go_switch();/清空状态转换函数的存储空间void action();/构造ACTION表void go_answer();/构造GOTO表int control();/总控程序int length(int);/返回增广文法产生式右部的长度int test(char);void printf_ag();/输出ACTION表和GOTO表bool test_link(int i,int num);void main() int i,j; ifstream in(input1.txt,ios_base:in);/读文献,从文献中读入pronum,vtnum,vnnum以及产生式 inpronumvnnumvtnum; invn; invt; for(i=1;ioldi;/将产生式存入old,old1为第一种产生式 for(i=1;iS，将原文法扩大，使其变为增广文法 vtvtnum=$;/把结束符$加入终结符集 D.cd_num=0; for(i=0;i=N;i+) D.si.item_num=0; D.si.link_num=0; /初始化状态个数、连接个数、项目个数 dfa(); action(); go_answer(); printf_ag(); control();/求一种状态的闭包void closure(int i) int j,k,m,x,flag; do j=D.si.item_num;/j是本轮循环开始前的项目数 for(k=0;kD.si.item_num;k+) for(m=0;ma.Ab应找到A-. flag=0;/判断该项与否在目前状态i中,即检查(m,1)与否存在于状态i中,保证求闭包时加入的新项目和原项目集不重叠 for(x=0;xD.si.item_num;x+) if(D.si.wx.f=m&D.si.wx.l=1) flag=1; break; if(flag=0)/如果该项不在目前状态i中，将其加入状态i D.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是符号编号，状态转换函数的成果存于sNvoid go_switch(int i,int num) int j; for(j=0;jD.si.item_num;j+) if(test(oldzD.si.wj.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,错误符号返回值=200int test(char c) int i,j; for(i=0;ivtnum;i+) if(vti=c) break; if(ivtnum) return i;else for(j=0;jvnnum;j+) if(vnj=c) break; if(jvtnum) return (100+j);else return 200; /检查状态转换函数的成果int test_go_switch() int i,j,k,flag;if(D.sN.item_num=0)/判断状态转换的成果与否为空，即目前状态可否接受该字符 return 0;else for(i=0;iD.cd_num;i+)/选定一状态，对sN中的每个项目进行循环，如果存在一种项目在目前状态中未找到，即flag=0，立即跳至下一状态 flag=1;/判断状态转换函数的成果与否已经完全涉及于某一既有状态中，例如go_switch(状态4,符号a)仍然存在于状态4中，go_switch(状态4,符号c)已经存在于状态5中 for(j=0;jD.sN.item_num;j+)/如果在目前状态i中找不到sN的目前项目j,就跳至下一状态 for(k=0;k=D.si.item_num) flag=0; break; if(flag=1) return 1000+i; return 1;/状态转换函数的成果未被任何既有状态完全涉及，完全满足建立新状态的条件 /把状态转换函数的成果加入DFA，即当建立新状态的条件符合时，建立新的状态sD.cd_numvoid add_go_switch() int i; for(i=0;iS加入初状态，并求其闭包 do i=D.cd_num;/本轮循环开始时状态数 for(j=0;jD.cd_num;j+)/对每个状态进行循环 for(k=0;k=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();/清空 for(k=0;k=1000) D.sj.uD.sj.link_num.f=k; D.sj.uD.sj.link_num.l=test_go_switch()-1000; D.sj.link_num+; del_go_switch(); while(i!=D.cd_num);/当一轮没有新的状态产生时，结束/构造ACTION表void action() int i,j,k; for(i=0;iD.cd_num;i+)/对每个状态循环 for(j=0;jD.si.link_num;j+)/S，对每个状态的每个连接循环，如果找到目前状态用终结符建立的连接，则ACTION目前状态号相应终结符编号=连接另一端状态号 if(D.si.uj.f100) ACTIONiD.si.uj.f=D.si.uj.l; for(j=0;jc. 则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;jS. 所在状态，则ACTION目前状态$=300，即acc if(D.si.wj.f=0&D.si.wj.l=2) ACTIONivtnum=300; break; /构造GOTO表void go_answer() int i,j; for(i=0;iD.cd_num;i+) for(j=0;j=100) GOTOiD.si.uj.f-100=D.si.uj.l; /总控程序int control() int i,j,num; char cY=/0;/初始化带分析字符串的存储空间 SqE stackN; int p1=0,p2=0;/p1是待分析字符串指针,p2是栈顶下一位元素的指针,stack0是栈底 vtnum+;/把$加入终结符集 for(i=0;ic; printf(/n栈中状态 栈中符号 输入串 分析动作/n);while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION栈顶状态号目前字符编号 for(i=0,j=0;stacki.c1!=/0;i+) printf(%d,stacki.t); j+; for(i=0;i14-j;i+) printf( );/输出栈中状态for(i=0,j=0;stacki.c1!=/0;i+) printf(%c,stacki.c1); j+; for(i=0;i14-j;i+) printf( );/输出栈中符号 for(i=p1,j=0;ci!=/0;i+) printf(%c,ci); j+; for(i=0;i0&ACTIONstackp2-1.ttest(cp1)100&ACTIONstackp2-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压栈，注意-100 stackp2.c1=oldznum0;/把oldznum0压栈 p2+; stackp2.c1=/0;/封顶 else if(ACTIONstackp2-1.ttest(cp1)=0)/Error printf(Error/n/nError,您输入的句型和文法不符!/n); return ERROR; printf(01 $%c $ acc/n,oldz10); printf(/nSucceed,您输入句型和文法匹配!/n); return OK;/返回增广文法产生式右部的长度int length(int i) int j; for(j=1;oldzij!=/0;j+) return (j-1);/j-1是产生式右部字符数/输出两张表void printf_ag() int i,j; printf(ACTION表为:/n); printf( ); for(i=0;i=vtnum;i+) printf(%c ,vti); printf(/n); for(i=0;iD.cd_num;i+) if(i10) printf(%d ,i); else printf(%d ,i); for(j=0;j=vtnum;j+) if(ACTIONij0) if(ACTIONij0) printf(s%d ,ACTIONij); else printf(s%d ,ACTIONij); else if(ACTIONij100&ACTIONij200) if(ACTIONij-100)0) printf(r%d ,ACTIONij-100); else printf(r%d ,ACTIONij-100); else if(ACTIONij=300) printf(acc ); else printf( ); printf(/n); printf(/nGOTO表为:/n); printf( ); for(i=0;ivnnum;i+) printf(%c ,vni); printf(/n); for(i=0;iD.cd_num;i+) if(i10) printf(%d ,i); else printf(%d ,i); for(j=0;jvnnum;j+) if(GOTOij10) printf(%d ,GOTOij); else printf(%d ,GOTOij); printf(/n); /检查在目前状态下与否已存在用目前字符建立的连接bool test_link(int i,int num) int j; for(j=0;jD.si.link_num;j+) if(D.si.uj.f=num) return true; return false;