编译原理提高型实验报告.doc

黄冈师范学院提高型实验报告实验课题小型编译程序的设计与实现（实验类型：综合性 设计性 应用性）实验课程编译原理程序设计实验时间2010年 12 月 20 日学生姓名崔东移专业班级软工0801学 号200826240112一、 实验目的和要求实验目的：综合运用各章的知识，完成一个至少具有词法分析器、语法分析器、中间代码产生器的小型编译系统，初步掌握编译系统开发的基本方法；提高学生的应用程序设计能力，提高分析问题、解决问题的能力。 要求：1、有语法的简要说明和主要部分的原理说明。2、有源代码及其说明和实验结果及其分析。3、可能的改进和讨论。二、 实验条件安装有Turbe C的计算机一台,操作系统为Windows XP的操作系统。三、 实验原理分析编译系统构成及原编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。下图给出了编译系统的顺序图：源程序表格管理出错处理单词符号语法单元中间代码序中间代码目标代码语法分析器语义分析与中间代码生成器优化器目标代码生成器词法分析器其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。语法分析器将这些单词符号做为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。语法分析器把语法单元做为输入供语义分析器使用。语义分析器主要采用的是语法制导方法，即在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理。四、 实验方案或步骤1、 词法分析器设计词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式：（单词种别编码，单词自身的值）由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查。1.1单词符号的内部定义及在编译程序中的定义我们对常量、变量、临时变量、保留关键字（if、while、begin、end、else、then、do等）、关系运算符、逻辑运算符、分号、括号等，规定其内部定义如下：符 号种别编码说 明sy_if0保留字 ifsy_then1保留字 thensy_else2保留字 elsesy_while3保留字 whilesy_begin4保留字 beginsy_do5保留字 dosy_end6保留字 enda7赋值语句semicolon8“ ; ”e9布尔表达式Jinghao10“ # ”S11语句L12复合语句Tempsy15临时变量EA18B and(即布尔表达式中的B)EO19B or(即布尔表达式中的B )Plus34“ + ”Times36“ * ”Becomes38“ := ” 赋值Op_and39“ and ”Op_or40“ or ”Op_not41“ not ”Rop42关系运算符Lparent48“ ( ”Rparent49“ ) ”Ident56变量Intconst57整常量1.2 变量及数据结构说明编译程序中涉及到的变量及数据结构说明如下：char ch=0; /*从字符缓冲区读取当前字符*/int count=0; /*词法分析结果缓冲区计数器*/static char spelling10=; /*存放识别的字*/static char line81=; /*一行字符缓冲区，最多80个字符*/char *pline; /*字符缓冲区指针*/static char ntab110010; /*变量名表，共100项，每项长度10*/struct ntab int tc; /*真值*/int fc; /*假值*/ntab2200; /*在布尔表达式E中保存有关布尔变量的真、假值*/int label=0; /*指向ntab2的指针*/struct rwordschar 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; /*保留字表初始化，大小为10*/struct aa int 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 tt1=0; /*变量名表指针*/char *cfile; /*源程序文件，为结束符*/int lnum=0; /*源程序行数记数*/int sign=0; /*sign=1为赋值语句；=2为while语句；=3为if语句*/*/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数组指针*/1.3 主函数main（）void main()cfile=fopen(pas.dat,r); /*打开C语言源文件*/readch(); /*从源文件读一个字符*/scan(); /*词法分析*/disp1();disp3();stacksp.pos=0;stacksp.sy1=-1; /*初始化状态栈*/stack1sp1=0; /*初始化状态栈1*/oth.sy1=-1;printf(n* 状态栈变化过程以及归约顺序 *n);readnu(); /*从二元式读入一个符号*/lrparse(); /*语法语义分析产生四元式*/getch();disp2();printf(n程序运行结束！n);getch();1.4 词法分析函数说明（1） 读取函数 readline( )、readch( )词法分析包含从源文件读取字符的操作，故实际上是从源程序文件“pas.dat”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执行readch（）从输入缓冲区获得的；若缓冲区已被读空，则再执行readline（）从pas.dat中读取下一行至输入缓冲区。（2） 扫描函数 scan( )扫描函数scan（）的功能是滤除多余空格并对主要单词进行分析处理，将分析得到的二元式存入二元式结果缓冲区。（3） 变量处理及变量名表 find( )变量处理中首先把以字母开头的字母数字串存到spelling10数组中，然后进行识别。识别过程是先让它与保留关键字表中的所有关键字进行匹配，若获得成功则说明它为保留关键字，即将其内码值写入二元式结果缓冲区；否则说明其为变量，这时让它与变量名表中的变量进行匹配（变量匹配函数find（），如果成功，则说明该变量已存在并在二元式结果缓冲区中标记为此变量（单词自身值填为该变量在变量名表中的位置），否则将该变量登记到变量名表中，再将这个新变量存入二元式缓存数组中。（5） 数字识别 digit( )数字识别将识别出的数字转换为等值的十进制数值并填入二元式结果缓存数组。（6） 显示函数显示函数的功能是在屏幕上输出词法分析的结果（即二元式序列和变量名表），同时给出二元式个数及源程序行数统计。2、语法语义分析器设计语法语义分析器的核心是描述程序语句、算术表达式、布尔表达式语法分析的三张LR分析表以及针对这三张LR分析表进行语义加工的语义动作。编译程序中语法分析处理及四元式生成部分主要是以二元式作为输入，并且通过LR分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。在处理if和while语句时，需要进行真值或假值的拉链和回填工作，以便转移目标的正确填入。2.1 LR分析表及实现（1）程序语句的文法及LR分析表实现程序语句的文法GS如下：Sif e then S else S|while e do S|begin L end|aLS;L|S在本小型编译程序的设计与实现中，我们将赋值语句与算术表达式归为一类处理，故在此处将赋值语句仅看作为程序语句文法中的一个终结符号a，将布尔表达式也看作终结符号e。将文法GS拓广为GS:(0) SS(1) Sif e then S else S(2) Swhile e do S(3) Sbegin L end(4) Sa(5) LS(6) LS;L由此得到程序语句LR分析的SLR（1）分析表如下：状态ACTIONGOTOifthenelsewhilebegindoenda;e#SL0s2s3s4s511acc2s63s74s2s3s4s5985r4r4r4r46s107s118s129r5s1310s2s3s4s51411s2s3s4s51512r3r3r3r313s2s3s4s591614s1715r2r2r2r216r617s2s3s4s51818r1r1r1r1（2） 算术表达式的LR分析表实现算术表达式的文法GE如下：EE+E|E*E|（E）|i将文法GE拓广为GS(0) SE(1) E E+E(2) E E*E(3) E (E)(4) E i由此得到算术表达式LR分析的SLR（1）分析表如下：状态ACTIONGOTOi+*（）#E0s3s211s4s5acc2s3s263r4r4r4r44s3s275s3s286s4s5s97r1s5r1r18r2r2r2r29r3r3r3r3（3） 布尔表达式的LR分析表实现布尔表达式的文法GB如下：BBB|BB|B|(B)|i rop i | i 为了便于语法分析时的加工处理，将上述文法改写为文法GS：BBAB|BOB|B|(B)|i rop i | i BABBOB将文法GS拓广为文法GS(0) SB (1) B i (2) B i rop i (3) B (B) (4) B not B(5) A B and(6) B AB(7) O B or(8) B OB由此得到算术表达式LR分析的SLR（1）分析表如下:状态ACTIONGOTOirop()notandor#BAO0s1s4s513781s2r1r1r1r12s33r2r2r2r24s1s4s511785s1s4s56786r1s9s10r47s1s4s514788s1S4S515789r5r5r510r7r7r711s12s9s1012r3r3r3r313s9s10acc14r6s9s10r615r8s9s10r82.2 算术表达式处理的语义加工程序根据算术表达式文法中产生式对应的语义动作，相应的加工处理程序如下：/* 赋值语句和算术表达式的分析 */lrparse1(int num) int lr1;lr1=action1stack1sp1change1(n1.sy1);if(lr1=-1) printf(n算术表示式或赋值语句出错！n);getch();exit(0); if(lr1=0) /*当前查找LR分析表中的状态为移进状态*/ sp1+;stack1sp1=lr1;if(n1.sy1!=tempsy) ssp+;num+;sstackssp.sy1=n1.sy1; /*将变量名压栈*/sstackssp.pos=n1.pos; /*将变量名地址压栈*/n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse1(num);if(lr1=100)&(lr1,105) /*当前查找LR分析表中的状态为归约状态*/ switch(lr1)case 100: /* SE */break;case 101: /* EE+E */E.pos=newtemp();gen(+,sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;case 102: /* EE*E */E.pos=newtemp();gen(*,sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3; /* EE+E产生式右部长度为3，故归约后栈指针减3 */break;case 103: /* E（E） */E.pos=sstackssp-1.pos;ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;case 104: /* Ei */E.pos=sstackssp.pos;sp1-;break;n1.sy1=tempsy; /* 归约后为非终结符*/n1.pos=E.pos;lrparse1(num);if(lr1=ACC)&(stack1sp1=1) /*赋值语句Ai：= E的归约*/ gen(:=,sstackssp,oth,ibuf0.pos);ssp=ssp-3;sp1=sp1-3; 2.3 布尔表达式处理的语义加工程序根据布尔表达式文法中产生式对应的语义动作，相应的加工处理程序如下：lrparse2(int num) int templabellr1=action2stack1sp1change2(n1.sy1);if(lr1=-1) if(sign=2) printf(nwhile语句出错！n);if(sign=3) printf(nif语句出错！n);getch();exit(0);if(lr1=0) /*当前查找LR分析表中的状态为移进状态*/ sp1+;stack1sp1=lr1;ssp+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;if(n1.sy1!=tempsy)&(n1.sy1!=EA)&(n1.sy1!=E0) num+;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);if(lr1=100)&(lr1109) /*当前查找LR分析表中的状态为归约状态*/ switch(lr1)case 100: /* S B */break;case 101: /* Bi */ntab2label.tc=nxq;ntab2label.fc=nxq+1;gen(jnz,sstackssp,oth,0);gen(j,oth,oth,0);sp1-; ssp-;label+;n1.sy1=tempsy; break;case 102: /* Bi rop i */ntab2label.tc=nxq; ntab2label.fc=nxq+1;switch(sstackssp-1.pos) case 0:gen(j=,sstackssp-2,sstackssp,0); break;case 1:gen(j=,sstackssp-2,sstackssp,0); break;case 3:gen(j,sstackssp-2,sstackssp,0); break;case 4:gen(j,sstackssp-2,sstackssp,0); break;case 5:gen(j=,sstackssp-2,sstackssp,0); break;gen(j,oth,oth,0);ssp=ssp-3; sp1=sp1-3;label+;n1.sy1=tempsy; break;case 103: /* B(B) */label=label-1;ssp=ssp-3; sp1=sp1-3;label+;n1.sy1=tempsy; break;case 104: /* Bnot B */label=label-1;templabel=ntab2label.tc;ntab2label.tc=ntab2label.fc;ntab