实验二算数表达式的扩充一、实验目的掌握LR分析表的设计方法和语义加工程序的扩充。
二、实验内容算术表达式文法扩充如下：E→E+E|E-E|E*E|E/E|(E)|i试根据该文法添加单词“-”、“/”的内部定义以及重新设计LR分析表，并修改语义加工程程序，最后验证修改的结果。
三、L R分析表的构造四、编译程序的修改与扩充定义符号减和除的编号#define sub 35//减#define div 37//除重新构造LR分析表action1static int action1[14][9]={{3,-1,-1,2,-1,-1,1,-1,-1,}, {-1,4,6,-1,-1,ACC,-1,5,7}, {3,-1,-1,2,-1,-1,8,-1,-1},{-1,104,104,-1,104,104,-1,104,104},{3,-1,-1,2,-1,-1,9,-1,-1},{3,-1,-1,2,-1,-1,10,-1,-1},{3,-1,-1,2,-1,-1,11,-1,-1},{3,-1,-1,2,-1,-1,12,-1,-1},{-1,4,6,-1,13,-1,-1,5,7},{-1,101,6,-1,101,101,-1,101,7},{-1,105,6,-1,105,105,-1,105,7},{-1,102,102,-1,102,102,-1,102,102},{-1,106,106,-1,106,106,-1,106,106},{-1,103,103,-1,103,103,-1,103,103}};在扫描程序中添加-，/情况case '-':buf[count].sy1=sub;count++;break;case '/':buf[count].sy1=div;count++;break;change1(int chan)//action1的符号查找排序（i,+,*,(,),#,E,-，/）加入：case sub:return 7;//-case div:return 8;// /lrparse1语义分析中状态数增加if((lr1<14)&&(lr1>=0))//在0~13个状态之中规约增加数if((lr1>=100)&&(lr1<107))case 105:E.pos=newtemp();//E->E-Egen("-",sstack[ssp-2],sstack[ssp],E.pos+100);ssp=ssp-2;sstack[ssp].sy1=tempsy;sstack[ssp].pos=E.pos;sp1=sp1-3;break;case 106:E.pos=newtemp();//E->E/Egen("/",sstack[ssp-2],sstack[ssp],E.pos+100);ssp=ssp-2;sstack[ssp].sy1=tempsy;sstack[ssp].pos=E.pos;sp1=sp1-3;break;测试字符是否为表达式中的值(不包括":")，test(int value)增加：case sub:case div:五、编译程序的验证测试用例：while (a>b) dobeginif m>=n then a:=a-1elsewhile k=h do x:=x/2;m:=n+x*(m+y)end#~测试结果：六、实验体会经过一个星期的编译原理课程设计，本人在李艳老师的指导下，顺利完成该课程设计。
通过该课程设计，收获颇多。
1.对实验原理有更深的理解通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。
通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。
2.对该理论在实践中的应用有深刻的理解通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。
3.激发了学习的积极性通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。
把死板的课本知识变得生动有趣，激发了学习的积极性。
把学过的计算机编译原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。
以前对与计算机操作系统的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机编译原理的认识更加深刻。
课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除。
在这次课程设计中，我就是按照实验指导的思想来完成。
加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。
四、理解了该知识点以及学科之间的融合渗透本次课程设计程序部分是用c语言编写的，把《计算机操作系统》，《编译原理》，《算法分析与设计》《c语言》四门学科联系起来，把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。
使我加深了对《计算机操作系统》，《编译原理》，《算法分析与设计》《c 语言》四门课程的认识。
七、源码#include "stdio.h"#include "string.h"#define ACC -2/**************************************/#define sy_if 0#define sy_then 1#define sy_else 2#define sy_while 3#define sy_begin 4#define sy_do 5#define sy_end 6#define a 7#define semicolon 8#define e 9#define jinghao 10#define S 11#define L 12#define tempsy 15#define EA 18#define E0 19#define plus 34#define sub 35//减#define times 36#define div 37//除#define becomes 38#define op_and 39#define op_or 40#define op_not 41#define rop 42#define lparent 48#define rparent 49#define ident 56#define intconst 57/********************************************/char ch='\0';//可用于存放读出的一个字符int count=0;//词法分析结果缓冲区计数器static char spelling[10]={""};//存放是别的字static char line[81]={""};//一行字符缓冲区char *pline;//line的指针static char ntab1[100][10];//变量类型名表struct ntab{int tc;//真int fc;//假}ntab2[200];//用于存放布尔表达式的值int label=0;//指向ntab2的指针struct rwords{char sp[10];int sy;};//匹配表结构体struct rwords reswords[10]={{"if",sy_if},{"do",sy_do},{"else",sy_else},{"while",sy_while},{"then",sy_then},{"begin",sy_begin},{"end",sy_end},{"and",op_and},{"or",op_or},{"not",op_not}};//初始化匹配表，用于关键字的匹配struct aa{int sy1;//存放变量的类型名int pos;//存放该变量在自己表中的位置}buf[1000],//词法分析结果缓冲区n,//存放二元式当前字符n1,//表达式当前的字符E,//非终结符sstack[100],//算术表达式和布尔表达式的符号栈ibuf[100],//算术表达式和布尔表达式的缓冲区stack[1000];//语法分析的符号栈struct aa oth;//四元式中没有填写的空白位置struct fourexp//四元式结构体{char op[10];struct aa arg1;struct aa arg2;int result;}fexp[200];int ssp=0;//指向 sstack的指针struct aa *pbuf=buf;//词法分析结果缓冲区的指针int nlength=0;//词法分析中记录单词的长度int lnum=0;//行数计数源程序int tt1=0;//变量类型名表的指针FILE *cfile;//源程序文件/********************************************************/int newt=0;//临时变量计数器int nxq=100;//总是指向下一个要形成的四元式每次执行gen()int lr;//用于存放action1中的当前状态int lr1;//用于存放action2，3中的当前状态int sp=0;//LR分析表栈顶指针int stack1[100];//状态栈1int sp1=0;//状态栈的指针int num=0;//算术表达式或布尔表达式的指针struct ll{int nxq1;//指向下一条四元式的指针int tc1;//真值链int fc1;//假值链}labelmark[10];//记录嵌套中每层布尔表达式e的首地址int labeltemp[10];//记录每层else之前四元式的地址int pointmark=-1,pointtemp=-1;//labelmark的指针，labelmark的指针int sign=0;// sign=1 赋值语句，sign=2 while语句，sign=3 if语句/********************程序语句的LR分析表********************/ static int action[19][13]={{2,-1,-1,3,4,-1,-1,5,-1,-1,10,1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1},{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8},{-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1},{-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1},{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1},{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1},{-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1},{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16},{-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1},{-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1},{2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1},{-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1}};/********************算术表达式的LR分析表********************/ static int action1[14][9]={{3,-1,-1,2,-1,-1,1,-1,-1,},{-1,4,6,-1,-1,ACC,-1,5,7},{3,-1,-1,2,-1,-1,8,-1,-1},{-1,104,104,-1,104,104,-1,104,104},{3,-1,-1,2,-1,-1,9,-1,-1},{3,-1,-1,2,-1,-1,10,-1,-1},{3,-1,-1,2,-1,-1,11,-1,-1},{3,-1,-1,2,-1,-1,12,-1,-1},{-1,4,6,-1,13,-1,-1,5,7},{-1,101,6,-1,101,101,-1,101,7},{-1,105,6,-1,105,105,-1,105,7},{-1,102,102,-1,102,102,-1,102,102},{-1,106,106,-1,106,106,-1,106,106},{-1,103,103,-1,103,103,-1,103,103}};/********************布尔表达式的LR分析表*********************/ static int action2[16][11]={{1,-1,4,-1,5,-1,-1,-1,13,7,8},{-1,2,-1,101,-1,101,101,101,-1,-1,-1},{3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,102,-1,102,102,102,-1,-1,-1},{1,-1,4,-1,5,-1,-1,-1,11,7,8},{1,-1,4,-1,5,-1,-1,-1,6,7,8},{-1,-1,-1,104,-1,9,10,104,-1,-1,-1},{1,-1,4,-1,5,-1,-1,-1,14,7,8},{1,-1,4,-1,5,-1,-1,-1,15,7,8},{105,-1,105,-1,105,-1,-1,-1,-1,-1,-1},{107,-1,107,-1,107,-1,-1,-1,-1,-1,-1},{-1,-1,-1,12,-1,9,10,-1,-1,-1,-1},{-1,-1,-1,103,-1,103,103,103,-1,-1,-1},{-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1},{-1,-1,-1,106,-1,9,10,106,-1,-1,-1},{-1,-1,-1,108,-1,9,10,108,-1,-1,-1}};/********************从文件读一行到缓冲区**********************/ readline()//读一行{char ch1;pline=line;ch1=fgetc(cfile);//从文件中取一个while((ch1!='\n')&&(ch1!=EOF))//把字符缓冲区填满{*pline=ch1;pline++;ch1=fgetc(cfile);}*pline='\0';//结尾终结符pline=line;//字符缓冲区指针重新回到字符缓冲区的第一个字符位置}/**********************从缓冲区读取一个字符*********************/ readch()//读一个{if(ch=='\0')//读到尾姐再来一行，行数加一{readline();lnum++;}ch=*pline;//从行缓冲区读取一个字符pline++;//字符缓冲区指针后移}/***********************标识符和关键字的识别********************/find(char spel[])//在变量表中查询{int ss1=0;// 是否查到的变量的标志（1为查到，0为没查到）int ii=0;//记录查到变量表第几条while((ss1==0)&&(ii<nlength))//只要没有查到，或没有超过变量表表长，就继续查{if(!strcmp(spel,ntab1[ii]))ss1=1;ii++;}if(ss1==1)//查到了return ii-1;//返回在表量表的地址（-1的原因是上面的ii++最后多加了一次） else return -1;//没查到，返回-1}identifier()//关键字或变量或常量查询{int iii=0,j,k;//iii关键字表中的指针位置int ss=0;//关键字是否匹配到的标识k=0;//存放的识别的字的指针（spelling[k]）do//将取出的字符放入识别的字 spelling数组中{spelling[k]=ch;k++;readch();//取一个字符}while(((ch>='a')&&(ch<='z'))||((ch>='0')&&(ch<='9')));//数字或小写字母 pline--;//取字时多加的一个，-1可使 *pline指向字符缓冲区行尾spelling[k]='\0';while((ss==0)&&(iii<10)){if(!strcmp(spelling,reswords[iii].sp))//在关键字表中查询ss=1;//查到标志置1iii++;}/*关键字匹配*/if(ss==1)//在关键字表中查到{buf[count].sy1=reswords[iii-1].sy;//关键字名字放入结果缓冲区}else//没查到{buf[count].sy1=ident;//将变量名置入结果缓冲区j=find(spelling);//变量表查询，查到就把变量在变量表的地址赋给jif(j==-1)//没查到就新建一个变量{buf[count].pos=tt1;//将其在变量表中的地址放入结果缓冲区中的地址栏strcpy(ntab1[tt1],spelling);//将识别的变量名放入变量名表tt1++;nlength++;//变量名表长加一}else buf[count].pos=j;//查到后，将变量名表中变量的地址放入结果缓冲区该变量的地址栏中}count++;//指向结果缓冲区下一位置for(k=0;k<10;k++) spelling[k]=' ';//以识别的临时字符清空}/**********************数字识别*************************/number(){int ivalue=0;int digit;do{digit=ch-'0';//取出的字符转换为数字ivalue=ivalue*10+digit;//数字地址从10后开始记录readch();//取一个字符}while((ch>='0')&&(ch<='9'));buf[count].sy1=intconst;//常量名存入结果缓冲区buf[count].pos=ivalue;//该常量地址存入结果缓冲区count++;// 向结果缓冲区下一位置pline--;//指向行缓冲区尾字符}/***********************扫描主程序************************/scan(){int i;while(ch!='~')//~为程序结束符{switch(ch){case ' ':break;case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':case 'g':case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':case 'v':case 'w':case 'x':case 'y':case 'z':identifier();break;//关键词或变量查询case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':number();break;//数字查询case '<':readch();//6种关系运算符buf[count].pos=（<=为0，<为1，>=为2，>为3，<>为4，=为5）if(ch=='=')buf[count].pos=0;else{if(ch=='>') buf[count].pos=4;else{buf[count].pos=1;pline--;}}buf[count].sy1=rop;//关系运算符名存入结果 count++;//结果指针后移break;case '>':readch();if(ch=='=')buf[count].pos=2;else{buf[count].pos=3;pline--;}buf[count].sy1=rop;count++;break;case '(':buf[count].sy1=lparent;count++;break;case ')':buf[count].sy1=rparent;count++;break;case '#':buf[count].sy1=jinghao;count++;break;case '+':buf[count].sy1=plus;count++;break;case '-':buf[count].sy1=sub;count++;break;case '*':buf[count].sy1=times;count++;break;case '/':buf[count].sy1=div;count++;break;case ':':readch();if(ch=='=')buf[count].sy1=becomes;count++;break;case '=':buf[count].sy1=rop;buf[count].pos=5;count++;break;case ';':buf[count].sy1=semicolon;count++;break;}readch();// 取下一个字符}buf[count].sy1=-1;//结束了}/*******************************************************/readnu()//读取当前结果缓冲区的二元式存入struct aa n中，pbuf指向结果缓冲区中下一位置的指针{if(pbuf->sy1>=0){n.sy1=pbuf->sy1;//存放当前二元式字符名称n.pos=pbuf->pos;//存放当前二元式字符位置pbuf++;}}/***********************中间变量的生成*********************/newtemp()//返回目前临时变量数{newt++;//临时变量计数器+1return newt;}/***********************生成四元式**************************/gen(char op1[],struct aa arg11,struct aa arg22,int result1)//op1算符，arg11操作数1，arg22操作数2， result1结果{strcpy(fexp[nxq].op,op1);//为四元式传入算符fexp[nxq].arg1.sy1=arg11.sy1;//为四元式操作数1传入名字fexp[nxq].arg1.pos=arg11.pos;// 为四元式操作数1传入地址fexp[nxq].arg2.sy1=arg22.sy1;//为四元式操作数2传入名字fexp[nxq].arg2.pos=arg22.pos;// 为四元式操作数2传入地址fexp[nxq].result=result1;// 为四元式结果传入结果nxq++;//每次指向下一个要生成的四元式地址return nxq-1;//当前四元式地址}/***********************布尔表达式的匹配**********************/merg(int p1,int p2)// 将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）{int p;if(p2==0) return p1;else{p=p2;while(fexp[p].result!=0)p=fexp[p].result;fexp[p].result=p1;return p2;}}backpatch(int p,int t)//用四元式序号t回填以p为首的链，将链中每个四元式的Result域改写为t的值。