编译原理-实验一

实验一 编译程序的分析与验证一、实验目的了解编译程序中LR分析表的作用以及语义加工程序的功能二、实验内容（1） 验证下述程序的正确性while (a=n then a:=a+1 else if ji then i=i+j else while k=h do x:=x+2; m:=n+m+x+y+n*m+x*yend#三、编译程序理解输入文件名，取一个字符，程序扫描，词法分析结果打印，变量名表打印，语句分析栈初始化，符号栈初始化，四元式空白初始化，状态栈加工过程及归约顺序，读结果缓冲区中字符到当前字符中，语句分析，四元式分析结果打印，程序运行结束。具体函数功能介绍：char ch=0;/可用于存放读出的一个字符 int count=0;/词法分析结果缓冲区计数器 static char spelling10=;/存放是别的字 static char line81=;/一行字符缓冲区 char *pline;/line的指针 static char ntab110010;/变量类型名表 struct ntab int tc;/真 int fc;/假 ntab2200;/用于存放布尔表达式的值 int label=0;/指向ntab2的指针 struct rwords char sp10; int sy; ;/匹配表结构体 struct rwords reswords10=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;/存放该变量在自己表中的位置 buf1000,/词法分析结果缓冲区 n,/存放二元式当前字符 n1,/表达式当前的字符 E,/非终结符 sstack100,/算术表达式和布尔表达式的符号栈 ibuf100,/算术表达式和布尔表达式的缓冲区 stack1000;/语法分析的符号栈 struct aa oth;/四元式中没有填写的空白位置 struct fourexp/四元式结构体 char op10; struct aa arg1; struct aa arg2; int result; fexp200;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 stack1100;/状态栈1 int sp1=0;/状态栈的指针 int num=0;/算术表达式或布尔表达式的指针 struct ll int nxq1;/指向下一条四元式的指针 int tc1;/真值链 int fc1;/假值链 labelmark10;/记录嵌套中每层布尔表达式e的首地址 int labeltemp10;/记录每层else之前四元式的地址 int pointmark=-1,pointtemp=-1;/labelmark的指针，labelmark的指针 int sign=0;/ sign=1 赋值语句，sign=2 while语句，sign=3 if语句构造程序语句的LR分析表算术表达式的LR分析表布尔表达式的LR分析表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=a)&(ch=0)&(ch=9);/数字或小写字母 pline-;/取字时多加的一个，-1可使 *pline指向字符缓冲区行尾 spellingk=0; while(ss=0)&(iii10) if(!strcmp(spelling,reswordsiii.sp)/在关键字表中查询 ss=1;/查到标志置1 iii+; /*关键字匹配*/ if(ss=1)/在关键字表中查到 bufcount.sy1=reswordsiii-1.sy;/关键字名字放入结果缓冲区 else/没查到 bufcount.sy1=ident;/将变量名置入结果缓冲区 j=find(spelling);/变量表查询 ，查到就把变量在变量表的地址赋给j if(j=-1)/没查到就新建一个变量 bufcount.pos=tt1;/将其在变量表中的地址放入结果缓冲区中的地址栏 strcpy(ntab1tt1,spelling);/将识别的变量名放入变量名表 tt1+; nlength+;/变量名表长加一 else bufcount.pos=j;/查到后，将变量名表中变量的地址放入结果缓冲区该变量的地址栏中 count+;/指向结果缓冲区下一位置 for(k=0;k=0)&(ch=9); bufcount.sy1=intconst;/常量名存入结果缓冲区 bufcount.pos=ivalue;/该常量地址存入结果缓冲区 count+;/ 向结果缓冲区下一位置 pline-;/指向行缓冲区尾字符 scan()/扫描主程序readnu()/读取当前结果缓冲区的二元式存入struct aa n中 ，pbuf指向结果缓冲区中下一位置的指针newtemp()/返回目前临时变量数gen(char op1,struct aa arg11,struct aa arg22,int result1)/op1算符，arg11操作数1，arg22操作数2， result1结果merg(int p1,int p2)/ 将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）backpatch(int p,int t)/用四元式序号t回填以p为首的链，将链中每个四元式的Result域改写为t的值。change1(int chan)/action1的符号查找排序（i,+,*,(,),#,E,-，/）change2(int chan)/action2的符号查找排序lrparse1(int num)/算数表达式语义分析lrparse2(int num)/ 布尔表达式的分析test(int value) / 测试字符是否为表达式中的值(不包括:)lrparse()/程序语句分析disp1()/打印词法分析结果disp2()/打印四元式分析结果disp3()/打印变量表名main()/主函数四、A语言程序分析与验证五、源码（带注释）#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 spelling10=;/存放是别的字 static char line81=;/一行字符缓冲区 char *pline;/line的指针 static char ntab110010;/变量类型名表 struct ntab int tc;/真 int fc;/假 ntab2200;/用于存放布尔表达式的值 int label=0;/指向ntab2的指针 struct rwords char sp10; int sy; ;/匹配表结构体 struct rwords reswords10=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;/存放该变量在自己表中的位置 buf1000,/词法分析结果缓冲区 n,/存放二元式当前字符 n1,/表达式当前的字符 E,/非终结符 sstack100,/算术表达式和布尔表达式的符号栈 ibuf100,/算术表达式和布尔表达式的缓冲区 stack1000;/语法分析的符号栈 struct aa oth;/四元式中没有填写的空白位置 struct fourexp/四元式结构体 char op10; struct aa arg1; struct aa arg2; int result; fexp200;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 stack1100;/状态栈1 int sp1=0;/状态栈的指针 int num=0;/算术表达式或布尔表达式的指针 struct ll int nxq1;/指向下一条四元式的指针 int tc1;/真值链 int fc1;/假值链 labelmark10;/记录嵌套中每层布尔表达式e的首地址 int labeltemp10;/记录每层else之前四元式的地址 int pointmark=-1,pointtemp=-1;/labelmark的指针，labelmark的指针 int sign=0;/ sign=1 赋值语句，sign=2 while语句，sign=3 if语句 /*程序语句的LR分析表*/static int action1913= 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 action1149= 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 action21611= 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=a)&(ch=0)&(ch=9);/数字或小写字母 pline-;/取字时多加的一个，-1可使 *pline指向字符缓冲区行尾 spellingk=0; while(ss=0)&(iii10) if(!strcmp(spelling,reswordsiii.sp)/在关键字表中查询 ss=1;/查到标志置1 iii+; /*关键字匹配*/ if(ss=1)/在关键字表中查到 bufcount.sy1=reswordsiii-1.sy;/关键字名字放入结果缓冲区 else/没查到 bufcount.sy1=ident;/将变量名置入结果缓冲区 j=find(spelling);/变量表查询 ，查到就把变量在变量表的地址赋给j if(j=-1)/没查到就新建一个变量 bufcount.pos=tt1;/将其在变量表中的地址放入结果缓冲区中的地址栏 strcpy(ntab1tt1,spelling);/将识别的变量名放入变量名表 tt1+; nlength+;/变量名表长加一 else bufcount.pos=j;/查到后，将变量名表中变量的地址放入结果缓冲区该变量的地址栏中 count+;/指向结果缓冲区下一位置 for(k=0;k=0)&(ch=9); bufcount.sy1=intconst;/常量名存入结果缓冲区 bufcount.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种关系运算符bufcount.pos=（=为0，=为2，为3，为4，=为5） if(ch=) bufcount.pos=0; else if(ch=) bufcount.pos=4; else bufcount.pos=1; pline-; bufcount.sy1=rop;/关系运算符名存入结果 count+;/结果指针后移 break; case : readch(); if(ch=) bufcount.pos=2; else bufcount.pos=3; pline-; bufcount.sy1=rop; count+; break; case (: bufcount.sy1=lparent; count+; break; case ): bufcount.sy1=rparent; count+; break; case #: bufcount.sy1=jinghao; count+; break; case +: bufcount.sy1=plus; count+; break; case -: bufcount.sy1=sub; count+; break; case *: bufcount.sy1=times; count+; break; case /: bufcount.sy1=div; count+; break; case : readch(); if(ch=) bufcount.sy1=becomes; count+; break; case =: bufcount.sy1=rop; bufcount.pos=5; count+; break; case ;: bufcount.sy1=semicolon; count+; break; readch();/ 取下一个字符 bufcount.sy1=-1;/结束了 /*/readnu()/读取当前结果缓冲区的二元式存入struct aa n中 ，pbuf指向结果缓冲区中下一位置的指针 if(pbuf-sy1=0) n.sy1=pbuf-sy1;/存放当前二元式字符名称 n.pos=pbuf-pos;/存放当前二元式字符位置 pbuf+; /*中间变量的生成*/newtemp()/返回目前临时变量数 newt+;/临时变量计数器+1 return newt;/*生成四元式*/gen(char op1,struct aa arg11,struct aa arg22,int result1)/op1算符，arg11操作数1，arg22操作数2， result1结果 strcpy(fexpnxq.op,op1);/为四元式传入算符 fexpnxq.arg1.sy1=arg11.sy1;/为四元式操作数1传入名字 fexpnxq.arg1.pos=arg11.pos;/ 为四元式操作数1传入地址 fexpnxq.arg2.sy1=arg22.sy1;/为四元式操作数2传入名字 fexpnxq.arg2.pos=arg22.pos;/ 为四元式操作数2传入地址 fexpnxq.result=result1;/ 为四元式结果传入结果 nxq+;/每次指向下一个要生成的四元式地址 return nxq-1;/当前四元式地址 /*布尔表达式的匹配*/merg(int p1,int p2)/ 将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值） int p; if(p2=0) return p1; else p=p2; while(fexpp.result!=0) p=fexpp.result; fexpp.result=p1; return p2; backpatch(int p,int t)/用四元式序号t回填以p为首的链，将链中每个四元式的Result域改写为t的值。 int tempq; int q; q=p; while(q!=0) tempq=fexpq.result; fexpq.result=t; q=tempq; /*/change1(int chan)/action1的符号查找排序（i,+,*,(,),#,E,-，/） switch(chan) case ident:/变量 case intconst:return 0;/i case plus:return 1;/+ case times:return 2;/* case lparent:return 3;/( case rparent:return 4;/) case jinghao:return 5;/# case tempsy:return 6;/E case sub:return 7;/- case div:return 8;/ / change2(int chan)/action2的符号查找排序 switch(chan) case ident: caseinconst:return 0; case rop:return 1; case lparent:return 2; case rparent:return 3; case op_not:return 4; case op_and:return 5; case op_or:return 6; case jinghao:return 7; case tempsy:return 8; case EA:return 9; case E0:return 10;/*赋值语句的分析*/lrparse1(int num)/算数表达式语义分析 lr1=action1stack1sp1change1(n1.sy1);/由栈顶装状态和当前符号查一个action1中的值 if(lr1=-1)/查出为-1表示出错 printf(n算术表达式或赋值语句出错!n); getch(); exit(0); if(lr1=0)/在013个状态之中 sp1+;/状态栈指针+1 stack1sp1=lr1;/该状态值存入状态栈该位置 if(n1.sy1!=tempsy)/当前符号不是非终结符 ssp+;/符号栈指针+1 num+;/ibuf(布尔或算术缓冲区)指针+1 sstackssp.sy1=n1.sy1;/将当前符号类型名存入符号栈名字域 sstackssp.pos=n1.pos;/ 将当前符号地址存入符号栈地址域 n1.sy1=ibufnum.sy1;/从布尔或算术缓冲区中取下一个符号名 n1.pos=ibufnum.pos;/从布尔或算术缓冲区中取下一个符号名的地址 lrparse1(num);/继续分析 if(lr1=100)&(lr1E case 101:E.pos=newtemp();/E-E+E gen(+,sstackssp-2,sstackssp,E.pos+100); ssp=ssp-2;/按照规约,符号栈退出个符号 E+E出栈 sstackssp.