编译原理课程设计.doc

编译原理课程设计

自顶向下语法分析器

学 院（系）： 计算机科学与技术学院
学 生 姓 名： xxxxxxxxx
学 号： xxxxxxxxx
班 级： 电计1102

大连理工大学
Dalian University of Technology

目 录
1 系统概论 1
2 需求分析 2
3 系统设计 2
4 系统实现 4
5 使用说明 4
5.1 程序运行平台 4
5.2 程序中所有定义的函数 5
5.3 文档说明 6
5.4 调试分析 7
6 课程设计总结 12
参考文献 12
附录：重要代码 13

I

编译原理课程设计
1 系统概论
语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示：

图1 语法分析器在编译程序中的地位

语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。
自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。
自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。
实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。

2 需求分析
以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快语法的分析，故设计了这个自顶向下的语法分析器。人们只要运行程序，输入几个简单的命令或语法，就能求出人们所需要的各种结果。虽然程序设计有一定的局限性，但在这个局限中却能如人们的要求对语法进行分析，从而在一定程度上帮助人们更好的完成工作。

3 系统设计
自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶自顶向下的分析程序有两类：回溯分析程序（backtracking parser）和预测分析程序（predictive parser）。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢，一般都在指数的数量级上，所以对于实际的编译器并不合适。
递归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作First集合和Follow集合。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序。
1、LL(1)文法
LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=Ø。这样，当前非终结符A面临输入符a时，如果a∈SELECT(A：=a)，则可以选择产生式A:=a去准确匹配。
如本程序中举例说明的a.txt的文法就是一个LL（1）文法：
S:=aBc|bAB
A:=aAb|b
B:=b|0
2、文法的左递归
当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AÞA…，则称该文法是左递归的。
左递归又可以分为直接左递归和间接左递归。
3、直接左递归
若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。
消除直接左递归的方法：
设有产生式是关于非终结符A的直接左递归：A→Aα|β （α,β∈V*，且β不以A开头）
对A引入一个新的非终结符A′，把上式改写为：
A →βA′
A′→αA′|ε
4、间接左递归
若文法中存在某一非终结符A，使得AÞA…至少需要两步推导，则称该文法是间接左递归的。
消除间接左递归的方法：
【方法一】采用代入法把间接左递归变成直接左递归。
【方法二】直接改写文法：设有文法G10[S]：
S→Aα|β ⑴
A→Sγ ⑵
因为SÞAαÞSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：
S→Sγα|β ⑶
⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：
S→βS′
S′→γαS′|ε
4 系统实现

系统流程图
5 使用说明
5.1 程序运行平台
Visual C++ 6.0
Windows XP SP2
5.2 程序中所有定义的函数
class Syntax_analysis
{
public:
char stotax[30][20]; //存放文法规则
char soudocu[1000]; //用于存放打开的文件内容
int sto_tax; //存放产生式总数
char firstchars[30]; //某个串的first集(可能有重复)
int first_num; //first集长度
char followchars[1000];
//存放某个非终结符的follow集(如果有(间接)右递归,可能有较大重复)
int follow_num; //follow集长度
int follownumkey; //用于判断右递归或间接右递归
char followkey;
char selectchars[30][30]; //存放每条产生式的select集
char colec0[30]; //存入所有能推导出0的非终结符
int colec0num; //能推导出0的非终结符个数
char capital; //第一个未被使用的大写字母
char preanatab[130][130][20];
//存放预测分析表,分别为非终结符(将字母转化为数字)、终结符(将字母转化为数字)、产生式
char _stotax[30][20]; //临时的stotax备份
int _sto_tax; //临时的_sto_tax备份
char startchar; //开始文法符号
char keylr;
char save[1000]; //保存结果到外存储器
char lie[20];
int li;
char hang[20];
int han;
int ll_key;
int input_key;
Syntax_analysis(){}
void openfile() //打开文件
void getin() //对读取出来的文件内容,推导式分解并保存在stotax数组中
void disp() //显示方法推导式
void get_in() //输入推导式,并保存stotax数组中
void save_file(char p[]) //保存到外存储器
void Delpare() //消除左递归
void findcapital() //查找未被使用的大写字母,把第一个未被使用的大写字母保存在capital中
void First_Collection(char p[]) //求字符串p的first集,把结果保存在数组firstchars[30]中
void Follow_Collection(char p) //求字符p的follow集,把结果保存在数组followchars中
void Select_Collection() //求每条产生式的select集,存放在数组selectchars[30][30]中
void Estab_preanatab() //创建预测分析表
void dispselect() //显示选择
void base_()
void disp_table() //打印预测分析表
void Analyse_course() //分析过程
void deduce0_colec() //将所有能推导出0的非终符放在数组colec0[30]中
void dispfirst() //显示First集
void dispfollow()
}
5.3 文档说明
文档
文法
句子
a.txt
LL(1)文法
baabbb#、baaabbbb#....
b.txt
直接左递归
abbbbb(可以任意多少个b)
c.txt
间接左递归
abbbbb(可以任意多少个b)
d.txt
LL(1)文法
maebn#...
5.4 调试分析
程序运行说明：
适应的文法类型：
1、一切LL(1)文法
2、含有直接左递归但可以转化为LL(1)文法的文法
3、含有间接左递归但可以转化为LL(1)文法的文法
说明：
1、文法表达方式
例如：S:=Aa|Bb，其中空串用数字0代替，每输入一个表达式换行写下一表达式
2、文法输入结束后，换行再按‘#’结束
3、需要输入命令来执行所需要的功能
命令说明：
Cmd命令
功能
open
从外存储器打开某文法
input
从键盘输入文法
lltab
查看预测分析表
select
查看每条产生式的SELECT集
first
求所输串的FIRST集
follow
求所输非终结符的FOLLOW集
ll
对某个输入句子进行分析
exit
退出程序

程序运行主界面：

（1）open：打开文件
打开附带文档a.txt
a.txt文档中的文法为LL(1)文法：
S:=aBc|bAB
A:=aAb|b
B:=b|0

（2）input：输入文法
输入文法过程中“ε”应用“0”代替使用
每输入一条新文法需重新另起一行
文法输入结束后换行以“＃”结束
输入文法后若要保存文件，请按“y”键，并按提示输入备份文件的路径和名称。若没有输入备份路径，文法则保存在默认路径（程序所在文件夹）中；若不进行保存，则键入除“y”键外的任意键退出当前命令。

打开a.bck.txt文档，可以看到文法：

（3）lltab：预测分析表
打开文件a.txt，对文档中语法进行分析：

（4）select：查看每条产生式的SELECT集
打开文件a.txt，求文档中语法的SELECT集

（5）first：求所输串的FIRST集
打开文件a.txt，求文档中语法的FIRST集
若需要继续求FIRST集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。

（6）follow：求所输非终结符的FOLLOW集
打开文件a.txt，求文档中语法的FOLLOW集
若需要继续求FOLLOW集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。

（7）ll：对某个输入句子进行分析
打开文件a.txt，输入要分析的字符串进行分析

（8）exit：推出程序
输入exit命令退出

6 课程设计总结
在三周的课程设计中，我设计了一个自顶向下的语法分析器。由于涉及大量的编译原理知识，且编程过程复杂，代码量大，完成的功能并不是很多，而且也不是很完善，设计过程难免出现或多或少的错误。由于时间有限，无法对程序进行很好的测试，只发现其中的一些小错误并加以改进和完善，对其他未发现的BUG，只能尽量避免其出现。倘若有足够多的时间，我相信我可以做出需求分析中要求的功能，使其满足人民的要求，减少人工操作，减少运算时间，避免由于人工计算出现的错误，最终加快人们对语法的分析，减少人们的工作量。
虽然三周的课程设计时间短，但却使我受益匪浅，通过这次课程设计我把课本中的理论转化成实际运用，从中加深了理论认识，为以后的后续学习奠定基础；并且在编程过程的资料查找和程序编制中掌握了编程的一些基本思路和构想，为以后的程序设计奠定了基础。

参考文献
1、陈火旺，刘春林. 《程序设计语言 编译原理》(第3版）. 国防工业出版社. 2000年
2、李建中，姜守旭. 《编译原理》. 机械工业出版社. 2003年年12月.
3、（美）阿佩尔，（美）金斯伯格. 《现代编译原理：C语言描述》. 人民邮电出版社. 2005年09月.

附录：重要代码
#include"stdio.h"
#include"string.h"
#include"iostream.h"
#include"ctype.h"
#include"fstream.h"

class Syntax_analysis
{
public:
char stotax[30][20]; //存放文法规则
char soudocu[1000]; //用于存放打开的文件内容
int sto_tax; //存放产生式总数
char firstchars[30]; //某个串的first集(可能有重复)
int first_num; //first集长度
char followchars[1000]; //存放某个非终结符的follow集(如果有(间接)右递归,可能有较大重复)
int follow_num; //follow集长度
int follownumkey; //用于判断右递归或间接右递归
char followkey;
char selectchars[30][30]; //存放每条产生式的select集
char colec0[30]; //存入所有能推导出0的非终结符
int colec0num; //能推导出0的非终结符个数
char capital; //第一个未被使用的大写字母
char preanatab[130][130][20]; //存放预测分析表,分别为非终结符(将字母转化为数字)、终结符(将字母转化为数字)、产生式
char _stotax[30][20]; //临时的stotax备份
int _sto_tax; //临时的_sto_tax备份
char startchar; //开始文法符号
char keylr;
char save[1000]; //保存结果到外存储器
char lie[20];
int li;
char hang[20];
int han;
int ll_key;
int input_key;
Syntax_analysis(){}

void openfile() //打开文件
{
input_key=0;
int i=0;
ifstream infile;
char path[255];
cin>>path;
infile.open(path);
if (infile.is_open())
{
while (infile.good())
soudocu[i++]=(char)infile.get();
infile.close();
soudocu[i]='#';
}
else
{
cout<<"Error opening file";
}
}

void getin() //对读取出来的文件内容,推导式分解并保存在stotax数组中
{
int cout=0;
char c;
char interim[50];
int i=0;
sto_tax=0;
again:
c=soudocu[cout++];
while(c!='#')
{
if(c!='\n')
{//把一行内容存放在interim数组里
if(c!=' ') interim[i++]=c;
c=soudocu[cout++];
}
else
{
if(!isupper(interim[0])||interim[1]!=':'||interim[2]!='=')
{//如果行首不是以大写字母:=这种格式,则输出错误信息
printf("The Syntax is wrong! please enter again:\n");
i=0;
goto again;
}
else
{
//字符数组加结束符
interim[i]='\0';
int m=0;
for(int j=0;j<strlen(interim);j++)
{//把后选式进行分解成一个个产生式
//如A:=a|b分解成A:=a,A:=b
if(interim[j]!='|')
{
stotax[sto_tax][m++]=interim[j];
continue;
}
else
{
stotax[sto_tax][m]='\0';
sto_tax++;
stotax[sto_tax][0]=stotax[sto_tax-1][0];
stotax[sto_tax][1]=stotax[sto_tax-1][1];
stotax[sto_tax][2]=stotax[sto_tax-1][2];
m=3;
continue;
}
}
stotax[sto_tax][m]='\0';
sto_tax++;
i=0;
c=soudocu[cout++];
}
}
}
startchar=stotax[0][0];
}

void disp() //显示方法推导式
{
for(int i=0;i<sto_tax;i++)
cout<<stotax[i]<<endl;
}

void get_in() //输入推导式,并保存stotax数组中
{
char c;
if(input_key==0) c=getchar();
input_key=1;
char interim[50];
int i=0;
sto_tax=0;
again:
c=getchar();
while(c!='#')
{
if(c!='\n')
{
if(c!=' ') interim[i++]=c;
c=getchar();
}
else
{
if(!isupper(interim[0])||interim[1]!=':'||interim[2]!='=')
{
printf("The Syntax is wrong! please enter again:\n");
i=0;
goto again;
}
else
{
interim[i]='\0';
int m=0;
for(int j=0;j<strlen(interim);j++)
{
if(interim[j]!='|')
{
stotax[sto_tax][m++]=interim[j];
continue;
}
else
{
stotax[sto_tax][m]='\0';
sto_tax++;
stotax[sto_tax][0]=stotax[sto_tax-1][0];
stotax[sto_tax][1]=stotax[sto_tax-1][1];
stotax[sto_tax][2]=stotax[sto_tax-1][2];
m=3;
continue;
}
}
stotax[sto_tax][m]='\0';
sto_tax++;
i=0;
c=getchar();
}
}
}
startchar=stotax[0][0];
int sav=0;
save[sav]='\0';
printf("save it? press 'y' to save or other to continue\n");
char command[30];
cin>>command;
if(!strcmp(command,"y"))
{
for(int i=0;i<sto_tax;i++)
{
strcat(save,stotax[i]);
sav=strlen(save);
save[sav]='\n';
save[sav+1]='\0';
}
save_file(save);
}
char g;
g=getchar();
}

void save_file(char p[]) //保存到外存储器
{
char filepath[30];
cout<<"Please enter the path and file name"<<endl;
cin>>filepath;
ofstream ofs(filepath);
ofs.write(p,strlen(p));
ofs.close();
}

void Delpare() //消除左递归
{
ll_key=0;
keylr=0;
//复制推导式数组
for(int i=0;i<sto_tax;i++) strcpy(_stotax[i],stotax[i]);
_sto_tax=sto_tax;
int key;
char p[30];
char key_c;
for(i=0;i<_sto_tax;i++)
{//消除直接左递归
key_c=_stotax[i][0];
if(_stotax[i][0]==_stotax[i][3])
{//如果存在直接左递归,则消除
//查找未被使用的大写之母
findcapital();
for(int j=0;j<_sto_tax;j++)
{
if(_stotax[j][0]==key_c)
{
keylr=1;
if(_stotax[j][3]==_stotax[j][0])
{
strcpy(&_stotax[j][3],&_stotax[j][4]);
_stotax[j][strlen(_stotax[j])]=capital;
_stotax[j][0]=capital;
_stotax[j][strlen(_stotax[j])+1]='\0';
_stotax[_sto_tax][0]=capital;
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
_stotax[_sto_tax][3]='0';
_stotax[_sto_tax][4]='\0';
_sto_tax++;
}
else if(_stotax[j][3]!='0')
{
int d;
d=strlen(_stotax[j]);
_stotax[j][d]=capital;
_stotax[j][d+1]='\0';
}
}
}
}
}
char keyc[30];
for(i=0;i<_sto_tax;i++)
{//消除间接左递归
key=0;
strcpy(keyc,_stotax[i]);
if(isupper(_stotax[i][3]))
{
for(int j=0;j<=_sto_tax;j++)
{
if(keyc[0]!=_stotax[j][0])
if(_stotax[j][0]==keyc[3])
{
if(key==0)
{
strcpy(p,&_stotax[i][4]);
strcpy(&_stotax[i][3],&_stotax[j][3]);
strcpy(&_stotax[i][strlen(_stotax[i])],p);
key=1;
}
else
{
_stotax[_sto_tax][0]=_stotax[i][0];
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
strcpy(&_stotax[_sto_tax][3],&_stotax[j][3]);
strcpy(&_stotax[_sto_tax][strlen(_stotax[_sto_tax])],p);
_sto_tax++;
}
}
}
}
for(int n=0;n<_sto_tax;n++)
{
key_c=_stotax[n][0];
if(_stotax[i][0]==_stotax[i][3])
{
keylr=1;
findcapital();
for(int j=0;j<_sto_tax;j++)
{
if(_stotax[j][0]==key_c)
{
if(_stotax[j][3]==_stotax[j][0])
{
strcpy(&_stotax[j][3],&_stotax[j][4]);
_stotax[j][strlen(_stotax[j])]=capital;
_stotax[j][0]=capital;
_stotax[j][strlen(_stotax[j])+1]='\0';
_stotax[_sto_tax][0]=capital;
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
_stotax[_sto_tax][3]='0';
_stotax[_sto_tax][4]='\0';
_sto_tax++;
}
else if(_stotax[j][3]!='0')
{
int d;
d=strlen(_stotax[j]);
_stotax[j][d]=capital;
_stotax[j][d+1]='\0';
}
}
}
}
}
}
if(keylr==1)
{
printf("该文法有直接或间接左递归,消除左递归后的文法为:\n");
for(i=0;i<_sto_tax;i++)
{
{
printf("%s",_stotax[i]);
printf("\n");
}
}
for(i=0;i<_sto_tax;i++) strcpy(stotax[i],_stotax[i]);
sto_tax=_sto_tax;
}
}

void findcapital() //查找未被使用的大写字母,把第一个未被使用的大写字母保存在capital中
{
int key;
for(int i=65;i<=90;i++)
{
key=0;
for(int j=0;j<_sto_tax;j++)
{
if(_stotax[j][0]==char(i)) key=1;
}
if(key==0)
{
capital=char(i);
break;
}
}
}

void First_Collection(char p[]) //求字符串p的first集,把结果保存在数组firstchars[30]中
{
if(islower(p[0])) firstchars[first_num++]=p[0];
else if(isupper(p[0]))
{
for(int i=0;i<sto_tax;i++)
if(stotax[i][0]==p[0])
if(islower(stotax[i][3])) firstchars[first_num++]=stotax[i][3];
for(i=0;i<strlen(p);i++)
{
if(isupper(p[i]))
{
char *q;
for(int n=0;n<sto_tax;n++)
if(p[i]==stotax[n][0])
{
q=&stotax[n][3];
First_Collection(q);
}
int key=0;
for(int j=0;j<colec0num;j++)
if(colec0[j]==p[i])
{
key=1;
break;
}
if(key==0) break;
}
else if(islower(p[i]))
{
firstchars[first_num++]=p[i];
break;
}
}
}
}

void Follow_Collection(char p) //求字符p的follow集,把结果保存在数组followchars中
{
if(p==stotax[0][0]) followchars[follow_num++]='#';
for(int i=0;i<sto_tax;i++)
{
for(int j=3;j<strlen(stotax[i]);j++)
if(p==stotax[i]