编译原理-课程设计报告-简单编译器实现-精品
更新时间:2024-05-04 00:19:01 阅读量: 综合文库 文档下载
- 嵌入式简单课程设计报告推荐度:
- 相关推荐
成绩:
课 程 设 计
题 目: 学 院: 专 业: 班 级: 组 长: 小组成员: 指导教师:
简单编译器实现 信息工程学院计算机系 计算机科学与技术 计科1103班
2014 年 12 月 19 日
1
目录
1 概述 ............................................................................................................................................................... 3
1.1源、目标语言简介 ............................................................................................................................. 3 1.2实现平台与运行平台简介 ................................................................................................................. 3 1.3其它 ..................................................................................................................................................... 4 2简单词法分析器的设计与实现 .................................................................................................................... 4
2.1 基础理论说明 .................................................................................................................................... 4 2.2 需求分析 ............................................................................................................................................ 4 2.3 概要设计 ............................................................................................................................................ 5 2.4 详细设计 ............................................................................................................................................ 5 2.5 测试数据与结果 ................................................................................................................................ 7 2.6 心得体会 ............................................................................................................................................ 7 3 简单语法分析器设计与实现 ....................................................................................................................... 8
3.1 基础理论说明 .................................................................................................................................... 8 3.2 需求分析 ............................................................................................................................................ 8 3.3 概要设计 ............................................................................................................................................ 8 3.4 详细设计 ............................................................................................................................................ 8 3.5 测试数据与结果 ................................................................................................................................ 9 3.6 心得体会 .......................................................................................................................................... 10 4 中间代码产生器的设计与实现 ................................................................................................................. 10
4.1 基础理论说明 .................................................................................................................................. 10 4.2 需求分析 .......................................................................................................................................... 10 4.3 概要设计 .......................................................................................................................................... 10 4.4 详细设计 ...........................................................................................................................................11 4.5 测试数据与结果 .............................................................................................................................. 12 4.6 心得体会 .......................................................................................................................................... 12 附录: ............................................................................................................................................................. 14
附录A:主要源程序与系统截图 .......................................................................................................... 14 附录B: 任务分配表及个人完成的程序模块 .................................................................................... 33 附录C: 小组讨论与研发记录 ............................................................................................................ 34
2
1 概述
编译程序的工作过程一般可以分为五个阶段:词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的,它一方面从上一个阶段获取分析的结果来进行分析,另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。
其中词法分析器利用超前搜索、状态转换等方法,将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入,对它进行语法分析。语法分析分为两种方法:自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法,当然两种方法也可以同时使用。语法分析器把语法单元作为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法,即在语法分析的同时进行语法分析,并产生一定的语义动作,来生成中间代码。上面三个过程可以与硬件无关,而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化,产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理,这些也都是非常重要的环节。
1.1源、目标语言简介
使用C语言做简单语法分析器,C语言是一门高级计算机编程语言,设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言
1.2实现平台与运行平台简介
在win32环境下进行编译,Win32是指Microsoft Windows操作系统的32位环境,是目前使用最多的操作系统。
实验环境:需要TC、VC++ 6.0等开发工具作为本次试验的环境。
3
1.3其它
通过实现一个可以把类似c语言的源代码转变为中间代码的编译器,更好地理解编译的过程,锻炼我们组的编程能力。
2简单词法分析器的设计与实现 2.1 基础理论说明
词法分析负责对源程序的字符串进行扫描和分解,根据构词法将字符流(Character Stream)转化成单词流(Token Stream)。
2.2 需求分析
词法分析器 产生下述小语言的单词序列
这个小语言的所有的单词符号,以及它们的种别编码和内部值[1]如下表:
单词符号 DIM IF DO STOP END 标识符 常数(整) = + * ** , ( )
种别编码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 助记符 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR 内码值 - - - - - - 内部字符串 标准二进形式 - - - - - - 4
2.3 概要设计
首先,所有的关键字(如IF﹑WHILE等)都是“保留字”。所谓的保留字的意思是,用户不得使用它们作为自己定义的标示符。例如,下面的写法是绝对禁止的:
IF(5)=x
其次,由于把关键字作为保留字,故可以把关键字作为一类特殊标示符来处理。也就是说,对于关键字不专设对应的转换图。但把它们(及其种别编码)预先安排在一张表格中(此表叫作保留字表)。当转换图识别出一个标识符时,就去查对这张表,确定它是否为一个关键字。
再次,如果关键字、标识符和常数之间没有确定的运算符或界符作间隔,则必须至少用一个空白符作间隔(此时,空白符不再是完全没有意义的了)。例如,一个条件语句应写为
IF i>0 i= 1; 而绝对不要写成
IFi>0 i=1;
因为对于后者,我们的分析器将无条件地将IFI看成一个标识符。
2.4 详细设计
状态转换图[2]
5
词法分析器的流程图[3]
开始 输入源文件路径否 路径是否有效是打开源文件初始化文件指针识别指针内容文件结束?否是空格,空白或换行吗是跳过该字符是结束否是字母吗是将字符加入字符数组Word[]否是数字吗否是界符吗否将字符加入字符数组Word[]是将字符加入字符数组Word[]是指向下一字符识别指针内容是输出word为界符输出Word内容为不可识别将字符加入字符数组Word[]将字符加入字符数组Word[]指向下一字符指向下一字符是字母惑数字吗回退否将word与关键字表key进行匹配输出word为普通标示符是数字吗否输出word为常数指向下一字符否匹配?是输出word为关键字 6
2.5 测试数据与结果
2.6 心得体会
设计该词法分析器的过程中虽然没有实际将所有的状态转移表建立出来,但是所用的思想是根据状态转移表实现对单词的识别。首先构造一个保留字表,然后,每输入一个字符就检测应该进入什么状态,并将该字符连接到d串后继续输入,如此循环,最后根据所在的接受状态以及保留字表识别单词
7
3 简单语法分析器设计与实现 3.1 基础理论说明
在计算机科学和语言学中,语法分析(英:Syntacticanalysis,也叫Parsing)是根据某种给定的形式文法对由单词序列(如英语单词序列)构成的输入文本进行分析并确定其语法结构的一种过程。
语法分析器(Parser)通常是作为编译器或解释器的组件出现的,它的作用是进行语法检查、并构建由输入的单词组成的数据结构(一般是语法分析树、抽象语法树等层次化的数据结构)。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”,并将单词流作为其输入。实际开发中,语法分析器可以手工编写,也可以使用工具(半)自动生成。
3.2 需求分析
语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法的产生式,识别输入串是否是一个句子。自上而下分析法的主旨是,对任何输入串,试图用一切可能的方法,从文法开始符号出发,自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程,是反复使用不同产生式谋求匹配输入串的过程。
3.3 概要设计
语法分析器 能识别由加+ 减- 乘* 除/ 乘方^ 括号()操作数所组成的算术表达式,其文法如下:
E→E+T|E-T|T T→T*F|T/F|F F→P^F|P p→(E)|i 使用的算法可以是:预测分析法;递归下降分析法;算符优先分析法;LR分析法等
3.4 详细设计
语法分析器主程序图[4]
8
3.5 测试数据与结果
9
3.6 心得体会
此次实验,让我们组对编译原理的基本知识有了深入的了解,加强了对语法分析的认识。代码的编写过程中用到了一些以前从未用过的函数,都是现学现用,掌握还不是很深。在代码调试过程中结果出现许多无法解释的错误,但仍旧坚持下来了,最终调试出了结果。通过这次实验,我们组的动手实践能力得到很大的提高。
4 中间代码产生器的设计与实现 4.1 基础理论说明
在进行了语法分析和语义分析阶段的工作之后,有的编译程序将源程序变成一种内部表示形式,这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统,这种记号系统复杂性介于源程序语言和机器语言之间,容易将它翻译成目标代码。另外,还可以在中间代码一级进行与机器无关的优化。产生中间代码的过程叫中间代码生成。
4.2 需求分析
定义一种语言除了要求定义语法外,还要求定义语义,即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查,然后分析其含义,并用另一种语言形式,即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此,中间代码就显得十分重要,它关系着整个程序语言的正确编译与否,同时也是进行下一步编译的重要先决条件。
4.3 概要设计
产生上述算术表达式的中间代码(四元式序列) 递归下降子程序:
数据结构: SYN —算符栈;
SEM —语义栈;
10
4.4 详细设计
中间代码生成器流程图[5]:
11
4.5 测试数据与结果
4.6 心得体会
我们知道,定义一种语言除了要求定义语法外,还要求定义语义,即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查,然后分析其含义,并用另一种语言形式,即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此,中间代码就显得十分重要,它关系着整个程序语言的正确编译与否,同时也是进行下一步编译的重要先决条件。
12
参考文献
[1] Alfred D.Ullman.Compilers: Principles,Techniques,and Tools:4页 [2] zjbujs.百度文库.编译原理词法语法语义分析器设计.2013-07-23:5页 [3] zjbujs.百度文库.编译原理词法语法语义分析器设计.2013-07-23:6页 [4] 线性大树.百度文库. 编译原理词法语法语义设计实现.2014-06-06:8页
[5] LWH1989216.百度文库.编译原理词法分析和语法分析 (C语言版)2011-05-11:10页
13
附录:
附录A:主要源程序与系统截图
/*******************************词法分析器源代码******************************/ #include
#define MAX 150 //词法分析表的最大容量 #define MAXBUF 255//缓冲区的最大缓冲量 char prog[MAXBUF],token[MAX]; char ch;
int syn,p,m,n,sum;
char *rwtab[6]={\/////////////////////////////////////////////// //词法分析程序
/////////////////////////////////////////////// void scaner() {
for(m=0;m ch=prog[p++];//读取下一个字符; if(ch>=65&&ch<=122 /*是字母字符*/) { while(ch>=65&&ch<=122||ch>=48&&ch<=57)/*为字母字符或数字字符*/ { 14 token[m++]=ch; ch=prog[p++];//读取下一个字符; } token[m++]='\\0'; p=p-1; syn=10; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0) } { syn=n+1;//给出syn值; break; } else if(ch>=48&&ch<=57/*ch为数字字符*/) { } while(ch>=48&&ch<=57/*ch为数字字符*/) { sum=sum*10+ch-'0'; ch=prog[p++];//读取下一个字符; } p=p-1;//回退一个字符; syn=11; else switch(ch) { case '<': m=0;token[m++]=ch; ch=prog[p++];//读取下一个字符; if(ch=='>') 15 { syn=21; token[m++]=ch; } else if(ch=='=') { syn=22; token[m++]=ch; } else { syn=20; p=p-1;//回退一个字符; } break; case'>': token[m++]=ch;; ch=prog[p++];//读取下一个字符; if(ch=='=') { syn=24;//将>=的中别码=>syn; token[m++]=ch;; } else { syn=23; p=p-1;//回退一个字符; } break; case':': token[m++]=ch;; ch=prog[p++];//读取下一个字符; 16 if(ch=='=') { syn=18; token[m++]=ch;; } else { syn=17; p=p-1;//回退一个字符; } break; case'+': syn=13;token[0]=ch; break; case'-': syn=14;token[0]=ch; break; case'*': syn=15;token[0]=ch; break; case'/': syn=16;token[0]=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=0;token[0]=ch; break; default: syn=-1; 17 } } break; /////////////////////////////////////////// //主函数 /////////////////////////////////////////// void main() { char A; cout<<\loop: p=0; cout<<\ printf(\以#结束):\\n\ do { } while(ch!='#'); p=0; do { scaner(); switch(syn) { case 11:cout<<\输出(数的二元组); break; case -1:cout<<\ break; 18 scanf(\ prog[p++]=ch;//输入源程序字符串,送到缓冲区prog[p++]中; default:cout<<\输出(其他单词二元组); } }while(syn!=0); cout<<\cout<<\请确定是否继续使用程序:S为继续;其它为退出;\cout<<\是否继续:\cin>>A; switch(A) { case 'S': goto loop; default: cout<<\ cout<<\ cout<<\ break; } } 结果: 19 /*******************************语法分析器源代码******************************/ #include char a[50] ,b[50],d[200],e[10]; 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(); 20 void input(); void input1(); void output(); void main() /*递归分析*/ { int f,p,j=0; char x; d[0]='E'; d[1]='='; d[2]='>'; d[3]='T'; d[4]='G'; d[5]='#'; printf(\ do{ scanf(\ a[j]=ch; j++; }while(ch!='#'); n1=j; ch=b[0]=a[0]; printf(\步骤\\t文法\\t分析串\\t\\t分析字符\\t剩余串\\n\ f=E1(); if (f==0) return; if (ch=='#') { printf(\ p=0; x=d[p]; while(x!='#') { printf(\ /*输出推导式*/ } } else { printf(\ printf(\回车返回\\n\ getchar();getchar(); return; } 21 printf(\ printf(\回车返回\\n\ getchar(); getchar(); } int E1() { int f,t; printf(\ 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(\ e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#'; 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(\ 22 e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#'; 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=='+') { b[i1]=ch; printf(\ e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#'; output(); flag=0; input(); input1(); ch=a[++i1]; f=T(); if (f==0) return(0); G(); return(1); } printf(\ e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#'; output(); flag=1; input();input1(); return(1); 23 } int S() { int f,t; if(ch=='*') { b[i1]=ch;printf(\ e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#'; output(); flag=0; input();input1(); ch=a[++i1]; f=F(); if (f==0) return(0); t=S(); if (t==0) return(0); else return(1);} printf(\ e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#'; output(); flag=1; a[i1]=ch; input(); input1(); return(1); } int F() { int f; if(ch=='(') { b[i1]=ch;printf(\ e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#'; output(); 24 flag=0; input(); input1(); ch=a[++i1]; f=E(); if (f==0) return(0); if(ch==')') { b[i1]=ch;printf(\ flag=0;input();input1(); ch=a[++i1]; } else { printf(\ return(0); } } else if(ch=='i') { b[i1]=ch;printf(\ e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#'; output(); flag=0;input();input1(); ch=a[++i1]; } else {printf(\ return(1); } void input() { 25 int j=0; for (;j<=i1-flag;j++) printf(\ /*输出分析串*/ printf(\ printf(\ /*输出分析字符*/ } void input1() { int j; for (j=i1+1-flag;j printf(\ /*输出剩余字符*/ printf(\ } void output(){ /*推导式计算*/ int m,k,j,q; int i=0; m=0;k=0;q=0; i=n; d[n]='=';d[n+1]='>';d[n+2]='#';n=n+2;i=n; i=i-2; while(d[i]!='>'&&i!=0) i=i-1; i=i+1; while(d[i]!=e[0]) i=i+1; q=i; m=q;k=q; while(d[m]!='>') m=m-1; m=m+1; while(m!=q) { d[n]=d[m];m=m+1;n=n+1; 26 } d[n]='#'; for(j=3;e[j]!='#';j++){ d[n]=e[j]; n=n+1; } k=k+1; while(d[k]!='=') { d[n]=d[k];n=n+1;k=k+1; } d[n]='#'; } 结果: 27 /****************************中间代码生成器源代码******************************/ #include #define DEFAULT_SIZE 100 char EMachine(char w); //表达式E的自动机 char TMachine(char w); //表达式T的自动机 char FMachine(char w); //表达式F的自动机 bool ZMachine(); //表达式Z的自动机 string intToString(int 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-1); } void clear(void) { top=-1; } }; stack::stack(int size) //栈类的构造函数 { top=-1; maxsize=size; stacka=new string[maxsize]; if(!stacka) { cerr<<\ exit(1); } } void stack::push(const string &item) //压栈操作 { 28 if(full()) { cerr<<\ return; } top++; stacka[top]=item; } string stack::pop(void) //出栈操作 { if(empty()) { cerr<<\ exit(1) ; } string item=stacka[top]; top--; return item; } string stack::gettop(void) const //取栈顶操作 { if(empty()) { cerr<<\ exit(1) ; } return stacka[top]; } static stack wordStack; //符号栈 static int noOfQuet=0; //静态四元式个数记录 static int noOfT = 1; //静态状态个数记录 void main(){ //主函数 char yesOrNo; //进行一个循环操作控制 do{ cout<<\请输入算术表达式:\ noOfT = 1; //每次结束询问 ZMachine(); cout< 29 } bool ZMachine(){ //Z自动机 char w; cin>>w; w = EMachine(w); //调用E自动机 if(w=='#'){ //遇到“#”则结束 return true; } else{ return false; } } char EMachine(char w){ //E自动机 string operate,a,b,c; string state[5]; w = TMachine(w); //调用T自动机 while(w=='+'||w=='-'){ //是加或减符号 operate = w; cin>>w; //读入下一字符 w = TMachine(w); //调用T自动机 b = wordStack.pop(); //字符栈弹出 a = wordStack.pop(); //两个操作字符 cout<<\ c = \ //输出四元式 wordStack.push(c); //新状态压栈 noOfT++; //状态计数加一 } return w; } char TMachine(char w){ string operate,a,b,c; string state[5]; w = FMachine(w); //调用F自动机 while(w=='*'||w=='/'){ //是乘除号 operate = w; cin>>w; //读取下一字符 w = FMachine(w); //调用F自动机 b = wordStack.pop(); //符号栈弹出 a = wordStack.pop(); //两个操作字符 cout<<\ c = \输出四元式 30 wordStack.push(c); //新状态压栈 noOfT++; //状态计数加1 } return w; } char FMachine(char w){ //F自动机 string theWord; if(w>='a'&&w<='z'||w>='A'&&w<='Z'){ theWord = w; //当前字符是字母 wordStack.push(theWord); //则压栈 } else if(w == '('){ //是左括号 cin>>w; //则读取下一字符 w = EMachine(w); //调用E自动机 if(w!=')'){ //不是右括号则输入有误,报错 cerr<<\ exit(0); } } else{ //否则有误,报错 cerr<<\ exit(0); } cin>>w; //读取下一字符 return w; } string intToString(int a){ //整形变字符串形函数 string d; char b='0',c; int i; while(a!=0){ i = a; a = a/10; c = (int)b + i; d = c + d; } return d; } 31 结果: //y=a+b //Y=a+b*(c-d) 32 附录B: 任务分配表及个人完成的程序模块 任务分配表 33 整理word文档,搜集代码程序资料 搜集代码程序资料,调试程序 整理文档,程序,完成PPT 附录C: 小组讨论与研发记录 2014-12-16 9:00-11:00 讨论课程设计需求,明确分工 2014-12-16 13:00-16:00 搜集相关资料,编写word文档 2014-12-17 11:00 整理word文档,讨论ppt演示内容 2014-12-17 15:00 讨论修改ppt 34
正在阅读:
钻井防喷模拟控制系统研究06-08
12.8材料科学研究与分析方法复习题最新答案 - 图文03-17
进口汽车维修技术缩略英语词典06-13
工程保修方案11-08
蜂群算法在路径优化上的应用09-21
高中完形填空练习题及答案10篇01-19
电大专科刑事诉讼法学历年试题及答案01-19
矿井通风设计06-11
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 编译器
- 编译
- 原理
- 课程
- 简单
- 实现
- 报告
- 精品
- 设计
- 高层建筑电气安装接地的施工技术分析
- 9届高三暑假第二次阶段性测试数学(理)试题(附答案)
- 精确叫牌之精髓
- 小区停车场车位自动显示系统 - 图文
- 海南华电老城天然气分布式能源工程环境影响报告书简本
- 服装缝纫基础 - 图文
- 东北大学17春法学计算机硬件技术基础试卷B徐彬(线下)作业参考答
- 顶管施工(修改1111) - 图文
- 课题调研报告格式
- 考研数学重点难点归纳辅导笔记及概率易错知识点总结
- 礼泉县大事记
- 数字图象处理第二次作业
- 证券从业资格考试《基础知识》出题方法举例分析
- 第五课 跑过冬天
- 陕西省2017-2018学年八年级(上)期中数学试卷及答案
- 交通运输-1114190601-卞文峰-基于Matlab的飞机高压直流电源系统
- 办理浦东新区“十三五”期间安商育商财政扶持资格认定所需材料
- 资产评估期末复习 2
- 运动会秩序册(最新)
- 组织部组织人事科科长岗位竞职演讲稿