编译原理:语法分析实验(LR分析法)
本文共 11223 字，大约阅读时间需要 37 分钟。
语法分析实验
一、实验目的
根据LR分析法的原理，对指定文法构造识别活前缀的DFA,做出相应的LR分析表，并编程实现相应的语法分析程序。或根据预测分析法的原理，对指定文法构造预测分析表，并编程实现相应的语法分析程序。
二、实验原理
1.所谓LR(k)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据当前已移进和规约出的全部文法符号，并至多再向前查看k个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所采取的分析动作。
2.LR分析器的逻辑结构
三、实验仪器设备和环境
开发环境：Visual c++ 6.0
开发语言：C语言 操作系统:win10 硬件环境: 16GB双通道内存条+250G SAMSUNG 970 EVO PLUS固态硬盘。四、主要内容和步骤
设已给文法G[L]: 1.L->E,L 2.L->E 3.E->a 4.E->b
文法G[L]的LR分析表如下，其中，用数0,1…表示分析器的状态；用字母S表示“移进动作”；用Rj表示按文法的第j个产生式进行规约；用acc表示“接受”动作，用ERROR表示“出错”动作。
五、软件设计与编程
代码如下：(由很多if-else，所以可读性可能差了点，功能倒是实现了)
//头文件typedef struct node{ char data; struct node *next;}Stack;typedef struct//封装LR分析表{ char action1[10];//a char action2[10];//b char action3[10];//, char action4[10];//# char goto1[10];//L char goto2[10];//E}LR;typedef struct{ char g[10];}G;//初始化void StackInitiate(Stack **head){ (*head)=(Stack *)malloc(sizeof(Stack)); (*head)->next = NULL;}//判空int StackNotEmpty(Stack *head){ if (head->next!=NULL) return 1; else return 0;}//入栈int StackPush(Stack *head, char x){ Stack *p; p = (Stack *)malloc(sizeof(Stack)); p->data = x; p->next = head->next; head->next = p; return 1;}//出栈int StackPop(Stack *head,char *x){ Stack *p; p = head->next; if(p == NULL) { printf("堆栈已空无法出栈!"); return 0; } else { head->next = p->next; *x=(p->data); free(p); return 1; }}//取栈顶数据元素int StackGet(Stack *head,char *x){ Stack *p; p = head; if (p->next == NULL) { printf("堆栈已空无法出栈!"); return 0; } else *x = p->next->data; return 1;}//撤销动态申请空间void Destroy(Stack *head){ Stack *p,*p1; p = head; while (p != NULL) { p1 = p; p = p->next; free(p1); }}void print(Stack *head)//打印当前栈中的所有元素{ Stack *p=head->next;// printf("当前栈中的内容为:"); while(p!=NULL) { printf("%c ",p->data); p=p->next; }}//源文件#include #include #include #include"stack.h"void testlr(LR array[7],char temp[20],G gl[4]){ char x1; int i=0; int stop=0;Stack *stack1;//状态栈Stack *stack2;//符号栈StackInitiate(&stack1);StackInitiate(&stack2);StackPush(stack1,'0');StackPush(stack2,'#');while(stop!=1||temp[i]!='\0'){ char state;//状态char character;//符号x1=temp[i];if(x1=='a') { printf("\n当前扫描的字符是a\n"); printf("当前状态栈:"); print(stack1); printf("当前符号栈:"); print(stack2); StackGet(stack1,&state); int state1=state-'0';//状态栈中是字符，这里转换为整型的值 if(!strcmp(array[state1].action1,""))//为空，出错 { printf("出错!"); } else if(!strcmp(array[state1].action1,"acc"))//acc-分析结束 { printf("\n***分析成功***\n"); stop=1; // exit(-1); } else if(array[state1].action1[0]=='s')//如果是移进动作 { //int number=array[state1].action1[1]-'0';//看下一个状态号 char number=array[state1].action1[1]; StackPush(stack1,number);//状态进栈 StackPush(stack2,x1); //符号进栈 i++; } else if(array[state1].action1[0]=='r')//规约动作 { int number=array[state1].action1[1]-'0';//看用第几个文法规约 int length=strlen(gl[number-1].g);//获取文法长度 if(length==3) { char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 StackPop(stack1,&st1);//先出状态栈 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } }else if(length==5) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 char ch3=gl[number-1].g[3];//右 char ch4=gl[number-1].g[4];//右 StackPop(stack1,&st1);//先出状态栈 StackPop(stack1,&st1);//出 StackPop(stack1,&st1);//出 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } } } } else if(x1=='b') { printf("\n当前扫描的字符是b\n"); printf("当前状态栈:"); print(stack1); printf("当前符号栈:"); print(stack2); StackGet(stack1,&state); int state1=state-'0';//状态栈中是字符，这里转换为整型的值 if(!strcmp(array[state1].action2,""))//为空，出错 { printf("出错!"); } else if(!strcmp(array[state1].action2,"acc"))//acc-分析结束 { printf("分析成功"); stop=1; } else if(array[state1].action2[0]=='s')//如果是移进动作 { char number=array[state1].action2[1]; StackPush(stack1,number);//状态进栈 StackPush(stack2,x1); //符号进栈 i++; } else if(array[state1].action2[0]=='r')//规约动作 { int number=array[state1].action2[1]-'0';//看用第几个文法规约 int length=strlen(gl[number-1].g);//获取文法长度 if(length==3) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 StackPop(stack1,&st1);//先出状态栈 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } }else if(length==5) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 char ch3=gl[number-1].g[3];//右 char ch4=gl[number-1].g[4];//右 StackPop(stack1,&st1);//先出状态栈 StackPop(stack1,&st1);//出 StackPop(stack1,&st1);//出 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } } } }else if(x1==',') { printf("\n当前扫描的字符是 ,\n"); printf("当前状态栈:"); print(stack1); printf("当前符号栈:"); print(stack2); StackGet(stack1,&state); int state1=state-'0';//状态栈中是字符，这里转换为整型的值 // printf("**state1=%d**",state1); // printf("%s\n",array[state1].action1); if(!strcmp(array[state1].action3,""))//为空，出错 { printf("出错!"); } else if(!strcmp(array[state1].action3,"acc"))//acc-分析结束 { printf("分析成功"); stop=1; // exit(-1); } else if(array[state1].action3[0]=='s')//如果是移进动作 { printf(" 进入S "); //int number=array[state1].action1[1]-'0';//看下一个状态号 char number=array[state1].action3[1]; // printf("%c",number); StackPush(stack1,number);//状态进栈 StackPush(stack2,x1); //符号进栈 // print(stack1); // print(stack2); i++; } else if(array[state1].action3[0]=='r')//规约动作 { printf("进入R"); int number=array[state1].action3[1]-'0';//看用第几个文法规约 // printf("\nnumber=%d\n",number); int length=strlen(gl[number-1].g);//获取文法长度 // printf("length==%d ",length); if(length==3) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 StackPop(stack1,&st1);//先出状态栈 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } }else if(length==5) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 char ch3=gl[number-1].g[3];//右 char ch4=gl[number-1].g[4];//右 StackPop(stack1,&st1);//先出状态栈 StackPop(stack1,&st1);//出 StackPop(stack1,&st1);//出 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } } else{ printf("什么都没干！"); } } }else if(x1=='#') { printf("\n当前扫描的字符是#\n"); printf("当前状态栈:"); print(stack1); printf("当前符号栈:"); print(stack2); StackGet(stack1,&state); int state1=state-'0';//状态栈中是字符，这里转换为整型的值 if(!strcmp(array[state1].action4,""))//为空，出错 { printf("出错!"); } else if(!strcmp(array[state1].action4,"acc"))//acc-分析结束 { printf("\n***分析成功***\n"); stop=1; exit(-1);//通知循环 } else if(array[state1].action4[0]=='s')//如果是移进动作 { char number=array[state1].action4[1]; StackPush(stack1,number);//状态进栈 StackPush(stack2,x1); //符号进栈 print(stack1); print(stack2); i++; } else if(array[state1].action4[0]=='r')//规约动作 { printf("进入R "); int number=array[state1].action4[1]-'0';//看用第几个文法规约 int length=strlen(gl[number-1].g);//获取文法长度 // printf(" number=%d ",number); // printf("length=%d gl[number-1].g[0]=%c",length,gl[number-1].g[0]); if(length==3) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 StackPop(stack1,&st1);//先出状态栈 StackGet(stack1,&st1); int number1=st1-'0';//用于goto StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } }else if(length==5) { int flag; char st1; char ch1=gl[number-1].g[0];//左 char ch2=gl[number-1].g[2];//右 char ch3=gl[number-1].g[3];//右 char ch4=gl[number-1].g[4];//右 StackPop(stack1,&st1);//先出状态栈 StackPop(stack1,&st1);//出 StackPop(stack1,&st1);//出 StackGet(stack1,&st1); int number1=st1-'0';//用于goto // printf("number1=%d",number1); StackPop(stack2,&ch1);//出符号栈 StackPop(stack2,&ch1);//出符号栈 StackPop(stack2,&ch1);//出符号栈 StackPush(stack2,gl[number-1].g[0]);//规约的左部进栈 if(gl[number-1].g[0]=='E') { StackPush(stack1,array[number1].goto2[0]); } else if(gl[number-1].g[0]=='L') { StackPush(stack1,array[number1].goto1[0]); } } } }}}int main(){ /*Stack *mystack; StackInitiate(&mystack); char *x; for(int i=0;i<10;i++) { StackPush(mystack,"a22"); } printf("\n"); x=StackGet(mystack); printf("栈顶:%s \n",x);while(StackNotEmpty(mystack)){x=StackPop(mystack);printf("%s ",x);}*/ //分析表 LR array[7]={ { "s3","s4","","","1","2"},{ "","","","acc","",""},{ "","","s5","r2","",""}, { "","","r3","r3","",""},{ "","","r4","r4","",""},{ "s3","s4","","","6","2"},{ "","","","r1","",""}}; //文法 G gl[4]={ { "L-E,L"},{ "L-E"},{ "E-a"},{ "E-b"}};//用-代替->,你也可以试着改下，不过 //改成->的话，你上面的代码就要改 char temp[20]={ "a,b,a#"}; printf("输入的符号串为:%s\n",temp); testlr(array,temp,gl); return 0；} 运行结果如下：
七、问题与建议
1.用双栈实现的话，自己的思路要非常清晰，否则你绝对会卡住，不知道到底执行到哪一步。
2.建议用链式栈不用顺序栈，咱们这个实验数据量小，不用担心存储问题，链式栈插入结点和删除结点的时间复杂度都是O(1)，在时间上的开销小。转载地址：http://hjzzi.baihongyu.com/
你可能感兴趣的文章
大智若愚也是领导力
查看>>
android如何编译MTK的模拟器
查看>>
android如何添加AP中要使用的第三方JAR文件
查看>>
利用sudo命令为Ubuntu分配管理权限
查看>>
Ubuntu下几个重要apt-get命令用法与加速UBUNTU
查看>>
Ubuntu中网页各种插件安装命令
查看>>
使用tar命令备份Ubuntu系统
查看>>
ubuntu flash 文字乱码解决方案
查看>>
在ubuntu中运行exe文件
查看>>
ubuntu安装命令
查看>>
和上司沟通必备8个黄金句
查看>>
联系查看两张卡的未接电话记录
查看>>
Python 3 之多线程研究
查看>>
APP第三方登录实现步骤
查看>>
KVO & KVC 比较 - KVC
查看>>
iOS-tableView联动
查看>>
iOS--Masonry解决 tableViewCell 重用时约束冲突
查看>>
git 与 svn 的主要区别!
查看>>
iOS-截屏,从相册选择图片,制作磨砂效果图片
查看>>
iOS-截取字符串中两个指定字符串中间的字符串
查看>>