编译原理实验(1).doc

实验一 编写词法实验程序
（题目字体为华文中宋，三号字体）
一.实验小组成员及任务分解（黑体，小四）
本组共有4个成员，本组全总成员参与程序代码的输入，每人输入2到3张程序代码不等，最后合并每个成员输入的程序段进行编译连接，修改错误，最终改正了程序，得到了正确的运行结果，最后制作出了实验报告电子文档。实验过程中每一个成员的任务如下：
姓名
任务
杨成凡
程序代码输入、编译、报告制作
刘春香
程序代码输入、编译、报告制作
曹卓
程序代码输入、编译、报告制作
李论
编译、报告制作
二.实验目的和要求（黑体，小四）
通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法;熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高此法分析方法的实践能力。通过本实验达到一下目标：
1、掌握从源程序文件中读取有效字符的方法和生产源程序的内部表示文件的方法。
2、掌握此法分析的实现方法。
3、上机调试编出的词法分析程序。
三. 背景知识（黑体，小四）
词法分析的背景知识：词法分析就是把组成说明和语句的单词逐个识别出来，给出单词的类别及其他属性，以供语法分析用。执行词法分析功能的程序称为词法分析程序，也称为词法分析器或词法扫描器，词法分析器可借助于有限自动机等工具手工构造或自动生成。
词法分析器的作用：
词法分析器（也称词法分析程序）的主要作用是根据单词的文法，把源程序中的单词逐个识别出来，并给出各个单词包括类别在内的属性。一般的高级语言中，单词由如下几个类别：
（1） 标识符；
（2） 关键字*（从文法上看，关键字集合是标识符集合的子集合）；
（3） 常数，包括整常数、实常数（或称浮点数）、字符常数、字符串常数等；
（4） 运算符，如+，—，*，/等；
（5） 分隔符，如逗号（，）、冒号（：）、分号（；）等。
词法分析器每识别出一个单词，要给出该单词所属的类别，此外还要给出该单词（语法分析需的）其他属性。对于标识符来说，还要给出它的源程序表示（即构成标识符的字符串）；对于关键字来说，还要给出它在关键字表中的地址或序号；对常数来说，还要给出它在常数表中的地址或序号；对于运算符和分隔符，还要给出它的源程序表示（即源程序中的形式）或编号。
词法分析器还提供单词在源程序中的位置信息，即行号和列号，也供错误处理部分使用。在分析过程中，词法分析器要略掉源程序中的注释。
词法分析器的构造方法：构造词法分析器既可以手工完成，也可以利用LEX处理系统自动完成。手工构造词法分析器一般都借助于状态转移图 。状态转移图是一个有穷有向图，它关联一个入字母表。图中的结点代表状态，状态之间的有向边标有取自输入字母表中的字母。图中的状态有一个是初始状态，还有若干个终止状态。在描述单词识别过程的转移图中，当尚未读取构成单词的任何字符时，处于初始状态；处于某个终止状态时，表示识别出一个单词。通常，在初始状态左边加一个箭头，以表示它是初始状态；终止状态用双圆圈表示，非终止状态用单圆圈表示。状态0是初始状态，处于状态0时，表示尚未读入构成标识符的任何字符；到状态1时，表示已读入了若干个字母、数字，并且读入的第1个字符一定是字母；到状态2时，表示已识别出一个标识符，即读入的字符序列恰好 构成了一个标识符。状态2右边加一个*，表示到达该状态时，多读了一个不属于标识符的字符。LEX是一个词法分析器的自动生成系统。LEX语言可用于描述单词的结构，LEX处理系统根据LEX语言源程序提能吸供单词结构信息，自动生成分析这些单词的词法分析程序。LEX语言用正则表达式描述单词的结构，LEX处理系统根据LEX语言中的描述单词结构正则式R生成相应的有限状态自动机M,满足L(R)=L(M),再根据M生成相应的词法分析程序。
此法分析师作为相对独立的阶段来完成的。在词法分析的过程中，编译程序是通过操作系统从外部介质中读取源程序文件中的各个字符的。同时为正确的 识别单词，有时还需进行超前搜索和回退字符等操作。因此，为了提高读盘效率和便于扫描器进行工作，通常可以采取缓冲输入的方案，即在内存中设置一个适当大小的输入缓冲区，让操作系统直接将磁盘上的源程序字符串分批送入此缓冲区中，供扫描器进行处理。
四. 实验内容及算法设计
#include<iostream.h>
#include<string.h>
char *KeyWord[32]={"auto","break","case","char",
"const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed","sizeof",
"static","struct","switch","typedef","union","unsigned",
"void","volatile","while"};
int i=0,j=0,k=0,t=0;
char ch;
char strToken[20];
char *chr_form[100];
char *int_form[100];
char form[1000];
int q=0;

void GetChar()
{
ch=form[k];
k++;
}
void GetBC()
{
while(ch==' '){
GetChar();
}
}

void Concat()
{
strToken[i]=ch;
i++;
}
bool isLetter()
{
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
return true;
else
return false;
}
bool isDigit()
{
if(ch>='0'&&ch<='9')
return true;
else
return false;
}
//第3，4篇

//第5，6页
int SearchKeyWord(){
for(int q=0;q<32;q++){
if(strcmp(strToken,KeyWord[q]))
return q;//是关键字
if(q==32)return -1;//是字符串
}
}
void Reset(){
k--;
ch=NULL;
}
char*InsertChar(){//将strToken中的标识符插入符号表，返回符号表的指针
chr_form[j]=strToken;
j++;return chr_form[0];
}
char*InsertInt(){//将strToken中的常数插入长鼠标，返回常数表指针
int_form[t]=strToken;
t++;
return int_form[0];
}
int code;
void analyze()
{
GetChar();
GetBC();
if(isLetter())
{//如果是字符
while(isLetter()||isDigit())
{
Concat();
GetChar();
}
Reset();
code=SearchKeyWord();
switch(code){
case-1:cout<<"<字符串,"<<strToken<<">"<<endl;break;
default:cout<<"<关键字"<<","<<strToken<<">"<<endl;break;}
}
else
{
if(isDigit())//是数字
{
while(isDigit()||ch=='.'){
Concat();
GetChar();
}
Reset();
cout<<"<是数字,"<<strToken<<">"<<endl;
}
else
{
switch(ch){
case '=':
case '*':
case '%':cout<<"运算符,"<<ch<<">"<<endl;break;
case '_':GetChar();
if(ch=='_')cout<<"<运算符,__>"<<endl;
else{Reset();cout<<"<运算符,_>"<<endl;}
break;
//第7页
case'+':GetChar();
if(ch=='+')cout<<"<运算符,++>"<<endl;
else{Reset();cout<<"<运算符,+>"<<endl;}
break;
case'|':GetChar();
if(ch=='|')cout<<"<运算符,||>"<<endl;
else{Reset();cout<<"非法符号"<<endl;}
break;
case'&':GetChar();
if(ch=='&')cout<<"<运算符,&&>"<<endl;
break;
case'/':GetChar();
if(ch=='/'){
do{GetChar();}
while(ch!='\n');
cout<<"<注释,//>"<<endl;
}
else{Reset();cout<<"<注释,/>"<<endl;}
break;
case';':
case'(':
case')':
case'{':
case'}':
case'[':
case']':
case':':
case',':
case'"':cout<<"<界符, "<<ch<<">"<<endl;break;
case'<':GetChar();

//第8页
if(ch=='<')cout<<"<运算符，<<>"<<endl;
else{Reset();cout<<"<界符，>>"<<endl;}
break;
case'>':GetChar();
if(ch=='+')cout<<"<运算符，>>"<<endl;
else{Reset();cout<<"<界符，>>"<<endl;}
break;
}
}
}
while(k<q)
{
for(int p=0;p<20;p++)
strToken[p]='\0';
i=0;
analyze();
}
}
void main()
{
cout<<"请输入一段C语言程序，以符号@结尾:"<<endl;
form[0]=cin.get();
for(q=1;form[q-1]!='@';q++){
form[q]=cin.get();
if(form[q]='@'){
cout<<"你输入的程序段为："<<endl;
cout.write(form,q);
cout<<endl;
break;
}
}
analyze();
}
五. 上机实现情况及运行结果（包括中间和最终结果）
本组发扬团结互助精神，分工合作，每一位同学都积极参与本门课程的实验，优秀的完成了各自的任务。各组员参与代码的输入，每人完成输入1到3页代码不等，最后综合起来合成一个程序。这个程序有众多的输入错误，经过全体组员的共同努力、仔细观察、动脑动手，亲自实验，解决了实验中遇到的难题和错误，运行出正确的结果如下：

六.小结
该程序虽然显示输入一短C语言程序以 @结尾，但是输入一些符号后一打回车就执行结果了，并且执行的结果也不是太正确，只能判断输入的第一个字符是什么符号。因为输入的一段是C语言程序，至少应能判断所输入的所有符号。
本组成员做事认真细心，一丝不苟，所以在输入过程中，几乎都是正确的，仅有个别字母输入错误而以，在调试过程式中，便一一发现其中的错误并给予纠正，但在“case'"':cout<<"<界符, "<<ch<<">"<<endl;break;”的输入过程中值得注意，在表面上很难看出来其中有什么的欺别，其实只要你仔细观察便可想到case语句后的语法是常量是由单引号引起的，怎么会是两面三刀个双引号呢，只是表面上看不容易发现，两个两引号和由单引号+双引号+单引号是极为相似的，本组输入时就是两个双引号，导致了调试时的一些困惑，但在全体组员的共同努力和思索下，得出了正确的结果。通过对词法分析程序的调试，我们又上了一课关于C++实验课，这一节课让我们对C++的认识更加深刻，了解更加彻底，同时也了解到词法分析器和有限自动机的一些关系，认识了我们的C，C++运行环境就是在词法分析器作用下判断源程序的符号，对源程序的符号进行识别。

八.参考文献
[ 1 ] 金成植.编译程序构造原理和现实技术.北京：人民邮电出版社，2006.
[ 2 ]张海藩，牟永敏，面向对象程序设计使用教程[M],北京：清华大学出版社，2001
[ 3 ]吕映之，编译原理，北京，清华大学出版社，1998
[ 4 ]杜淑敏，编译原理，北京，北京大学出版社，1990
九.实验成绩