编译技术课程设计报告

编译技术课程设计班 级 计算机0802 学 号 姓 名 龚 科 指导老师 朱 玉 全 二零一一年 七 月一、目的是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。二、任务及要求基本要求：1 词法分析器 产生下述小语言的单词序列这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值DIMIFDOSTOPEND标识符常数（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-内部字符串标准二进形式-对于这个小语言，有几点重要的限制：首先，所有的关键字（如IFWHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 IF i0 i= 1;而绝对不要写成 IFi0 i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。这个小语言的单词符号的状态转换图，如下图： 2 语法分析器 能识别由加+ 减- 乘* 除/ 乘方 括号（）操作数所组成的算术表达式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。3 中间代码生成器 产生上述算术表达式的中间代码（四元式序列）较高要求：1 扩充上述小语言的单词；2 增加语法分析器的功能，能识别条件语句和循环语句等；3 增加中间代码生成器的功能，能产生条件语句和循环语句等的中间代码（四元式序列）4 增加报错功能；5 将中间代码翻译成汇编语言。三、实现过程说明数据定义清单：#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 /*E and*/#define E0 19 /*E or*/#define plus 34#define times 36#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#define minus 58#define div 59#define chengfang 60/*/char ch=0;/*从字符缓冲区读取当前字符*/int count=0;/*词法分析结果缓冲区计数器*/static char spelling10=;/*存放识别的字*/static char line81=;/*一行字符缓冲区，最多80个字符*/char *pline;/*字符缓冲区指针*/static char ntab110010;/*变量名表，共100项，每项长度10*/struct ntabint tc;/*真值*/int fc;/*假值*/ntab2200;/*在布尔表达式E中保存有关布尔变量的真、假值*/int label=0;/*指向ntab2的指针*/struct rwords/*存放临时变量的表的定义*/char sp10;int sy;/*（保留字表）匹配表的结构，用来与输入缓冲区中的单词进行匹配*/*匹配表初始化，大小为10*/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 aaint sy1;/*存放名字*/int pos;/*存放名字所对应的地址*/buf1000,/*词法分析结果缓冲区*/n,/*读取二元式的当前字符*/n1,/*当前表达式中的字符*/E,/*非终结符*/sstack100,/*算术或布尔表达式加工处理使用的符号栈*/ibuf100, /*算术或布尔表达式使用的缓冲区*/stack1000;/*语法分析加工处理使用的符号栈*/struct aa oth;/*四元式中空白位置*/struct fourexpchar 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;/*nxq指向下一个形成的四元式的地址*/ /*每次执行gen（）时，地址自动增1*/int lr; /*扫描LR分析表1过程中保存的当前状态值*/int lr1; /*扫描LR分析表2或表3所保存的当前状态值*/int sp=0; /*查找LR分析表时状态栈的栈顶指针*/int stack1100;/*状态栈1的定义*/int sp1=0;/*状态栈1的栈顶指针*/int num=0;/*算术或布尔表达式缓冲区指针*/struct llint nxq1;/*记录下一条四元式的地址*/int tc1; /*真值链*/int fc1; /*假值链*/labelmark10; /*记录语句嵌套层次的数组，*/ /*即记录嵌套中每层的布尔表达式E的首地址*/int labeltemp10;/*记录语句嵌套层次的数组，*/ /*即记录每层else之前的四元式地址*/int pointmark=-1,/*labelmark数组指针*/pointtemp=-1;/*labeltemp数组指针*/int sign=0; /*sign=1，为赋值语句；sign=2，为布尔表达式。*/*程序语句LR分析表*/static int action1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,-1,-1,/*1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/*算术表示式的LR分析表*/static int action11610=/*0*/12,-1,-1,-1,-1,-1,14,-1,-1,1,/*1*/-1,2,3,4,5,6,-1,-1,ACC,-1,/*2*/12,-1,-1,-1,-1,-1,13,-1,-1,7,/*3*/12,-1,-1,-1,-1,-1,13,-1,-1,8,/*4*/12,-1,-1,-1,-1,-1,13,-1,-1,9,/*5*/12,-1,-1,-1,-1,-1,13,-1,-1,10,/*6*/12,-1,-1,-1,-1,-1,13,-1,-1,11,/*7*/-1,101,101,4,5,6,-1,101,101,-1,/*8*/-1,102,102,4,5,6,-1,102,102,-1,/*9*/-1,103,103,103,103,6,-1,103,103,-1,/*10*/ -1,104,104,104,104,6,-1,104,104,-1,/*11*/ -1,105,105,105,105,105,-1,105,105,-1,/*12*/ -1,107,107,107,107,107,-1,107,107,-1,/*13*/ 12,-1,-1,-1,-1,-1,13,-1,-1,-14,/*14*/ -1,2,3,4,5,6,-1,15,-1,-1,/*15*/ -1,106,106,106,106,106,-1,106,106,-1;/*布尔表示式的LR分析表*/static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,-1,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,-1,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;函数清单：void main(); /*主程序*/void readline(); /* 从文件读一行到缓冲区 */void readch(); /* 从缓冲区读取一个字符 */int find(char spel); /* 标识符和关键字的识别 */void identifier(); /* 字符串的识别 */void number(); /* 数字的识别 */void scan(); /* 扫描主函数 */void readnu(); /* 读取二元式的一个字符 */int newtemp(); /* 中间变量的生成 */int gen(char op1,struct aa arg11,struct aa arg22,int result1); /* 生成四元式 */int merg(int p1,int p2); /* 布尔表示式的匹配 */void lrparse1(int num); /* 赋值语句的分析 */int lrparse2(int num); /* 布尔表达式的分析 */int test(int value); /* 测试字符是否为表达式中的值（不包括;） */int lrparse();/* 程序语句处理 */void disp1(); /* 显示词法分析结果 */void disp2(); /* 四元式分析结果 */void disp3(); /* 变量名表显示 */主要函数流程图：主函数：结束四元式的分析，显示结果语法分析lrparse()从二元式读一个字符初始化状态栈显示词法分析结果扫描主函数scan从缓冲区读取一个字符readch打开文件pas.dat开始词法分析扫描函数scan：结束读取下一符号分情况识别(带不带=)数字的识别number()字符串识别identifier()ch为其它符号？ch为数字？ch为字母？ch= ch=扫描程序scan Y N词法分析标识符及关键字识别函数identifier：若ss1=1,返回ii-1,否则返回1顺序查看数组ntab。若ss1=1,则为关键字，若不为1，则ii+ss1=0; ii=0;标识符和关键字的识别赋值语句的语法分析函数lrparse1结束A-i:=Elr=ACC)&stack1sp1=1?规约后为非终结符E-(E)E-iE-E+Elr=107?lr=106?lr=101?lr=100?堆栈管理,并递归进行管理lr1=108?lr1=0?出错lr1=-1?读SLR(1)表,得lr1赋值语句的分析lrparse1:对应文法：S-E;E-E+E;E-E-E;E-E*E;E-E/E;E-EE;E-(E); YE-i； N Y N N Y. Y Y Y Y N Y布尔表达式的语法分析函数lrparse2：结束return 1lr=ACC?规约后为非终结符EO-E(1)orE-EO E(2)E-ilr=108?lr=107?lr=101?lr=100?堆栈管理,并递归进行管理lr1=109?lr1=0?出错lr1=-1?读SLR(1)表,得lr1布尔表达式的分析lrparse2对应文法：S-E;E-i;E-i rop i;E-(E);B-not E;E-E and;E-E or;E-EE; Y Y N Y N N Y. Y Y Y Y N Y注：老师给出的赋值语句文法为：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i我将此文法给些为：(0)S-E;(1)E-E+E;(2)E-E-E;(3)E-E*E;(4)E-E/E;(5)E-EE;(6)E-(E);(7)E-i；并计算其SLR分析表:状态 ACTIONGOTO i + - * / ( ) #E0S12s141 1S2S3S4S5S6Acc 2S12S137 3S12S138 4S12S139 5S12S1310 6S12S1311 7R1R1S4S5S6R1R1 8R2R2S4S5S6R2R2 9R3R3R3R3S6R3R310R4R4R4R4S6R4R411R5R5R5R5R5R5R512R7R7R7R7R7R7R713S12S1314S2S3S4S5S6S1515R6R6R6R6R6R6R6四、源程序清单/ ht.cpp : 定义控制台应用程序的入口点。/小型编译程序：高级语言到四元式的编译#include stdio.h/*如果使用TC的话，需要配置头文件路径*/#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 /*E and*/#define E0 19 /*E or*/#define plus 34#define times 36#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#define minus 58#define div 59#define chengfang 60/*/char ch=0;/*从字符缓冲区读取当前字符*/int count=0;/*词法分析结果缓冲区计数器*/static char spelling10=;/*存放识别的字*/static char line81=;/*一行字符缓冲区，最多80个字符*/char *pline;/*字符缓冲区指针*/static char ntab110010;/*变量名表，共100项，每项长度10*/struct ntabint tc;/*真值*/int fc;/*假值*/ntab2200;/*在布尔表达式E中保存有关布尔变量的真、假值*/int label=0;/*指向ntab2的指针*/struct rwords/*存放临时变量的表的定义*/char sp10;int sy;/*（保留字表）匹配表的结构，用来与输入缓冲区中的单词进行匹配*/*匹配表初始化，大小为10*/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 aaint sy1;/*存放名字*/int pos;/*存放名字所对应的地址*/buf1000,/*词法分析结果缓冲区*/n,/*读取二元式的当前字符*/n1,/*当前表达式中的字符*/E,/*非终结符*/sstack100,/*算术或布尔表达式加工处理使用的符号栈*/ibuf100, /*算术或布尔表达式使用的缓冲区*/stack1000;/*语法分析加工处理使用的符号栈*/struct aa oth;/*四元式中空白位置*/struct fourexpchar 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;/*源程序文件，为结束符*/*FILE *mfile;*/int newt=0;/*临时变量计数器*/int nxq=100;/*nxq指向下一个形成的四元式的地址*/ /*每次执行gen（）时，地址自动增1*/int lr;/*扫描LR分析表1过程中保存的当前状态值*/int lr1;/*扫描LR分析表2或表3所保存的当前状态值*/int sp=0;/*查找LR分析表时状态栈的栈顶指针*/int stack1100;/*状态栈1的定义*/int sp1=0;/*状态栈1的栈顶指针*/int num=0;/*算术或布尔表达式缓冲区指针*/struct llint nxq1;/*记录下一条四元式的地址*/int tc1;/*真值链*/int fc1;/*假值链*/labelmark10;/*记录语句嵌套层次的数组，*/ /*即记录嵌套中每层的布尔表达式E的首地址*/int labeltemp10;/*记录语句嵌套层次的数组，*/ /*即记录每层else之前的四元式地址*/int pointmark=-1,/*labelmark数组指针*/ pointtemp=-1;/*labeltemp数组指针*/int sign=0;/*sign=1，为赋值语句；sign=2，为布尔表达式。*/*程序语句LR分析表*/static int action1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,-1,-1,/*1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/*算术表示式的LR分析表*/static int action11610=/*0*/12,-1,-1,-1,-1,-1,14,-1,-1,1,/*1*/-1,2,3,4,5,6,-1,-1,ACC,-1,/*2*/12,-1,-1,-1,-1,-1,13,-1,-1,7,/*3*/12,-1,-1,-1,-1,-1,13,-1,-1,8,/*4*/12,-1,-1,-1,-1,-1,13,-1,-1,9,/*5*/12,-1,-1,-1,-1,-1,13,-1,-1,10,/*6*/12,-1,-1,-1,-1,-1,13,-1,-1,11,/*7*/-1,101,101,4,5,6,-1,101,101,-1,/*8*/-1,102,102,4,5,6,-1,102,102,-1,/*9*/-1,103,103,103,103,6,-1,103,103,-1,/*10*/ -1,104,104,104,104,6,-1,104,104,-1,/*11*/ -1,105,105,105,105,105,-1,105,105,-1,/*12*/ -1,107,107,107,107,107,-1,107,107,-1,/*13*/ 12,-1,-1,-1,-1,-1,13,-1,-1,-1,/*14*/ -1,2,3,4,5,6,-1,15,-1,-1,/*15*/ -1,106,106,106,106,106,-1,106,106,-1;/*布尔表示式的LR分析表*/static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,-1,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,-1,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;/*从文件读一行到缓冲区*/void readline()char ch1;pline=line;ch1=fgetc(cfile); while(ch1!=n)*pline=ch1;pline+;ch1=fgetc(cfile); *pline=0;pline=line;/*从缓冲区读取一个字符*/void readch()if(ch=0)readline();lnum+;ch=*pline;pline+;/*标识符和关键字的识别*/int find(char spel)int ss1=0;int ii=0;while(ss1=0)&(ii=a)&(ch=0)&(ch=9);pline-;spellingk=0;while(ss=0)&(iii10)if(!strcmp(spelling,reswordsiii.sp) ss=1;iii+;/*关键字匹配*/if(ss=1)bufcount.sy1=reswordsiii-1.sy;elsebufcount.sy1=ident;j=find(spelling);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=