LR分析程序

LR分析程序构造LR分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。1)实验原理LR分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表:分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器结构：其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：action[i，a]=Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。2)、实验过程(1):数据结构:动作表（ACTION）和状态转换（GOTO）表用二维数组表示.(2)).使用文法E-E+TE-TT-T*FT-FF-(E)F-i3)程序思路（1）建立LR分析表（2）控制部分：从键盘输入一个表达式符号串；利用LR分析算法进行表达式处理：根据LR分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。（3）主函数：从键盘输入一个表达式符号串进行识别；参考程序#includestdio.h#includestring.hchar*action[12][6]={S5#,NULL,NULL,S4#,NULL,NULL,/*ACTION表*/NULL,S6#,NULL,NULL,NULL,acc,NULL,r2#,S7#,NULL,r2#,r2#,NULL,r4#,r4#,NULL,r4#,r4#,S5#,NULL,NULL,S4#,NULL,NULL,NULL,r6#,r6#,NULL,r6#,r6#,S5#,NULL,NULL,S4#,NULL,NULL,S5#,NULL,NULL,S4#,NULL,NULL,NULL,S6#,NULL,NULL,S11#,NULL,NULL,r1#,S7#,NULL,r1#,r1#,NULL,r3#,r3#,NULL,r3#,r3#,NULL,r5#,r5#,NULL,r5#,r5#};intgoto1[12][3]={1,2,3,/*GOTO表*/0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0};charvt[6]={'i','+','*','(',')','#'};/*存放终结符*/charvn[3]={'E','T','F'};/*存放非终结符*/char*LR[7]={S-E#,E-E+T#,E-T#,T-T*F#,T-F#,F-(E)#,F-i#};/*存放产生式*/inta[10];charb[10],c[10],c1;inttop,m,n;intjudge(){intg,h,i,j,k,l,p,y,z,count;charx,copy[10],copy1[10];length;top=0;a[0]=0;y=a[0];b[0]='#';count=0;z=0;printf(步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n);do{y=z;/*y,z指向状态栈栈顶*/g=top;k=0;x=c[top];count++;printf(%d\t,count);m=0;while(m=top){/*输出状态栈*/printf(%d,a[m]);m=m+1;}printf(\t\t);n=0;while(n=top){/*输出符号栈*/printf(%c,b[n]);n=n+1;}printf(\t\t);while(g=length){/*输出输入串*/printf(%c,c[g]);g=g+1;}printf(\t\t);j=0;while(j6&&x!=vt[j])j++;if(j=6){printf(error\n);return0;}if(action[y][j]==NULL){printf(error\n);return0;}strcpy(copy,action[y][j]);if(copy[0]=='a')return1;if(copy[0]=='S'){/*处理移进*/z=copy[1]-'0';if(copy[2]!='#')z=z*10+copy[2]-'0';top=top+1;a[top]=z;b[top]=x;i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}printf(\n);}if(copy[0]=='r'){/*处理归约*/i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}h=copy[1]-'0';strcpy(copy1,LR[h]);while(copy1[0]!=vn[k])k++;l=strlen(LR[h])-4;top=top-l+1;y=a[top-1];p=goto1[y][k];a[top]=p;b[top]=copy1[0];z=p;printf(\t);printf(%d\n,p);}}while(1);}voidmain(){inti;length=0;printf(请输入表达式\n);do{scanf(%c,&c1);c[length]=c1;length=length+1;}while(c1!='#');i=judge();if(i==1)printf(acc\n);}