LR文法分析报告

标准有用 试验名称：LR〔0〕文法分析试验目的：输入：任意的压缩了的上下文无关文法。LR〔0〕分析表。二、试验原理：LRLR这种句柄之后不含任何符号的前缀称为活前缀。LR〔自栈底而上〕XX…X12 m〔假设整个输。因此，只要输入串的已扫描局部保持可归约成一个活前缀，那就意味着所扫描过的局部没有错误。GLRLRLR在分析的过程中，假设分析的句子是正确的，栈里的文法符号〔自栈底而上〕始终构成活前缀。假设一个文法G的拓广文法G的活前缀识别自动机中的每个状态〔工程集〕不存在下述状况〔1〕既含移进工程又含归约工程〔2〕含有多个归约工程，则GLR〔0〕LR〔0〕工程集标准族。DFA3再确定为DFA；求出文法的全部工程，按肯定规章构造识别活前缀的NFA再确定化为DFA；〔CLOSURE〕和转向函数(GO(I,X))构造文法G’的LR(0)的工程集标准族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。εabc，其前缀有ε，a，ab，abc。假设输入串没有错误的话，一个标准句型的活前缀是在该前缀后联接尚未输入的符号串可以构成一个标准句型。活前缀与句柄的关系如下：A→β的右部β已消灭在栈顶。活前缀只含句柄的一局部符号，说明A→ββ的右部子串β已消灭在1 2 1栈顶，期盼从输入串中看到β推出的符号。2A→β的右部所推出的符号串。在文法G的每个产生式的右部〔候选式〕的任何位置上添加一个圆点，所构LR〔0〕AxyzA.xyz，Ax.yz，Axy.z，Axyz.。为刻划分析过程中的文法的每一个产生式的右部〔消灭在栈顶定。A→β.刻划产生式A→β的右部β已消灭在栈顶。A→β.β刻划A→βββ1 2 1 2 1看到β推出的符号。2A→.β刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串。对于A→ε的LR(0)工程只有A→．。T N rmAw1错误！未找到引用源。2w〔其中A错误！未找到引用源。错误！未找到引用源。1错误！2PA错误！未找到引用源。错误！未找到引用源。1错误！未找到引用源。2对活前缀错误！未找到引用源。=错误！未找到引用源。错误！未找到引用源。1是有效的，即LR(0)从直观意义上讲，一个LR(0)工程指明白在分析过程中的某一步我们看到产生式的多大局部被识别，LR(0)工程中的圆点可看成是分析栈栈顶与输入串的分LR(0)LR(0)工程的作用不同，将其分为四类：：A→a.A→a承受工程：LR(0)工程实际是特别的归约工程，表a，S→a移进工程：表现形式：A→a.b〔bV〕T这类LR(0)工程表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。待约工程：表现形式：A→α.Bβ 〔BV〕N这类LR(0)工程表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。LR(0)工程动身，来构造动机。由文法GLR(0)工程构造识别文法G方法：规定含有文法开头符号的产生式〔设S→A〕的第一个LR(0)工程〔即S→.A〕NFALR(0)NFALR(0)工程为归约工程的对应状态为终态。GLR(0)工程的圆点只相差一个位置，即：X→XX…X·X

…Xi12 i-1 i

12

i+1 nX的弧到状态j。ii〔X→α·AβiεA为了使“承受”状态易于识别，我们通常将文法G进展拓广。GSG，它包含了整GGSS→S，以S→SG为开头符号。那么，我们称GG这样，便会有一个仅含工程S→S的状态，这就是惟一的“承受”态。假设I是文法G＇的一个工程集，定义和构造I的闭包CLOSURE(I)如下：I的工程都在CLOSURE(I)中。A→.B属于CLOSURE(I)，则每一形如B→.的工程也属于CLOSURE(I)。重复〔2〕直到CLOSURE(I)不再扩大。定义转换函数如下：GO〔I，X〕=CLOSURE〔J〕其中：I为包含某一工程集的状态，X为一文法符号，J={A→X|A→.X∈I}。圆点不在产生式右部最左边的工程称为核，惟一的例外是S′→.S，因此用GOTO〔I，X〕状态转换函数得到的J为转向后状态闭包工程集的核。集标准族，步骤如下：得到初态的闭包工程集。求出状态J的闭包工程集。重复〔2〕直到不消灭的工程集为止。计算LR〔0〕工程集标准族C={I，I,...In}的算法伪代码如下：0 1Procedureitemsets(G’);Begin C:={CLOSURE({S’.S})}RepeatForC中每一工程集I和每一文法符号XDo if GO(I,X)非空且不属于CThen把GO(I,X)放入C中UntilC不再增大End;一个工程集可能包含多种工程，假设移进和归约工程同时存在，则称移进-归约冲突，假设归约和归约工程同时存在，则称归约-归约冲突。下面看一个具体的例子：DFALRDFA〔状态〕中的工程的不同作用。我们说工程A→ββ1 2

对活前缀αβ1

是有效的，其条件是存在标准推导SA1

。一般而言，同一工程可能对几个活前缀都是有效的〔当一个2工程消灭在几个不同的集合中时便是这种情形。假设归约工程A→β

.对活前缀1是有效的，则它告知我们应把符号串1

A，即把活前缀1

变成αA。假设移进工程A→β.β对活前缀 是有效的，则它告知我们，句柄尚未形成，1 2 1因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在这种冲突通过向前多看几个输入符号，或许能够获得解决。γγ〔状态。换言之，在任何时候，分析栈中的活前缀XX…X的有效工程集正是栈顶12 m状态S所代表的那个集合。这是LR分析理论的一条根本定理。实际上，栈顶的m工程集〔状态〕表达了栈里的一切有用信息——历史。是如何构造的。LR〔0〕文法，我们可以直接从它的工程集标准族CGOLRLR〔0〕分析表的算法。假定C={IIIn}，令每个工程集Ik为分析器的一个状态，因0 1 k此，G”的LR(0)分析表含有状态0，1，…，n。令那个含有工程S”→．S的Ik标k为初态。ACTION子表和GOTO子表可按如下方法构造：〔1A→α.aβ属于I且GO(Ia)=IaACTION[k,k k jja“sjk产生式A→αrA→α为文法G”的第j个产j生式；假设工程IACTION[k,k假设GO(IA)=IA为非终结符，则置GOTO[k,A]=j；k j分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。ACTION和GOTO重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR〔0〕文法，LR(0)文法是无二义的。例如，文法G〔E〕的拓广文法如下：(0)S”→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB三、试验内容及其代码如下所示：#include<iostream>#include<stdio.h>#include<fstream>#include<malloc.h>usingnamespacestd;#defineOK1#defineERROR0#defineN50#defineY20intvtnum,vnnum,pronum;//依次是终结符个数，非终结符个数，产生式个数charvt[N];//终结符集charvn[N];//非终结符集charold[N][N]={”/0”};//用于存储文法charoldz[N][N]={”/0”};//用于存储增广文法intACTION[N][N]={0};//动作表intGOTO[N][N]={0};//状态转换表typedefstructSqE{intt;//状态编号charc1;}SqE;//堆栈元素typedefstructitem{intf;//工程前部，表示产生式编号intl;//工程后部，表示停顿点在产生式的位置}item;//定义工程typedefstructlink{intf;//连接前部，表示所用符号的编号，非终结符编号=在vn[]中的下标+100intl;//连接后部，即状态编号}link;//定义状态之间的连接typedefstructcd{intitem_num;//状态中的工程数intlink_num;//状态的连接数itemw[N];//工程集linku[N];//连接集}cd;//定义状态typedefstructDFA{intcd_num;//状态个数cds[N+1];//状态集,D.s[N]go_switch的存储空间DFAD;工程族voidclosure(int);//求闭包voidgo_switch(int,int);//求转换inttest_go_switch;voidadd_go_switch;//增加状态voiddel_go_switch;//清空状态转换函数的存储空间action;//ACTIONGOTOintcontrol;//总控程序intlength(int);//返回增广文法产生式右部的长度inttest(char);voidprintf_ag;//ACTIONGOTObooltest_link(inti,intnum);voidmain{inti,j;ifstreamin(“input1.txt“,ios_base::in);//in>>pronum>>vnnum>>vtnum;in>>vn;in>>vt;for(i=1;i<=pronum;i++)old[][],old[1]为第一个产生式for(i=1;i<=pronum;i++)for(j=0;old[i][j]!=”/0”;j++)old[][oldz[][]oldz[0][0]=”P”;P->S，将原文法扩大，使其变为增广文法vt[vtnum]=”$”;//把完毕符”$”参加终结符集D.cd_num=0;for(i=0;i<=N;i++){D.s[i].item_num=0;D.s[i].link_num=0;}//初始化状态个数、连接个数、工程个数dfa;action;go_answer;printf_ag;control;}//求一个状态的闭包voidclosure(inti){intj,k,m,x,flag;do{j=D.s[i].item_num;//jfor(k=0;k<D.s[i].item_num;k++){for(m=0;m<=pronum;m++){iA->a.AbA->...{i(m,1)是ifor(x=0;x<D.s[i].item_num;x++){if(D.s[i].w[x].f==m&&D.s[i].w[x].l==1){flag=1; break;}}if(flag==0)//ii{D.s[i].w[D.s[i].item_num].f=m;D.s[i].w[D.s[i].item_num].l=1;D.s[i].item_num++;}}}}}while(j!=D.s[i].item_num);//i}voidgo_switch(inti,intnum){ intj;for(j=0;j<D.s[i].item_num;j++){if(test(oldz[D.s[i].w[j].f][D.s[i].w[j].l])==num){D.s[N].w[D.s[N].item_num].f=D.s[i].w[j].f;D.s[N].w[D.s[N].item_num].l=D.s[i].w[j].l+1;D.s[N].item_num++;closure(N);}}}//返回终结符和非终结符的标号,推断符号的类型,0<=终结符返回值<100,100<=<200,错误符号返回值=200inttest(charc){ inti,j;for(i=0;i<vtnum;i++){ if(vt[i]==c)break;}if(i<vtnum)returni;else{for(j=0;j<vnnum;j++){if(vn[j]==c)break;}if(j<vtnum) return(100+j);else return200;}}inttest_go_switch{ inti,j,k,flag;接收该字符return0;else{ s[N]中的每个工程进展循环，假设存在一个工程在当前状态中未找到，即flag=0，马上跳至下一状态{flag=1;//推断状态转换函数的结果是否已经完全包含于某一现有状c)5for(j=0;j<D.s[N].item_num;j++)//假设在当前状态is[N]的当前工程j,就跳至下一状态{for(k=0;k<D.s[i].item_num;k++){if(D.s[i].w[k].f==D.s[N].w[j].f&&D.s[i].w[k].l==D.s[N].w[j].l)break;}if(k>=D.s[i].item_num){ flag=0; break;}}if(flag==1) return1000+i;}return1;//状态转换函数的结果未被任何现有状态完全包含，完全满足建立状态的条件}}s[D.cd_num]voidadd_go_switch{inti;for(i=0;i<D.s[N].item_num;i++){D.s[D.cd_num].w[D.s[D.cd_num].item_num].f=D.s[N].w[i].f;D.s[D.cd_num].w[D.s[D.cd_num].item_num].l=D.s[N].w[i].l;D.s[D.cd_num].item_num++;}D.cd_num++;}voiddel_go_switch{D.s[N].item_num=0;}voiddfa{inti,j,k;D.s[0].w[0].f=0;D.s[0].w[0].l=1;D.cd_num++;D.s[0].item_num++;初状态，并求其闭包do{ i=D.cd_num;//本轮循环开头时状态数for(j=0;j<D.cd_num;j++)//对每个状态进展循环{for(k=0;k<vnnum;k++)//对当前状态，每个非终结符{if(!test_link(j,k+100))//检验当前状态用当前非终结符构造的连接是否已经存在，假设存在，则跳至下一非终结符，这样可以防止do_whiles[0]{if(test_go_switch==1)//假设符合建立状态的条件{和状态的连接

}else{

add_go_switch;D.s[j].u[D.s[j].link_num].f=k+100;//建立当前状态D.s[j].u[D.s[j].link_num].l=D.cd_num-1;D.s[j].link_num++;if(test_go_switch>=1000)//假设状态转换的结果包{D.s[j].u[D.s[j].link_num].f=k+100;//建立当前状态和该现有状态的连接D.s[j].u[D.s[j].link_num].l=test_go_switch-1000;D.s[j].link_num++;}}del_go_switch;//清空}}for(k=0;k<vtnum;k++)//对当前状态，每个终结符{if(!test_link(j,k)){go_switch(j,k);if(test_go_switch==1){add_go_switch;D.s[j].u[D.s[j].link_num].f=k;D.s[j].u[D.s[j].link_num].l=D.cd_num-1;D.s[j].link_num++;}else{if(test_go_switch>=1000){D.s[j].u[D.s[j].link_num].f=k;D.s[j].u[D.s[j].link_num].l=test_go_switch-1000;D.s[j].link_num++;}}del_go_switch;}}}}while(i!=D.cd_num);//当一轮没有的状态产生时，完毕}voidaction{ inti,j,k;for(i=0;i<D.cd_num;i++)//对每个状态循环{for(j=0;j<D.s[i].link_num;j++)//S，对每个状态的每个连接循环，假设找到当前状态用终结符建立的连接，则ACTION[当前状态号][对应终结符编号]=连接另一端状态号{if(D.s[i].u[j].f<100){ACTION[i][D.s[i].u[j].f]=D.s[i].u[j].l;}}找到一个终结工程，例如A->c.则ACTION[当前状态][全部vt和$]=产生式A->c{if(oldz[D.s[i].w[j].f][D.s[i].w[j].l]==”/0”){for(k=0;k<=vtnum;k++){ACTION[i][k]=D.s[i].w[j].f+100;}}}P->S.ACTION[当前状态][$]=300acc{if(D.s[i].w[j].f==0&&D.s[i].w[j].l==2){ACTION[i][vtnum]=300; break;}}}}GOTOvoidgo_answer{ inti,j;for(i=0;i<D.cd_num;i++){GOTO[当前状态号][对应非终结符编号]=连接另一端状态号{if(D.s[i].u[j].f>=100){GOTO[i][D.s[i].u[j].f-100]=D.s[i].u[j].l;}}}}//总控程序intcontrol{inti,j,num;charc[Y]={”/0”};//初始化带分析字符串的存储空间SqEstack[N];intp1=0,p2=0;//p1是待分析字符串指针,p2是栈顶下一位元素的指针,stack[0]是栈底把”$”参加终结符集for(i=0;i<N;i++)初始化符号栈stack[p2].t=0;把(0,$)压栈p2++;//指针更$结尾):“);cin>>c;printf(“/n栈中状态 栈中符号 输入串 分析动作/n“);while(ACTION[stack[p2-1].t][test(c[p1])]!=300)//ACTION[栈顶状态号][当前字符编号]{for(i=0,j=0;stack[i].c1!=”/0”;i++){printf(“%d“,stack[i].t);j++;}for(i=0;i<14-j;i++)printf(““);//输出栈中状态for(i=0,j=0;stack[i].c1!=”/0”;i++){printf(“%c“,stack[i].c1);j++;}for(i=0;i<14-j;i++)printf(““);//输出栈中符号for(i=p1,j=0;c[i]!=”/0”;i++){printf(“%c“,c[i]);j++;}for(i=0;i<14-j;i++)printf(““);//输出剩余字符串if(ACTION[stack[p2-1].t][test(c[p1])]>0&&ACTION[stack[p2-1].t][test(c[p1])]<100)//S{printf(“S%d/n“,ACTION[stack[p2-1].t][test(c[p1])]);//作将状态压栈stack[p2].c1=c[p1];//将当前字符压栈p2++;p1++;//更两个指针}elseif(ACTION[stack[p2-1].t][test(c[p1])]>100&&ACTION[stack[p2-1].t][test(c[p1])]<200)//r,归约{num=ACTION[stack[p2-1].t][test(c[p1])]-100;//num是归约所用的产生式编号printf(“r%d/n“,num);p2=p2-length(num);//length(num)个元素T压栈，留意-100stack[p2].c1=oldz[num][0];//oldz[num][0]压栈p2++;stack[p2].c1=”/0”;//封顶}else{if(ACTION[stack[p2-1].t][test(c[p1])]==0)//Error{您输入的句型和文法不符!/n“);returnERROR;}}}printf(“01 $%c$ acc/n“,oldz[1