实验二、语法分析实验 实现 LR 分析法（P147,例 4.6） 或预测分析法（P121,例 4.3） 1． 实验目的 实现 LR 分析法（P147,例 4.6） （1）掌握 LR(1)分析法的基本原理； （2）掌握 LR(1)分析表的构造方法； （3）掌握 LR(1)驱动程序的构造方法。 2． 实验原理 （1）严格地进行最左归约（识别句柄并归约它）。 （2）将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。 （3）分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息； （4）由一个总控程序来控制整个识别过程。 3． 主要仪器设备 操作系统：WindowsXP 开发语言：Visual C++6.0 4． 主要内容和步骤 对下列文法，用 LR(1)分析法对任意输入的符号串进行分析： （1）L->E，L（2）L->E（3）E->a（4）E->b （1）将初始状态 S0 和输入串的左边界(#) 分别进分析栈； （2）根据状态栈栈顶和当前输入符号查动作表进行如下工作; 移进:若动作表中对应“移进”，那么当前输入符号进符号栈，并据状态转换表查得输入 符号所对应的新的状态进状态栈，继续扫描，即下一个输入符号变成当前得输入符号； 归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的符号串长度 为 n，则符号栈栈顶的 n 个符号为句柄，所以符号栈栈顶 n 个符号出栈，同时，状态栈顶的 n 个元素也出栈，归约后的文法符号(非终结符)进符号栈，并据状态转换表查归约后的文法 符号所对应的新状态进状态栈； 接受:若动作表中对应“acc”，则分析成功； 出错:若动作表中对应空白，则报告错误信息。 （3）重复以上(2)的工作直到接受或出错为止。 5． 软件编程与设计 #include #include char *action[7][4]={"S3#","S4#",NULL,NULL, NULL,NULL,NULL,"acc", /*ACTION 表*/ 

NULL,NULL,"S5#","r2#", NULL,NULL,"r3#","r3#", NULL,NULL,"r4#","r4#", "S3#","S4#",NULL,NULL, NULL,NULL,NULL,"r1#"}; /*GOTO 表*/ int goto1[7][2]={ 1,2, 0,0, 0,0, 0,0, 0,0, 6,2, 0,0 }; /*存放非终结符*/ char vt[4]={'a','b',',','#'}; char vn[2]={'L','E'}; /*存放终结符*/ char *LR[4]={"L->E,L#","E->a#","L->E#","E->b#"};/*存放产生式*/ int a[7]; char b[7],c[7],c1; int top1,top2,top3,top,m,n; void main(){ int g,h,i,j,k,l,p,y,z,count; char x,copy[7],copy1[7]; top1=0;top2=0;top3=0;top=0; a[0]=0;y=a[0];b[0]='#'; count=0;z=0; printf("----------请输入表达式----------\n"); /*输出状态栈、输出符号栈、输出输入串*/ do{ scanf("%c",&c1); c[top3]=c1; top3=top3+1; }while(c1!='#'); printf("步骤\t 状态栈\t\t 符号栈\t\t 输入串\t\tACTION\tGOTO\n"); do{ y=z;m=0;n=0; g=top;j=0;k=0; x=c[top]; count++; printf("%d\t",count); while(m<=top1){ printf("%d",a[m]); /*y,z 指向状态栈栈顶*/ /*输出状态栈*/ 

m=m+1; } printf("\t\t"); while(n<=top2){ printf("%c",b[n]); n=n+1; printf("\t\t"); while(g<=top3){ printf("%c",c[g]); g=g+1; } } printf("\t\t"); while(x!=vt[j]&&j<=2) j++; if(j==2&&x!=vt[j]){ printf("error\n"); return; } if(action[y][j]==NULL){ printf("error\n"); return; } else strcpy(copy,action[y][j]); if(copy[0]=='S'){ z=copy[1]-'0'; top1=top1+1; top2=top2+1; a[top1]=z; b[top2]=x; top=top+1; 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; top1=top1-l+1; top2=top2-l+1; y=a[top1-1]; p=goto1[y][k]; a[top1]=p; b[top2]=copy1[0]; z=p; printf("\t"); printf("%d\n",p); } } while(action[y][j]!="acc"); printf("acc\n"); getchar(); } 6． 程序测试结果 7． 问题与建议 在对实验分析的时候，也遇到很多的问题，刚开始根本想不到用程序怎么实现这么繁 杂的 LR（1）文法，后来看了程序才知道，才转过来弯，通过对这个程序的分析与揣摩，让 自己对这方面文法的实现有了一定的头绪，对以后的的一些文法的程序实现会有很大的帮 助，通过练习我也感到仅留在理论是远远不行的，通过一定方式实现才有实用价值。