编译原理-课程设计报告-简单编译器实现

1、成绩： 课 程 设 计题 目：简单编译器实现学 院：信息工程学院计算机系专 业：计算机科学与技术班 级：计科1103班组 长：小组成员：指导教师：2014年12月19日目录1 概述31.1源、目标语言简介31.2实现平台与运行平台简介31.3其它42简单词法分析器的设计与实现42.1 基础理论说明42.2 需求分析42.3 概要设计52.4 详细设计52.5 测试数据与结果72.6 心得体会73 简单语法分析器设计与实现83.1 基础理论说明83.2 需求分析83.3 概要设计83.4 详细设计83.5 测试数据与结果93.6 心得体会104 中间代码产生器的设计与实现104.1 基础理论说明

2、104.2 需求分析104.3 概要设计104.4 详细设计114.5 测试数据与结果124.6 心得体会12附录：14附录A：主要源程序与系统截图14附录B： 任务分配表及个人完成的程序模块33附录C： 小组讨论与研发记录341 概述编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词

3、符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法，当然两种方法也可以同时使用。语法分析器把语法单元作为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法，即在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编

4、语言。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。1.1源、目标语言简介使用C语言做简单语法分析器，C语言是一门高级计算机编程语言，设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言1.2实现平台与运行平台简介在win32环境下进行编译，Win32是指Microsoft Windows操作系统的32位环境，是目前使用最多的操作系统。实验环境：需要TC、VC+ 6.0等开发工具作为本次试验的环境。1.3其它通过实现一个可以把类似c语言的源代码转变为中间代码的编译器，更好地理解编译的过程，锻炼我们组的编

5、程能力。2简单词法分析器的设计与实现2.1 基础理论说明词法分析负责对源程序的字符串进行扫描和分解，根据构词法将字符流(Character Stream)转化成单词流(Token Stream)。2.2 需求分析词法分析器 产生下述小语言的单词序列这个小语言的所有的单词符号，以及它们的种别编码和内部值1如下表： 单词符号种别编码助记符内码值DIMIFDOSTOPEND标识符常数（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-内部字符串标准二进形式-2.3

6、概要设计首先，所有的关键字（如IFWHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 IF i>0 i=

7、1;而绝对不要写成 IFi>0 i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。2.4 详细设计状态转换图2词法分析器的流程图32.5 测试数据与结果2.6 心得体会设计该词法分析器的过程中虽然没有实际将所有的状态转移表建立出来，但是所用的思想是根据状态转移表实现对单词的识别。首先构造一个保留字表,然后,每输入一个字符就检测应该进入什么状态,并将该字符连接到d串后继续输入,如此循环,最后根据所在的接受状态以及保留字表识别单词3 简单语法分析器设计与实现3.1 基础理论说明在计算机科学和语言学中，语法分析（英：Syntacticanalysis，也叫Parsing）是根

8、据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。语法分析器（Parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。3.2 需求分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法

9、的产生式，识别输入串是否是一个句子。自上而下分析法的主旨是，对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。3.3 概要设计语法分析器 能识别由加+ 减- 乘* 除/ 乘方 括号（）操作数所组成的算术表达式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等3.4 详细设计语法分析器主程序图43.5 测试数据与结果3.6 心得体会此次实验，让我们组对编译原理的基本知识有了深入的了解，

10、加强了对语法分析的认识。代码的编写过程中用到了一些以前从未用过的函数，都是现学现用，掌握还不是很深。在代码调试过程中结果出现许多无法解释的错误，但仍旧坚持下来了，最终调试出了结果。通过这次实验，我们组的动手实践能力得到很大的提高。4 中间代码产生器的设计与实现4.1 基础理论说明在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。产生中间代码的

11、过程叫中间代码生成。4.2 需求分析定义一种语言除了要求定义语法外，还要求定义语义，即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式，即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此，中间代码就显得十分重要，它关系着整个程序语言的正确编译与否，同时也是进行下一步编译的重要先决条件。4.3 概要设计产生上述算术表达式的中间代码（四元式序列）递归下降子程序：数据结构： SYN 算符栈；SEM 语义栈；4.4 详细设计中间代码生成器流程图5：4.5 测试数据与结果4.6 心得体会我们知道，定义一种语言除了

12、要求定义语法外，还要求定义语义，即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式，即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此，中间代码就显得十分重要，它关系着整个程序语言的正确编译与否，同时也是进行下一步编译的重要先决条件。参考文献1 Alfred D.Ullman.Compilers: Principles,Techniques,and Tools:4页2 zjbujs.百度文库.编译原理词法语法语义分析器设计.2013-07-23:5页3 zjbujs.百度文库.编译原理词法语法语义分析器

13、设计.2013-07-23:6页4 线性大树.百度文库. 编译原理词法语法语义设计实现.2014-06-06:8页5 LWH1989216.百度文库.编译原理词法分析和语法分析 (C语言版)2011-05-11:10页附录： 附录A：主要源程序与系统截图 /*词法分析器源代码*/#include<stdio.h>#include<iostream.h>#include<string.h>#define MAX 150 /词法分析表的最大容量#define MAXBUF 255/缓冲区的最大缓冲量char progMAXBUF,tokenMAX;char ch

14、;int syn,p,m,n,sum;char *rwtab6="begin","if","then","while","do","end"/词法分析程序/void scaner()for(m=0;m<MAX;m+)tokenm=NULL;m=0;sum=0;ch=progp+;while(ch=' ') ch=progp+;/读取下一个字符; if(ch>=65&&ch<=122 /*是字母字符*/) while(ch>

15、;=65&&ch<=122|ch>=48&&ch<=57)/*为字母字符或数字字符*/ tokenm+=ch; ch=progp+;/读取下一个字符； tokenm+='0' p=p-1; syn=10; for(n=0;n<6;n+) if(strcmp(token,rwtabn)=0) syn=n+1;/给出syn值; break; else if(ch>=48&&ch<=57/*ch为数字字符*/)while(ch>=48&&ch<=57/*ch为数字字符*/)

16、sum=sum*10+ch-'0' ch=progp+;/读取下一个字符；p=p-1;/回退一个字符；syn=11;else switch(ch) case '<': m=0;tokenm+=ch; ch=progp+;/读取下一个字符； if(ch='>') syn=21; tokenm+=ch; else if(ch='=') syn=22; tokenm+=ch; else syn=20; p=p-1;/回退一个字符； break; case'>': tokenm+=ch; ch=progp

17、+;/读取下一个字符； if(ch='=') syn=24;/将>=的中别码=>syn; tokenm+=ch; else syn=23; p=p-1;/回退一个字符； break; case':': tokenm+=ch; ch=progp+;/读取下一个字符； if(ch='=') syn=18; tokenm+=ch; else syn=17; p=p-1;/回退一个字符； break; case'+': syn=13;token0=ch; break; case'-': syn=14;token

18、0=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; br

19、eak; default: syn=-1; break;/主函数/void main()char A;cout<<"*"<<endl;loop: p=0;cout<<"*"<<endl; printf("please input string (以#结束):n");doscanf("%c",&ch);progp+=ch;/输入源程序字符串，送到缓冲区progp+中；while(ch!='#');p=0;doscaner();switch(syn

20、)case 11:cout<<"( "<<syn<<","<<sum<<" )"<<endl;/输出（数的二元组）； break;case -1:cout<<"error"<<endl; break;default:cout<<"( "<<syn<<","<<token<<" )"<<end

21、l;/输出(其他单词二元组);while(syn!=0);cout<<"*"<<endl;cout<<"请确定是否继续使用程序:S为继续；其它为退出；"<<endl;cout<<"是否继续:"cin>>A;switch(A) case 'S': goto loop; default: cout<<"*"<<endl; cout<<"Thank you ! Bye Bye !"

22、;<<endl; cout<<"*"<<endl; break; 结果：/*语法分析器源代码*/#include <stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>char a50 ,b50,d200,e10;char ch;int n1,i1=0,flag=1,n=5;int total=0; int E();int E1();int T();int G();int S();int F();void input();vo

23、id input1();void output();void main() /*递归分析*/ int f,p,j=0; char x; d0='E' d1='=' d2='>' d3='T' d4='G' d5='#' printf("Please input character string(length<50,end of '#'):n"); do scanf("%c",&ch); aj=ch; j+; while(ch

24、!='#'); n1=j; ch=b0=a0; printf("步骤t文法t分析串tt分析字符t剩余串n"); f=E1(); if (f=0) return; if (ch='#') printf("nAccept! Right Expression!nn"); p=0; x=dp; while(x!='#') printf("%c",x);p=p+1;x=dp; /*输出推导式*/ else printf("nError!n"); printf("回车返

25、回n"); getchar();getchar(); return; printf("n"); printf("回车返回n"); getchar(); getchar();int E1() int f,t; printf("%dtE->TGt",total);total+; flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int E() int f,t; printf(&quo

26、t;%dtE->TGt",total);total+; e0='E'e1='='e2='>'e3='T'e4='G'e5='#' output(); flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int T() int f,t; printf("%dtT->FSt",total);total+; e0=

27、9;T'e1='='e2='>'e3='F'e4='S'e5='#' output(); flag=1; input(); input1(); f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1);int G() int f; if(ch='+') bi1=ch; printf("%dtG->+TGt",total);total+; e0='G'e1='

28、='e2='>'e3='+'e4='T'e5='G'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf("%dtG->t",total);total+; e0='G'e1='='e2='>'e3=''e4='#' output(); flag

29、=1; input();input1(); return(1);int S() int f,t; if(ch='*') bi1=ch;printf("%dtS->*FSt",total);total+; e0='S'e1='='e2='>'e3='*'e4='F'e5='S'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S

30、(); if (t=0) return(0); else return(1); printf("%dtS->t",total);total+; e0='S'e1='='e2='>'e3=''e4='#' output(); flag=1; ai1=ch; input();input1(); return(1);int F() int f; if(ch='(') bi1=ch;printf("%dtF->(E)t",total);total+;

31、 e0='F'e1='='e2='>'e3='('e4='E'e5=')'e6='#' output(); flag=0; input();input1(); ch=a+i1; f=E(); if (f=0) return(0); if(ch=')') bi1=ch;printf("%dtF->(E)t",total);total+; flag=0;input();input1(); ch=a+i1; else printf("

32、;nError!n"); return(0); else if(ch='i') bi1=ch;printf("%dtF->it",total);total+; e0='F'e1='='e2='>'e3='i'e4='#' output(); flag=0;input();input1(); ch=a+i1; else printf("nError!n");return(0); return(1);void input() int j=0;

33、 for (;j<=i1-flag;j+) printf("%c",bj); /*输出分析串*/ printf("tt"); printf("%ctt",ch); /*输出分析字符*/ void input1() int j; for (j=i1+1-flag;j<n1;j+) printf("%c",aj); /*输出剩余字符*/ printf("n"); void output() /*推导式计算*/ int m,k,j,q; int i=0; m=0;k=0;q=0; i=n;

34、 dn='='dn+1='>'dn+2='#'n=n+2;i=n; i=i-2; while(di!='>'&&i!=0) i=i-1; i=i+1; while(di!=e0) i=i+1; q=i; m=q;k=q; while(dm!='>') m=m-1; m=m+1; while(m!=q) dn=dm;m=m+1;n=n+1; dn='#' for(j=3;ej!='#'j+) dn=ej; n=n+1; k=k+1; while(dk!

35、='=') dn=dk;n=n+1;k=k+1; dn='#'结果：/*中间代码生成器源代码*/#include<string>#include <iostream>using namespace std;#define DEFAULT_SIZE 100char EMachine(char w); /表达式E的自动机char TMachine(char w); /表达式T的自动机char FMachine(char w); /表达式F的自动机bool ZMachine(); /表达式Z的自动机string intToString(int

36、a); /整形变成字符串形函数class stack/栈类定义private: int top; string *stacka; int maxsize;public: stack(int size=DEFAULT_SIZE); stack() delete stacka; void push(const string &item); string pop(void); string gettop(void) const ; bool empty(void) const return (top=-1); bool full(void) const return (top=maxsize

37、-1); void clear(void) top=-1; ;stack:stack(int size) /栈类的构造函数 top=-1; maxsize=size; stacka=new stringmaxsize; if(!stacka) cerr<<"allocate memory failed."<<endl; exit(1); void stack:push(const string &item) /压栈操作 if(full() cerr<<"stack full, cannot push."<

38、<endl; return; top+; stackatop=item;string stack:pop(void) /出栈操作 if(empty() cerr<<"stack empty, cannot pop."<<endl; exit(1) ; string item=stackatop; top-; return item;string stack:gettop(void) const /取栈顶操作 if(empty() cerr<<"stack empty, cannot gettop."<<

39、;endl; exit(1) ; return stackatop;static stack wordStack; /符号栈static int noOfQuet=0; /静态四元式个数记录static int noOfT = 1; /静态状态个数记录void main() /主函数char yesOrNo; /进行一个循环操作控制docout<<"请输入算术表达式："<<endl;noOfT = 1; /每次结束询问ZMachine();cout<<endl<<"Continue?Yes or Not:"

40、 cin>>yesOrNo; /输入“Y”则继续while(yesOrNo='y'); /否则程序结束bool ZMachine() /Z自动机char w;cin>>w;w = EMachine(w); /调用E自动机if(w='#') /遇到“#”则结束return true;elsereturn false;char EMachine(char w) /E自动机string operate,a,b,c;string state5;w = TMachine(w); /调用T自动机while(w='+'|w='-

41、') /是加或减符号operate = w;cin>>w; /读入下一字符w = TMachine(w); /调用T自动机b = wordStack.pop(); /字符栈弹出a = wordStack.pop(); /两个操作字符cout<<"(""<<operate<<"","<<a<<","<<b<<",t"<<noOfT<<")"<<endl;c = "t"+intToString(noOfT); /输出四元式wordStack.push(