合肥工业大学编译原理 LL自上而下文法分析.docx
《合肥工业大学编译原理 LL自上而下文法分析.docx》由会员分享,可在线阅读,更多相关《合肥工业大学编译原理 LL自上而下文法分析.docx(47页珍藏版)》请在冰点文库上搜索。
合肥工业大学编译原理LL自上而下文法分析
合肥工业大学计算机与信息学院
计算机系2013级
编译原理课程设计报告
姓名:
马骏
专业年级:
信息安全13-1
学号:
2013211869
提交时间:
2016年07月
1、实验题目
自上而下的LL
(1)文法分析
2、实验目的
了解掌握自上而下的LL
(1)文法分析过程。
二、实验内容与要求
从语法分析树构造句型所有的推导的程序实现,接受用户任意输入的一个句型的语法分析树(其表示存于指定文件中),生成该语法分析树中包含的该句型的所有推导(显示输出)。
构造一程序,实现教材P.78的FIRST(X)集合的构造算法。
对任一给定的文法G,程序输出所有非终结符P的FIRST(P)。
构造一程序,实现教材P.78的FIRST(X)集合的构造算法。
对任一给定的文法G,程序输出所有非终结符P的FIRST(P)。
在此基础上,构造一程序,实现教材P.79的FOLLOW(A)集合的构造算法。
对任一给定的文法G,程序输出所有非终结符A的FOLLOW(A)。
对于给定的一个LL
(1)文法,假定所有非终结符号P的集合FIRST(P)和集合FOLLOW(P)都已知,构造其预测分析表(实现教材P.79给出的预测分析表构造算法)。
对教材P.79给出的例4.7构造出预测分析表。
程序显示输出预测分析表或输出到指定文件中。
首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再实现教材P.79给出的预测分析表构造算法。
程序显示输出预测分析表或输出到指定文件中。
对文法按教材P.76表4.1构造出G的预测分析程序,程序显示输出如P.78那样的匹配过程。
三、实验环境与工具
操作系统:
Windows7
开发语言:
C++
4、开发过程
1)字符要求:
你的程序必须能够根据以下字符来处理语法:
-终端字符:
字母,数字,符号例如“+”,“—”,…;
-非终端字母表中的大写字母。
符号“=”,“|”和“#”(替换“ε”,因为它更容易输入到文本文件)被保留用于语法的描述中,因此不能被用作终端。
2)初始状态
您的程序通过读取一个文件中的“文本”格式开始。
这个文件的结构可以随意构建,不做要求,但建议做成简单的。
例如,程序描述以下语句:
E=E+T|T
T=T*F|F
F=(E)|0|1
在这种情况,我们可以很容易确定E,T和F是非终端,而符号“(”,“)”,“*”和“+”和数字“0”和“1”是在终端。
第一个非终端(第一衍生物)被认为是语法的公理。
文本结构(在内存中)
过程
显示在屏幕
结果必须存储在内存中,是一个您所选择的数据结构。
然后,使用一个函数再取出数据,存储在内存中并屏幕上显示(以你选择的格式)。
在上面的图中,并在下文中,右列显示的程序的执行的过程,并左栏表示中使用的数据结构。
这些都是明显的例子。
你可以使用任何你想要的格式。
3)消除传递
没有发现传递关系
发现传递关系
判断:
是否包含左传递
消除传递关系
判断你的程序是否包含一个传递关系或没有。
如果包含,递归应该被消除。
没有传递关系的语句
遍历语句
指向自己的判断:
您可以创建一个新的数据结构语句来表示其中传递关系已被删除,这有利于进一步加工。
在这种情况下,如果语法不包含判定递归的语句,程序当然必须使用第二数据结构的副本。
3)计算“first集”和“follow集”的集合
为了产生一个分析器,你现在必须计算,每个分支,“第一个”和“其后”的集合·。
结果被存储在数据结构,再次“你的选择。
”
然后,这些集合被显示在屏幕上
图注释:
Calculdesensembles«premiers»et«suivants»计算“第一个”和“其后”的集合
Affichagedesensembles显示集合premiers第一个suivants其后
4)分析表的结构
具有非递归语法以及“第一个”和“其后”的集合,你的程序现在可以建立预测分析表。
结果以表的形式显示在屏幕上。
图注释:
Constructiondelatabled’analyse分析表的结构
tabled’analyse分析表Affichagedelatabled’analyse显示分析表
输入字符串的分析
最后一步:
你的程序读取输入(键盘)的表达和分析。
指出,结果是否符合语法。
你要尽可能准确的鉴定结果:
定位错误在没有辨认出表达式的情况下。
其次,你的程序必须能够完成对输入多个字符串作为输入,不要忘记重新启动你的程序。
显示分析结果
判断是否继续
读取表达式
5、程序实现
6、程序代码
/*
不支持规则源文件中有空格
注意使用#表示空产生式使用$表示结束符#
*/
#include
#include
#include
#include
usingnamespacestd;
constchar*sourcefile="ma_grammaira.txt";//定义源文件
//constintmax=100;
#definemax100
classsign
{
public:
sign(){}
sign(intcheck,charfu)
{
if(check!
=0&&check!
=1)//符号属性只有0和1
{
cout<<"errorsigncreat!
"<}
else
{
identity=check;//设置符号属性
id=fu;//设置非终结符符号
funnumber=0;//设置符号规则数为0
firstnumber=0;
follownumber=0;
}
}
voidadd(stringsl)//添加产生规则
{
fun[funnumber]=sl;
funnumber++;
}
voidpop(intq)//删除某一规则
{
if(q>=funnumber||q<0)
{
cout<<"errorwrongdeletefuninsign!
";
return;
}
for(intx=q;xfun[x]=fun[x+1];
funnumber--;
}
voidpop_first(charq)//从first集删除某一节点
{
for(intx=0;x{
if(first[x]==q)
{
for(inty=x;yfirst[y]=first[y+1];
firstnumber--;
x--;//为了接着上次检查点
}
}
}
voidpop_follow(charq)//从first集删除某一节点
{
for(intx=0;x{
if(follow[x]==q)
{
for(inty=x;yfollow[y]=follow[y+1];
follownumber--;
x--;//为了接着上次检查点
}
}
}
voidadd_first(charq)//向first添加元素
{
for(intx=0;x{
if(first[x]==q)return;
}
first[firstnumber]=q;
firstnumber++;
}
voidadd_follow(charq)//向follow添加元素
{
for(intx=0;x{
if(follow[x]==q)return;
}
follow[follownumber]=q;
follownumber++;
}
intidentity;//符号属性0为非终结符1为终结符
charid;//符号
stringfun[max];//符号产生规则
intfunnumber;//符号产生规则数量
charfirst[max];//first集
intfirstnumber;
charfollow[max];//follow集
intfollownumber;
};
classcell//分析表的单元格结构
{
public:
charcell_unendsign;//终结符
charcell_endsign;//非终结符
stringcell_fun;//产生式
};
celltable[max][max];//分析表数据结构
inttable_unend_number;//非终结符数
inttable_end_number;//终结符数
signunendsign[max];//非终结点集合
intunendsignnumber=0;
signendsign[max];//终结点集合
intendsignnumber=0;
voidreadsource(constchar*sf)//读取源文件ma_grammaira.txt
{
intx;
unendsignnumber=0;
endsignnumber=0;
ifstreamifs;
ifs.open(sourcefile);
charbuf[max];
for(x=0;xbuf[x]='\0';
while(ifs.getline(buf,sizeof(buf)))//一行一行读取
{
unendsign[unendsignnumber]=sign(0,buf[0]);
unendsignnumber++;
stringrule;
for(intx=2;x{
if(buf[x]=='\0')
{
break;
}
if(buf[x]=='|')
{
//cout<unendsign[unendsignnumber-1].fun[unendsign[unendsignnumber-1].funnumber]=rule;//规则放在每个非终结符实例中
unendsign[unendsignnumber-1].funnumber++;
rule="";
continue;
}
rule+=buf[x];
charkk=buf[x];
}
unendsign[unendsignnumber-1].fun[unendsign[unendsignnumber-1].funnumber]=rule;
unendsign[unendsignnumber-1].funnumber++;
//cout<}
}
voidaddendsign(charsg)//添加终结符
{
for(intx=0;x{
if(endsign[x].id==sg)
return;
}
endsign[endsignnumber].id=sg;
endsign[endsignnumber].identity=1;
endsignnumber++;
}
voiddealend()//由非终结符产生式得到终结符
{
for(intx=0;x{
for(inty=0;y{
for(intz=0;z{
charkk=unendsign[x].fun[y][z];
if(int(kk)>=65&&int(kk)<=90)continue;//A到Z为非终结符
elseaddendsign(kk);
}
}
}
}
boolexit_endsign(charsg)//终结符表是否有sg
{
intx;
for(x=0;x{if(endsign[x].id==sg)
returntrue;
}
returnfalse;
}
boolexit_unendsign(charsg)//非终结符表是否有sg
{
for(intx=0;x{
if(unendsign[x].id==sg)
returntrue;
}
returnfalse;
}
signget_unendsign(charsg)//从非终结符表中得到非终结符为sg的实例
{
for(intx=0;x{
if(unendsign[x].id==sg)returnunendsign[x];
}
cout<<"errorgetnounendsign!
"<signer;
returner;
}
intget_unendsign_number(charsg)//从非终结符表中得到非终结符为sg的下标
{
for(intx=0;x{
if(unendsign[x].id==sg)returnx;
}
cout<<"errorgetnounendsign!
"<return0;
}
intget_endsign_number(charsg)//从非终结符表中得到终结符为sg的下标
{
for(intx=0;x{
if(endsign[x].id==sg)returnx;
}
cout<<"errorgetnoendsign!
"<return0;
}
boolrule_first_check(signm_sign,charsg)//查看非终结符实例m_sign产生式首是否为sg
{
inty;
for(y=0;y{
if(m_sign.fun[y][0]==sg)returntrue;
}
intcheck=0;
for(y=0;y{
if(exit_unendsign(m_sign.fun[y][0]))
{
signmsg=get_unendsign(m_sign.fun[y][0]);
if(rule_first_check(msg,sg))
{
check=1;
break;
}
}
}
if(check)returntrue;
elsereturnfalse;
}
boolcheck_L_recursion()//检查是否含有直接左递归和传递左递归true表示有false表示没有
{
intx,y;
for(x=0;x{
for(y=0;y{
if(unendsign[x].fun[y][0]==unendsign[x].id)returntrue;
}
}
for(x=0;x{
if(rule_first_check(unendsign[x],unendsign[x].id))
returntrue;
}
returnfalse;
}
signnew_unendsign()//创建一个新非终结符即用于规则p=p.....需要p'
{
chara=65;
while
(1)
{
if(a>90||unendsignnumber>26)
{
cout<<"errornomoresizeforunendsign!
"<break;
}
intcheck=1;
for(intx=0;x{
if(unendsign[x].id==a)
{
a++;
check=0;
break;
}
}
if(check)
{
unendsign[unendsignnumber].id=a;
unendsign[unendsignnumber].identity=0;
unendsignnumber++;
break;
}
}
returnunendsign[unendsignnumber-1];
}
voidpop_unendsign(charsg)//删除某一非终结符
{
for(intx=0;x{
if(unendsign[x].id==sg)
{
for(inty=x;yunendsign[y]=unendsign[y+1];
unendsignnumber--;
return;
}
}
cout<<"errornounendsignforpop"<return;
}
voiddeal_direct_L_recursion(intthisnumber)//消除unendsign[thisnumber]的直接左递归在deal_L_total_recursion()中调用
{
inti;
if(!
check_L_recursion())
return;
intcheck=0;
for(i=0;i{
if(unendsign[thisnumber].fun[i][0]==unendsign[thisnumber].id)
{
check=1;
break;
}
}
if(check)
{
new_unendsign();
intkp=unendsignnumber-1;
for(i=0;ib0p'|b1p'
{
if(unendsign[thisnumber].fun[i][0]==unendsign[thisnumber].id)
{
stringss="";
for(intx=1;xss+=unendsign[thisnumber].fun[i][x];
if(ss=="#")
{
cout<<"errorcan'tdealwhithP->P#"<return;
}
ss=ss+unendsign[kp].id;
unendsign[kp].add(ss);
}
else
{
if(unendsign[thisnumber].fun[i]!
="#")
{
unendsign[thisnumber].fun[i]=unendsign[thisnumber].fun[i]+unendsign[kp].id;
}
if(unendsign[thisnumber].fun[i]=="#")
{
stringss="";
ss+=unendsign[kp].id;
unendsign[thisnumber].add(ss);
}
}
}
unendsign[kp].add("#");//为p'增加p->#的规则
for(i=0;ip...的产生式
{
if(unendsign[thisnumber].fun[i][0]==unendsign[thisnumber].id)
{
unendsign[thisnumber].pop(i);
i=0;
}
}
}
}
voiddeal_L_total_recursion()//消除所有左递归
{
inti,j,t,k,qq;
for(i=0;i{
for(j=0;j
{
for(t=0;t{
if(unendsign[i].fun[t][0]==unendsign[j].id)
{
stringsay="";
for(k=1;ksay+=unendsign[i].fun[t][k];
unendsign[i].pop(t);
for(qq=0;qq{
stringsp=unendsign[j].fu