编译原理专业课程设计LL文法分析器设计C语言实现.docx

集美大学计算机工程学院
编译原理课程设计汇报
选题名称: LL（1）文法分析
院（系）: 计 算 机 工 程 学院
专 业: 计算机科学和技术
班 级: 计算1412
指导老师: 付永刚
年学期: ~ 年 第 2 学期
年 06 月 29 日

摘要：选题要求：依据某一文法编制调试LL(1) 文法语法分分析程序，方便对任意输入符号串进行分析。此次课程设计目标关键是加深对估计分析LL(1)文法语法分析法了解。具体以下：1、对语法规则有明确定义；2、编写分析程序能够对给定文法进行正确语法分析；3、对输入给定文法，手工计算FIRST、FOLLOW集合和select集合，应能判定识别是否为给定文法句子，并给出推导过程。4、对输入给定文法，由程序自动结构FIRST、FOLLOW集合。5、对于碰到语法错误，能够做出简单错误处理，给出简单错误提醒，确保顺利完成语法分析过程。 
关键词：语法分析；FIRST集合；FOLLOW集合；分析表
一、设计内容及要求
(1) 基于PL/0语言，经过编程判定该文法是否为LL(1)文法；
(2)计算出文法First() Follow()
(3)结构对应文法估计分析表
(4)对某个输入句子进行语法分析
二、实现原理
1．LL(1)文法
LL(1)文法是一类能够进行确定自顶向下语法分析文法。就是要求描述语言文法是无左递归和无回溯。依据LL(1)文法定义，对于同一非终止符A任意两个产生式A:=a和A:=b，全部要满足：SELECT(A：=a )∩SELECT(A:=b)=Ø。
（1）文法左递归
当一个文法是左递归文法时，采取自顶向下分析法会使分析过程进入无穷循环之中。所以采取自顶向下语法分析需要消除文法左递归性。文法左递归是指若文法中对任一非终止符A有推导AÞA…，则称该文法是左递归。
左递归又能够分为直接左递归和间接左递归。
● 直接左递归
若文法中某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归。
消除直接左递归方法：
设有产生式是相关非终止符A直接左递归：A→Aα|β （α,β∈V*，且β不以A开头）
对A引入一个新非终止符A′，把上式改写为：
A →βA′
A′→αA′|ε
● 间接左递归
若文法中存在某一非终止符A，使得AÞA…最少需要两步推导，则称该文法是间接左递归。
消除间接左递归方法：
【方法一】采取代入法把间接左递归变成直接左递归。
【方法二】直接改写文法：设有文法G10[S]：
S→Aα|β ⑴
A→Sγ ⑵
因为SÞAαÞSγα，所以S是一个间接递归非终止符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到和原文法等价文法（能够证实）：
S→Sγα|β ⑶
⑶式是直接左递归，能够采取前面介绍消除直接左递归方法，对文法进行改写后可得文法：S→βS′
S′→γαS′|ε

2. 计算First集
(1) 若X∈VT ，则First(X)={X}
(2) 若X∈VN ，且有产生式X→a…, a∈VT则First(X)={X}
(3) 若X∈VN ，且有产生式X→ε,则First(X)={X}
(4) 若X，Y1 ，Y2 ，…，Yn 全部∈VN，而由产生式X→Y1 Y2 …Yn 。当Y1 ，Y2 ，…，Yi-1全部能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε}, First(Y2)-{ε},…, First(Yi)全部包含在First(X)中
(5)当(4)中全部Yi全部能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}
反复使用上述步骤直到每个符合First集合不再增大为止。

3. 计算Follow集
对文法中每个A∈VN，计算Follw(A)：
(1) 设S为文法开始符合，把{#}加入Follow(S)中；
(2) 若A→αBβ是一个产生式，则把First(β)非空元素加入Follow(B)中，假如β能推导出ε，则把Follow(A)也加入(B)中；
(3) 反复使用以上步骤直到每个非终止符号Follow集不再增大为止。
4. 估计分析方法
估计分析方法是自顶向下分析另一个方法，一个估计分析器是由三个部分组成：估计分析程序；优异后出栈；估计分析表。
估计分析程序框图以下：

目录
1系统分析1
1.1选题要求1
1.2预期目标1
2.程序流程图1
2.1总流程图1
2.2First集和Follow集2
2.3预测分析表流程3
3.代码编写3
3.1检查左递归3
3.2first集合5
3.3follow集合6
3.4分析表输出8
4.程序调试10
5.总结11
6.指导教师评语12
7.源码13

正文：
1.系统分析
1.1选题要求
依据某一文法编制调试LL(1) 文法语法分分析程序，方便对任意输入符 号串进行分析。此次课程设计目标关键是加深对估计分析LL(1)文法语法分析法了解。
1.2预期目标
结构LL(1)文法语法分析程序，任意输入一个文法符号串，并判定它是否为文法一个句子。程序要求为该文法结构估计分析表，并根据估计分析算法对输入串进行语法分析，判别程序是否符合已知语法规则，假如不符合（编译犯错），则输犯错误信息。
2. 程序步骤图
2．1.总步骤图

2.2.First集和Follow集步骤图

2.3.估计分析表步骤：

3. 代码编写
3.1检验左递归：
Parser& Parser::DelLeft(int i)
{
int n=StrNum(content[i]);
char c=RandChar();
char z=content[i][0];
int s=0;
for(int k=1;k<=n;k++)
{
string tmp=GetSub(k,content[i],'|');
if(z==tmp[0]) s=1;
}
if(s==0) return *this;
cout<<"文法句"<<content[i]<<"含有直接左递归,";
while(1)
{
if(Findchar(c,non)==-1) break;
else c=RandChar();
}
cout<<"随机产生非终止符为:"<<c<<endl;
non.append(1,c);
string temp;
temp+=z;
temp+="->";
string next;
next+=c;
next+="->";
for(int k=1;k<=n;k++)
{
string t=GetSub(k,content[i],'|');
if(z==t[0])
{
t.erase(0,1);
t+=c;
next+=t;
next+='|';
}
else
{
if(t=="^") t.clear();
t+=c;
temp+=t;
temp+='|';
}
}
next+='^';
temp.erase(temp.size()-1,1);
content[i]=temp;
num=num+1;
content[num]=end;
for(int j=num-1;j>i;j--)
content[j]=content[j-1];
content[i+1]=next;
return *this;
}

3.2 first集合
string Parser::First(char x)
{
string ch="";
if(Findchar(x,ter)!=-1)
{ ch.append(1,x);
ch.append(1,' ');
}
else if(Findchar(x,non)!=-1)
{
int i=Findid(x);
if(i!=-1)
{
string q=content[i];
unsigned int k=3;
while(k<q.size())
{
if(q[k-1]=='|'||k==3)
{
if(Findchar(q[k],ter)!=-1||q[k]=='^')
{
ch.append(1,q[k]);
ch.append(1,' ');
} else
{
if(k==3||q[k+1]=='|'||k==q.size()-1) ch+=First(q[k]);
else
{
string temp=First(q[k-1]);
if(Findchar('^',temp)!=-1) ch+=First(q[k]);
}
}
k++;
}
else k++;
}
}
}
return ch;
}
3.3 follow集合
string Parser::Follow(char x)
{
string ch;
if(Findchar(x,non)!=-1)
{
if(!Findid(x))
{
ch+="$";
ch+=' ';
}
int i=0;
while(i<num)
{
string q=content[i];
unsigned int k=3;
char c=content[i][0];
while(k<q.size())
{
while(q[k]==x)
{
if(k<q.size()-1&&q[k+1]!='|')
{
string temp=Delchar('^',First(q[k+1]));
if(ch.find(temp)==string::npos) ch+=temp;
if(Findchar('^',First(q[k+1]))!=-1)
{
string follow_c = Follow(c);
if(ch!=follow_c&&ch.find(follow_c)==std::string::npos)
ch+=follow_c;
}
}
else if(k==q.size()-1)
{
string follow_c = Follow(c);
if(ch.find(follow_c)==std::string::npos) ch+=follow_c;
}
k++;
}
k++;
}
i++;
}
}
return ch;
}
3.4 分析表输出
int Parser::Analysis()
{
stack.append("$");
char chose;
cout<<"是否输入分析串(y or n):";
cin>>chose;
while(chose=='y')
{
stack+=non[0];
cout<<"请输入分析串<退出(q)>：";
cin>>instack;
if (instack=="q") exit(0);
if(instack[instack.size()-1]!='$') instack+="$";
int k=1,flag=0;
char x=Top();
char c=Ip();
cout<<"分析栈\t目前输入\t动作"<<endl;
while(x!='$')
{
x=Top();
c=Ip();
cout<<stack<<"\t"<<instack<<"\t\t";
if(Findchar(x,ter)!=-1)
{
if(Mate(x,c))
{
k++;
cout<<"匹配"<<c<<endl;
}
else
{
cout<<"["<<k<<"]犯错(终止符不匹配)！"<<endl;
flag=1;
if(x==')') Pop();
else instack.erase(0,1);
k++;
}
}
else if(Findchar(x,non)!=-1)
{
int idf=Findchar(x,non);
int idz=Findchar(c,ter);
if(idz==-1) idz=int(ter.size());
string temp=table[idf][idz];
if(temp.empty())
{
cout<<"["<<k<<"]犯错（"<<c<<"不属于FIRST("<<x<<")）！"<<endl;
flag=1;
instack.erase(0,1);
k++;
}
else
{
Pop();
if(temp!="^")
{
Push(temp);
cout<<x<<"->"<<temp<<endl;
}
else cout<<x<<"->"<<temp<<endl;

}

}
else if(x=='$'&&c=='$')
{
if(flag==0) cout<<"正确"<<endl;
else cout<<"错误"<<endl;
}
else
{
cout<<"["<<k<<"]犯错(未能识别字符)！"<<endl;
flag=1;
instack.erase(0,1);
k++;
}
}
}
}

4. 程序调试
导入正确文法：

符合文法串

不符合文法串

导入有左递归文法：

串分析：

总 结
经过这次课程设计，对于LL1文法认识有了深入提升，尤其是对于FIRST集合和FOLLOW集合求取，前面对于求取者两个集合了解还不是很好，经过这次课程设计，逐步了解了求解过程，而且知道了怎样经过代码，自动生成某LL1文法FIRST集合和FOLLOW集合，在刚开始做时，根本不知道求，经过网上查找资料，同学请教，慢慢地知道了怎样做，最终正确地求出FIRST集合和FOLLOW集合。而且能够使用者两个集合构建估计分析表和对一段输入串进行分析是否是该文法串，犯错地方能够做犯错处理，总来说，完成了课程设计要求大部分内容，对于GUI使用没有能够实现，暴露了本身在这方面不足，需要在以后学习和工作中进行沉入学习提升。
在实现功效中还有存在着，对于不含直接左递归文法没法正确找出，提醒错误。在判定是否是LL1文法上还有很大不足，没法使用代码实现当两个FIRST有存在交集判定不是LL1文法功效，这点要求自己对于代码编程能力有着必需提升。
这次课程设计使用C++来实现LL1文法分析功效，自己对于C++语言使用有了很大提升。尤其是对于部分C++语法要求，有了很大认识。但存在不足还是比较多。全部是需要在以后学习中认真总结，以使自己能愈加好地语言使用，提升本身技能。
这次课程设计总收获是不少。每一次实践全部是提升本身能力机会，在以后生活中，要抓住实践机会，实践是验证真理最好路径。对于一个计算机专业学生来说，更应该重视实践机会，只有实践多了，部分理论知识才能被自己正真认识，不然，值懂理论，没有对于正确性进行验证，还是会有问题，尤其是计算机机器，总存在未知错误，只有不停地探索，才能愈加好地去使用我们工具。

指导老师评语
学号

姓名

班级

选题
名称

序号
评价内容
权重（%）
得分
1
考勤统计、学习态度、工作作风和表现。
5

2
自学情况：
上网检索机时数、文件阅读情况（笔记）。
10

3
论文选题是否优异，是否含有前沿性或前瞻性。
5

4
结果验收：
是否完成设计任务；能否运行、可操作性怎样等。
20

5
汇报格式规范程度、是否图文并茂、语言规范及流畅程度；专题是否鲜明、重心是否突出、叙述是否充足、结论是否正确；是否提出了自己独到见解。
30

6
文件引用是否合理、充足、真实。
5

7
答辩情况：
自我陈说、回复问题正确性、用语正确性、逻辑思维、是否含有独到见解等。
25

累计

指导老师（签章）：
年 月 日

源码：LL1.h
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;

class Parser
{
public:
Parser();
Parser(const Parser&);
friend ostream& operator<<(ostream& output,const Parser& rs);
friend istream& operator>>(istream& input,Parser& rs);
int Findid(char);
int Check();
string Checkstr(string&);
string Delchar(char,string);
int Findchar(char,string);
int StrNum(const string&);
char RandChar();
string GetSub(int,const string&,char);
Parser& DelLeft(int);
string First(char);
string First(const string&);
string Follow(char);
Parser& FirstAndFollow();
Parser& CreateTable();
~Parser();
char Pop();
int Mate(char,char);
char Top();
char Ip();
Parser& Push(const string&);
int Analysis();
private:
int num;
string ter,non,end,stack,instack;
string *content;
string *first;
string *follow;
string **table;
};
LL1.cpp
#include "LL1.h"

Parser::Parser()
{
content=new string[255];
first=new string[255];
follow=new string[255];
table=new string *[255];
}

Parser::Parser(const Parser& rs)
{
ter=rs.ter;
non=rs.non;
end=rs.end;
num=rs.num;
content=new string[255];
first=new string[255];
follow=new string[255];
table=new string *[255];
for(int i=0;i<=num;i++)
content[i]=rs.content[i];
FirstAndFollow();
CreateTable();
}

ostream& operator<<(ostream& output,const Parser& rs)
{
output<<"文法内容(共"<<rs.num<<"条):"<<endl;
int i=0;
while(i<rs.num)
{
output<<rs.content[i++]<<endl;
}
output<<"结 终 符:"<<rs.ter<<endl;
output<<"非结终符:"<<rs.non<<endl;
cout<<"非终止符FIRST集合 "<<endl;
for(unsigned int j=0;j<rs.non.size();j++)
cout<<"FIRST("<<rs.non[j]<<") = {"<<rs.first[j]<<"}\t"<<endl;
cout<<"非终止符FOLLOW集合 "<<endl;
for(unsigned int j=0;j<rs.non.size();j++)
cout<<"FOLLOW("<<rs.non[j]<<") = {"<<rs.follow[j]<<"}\t"<<endl;
output<<"估计分析表:"<<endl<<"\t";
for(unsigned int j=0;j<rs.ter.size();j++)
output<<rs.ter[j]<<"\t";
output<<"$"<<endl;
for(unsigned int j=0;j<rs.non.size();j++)
{
output<<rs.non[j]<<"\t";
for(unsigned int k=0;k<=rs.ter.size();k++)
cout<<rs.table[j][k]<<"\t";
output<<endl;
}
return output;
}
istream& operator>>(istream& input,Parser& rs)
{
unsigned int j=0;
char filename[255];
cout<<"请输入文件名:";
input>>filename;
ifstream infile(filename,ios::in);
if(!infile){
cout<<"无法打开文件！"<<endl;
exit(0);
}
while(1)
{
unsigned int i=0;
infile>>rs.end;
rs.content[j++]=rs.end;
if(infile.eof()) break;
while(i<rs.end.size())
{
if(rs.end[i]=='|'||rs.end[i]=='^');
else if(i==1||i==2) i++;
else if(rs.end[i]>='A'&&rs.end[i]<='Z'){
if(std::string::npos==rs.non.find(rs.end[i])) rs.non.append(1,rs.end[i]);
}
else if(std::string::npos==rs.ter.find(rs.end[i])) rs.ter.append(1,rs.end[i]);
i++;
}
}
rs.num=j-1;
if(rs.Check()==0)
{
exit(0);
}
rs.FirstAndFollow();
rs.CreateTable();
return input;
}

int Parser::Findid(char a)
{
int i=0;
while(i<num)
{
if(content[i][0]==a) return i;
i++;
}
return -1;
}

char Parser::RandChar()
{
switch(rand()%3)
{
case 0:return 'A';
case 1:return 'B';
case 2:return 'C';
case 3:return 'D';
}
return 'D';
}

int Parser::Check()
{
unsigned int j=0;
int i=0;
while(i<num)
{
if(content[i].size()<=3)
{
cout<<"文法句"<<content[i]<<"长度不对!"<<endl;
return 0;
}
if(content[i][1]!='-'||content[i][2]!='>')
{
cout<<"文法句"<<content[i]<<"未来使用推导符\"->\"!"<<endl;
return 0;
}
int n=StrNum(content[i]);
int s=0;
char z=content[i][0];
int m=0;
for(int k=1;k<=n;k++)
{
string tmp=GetSub(k,content[i],'|');
if(z==tmp[0])
{
s=1;
m++;
}
}
if(m==n)
{
cout<<"文法句"<<content[i]<<"将形成无穷推导！"<<endl;
return 0;
}
if(s==1)
DelLeft(i);
i++;
}
return 1;
}

Parser& Parser::DelLeft(int i)
{
int n=StrNum(content[i]);
char c=RandChar();
char z=content[i][0];
int s=0;
for(int k=1;k<=n;k++)
{
string tmp=GetSub(k,content[i],'|');
if(z==tmp[0]) s=1;
}
if(s==0) return *this;
cout<<"文法句"<<content[i]<<"含有直接左递归,";
while(1)
{
if(Findchar(c,non)==-1) break;
else c=RandChar();
}
cout<<"随机产生非终止符为:"<<c<<endl;
non.append(1,c);
string temp;
temp+=z;
temp+="->";
string next;
next+=c;
next+="->";
for(int k=1;k<=n;k++)
{
string t=GetSub(k,content[i],'|');
if(z==t[0])
{
t.erase(0,1);
t+=c;
next+=t;
next+='|';
}
else
{
if(t=="^") t.clear();
t+=c;
temp+=t;
temp+='|';
}
}
next+='^';
temp.erase(temp.size()-1,1);
content[i]=temp;
num=num+1;
content[num]=end;
for(int j=num-1;j>i;j--)
content[j]=content[j-1];
content[i+1]=next;
return *this;
}

string Parser::Checkstr(string & a)
{
unsigned int i=0,j=0;
for(;i<a.size();i++){
for(j=i+1;j<a.size();j++){
if(a[i]==a[j]){
a.erase(j,1);
}
}
}
return a;
}

string Parser::Delchar(char x,string a)
{
int j,i=int(a.size());
for(j=0;j<i;j++)
if(a[j]==x)
a.erase(j,1);
return a;
}

int Parser::Findchar(char x,string a)
{
unsigned int i=0;
while(i<a.size())
{
if(a[i]==x) return i;