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

成绩：

课 程 设 计

题 目：
简单编译器实现
学 院：
信息工程学院计算机系
专 业：
计算机科学与技术
班 级：
计科1103班
组 长：

小组成员：

指导教师：

2014
年
12
月
19
日

目录
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

1 概述
编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。
其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法，当然两种方法也可以同时使用。语法分析器把语法单元作为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法，即在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。

1.1源、目标语言简介
使用C语言做简单语法分析器，C语言是一门高级计算机编程语言，设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言
1.2实现平台与运行平台简介
在win32环境下进行编译，Win32是指Microsoft Windows操作系统的32位环境，是目前使用最多的操作系统。
实验环境：需要TC、VC++ 6.0等开发工具作为本次试验的环境。
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
-
-
-
-
-
-
内部字符串
标准二进形式
-
-
-
-
-
-

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

词法分析器的流程图[3]

2.5 测试数据与结果

2.6 心得体会
设计该词法分析器的过程中虽然没有实际将所有的状态转移表建立出来，但是所用的思想是根据状态转移表实现对单词的识别。首先构造一个保留字表,然后,每输入一个字符就检测应该进入什么状态,并将该字符连接到d串后继续输入,如此循环,最后根据所在的接受状态以及保留字表识别单词
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]

3.5 测试数据与结果

3.6 心得体会
此次实验，让我们组对编译原理的基本知识有了深入的了解，加强了对语法分析的认识。代码的编写过程中用到了一些以前从未用过的函数，都是现学现用，掌握还不是很深。在代码调试过程中结果出现许多无法解释的错误，但仍旧坚持下来了，最终调试出了结果。通过这次实验，我们组的动手实践能力得到很大的提高。
4 中间代码产生器的设计与实现
4.1 基础理论说明
在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。产生中间代码的过程叫中间代码生成。
4.2 需求分析
定义一种语言除了要求定义语法外，还要求定义语义，即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式，即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此，中间代码就显得十分重要，它关系着整个程序语言的正确编译与否，同时也是进行下一步编译的重要先决条件。
4.3 概要设计
产生上述算术表达式的中间代码（四元式序列）
递归下降子程序：
数据结构： SYN —算符栈；
SEM —语义栈；

4.4 详细设计
中间代码生成器流程图[5]：

4.5 测试数据与结果

4.6 心得体会
我们知道，定义一种语言除了要求定义语法外，还要求定义语义，即对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式，即比源语言更加接近于目标语言的一种中间代码来进行描述这种语言。因此，中间代码就显得十分重要，它关系着整个程序语言的正确编译与否，同时也是进行下一步编译的重要先决条件。
参考文献
[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页

附录：
附录A：主要源程序与系统截图
/*******************************词法分析器源代码******************************/
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#define MAX 150 //词法分析表的最大容量
#define MAXBUF 255//缓冲区的最大缓冲量
char prog[MAXBUF],token[MAX];
char ch;
int syn,p,m,n,sum;
char *rwtab[6]={"begin","if","then","while","do","end"};
///////////////////////////////////////////////
//词法分析程序
///////////////////////////////////////////////
void scaner()
{
for(m=0;m<MAX;m++)
token[m]=NULL;
m=0;sum=0;
ch=prog[p++];
while(ch==' ')
ch=prog[p++];//读取下一个字符;

if(ch>=65&&ch<=122 /*是字母字符*/)
{
while(ch>=65&&ch<=122||ch>=48&&ch<=57)/*为字母字符或数字字符*/
{
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=='>')
{
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++];//读取下一个字符；
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;
break;
}
}
///////////////////////////////////////////
//主函数
///////////////////////////////////////////
void main()
{
char A;
cout<<"*****************************************"<<endl;
loop:
p=0;
cout<<"*****************************************"<<endl;
printf("please input string (以#结束):\n");
do
{
scanf("%c",&ch);
prog[p++]=ch;//输入源程序字符串，送到缓冲区prog[p++]中；
}
while(ch!='#');
p=0;
do
{
scaner();
switch(syn)
{
case 11:cout<<"( "<<syn<<","<<sum<<" )"<<endl;//输出（数的二元组）；
break;
case -1:cout<<"error"<<endl;
break;
default:cout<<"( "<<syn<<","<<token<<" )"<<endl;//输出(其他单词二元组);
}
}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 !"<<endl;
cout<<"*****************************************"<<endl;
break;
}
}
结果：

/*******************************语法分析器源代码******************************/

#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>

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();

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("Please input character string(length<50,end of '#'):\n");

do{
scanf("%c",&ch);
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("\nAccept! Right Expression!\n\n");
p=0;
x=d[p];
while(x!='#') {
printf("%c",x);p=p+1;x=d[p]; /*输出推导式*/
}
}
else {
printf("\nError!!!\n");
printf("回车返回\n");
getchar();getchar();
return;
}
printf("\n");
printf("回车返回\n");
getchar();
getchar();
}

int E1()
{ int f,t;
printf("%d\tE-->TG\t",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("%d\tE-->TG\t",total);total++;

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("%d\tT-->FS\t",total);total++;
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("%d\tG-->+TG\t",total);total++;
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("%d\tG-->^\t",total);total++;

e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';

output();
flag=1;
input();input1();
return(1);

}

int S()
{

int f,t;

if(ch=='*') {
b[i1]=ch;printf("%d\tS-->*FS\t",total);total++;
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("%d\tS-->^\t",total);total++;
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("%d\tF-->(E)\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';

output();
flag=0;
input();
input1();

ch=a[++i1];
f=E();

if (f==0) return(0);
if(ch==')') {

b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;

flag=0;input();input1();
ch=a[++i1];

}

else {

printf("\nError!!!\n");
return(0);

}
}
else if(ch=='i') {

b[i1]=ch;printf("%d\tF-->i\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];

}

else {printf("\nError!!!\n");return(0);}

return(1);

}

void input()

{

int j=0;

for (;j<=i1-flag;j++)
printf("%c",b[j]); /*输出分析串*/

printf("\t\t");
printf("%c\t\t",ch); /*输出分析字符*/

}

void input1()
{

int j;

for (j=i1+1-flag;j<n1;j++)
printf("%c",a[j]); /*输出剩余字符*/
printf("\n");

}

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;

}

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]='#';

}
结果：

/****************************中间代码生成器源代码******************************/
#include<string>
#include <iostream>
using namespace std;

#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<<"a