编译技术课程设计报告书-L语言编译器的设计与实现

1、 课程设计报告( 2010 2011 年度第1学期)名 称： 编译技术课程设计A 题 目：L语言编译器的设计与实现院 系： 计算机系 班 级： 软件0802 学 号： 2学生姓名： 指导教师： 设计周数： 2 周 成 绩： 日期： 2011 年 1 月 14 日2编译技术课程设计任 务 书一、课程设计的目的与要求1 任务：实现一个简单的编译程序，能够对指定程序设计语言进行编译。2 目的：加深对课堂讲授知识的理解，熟练掌握编译程序设计原理及常用的技术，建立编译程序的整体概念，使得学生初步具有研究、设计、编制和调试编译程序的能力。3 要求：熟悉有关定义、概念和实现算法，设计出程序流程框图和数据结构

2、，编写出完整的源程序，进行静态检查，设计出输入数据、显示输出数据；基本功能完善，方便易用，操作无误；通过课程设计学会编译程序设计与实现的常用技术，具备初步分析、设计和开发编译程序的能力，具备分析与检查软件错误、解决和处理实验结果的能力。4 学生要求人数：2人，1人负责扫描器和目标代码生成器的设计和实现，另1人负责语法分析器和语法制导翻译程序的设计和实现。二、 主要内容下面是课程设计主要内容的简介，详细内容请见编译技术课程设计指导书。1 扫描器设计该扫描器是一个子程序，其输入是源程序字符串，每调用一次输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设程序设计语言中，基本字不

3、能用作一般标识符，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。2 语法分析器设计以算法优先分析方法为例，设计一个算符优先语法分析程序。算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。当然，也可采用预测分析等方法设计语法分析器，具体方法自定。3 语法制导翻译程序设计采用语法制导翻译方法，实现算术表达式、赋值语句和基本控制语句等的翻译。本语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入符号串是句子,则按照其语义进行翻译,输

4、出等价的四元式序列。4 目标代码生成器设计将程序设计语言的中间代码翻译为目标代码，输入是四元式序列，输出是汇编代码文件。三、 进度计划序号设计内容完成时间备注1任务布置，资料查询，方案制定第一周周一2算法设计，程序实现第一周周二至第二周周四3撰写报告，软件验收第二周周五4四、设计成果要求1 完成规定的课程设计任务，所设计软件功能符合要求；2 完成课程设计报告，要求格式规范，内容具体而翔实，应体现自身所做的工作，注重对设计思路的归纳和对问题解决过程的总结。五、 考核方式1 平时成绩验收答辩实验报告；2 五级分制。 学生姓名： 指导教师：鲁 斌 李 莉 2011 年 1 月 4 日本组组员：龚泽滢

5、（200809020205） 邵婧婕（200809020224） 其中我负责语法/语义分析部分。语法/语义分析目 的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。任 务在词法分析程序产生的token文件、符号表文件基础上，完成语法和语义分析，产生相应的中间代码四元式序列。在此，可把语法/语义分析作为独立的一遍进行处理。 语法/语义分析程序符号表文件四元式序列文件符号表文件token文件采用如下四元式：操作码助记符四元式意 义:=( 51, a, 0, r )ra+( 43, a, b, r )ra+b-( 4

6、5, a, b, r )ra-b*( 41, a, b, r )ra*b/( 48, a, b, r )rb/aj<( 53, a, b, n )若a<b转至第n个四元式j<=( 54, a, b, n )若a<=b转至第n个四元式j>( 57, a, b, n )若a>b转至第n个四元式j>=( 58, a, b, n )若a>=b转至第n个四元式j =( 56, a, b, n )若a=b转至第n个四元式j( 52, 0, 0, n )转至第n个四元式j <>( 55, a, b, n )若a<>b转至第n个四元式 实

7、验正文数据结构1输入token文件、符号表文件，其数据结构与词法分析产生的文件相同。2输出l 四元式序列文件，其纪录结构如下：typedef struct equint op; /四元式操作码int op1; /操作数在符号表中的入口地址int op2; /操作数在符号表中的入口地址int result; /结果变量在符号表中的入口地址 equ;l 程序中可用数组Equ存放四元式序列，定义为：equ EquEQU_LENl 可用变量int LineOfEqu做指针，指向下一个即将产生的四元式l 符号表文件的结构与输入相同，语法分析中对于符号表不做操作，只是在文件头部增加一个记录变量多少的数据。

8、 程序结构说明为方便编程，将语言文法整理如下：n LS | S ; LSid := ESif B then SSif B then S else SSwhile B do SSbegin L end变量说明语句的文法：Svar D|DL : K ; | L : K ; DLi , L | iKinteger | bool | real其中，B表示布尔表达式，E表示算术表达式可采用递归下降分析法或其它方法进行语法分析。语法/语义分析程序可划分为三个模块，结构如下：L_BeginparserDeclearparser为主程序模块，Declear为说明语句分析模块，L_begin为复合语句分析模块。

9、其中L_begin结构图如下：L_IfL_BeginL_LetL_WhileL_AnalizeB_AnalizeE_Analize§ 经常使用的过程和函数：l gen(int op,int a,int b, int r)：生成一个四元式l NewTemp()：产生一个临时变量，返回其在符号表中的入口地址l BackPatch(int addr, int addr2)：回填函数，完成四元式转移目标的回填l void getbuf()：获取文件中的一组数据l void program()：程序由程序首部、程序体和;组成l void proghead()：程序首部：program+标识符+

10、；l void block()：程序体部分，常量说明、变量说明、语句部分§ 实验算法思想（包含主程序的示意图）（1）主程序的示意图如下图所示：程序首部调用getbuf()获取文本文档中的下一组字符调用block()End（2）递归下降分析程序示意图如下图所示：（3）语法串分析过程示意图如下图所示： （4）statement语句分析函数示意图如下图所示： （5）expression表达式分析函数如下图所示：（6）term分析函数示意图如下图所示： （7）factor分析过程示意图如下图所示：（8）语义分析器： 设置语义过程1、emit(char *result,char *ag1,ch

11、ar *op,char *ag2)该函数的功能是生成一个三地址语句送到四元式表中。四元式表的结构如下：structchar result8;char ag18;char op8;char ag28;quad20; (2) char *newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，char *newtemp(void)char *p; char m8; p=(char *)malloc(8); k+; itoa(k,m,10); strcpy(p+1,m); p0=t; return(p);2、设计思想函数lrparser 在语法分析的基础上插入相应的语义动作

12、：将输入串翻译成四元式序列。分析程序可知，需要进行四元式翻译的只有赋值语句、表达式和if语句、while语句等控制语句。在实现时，我采用这样的方法：先建立一个关于四元式的结构体，并建立一个存放这样的结构体的向量。当遇到赋值号:=时，声明一个结构体，并把这个结构体插入向量中。由于在赋值号前必然是一个变量ID，可以在遇到一个变量ID时，就把这个ID的值存入临时变量tmp。由于在后面可能要用到也可能用不到，所以不用担心tmp值覆盖的问题。在向量中插入结构体变量后，需要将ID填入对应的项中，然后可以继续遍历。遇到下一个ID则写入。若:=后面是一个表达式，则可以在再新建一个结构体变量，在其中处理表达式的

13、四元式生成。然后把所得的地址存入上一层的对应位置。§ 实验总结这次的实验比较难。刚刚拿到手的时候感觉无从下手，找不到一个突破点。其主要难点在于如何实现回填技术。在实现语法分析器时，整体采用模块化编程的思想。将一个程序拆分成各个部分，分别实现。在实现各个子模块时需要注意的地方就是在实现语法分析时要考虑到各种情况，比如同时定义多个变量等。对此我采用了后缀的处理方式。后缀可有可无。这样就能解决在顺序分析程序时出现多条相同类型的语句以及在一条语句中出现多个变量定义等情况。还有就是在处理语义分析时如何处理表达式和控制语句回填位置这样的问题。本次实验虽然比较大，但不得不说，它在很大程度上锻炼了我

14、们分析、处理问题的能力。由于我采用的是模块化编程的方式。这样编程的好处在于程序的结构清晰，紧密相连。但是带来的负面结果是程序的函数多。无论在写函数还是在调试程序的时候需要极大的耐心。实验中也遇到了不少小问题。比如读文件时如何才能使指针回退等。这些都通过自己的努力和同学的帮助，不仅仅是克服了这些问题，更重要的意义在于我又学会了一些以前不懂的知识。同时我也感受到了理论与实现之间的差距。那些平时上课时觉得很容易懂的知识，要通过自己在计算机上进行实现并不像想象中的那么容易。我们能理解的知识用计算机语言表述成计算机能理解的语言，这不仅需要很扎实的编程基础，更要彻彻底底的搞懂所学的理论知识，并达到将所学知

15、识融会贯通的程度。这样才能自由的应付实现时出现的细节问题。总之，这次的课程设计让我收获颇多。§ 参考资料【1】陈火旺、刘春林、谭庆平、赵克佳、刘越，编译原理（第三版）.北京：国防工业出版社【2】黄贤英、王柯柯，编译原理及实践教程。北京：清华大学出版社【3】马知行、曹启君，编译方法。机械工业出版社附录一：程序代码#include <iostream>#include <windows.h>#include <stdio.h>using namespace std;#define AND 1#define BEGIN 2#define BOOL 3#d

16、efine DO 4#define ELSE 5#define END 6#define FALSE 7#define IF 8#define INTEGER 9#define NOT 10#define OR 11#define PROGRAM 12#define REAL 13#define THEN 14#define TRUE 15#define VAR 16#define WHILE 17#define ID 18#define 整数19#define 实数20#define LBR 21#define RBR 22#define ADD 23#define SUB 24#defin

17、e MUL 25#define DIV 26#define DOT 27#define COM 28#define COL 29#define SEM 30#define ASS 31#define EQU 32#define LEQ 33#define LAB 34#define NEQ 35#define RAB 36#define GEQ 37#define ODD 38#pragma oncetypedef struct tokenint label; /单词序号char name30; /单词本身int code; /单词的机内码int addr; /地址，单词为保留字时为-1，为标

18、识符或常数时为大于的数值，即在符号表中的入口地址。token() label=0;code=0;addr=0;token;void getbuf();void program();void proghead();/程序首部由program 标识符组成void block();/程序体部分void error(int n);void consdefi();void consexpl();void conssuff();void varexpl();void vardefi();void varsuff();/void procdefi();/void procedh();/void procsu

19、ff();void typeil();void assipro();void sentence();void suffix();void ifsent();void read();void whilesent();void idsuff();void write();void compsent();void exprsuff();void sentsuff();void conditio();void termsuff();void express();void term();void factsuff();void factor();void addoper();void muloper()

20、;void respoper();void argument();token t;FILE *opt=fopen("token.txt","r");bool flag=true;/还能否读void main()getbuf();program();printf("the program is right!n");/*Sleep(5000);*/fclose(opt);void getbuf()if(opt=NULL)cout<<"can't open the file!n"exit(0);if(

21、feof(opt)flag=false;/到了结尾不可再读cout<<"file endsn"elsefscanf(opt,"%d %s %d %dn",&t.label,,&t.code,&t.addr);void program()/程序由程序首部、程序体和;组成proghead();block();if(t.code=SEM)getbuf();elsecout<<"miss ''n"exit(0);void proghead()/程序首部：program

22、+标识符+；if(t.code=PROGRAM)getbuf();if(t.code=ID)getbuf();if(t.code=SEM)getbuf();elsecout<<"miss ''n"exit(0);elsecout<<"error of IDn"elsecout<<"miss keyword programn"exit(0);void block()/程序体部分，常量说明、变量说明、语句部分 /变量说明、复合句consexpl();varexpl();/*procdef

23、i(t);*/compsent();void consexpl()/常量说明部分：整数|实数if(t.code=整数|t.code=实数)getbuf();consdefi();conssuff();if(t.code=SEM)getbuf();elsecout<<"miss ''n"exit(0);void consdefi()/常量定义：标识符+等号+无符号数if(t.code=ID)getbuf();if(t.code=EQU)getbuf();if(t.code=INTEGER)getbuf();elsecout<<"

24、;miss INTEGERn"exit(0);elsecout<<"miss '='"exit(0);elsecout<<"miss IDn"exit(0);void conssuff()/常量定义后缀：，+常量定义后缀if(t.code=COM)getbuf();consdefi();conssuff();if(t.code=SEM)getbuf();elsecout<<"miss ''n"exit(0);void varexpl()/变量说明部分，var

25、+变量定义+变量定义后缀if(t.code=VAR)getbuf();vardefi();varsuff();void vardefi()/变量定义：标识符+标识符后缀+：+类型+；|标识符+标识符后缀+：+类型+；+变量定义if(t.code=ID)getbuf();idsuff();if(t.code=COL)getbuf();typeil();if(t.code=SEM)getbuf();elsecout<<"miss ''n"exit(0);elsecout<<"miss ':'n"exit

26、(0);void varsuff()/变量后缀：变量定义+变量后缀|空if(t.code=ID)vardefi();varsuff();void typeil()/类型:real|bool|integerif(t.code=REAL|t.code=BOOL|t.code=INTEGER)getbuf();elsecout<<"wrong tyoe of definen"exit(0);/void procdefi(token t)/过程定义：程序首部+分程序+/if(=/void compsent()/复合句：begin+语句表+endif(t.co

27、de=BEGIN)getbuf();sentence();sentsuff();if(t.code=END)getbuf();elsecout<<"miss BEGIN as the startn"exit(0);void sentence()/赋值语句、if语句、while语句、复合句if(t.code=ID)assipro();else if(t.code=IF)ifsent();else if(t.code=WHILE)whilesent();else if(t.code=BEGIN)compsent();void sentsuff()/语句后缀：；+语句

28、+语句后缀if(t.code=SEM)getbuf();sentence();sentsuff();void assipro()/赋值语句if(t.code=ID)getbuf();suffix();elsecout<<"赋值语句错误n"exit(0);void suffix()/赋值号的后缀为赋值语句，否则为过程调用语句if(t.code=ASS)getbuf();express();else if(t.code=LBR)getbuf();express();if(t.code=RBR)getbuf();elsecout<<"缺少右半边括

29、号n"exit(0);void express()/表达式：正负号+项+项后缀if(t.code=SUB)getbuf();term();termsuff();else if(t.code=整数|t.code=实数|t.code=ID)term();termsuff();void exprsuff()/表达式后缀：，+表达式+表达式后缀if(t.code=COM)getbuf();express();exprsuff();void term()/项：因子+因子后缀factor();factsuff();void termsuff()/项后缀：加减型运算符+因子+因子后缀|空if(t.

30、code=ADD|t.code=SUB)getbuf();factor();factsuff();void factsuff()/因子后缀：因子+因子后缀|空if(t.code=MUL|t.code=DIV)getbuf();factor();factsuff();void factor()/因子：标识符+整数、实数+括号内的表达式if(t.code=ID)getbuf();factsuff();else if(t.code=整数|t.code=实数)getbuf();factsuff();else if(t.code=LBR)getbuf();express();if(t.code=RBR)

31、getbuf();elsecout<<"缺少右半边括号n"exit(0);elsecout<<"因子定义错误n"exit(0);void ifsent()/if语句：if+条件+then+语句if(t.code=IF)getbuf();conditio();if(t.code=THEN)getbuf();sentence();elsecout<<"if语句缺少thenn"exit(0);elsecout<<"if语句定义错误n"exit(0);void conditi

32、o()/作用在表达式上或者两个表达式进行比较if(t.code=ID|t.code=LBR)express();/可能出错respoper();express();void whilesent()/while语句：while语句、if语句、do语句if(t.code=WHILE)getbuf();conditio();if(t.code=DO)getbuf();sentence();elsecout<<"while语句缺少don"exit(0);elsecout<<"while语句定义错误n"exit(0);void idsuff

33、()/标识符后缀：，+标识符+标识符后缀if(t.code=COM)getbuf();if(t.code=ID)getbuf();idsuff();elsecout<<"标识符定义错误n"exit(0);void addoper()/加型运算，加+减if(t.code=ADD|t.code=SUB)getbuf();elsecout<<"加减运算定义错误n"exit(0);void muloper()/乘型运算，乘+除if(t.code=MUL|t.code=DIV)getbuf();elsecout<<"乘

34、除运算定义错误n"exit(0);void respoper()/比较运算符是否为=，<>,<,<=,>,>=if(t.code>=EQU&&t.code<=GEQ)getbuf();elsecout<<"比较运算定义错误n"exit(0);#include<stdio.h>#include<string.h>#include<iostream.h>#include<stdlib.h>structchar result12;char ag11

35、2;char op12;char ag212;quad;char prog80,token12;char ch;int syn,p,m=0,n,sum=0,kk; /p是缓冲区prog的指针，m是token的指针char *rwtab6="begin","if","then","while","do","end"void scaner();char *factor(void);char *term(void);char *expression(void);int yucu()

36、;void emit(char *result,char *ag1,char *op,char *ag2);char *newtemp();int statement();int k=0;void emit(char *result,char *ag1,char *op,char *ag2)strcpy(quad.result,result);strcpy(quad.ag1,ag1); strcpy(quad.op,op);strcpy(quad.ag2,ag2); cout<<quad.result<<"="<<quad.ag1<

37、<quad.op<<quad.ag2<<endl;char *newtemp()char *p;char m12;p=(char *)malloc(12);k+;itoa(k,m,10);strcpy(p+1,m);p0='t'return (p);void scaner()for(n=0;n<8;n+) tokenn=NULL;ch=progp+;while(ch=' ')ch=progp;p+;if(ch>='a'&&ch<='z')|(ch>='A

38、'&&ch<='Z')m=0;while(ch>='0'&&ch<='9')|(ch>='a'&&ch<='z')|(ch>='A'&&ch<='Z')tokenm+=ch;ch=progp+;tokenm+='0'p-;syn=10;for(n=0;n<6;n+)if(strcmp(token,rwtabn)=0)syn=n+1;break;els

39、e if(ch>='0'&&ch<='9')sum=0;while(ch>='0'&&ch<='9')sum=sum*10+ch-'0'ch=progp+;p-;syn=11;if(sum>32767)syn=-1;else switch(ch)case'<':m=0;tokenm+=ch;ch=progp+;if(ch='>')syn=21;tokenm+=ch;else if(ch='=')

40、syn=22;tokenm+=ch;elsesyn=23;p-;break;case'>':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=24;tokenm+=ch;elsesyn=20;p-;break;case':':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=18;tokenm+=ch;elsesyn=17;p-;break;case'*':syn=13;token0=ch;break;case'/':syn=14;tok

41、en0=ch;break;case'+':syn=15;token0=ch;break;case'-':syn=16;token0=ch;break;case'=':syn=25;token0=ch;break;case'':syn=26;token0=ch;break;case'(':syn=27;token0=ch;break;case')':syn=28;token0=ch;break;case'#':syn=0;token0=ch;break;default: syn=-1;

42、break;int lrparser()/cout<<"调用lrparser"<<endl;int schain=0; kk=0; if(syn=1) scaner(); schain=yucu(); if(syn=6) scaner(); if(syn=0 && (kk=0) cout<<"success!"<<endl; else if(kk!=1)cout<<"缺end!"<<endl;kk=1; else cout<<"

43、;缺begin!"<<endl;kk=1; return(schain);int yucu()/cout<<"调用yucu"<<endl;int schain=0; schain=statement(); while(syn=26)scaner(); schain=statement(); return(schain);int statement()/cout<<"调用statement"<<endl;char *eplace,*tt; eplace=(char *)malloc(12

44、); tt=(char *)malloc(12); int schain=0;switch(syn)case 10:strcpy(tt,token);scaner();if(syn=18)scaner();strcpy(eplace,expression();emit(tt,eplace,"","");schain=0;elsecout<<"缺少赋值符!"<<endl;kk=1;return(schain);break;return(schain);char *expression(void)char *tp,

45、*ep2,*eplace,*tt;tp=(char *)malloc(12);ep2=(char *)malloc(12);eplace=(char *)malloc(12);tt =(char *)malloc(12);strcpy(eplace,term ();/调用term分析产生表达式计算的第一项eplacewhile(syn=15)|(syn=16)if(syn=15)strcpy(tt,"+");else strcpy(tt,"-");scaner();strcpy(ep2,term();/调用term分析产生表达式计算的第二项ep2strc

46、py(tp,newtemp();/调用newtemp产生临时变量tp存储计算结果emit(tp,eplace,tt,ep2);/生成四元式送入四元式表strcpy(eplace,tp);return(eplace);char *term(void)/cout<<"调用term"<<endl;char *tp,*ep2,*eplace,*tt;tp=(char *)malloc(12);ep2=(char *)malloc(12);eplace=(char *)malloc(12);tt=(char *)malloc(12);strcpy(eplace

47、,factor();while(syn=13)|(syn=14)if(syn=13)strcpy(tt,"*");else strcpy(tt,"/");scaner();strcpy(ep2,factor();/调用factor分析产生表达式计算的第二项ep2strcpy(tp,newtemp();/调用newtemp产生临时变量tp存储计算结果emit(tp,eplace,tt,ep2);/生成四元式送入四元式表strcpy(eplace,tp);return(eplace); char *factor(void)char *fplace;fplac

48、e=(char *)malloc(12);strcpy(fplace,"");if(syn=10)strcpy(fplace,token);/将标识符token的值赋给fplacescaner();else if(syn=11)itoa(sum,fplace,10);scaner();else if(syn=27)scaner();fplace=expression();/调用expression分析返回表达式的值if(syn=28)scaner();elsecout<<"缺)错误!"<<endl;kk=1;elsecout<

49、;<"缺(错误!"<<endl;kk=1;return(fplace);void main()p=0;cout<<"*语义分析程序*"<<endl;cout<<"Please input string:"<<endl;docin.get(ch);progp+=ch;while(ch!='#');p=0;scaner();lrparser();附录二：运行结果图一、语法分析器运行结果图二、语法分析器的token文件图三、语义分析器运行结果图四、语义分析器运

50、行结果Dr3uhd3uhd3u断喉弩好多年课代表卡不都快递吧4坤角儿4进而34就可4蛕?D脙#軟媁?vo滂焜?蔣 鳄N-P"-觞?F瀢?鷲2SXWJ扱;$E锴?咼?wb,O?hW芀嚙C八?迎q?&锃?.楧D峘?wB賛装 綄?衈瞹?嘁?尥?b袦20?箻>yF邴?詑攗檢锟袥匏=憌?&丹?鐘w鲽毨G>艟<熋H?&鰢Z?L?&?;.z刧绗鰀畬拃Szl<4-榌m "Y朗k?<v?+犢Hmu鏸tn褛 埈蕛癤當? m%犔?QVP?0<蜈_"?绹?爔豴t纴餚?鉙?hte候R?D"檘堑?乒h齊?砱蜮陾巁?g?硃?'硘敍橼Z?G贒?IJw谆'揚?+u醸?羛?;H?豋H