编译原理课设实验报告

编译技术课程设计报告实验名称编译器设计姓名 学号 班级 本课设的任务是完成一个完整的编译器， 处理用户提交的符合所定文法的源程序代 码，生成四元式中间代码，进而翻译成等价的 X86平台上汇编语言的目标程序。编译程序的工作过程划分为下列 5个过程：词法分析，语法分析，语义分析和中间 代码生成，代码优化，目标代码生成。其中，词法分析阶段的基本任务是从以字符串表示的源程序中识别出具有独立意义 的单词符号，并以二元组的形式输出，以作为语法分析阶段的输入。语法分析阶段的基 本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。语义分析的任务是首先对每 种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式（本课设采用四元式）来描述这种语义。代码优化的任务是对前阶段产生的中间代码进行等价变换或 改造，以期获得更为高效即省时间和空间的目标代码。目标代码生成的任务是将中间代 码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码（本课设生成汇编指令代码）。在词法分析阶段，通过DOS环境手动输入字符串序列 （以作为结束标志）作为带 分析的源程序，调用词法扫描子程序将字符串以二元组的形式输出（若有不属于该语言单词符号出现，则进行出错处理），词法扫描子程序包括了对源程序的预处理（忽略多 余空格、回车换行符等空白字符），以及对单词的识别和分类，以形成（单词种别，单 词自身的值）形式的二元组，并将用户自定义变量信息存入程序变量信息表。在语法分析阶段，采用自上而下的递归下降分析法，从文法的开始符号出发，根据 文法规则正向推导出给定句子。根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描程序，发出“取下一个单词符号”的 命令，以取得下一个单词符号作语法分析。在语义分析和中间代码生成阶段，采用语法制导翻译法，使用属性文法为工具来描述 程序设计语言的语义。首先审查词法分析得到的每个语法结构的静态语义，如果静态语义正确再生成中间代码（本课设中采用四元式）。使用属性文法作为描述程序设计语言 语义的工具，采用语法制导翻译法完成对语法成分的翻译工作，即在语法分析过程中， 依随分析的过程，根据每个产生式所对应的语义子程序（或语义规则描述的语义处理的加工动作）进行翻译。目标代码生成是编译程序的最后一个阶段，根据符号表等信息，将中间代码转化为等价的目标代码。为减少访问计算机内存的次数， 应尽可能把基本块内还要被引用的变 量放到寄存器中，而把基本块内不用的变量所占的寄存器释放。为了随时掌握寄存器的使用情况和变量的存放情况， 以便生成适当地目标代码， 可以建立寄存器描述表和变量 地址描述表。在编译程序的各个阶段中都要涉及到表格管理和错误处理。编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息（本课设中建立了 程序变量信息表，变量地址描述表，寄存器描述表）。一个好的编译程序在编译过程中， 应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。实验的整体设计思想可由以下图示表示：编译器基本模块设计词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号，包括关键字，标识符，常数，运非d+、d0的功能是识别由该非终结符所表示的语法成 此相应的这组函数采用自出给定的每个非终结符编写一个函数，根据文法规则正向推导程序）,每个函数（或子程序） 去常常是递归定义的，因（或子程序）1312为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函 数体则是根据规则右部符号串的结构和顺序编写，完成相应非终结符匹配，通过所有子程序的相互调用，完成整个终结符号串的分析。(1) 当遇到终结符a时，则编写语句if (当前读来的输入符号=a)读下一个输入符号；(2) 当遇到非终结符A时，则编写语句调用 A();(3) 当遇到规则A-&时，则编写语句if (当前读来的输入符号FOLLOW(A)error()；递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。语法结构定义采用扩充的BNF表示法，避免了直接左递归规则，并且也没有公共左因子。对于非终结符 L T +T ,函数T()用while语句描述如下：T ()F ();while ( sym = = =,JGE )|(,JG)|(v=,JLE)|(v,JL)说明：使用到的80X86宏汇编指令:一般传送指令MOV OPD,OPS将字转换成双字指令(将AX中的符号扩展至 DX中)：CBW加指令：ADD OPD,OPS减指令：SUB OPD,OPS有符号乘指令：IMUL OPD,OPS有符号除指令：IDIV OPS(字除法：(DX,AX)/(OPS) AX商 ),DX余数)比较指令：CMP OPD,OPS转移指令：JE相等转移JNE不相等转移JG大于转移JGE大于或等于转移JL小于转移JLE小于或等于转移JMP无条件转移指令限制:目的操作数不能是立即操作数；(2) 操作结束后，运算结果送人目的地址中；(3) 源操作数和目的操作数不能同时为存储器操作数;(4) IMUL OPD,OPS OPD为寄存器(5) IDIV OPS中OPS不能是立即操作数1.流程框图 1)词法分析器seaner()函数流程图2)语法分析器(递归下降法)P()函数流程图B()函数流程图SS(函数流程图3)语义分析及中间代码生成初始化:flag,nVar,index,nSuffix 置 0Parse()函数流程图4)目标代码生成2.函数相关说明1)词法分析部分函数Scaner()识别源程序的一个单词符号 词法分析程序所用的全局变量如下：rwtab关键字对应到编码值的映射表。prog字符数组，存放源程序ch字符变量，存放当前读进的源程序字符。syn整型，当前单词种别编码token 字符数组,存放当前构成单词符号的字符串。sum双精度型，存放当前常量的数值。variable 用户自定义变量信息表。flag 1表示刚读取一个变量或常数，+/-为运算符；0反之，+/-可能为数值符号将从键盘输入的字符串存储到prog数组，用scaner()函数从prog中取出有独立意义的字符串存到token中：1、 首字符为字母，且其后为字母与数字的组合，syn对应到码值10，进一步检查此组合字符串是否在关键字表中，若在其中，则修改syn对应到相应码值；2、 数字串的组合中：整数数字串、小数数字串码值、(含有字母e)指数数字串，将其二进制数值存入sum；3、其他符号先判断是否为符号组合一部分，若为符号组合，则继续扫描，syn应到相应码值；若为单个符号，则回退，syn对应到相应码值。main():先从键盘输入待编码字符串，存入prog中，用#判断是否输入结束，然后调用scaner()函数，得到对应码值，有 print函数显示输出。d) 语法分析部分(递归下降法)(1) 函数 Scaner()功能：读进源程序的下一个单词符号并将它放在全程变量 sym。(2) 函数 error()功能：出错处理程序。数组 prog、token、rwtab，函数 scanner()作用同上。递归下降算法分析：调用 scan er()函数，对应出码值若不为 0,则报错；然后调用 语句串分析函数；判断是否含有 end;若含有则再次调用 sca ner()函数，对应得相 应码值；判断是否由#提示结束；若是，则打印分析成功，若否则转报错处理。3. 输入与输出(包括出错处理)a)词法分析程序词法分析程序的输入是字符串形式的源程序，词和词之间可以用空白字符(空格、回车、制表符)隔开。词法分析程序的输入是一个二元组，形式为：(单词种别码，单词自身的值)。若输入的字符串带有不合法的字符，则对应的字符(串)在输出中不以二元组的形式显示，而以“ error!表示出错。例如：输入 main while if 123.455e+123#输出：(1,ma in)(9,while)(6,if)(20,1.23455e+125)(0,#)b)语法分析程序语法分析程序的输入与词法分析的输入一致，即字符串形式的源程序， 词和词之间可以用空白字符(空格、回车、制表符)隔开。语法程序的输出是判断所输入字符串是否是该语言的句子的结果，也即“ success或者“ fail!” ，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。出错时结果为“fail! ”。例如：输入 123.345e+123+(1*3+(2+4)/212)+12#结果为“ success! ”4. 程序运行结果(屏幕截图)5. 编译器使用说明语法分析器的输入为字符串形式的源程序，词与词之间可以用空白字符(空格、回 车、制表符)隔开；语法程序的输出是判断所输入字符串是否是该语言的句子的结果，也即“ success!或者“ fail!”，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。是则输出“ success，出错则输出“ fail”。6. 心得与体会大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。设计词法分析 器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序；上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器中，代码优化技术已用于程序验证器和从非结构化的程序产生结构化程序的编程之中。通过动手编写程序对词法语法的分析有了更加深入的体会，巩固了编译原理的基本 知识，亲自动手实践编译程序，使我对编译更加感兴趣。此次实验只是实现了编译器最 基本的功能，不由得感叹实际的编译器实在太强大了！继续认真学习，勤于思考，学习 编译中的精妙思想，做好课设！7. 源程序清单#include stdafx.h#include #include #include #include #include #include /*/词法分析#define max 10 char *rwtab 9 = main ,int ,float double ,char ,if ,else,do ,while;char prog1OO; 源程序int p;当前处理字符位置char ch; /当前处理字符int flag; /1表示刚读取一个变量或常数，+/-为运算符；0反之，+/-可能为数值符号int syn;/种别编码char token max; /保留字、内部字符串或操作符|double sum; / 数值char* variable;/ 变量信息表int nVar;/*/ void scaner()int i;for(i=O;imax;i+) token i=0;sum=0;int m=0;int e=0;/数值指数ch=progp+;while(isspace(ch) ch=progp+;/预处理，去除注释、多余空格、回车换行符等 if(isalpha(ch)/保留字、内部字符串while(isalnum(ch)tokenm+=ch;ch=progp+;tokenm+=0;p-;syn=10;for(i=0;i9;i+)if(strcmp (token ,rwtabi)=0)syn=i+1;flag=0;break;if(syn=1O)flag=1;for (i=1;i=nVar;i+)if (!strcmp(token,variablei) return; strcpy(variable +nVar, token);else if (ch =+| ch =-| isdigit(ch)/ 数值、+、-if (!isdigit(ch)&(flag = 1|! isdigit(progp)tokenm+=ch;if (ch = +) syn =22;elsesyn = 23;flag = 0;elseint flag1 = 0;int flag2 = 0;if(ch = +| ch =-)ch=progp+;if(ch = -) flag1=1;while(isdigit (ch)sum=sum*10+ ch-0;ch=progp+;int k=10;if(ch=. & isdigit (progp)ch=progp+;while(isdigit (ch)double d=ch-0;sum=sum+d/k;k=k*10;ch=prog p+; |if(ch=e | ch=E)char ch_tmp =prog p;if(ch_tmp=-+ | ch_tmp =-) & isdigit(progp+1) | isdigit (ch_tmp) ch=prog p+;if(!isdigit (ch)if(ch+)flag2=0;elseflag2=1;ch=progp+;while(isdigit (ch)e=e*10+ch-0;ch=progp+;if(flag2)sum=sum*pow(10.0,-e);elsesum=sum*pow(10.0,e);if(flag1) sum*=(-1);p-;syn=20;flag=1;else/运算符、分隔符flag = 0;m=0;switch (ch)casev:tokenm+=ch;ch=progp+;if(ch=)syn=35;tokenm+=ch;elsesyn=34;P-； break;case：tokenm+=ch; ch=progp+; if(ch=)syn=33; tokenm+=ch;elsesyn=32;P-; break;case=:tokenm+=ch; ch=progp+; if(ch=)syn=36; tokenm+=ch;elsesyn=21;p-; break;case!:tokenm+=ch; ch=progp+; if(ch=)syn=37; tokenm+=ch;elsesyn=-1; break;case*:syn=24; token0=ch; break;case/:syn=25; token 0=ch; break;case(:syn=26; token 0=ch; break;case):syn=27; token 0=ch; break;case:syn=28; token 0=ch; break;case:syn=29; token 0=ch; break;case,:syn=30; token 0=ch; break;case;:syn=31; token 0=ch; break;case#:syn=0; token 0=ch; break;default:syn=-1; printf (illegal character %c/n ,ch);return ;/*/*语法语义分析*/*/递归下降法/void P (); / 程序void B (int *nChain); / 语句块void SSint *nChain); / 语句串void S (int *nChain); / 语句void AS(int *nChain); / 赋值语句void CS(int *nChain); / 条件语句void LS(int *nChain); / 循环语句void C (int *etc,int *efc); / 条件char * E ();/ 表达式char * T ();/ 项char * F ();/ 因子void error (); / 出错处理/语法制导翻译/1/typedef struct quaternion char opmax;char argv1max;char argv2max;char resmax;quad;四元式quad *pQuad;四元式组指针int index,nSuffix;四元式编号，临时变量编号/*void gen(char *op,char *argv1 ,char *argv2,char *result); char *NewTemp();int merg (int p1,int p2);void bp(int p,int t);void printQuad ();void Parse();/* void error ()if (syn=20) printf (Syntax error before %g ,sum); else printf (Syntax error before %g ,token); syn=50;/程序 :=main()语句块void P()int nChain;scaner();if (syn = 1)scaner();if(syn = 26)scaner();if (syn = 27)scaner();B(&n Chain);else error ();else error ();else error ();/语句块 :=语句串void B(int * nChain)if (syn=28)scaner();SSnChain);if (syn = 29) scaner(); else error ();else error ();/语句串 :=语句;语句;void SS(int *nChain)S(nChain);if (syn=31) scaner();else error ();while (syn != 29)S(nChain);if (syn=31) scaner(); else error ();/语句 :=赋值语句|v条件语句|v循环语句void S(int *nChain)if(syn=10) AS(nChain);else if (syn=6) CS(nChain);else if (syn=8) LS(nChain);else error ();/赋值语句:=ID=表达式void AS(int *nChain)char stempmax;char *place;if (syn=10)strcpy(stemp, token);scaner();if (syn=21)scaner();place=E();gen(=,place, ,stemp);*nChain = 0;else error ();else error ();bp(*nChain,index);/条件语句:=if条件 语句块else 语句块 void CSint *nChain)int nChaintmp ,ntc,nfc;if (syn=6)scaner();C(&ntc, &nfc);bp(ntc,index); B(&n Chaintmp);*nChain=merg(nChaintmp ,nfc);if (syn=7)int nfc1;scaner();nfc1 =index;gen(goto ,0);bp(*nChain,index);B(&n Chaintmp);*nChain=merg(nChaintmp ,nfc1);bp(*nChain,index);else*nChain=merg(nChaintmp ,nfc);bp(*nChain,index);else error ();/循环语句:=do 语句块while 条件 void LS(int *nChain)int ntc ,nfc;if (syn = 8)int nChaintmp; scaner();int indextmp =index;B(&n Chaintmp);if (syn = 9)scaner();C(&ntc, &n fc); bp(ntc,indextmp); bp(nfc,index);*nChain=merg(nChaintmp ,nfc); bp(*nChain,index);else error ();else error ();/条件:=表达式v关系运算符 表达式void C(int *etc,int *efc) char opmax,optmpmax,* place1,* place2; place1 =E();if (syn31 & syn38)sprintf (op,%s,token);scaner();place2=E();*etc=index;*efc=index+1;sprintf(optmp ,goto %s,op); gen(optmp ,place1 ,place2,0);gen(goto ,0);else error ();/表达式 := 项 +V项|-项char * E()char opmax,* placel ,* place2;char *place = (char *) malloc(max); place=place1=T();while (syn = 22 | syn = 23)sprintf (op,%s,token ); scaner();place2=T(); place=NewTemp();gen(op,place1 ,place2,place); placel =place;return place;/项:= 因子*v因子|/v因子char * T()char opmax,* placel ,* place2;char *place ;place=place1=F();while (syn = 24 | syn = 25)sprintf (op,%s,token ); scaner();place2=F(); place=NewTemp();gen(op,place1 ,place2,place); placel =place;return place;/ 因子 :=ID|num|( 表达式 )char * F() char *place = (char *) malloc(max); if (syn = 10)sprintf (place,%s,token); scaner();else if (syn = 20)sprintf (place ,%g,sum); scaner();else if (syn = 26)scaner();place=E();if(syn = 27) scaner();else error ();else error ();return place;/*/生成四元式void gen(char *op,char *argv1 ,char *argv2,char *result)sprintf (pQuadindex.op,%s,op);sprintf (pQuadindex. argv1,%s,argv1);sprintf (pQuadindex.argv2,%s,argv2);sprintf (pQuadindex. res,%s ,result); index+;/产生临时变量char *NewTemp()char *tmplD = (char *)malloc (max);sprintf (tmpID ,T%d,+nSuffix);return tmpID;/ 合并 p1、p2int merg (int p1,int p2)int p,nRes;if(p2 = 0)nRes = p1;elsep = p2;nRes = p2;while(atoi(pQuadp.res)p = atoi(pQuadp.res);sprintf (pQuadp.res,%s,p1);return nRes;/将t回填到p为首的四元式链void bp(int p,int t)int w,q = p;while (q)w=atoi(pQuadq.res);sprintf (pQuadq.res,%d ,t);q=w;return ;/打印四元式序列到文件，控制台输岀void printQuad ()int n;FILE*fw = fopen (quaternion.txt ,w);printf (四元式序列如下：n);for (n=1;nindex;n+)fprintf (fw,n%2d:%7s,%5s,%5s,%5sn,pQuadn.op,pQuadn.argv1,pQuad n.argv2,pQuadn.res);printf (n%2d:%7s,%5s,%5s,%5sn,pQuadn.op,pQuadn.argv1,pQuad n.argv2,pQuadn.res); fclose(fw);/*/语法分析、语义分析和中间代码生成主程序void Parse() int i;p=0;flag = 0;/程序变量信息表variable = (char*) malloc(strlen(prog)*sizeof(char*);for (i=0;i strlen (prog); i+) variablei=(char *)malloc(max); nVar=0;/四元式序列pQuad = (quad *) malloc(strlen (prog)*sizeof(quad); index=1;/四元式临时变量编号nSuffix=0;P();if(syn = 0)printf (Success!n);printQuad ();else printf (Fail!n);/*/目标代码生成(汇编语言)*/*/typedef struct assembly_commandchar Lablemax;char OPmax;char OPDmax;char OPSmax;assemb;/汇编指令assemb * pAssemb;/汇编指令序列指针int indexA;/汇编指令编号int* lable;/四元式编号所对应汇编指令编号char* registerT;/临时变量地址描述表|char* registerName7=AX,BX,CX,DX,BP,SI,DI; 通用寄存器表int registerStatus7;/通用寄存器描述表，0代表未使用，1代表在使用/*/生成汇编指令void genA(char *OP,char *OPD,char *OPS)char *Lable)sprintf (pAssemb indexA.OP,%s ,OP);sprintf (pAssemb indexA.OPD,%s,OPD);sprintf (pAssemb indexA.OPS%s,OPS;sprintf (pAssemb indexA.Lable,%s ,Lable);indexA+;/分配空闲寄存器char* GetfreeR()int i;char *reg = (char *) malloc(max);for (i=0;i7;i+)if(registerStatusi=0)sprintf (reg, %s, registerName i);registerstatus i=1;return reg;reg=Full;return reg;/参数为临时变量，为未分配寄存器的临时变量分配寄存器，返回其所在寄存器/参数为立即数或程序变量，则返回本身char* Place(char *var)if (var0=T)char *place = (char *)malloc(max);if (registerTatoi(va r+1) = NULL)place = GetfreeR();registerTatoi (var+1) = place;elseplace = registerTatoi (var+1);return place;elsereturn var;/回填汇编语句中所有转移指令中标号labelvoid bpAII()int i;int nLable=0;int tmp;for (i=1;iindexA;i+)if (pAssembi.OP0=J)tmp=lableatoi(pAssembi.OPD);sprintf (pAssembtmp .Lable,L%d:,+nLable); sprintf (pAssemb i.OPD,L%d,nLable);/汇编语言文件生成、控制台输岀void printAssemb()int n;FILE*fw = fopen (Assembly.asm ,w);/汇编伪指令fprintf (fw,.386);fprintf (fw,nDATAtSEGMENT USE16);for (n=1;n=nVar;n+)fprintf (fw,n%stDW 0,variablen);fprintf (fw,nDATAtENDS);fprintf (fw,nSTACKtSEGME