编译原理实验LL1分析.docx
《编译原理实验LL1分析.docx》由会员分享，可在线阅读，更多相关《编译原理实验LL1分析.docx（15页珍藏版）》请在冰点文库上搜索。
编译原理实验LL1分析
实验三语法分析---LL
（1）分析器
一.实验的目的与思路
（1）目的
1.用程序的方法实现语法分析的LL
（1）方法。
（2）思路
本程序是采用的LL
（1）方法进行的语法分析，而LL
（1）的分析方法是属于自上而下的方法。
自上而下分析的基本思想是：
对任意输入串，试图用一切可能的方法，从文法开始符号（根结点）出发，自上而下为输入串建立一棵语法树。
从推导的角度看，它是从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。
在输入之前必须要进行该文法是不是LL
（1）文法的判断，然后再构造相应的LL
（1）分析表来用预测分析方法进行语法分析，依据下面的文法及分析表来设计程序实现预测分析的分析过程。
1.文法G[E]：
E-->E+T|T
T-->T*F|F
F-->（E）|i
2.通过观察可知道该文法是一个左递归文法，要进行语法分析就必须消除左递归才能继续判断它是不是LL
（1）文法，然后才能用预测分析方法进行语法分析。
3.消除左递归：
E-->TM
M-->+TM|u
T-->FQ
Q-->*FQ|u
F-->（E）|i
4.在进行LL
（1）文法的判断：
（1.）各非终结符的FIRST集如下：
FIRST（E）=FIRST（TM）={（，i}
FIRST（M）={+}
FIRST（T）={（，i}
FIRST（Q）={*}
FIRST（F）={（，i}
（2.）各非终结符的FOLLOW集如下：
FOLLOW（E）={），#}
FOLLOW（M）={），#}
FOLLOW（T）={+，），#}
FOLLOW（Q）={+，），#}
FOLLOW（F）={*，+，），#}
（3.）各产生式的SELECT集如下：
SELECT（E→TM）={（,i}
SELECT（M→+TM）={+}
SELECT（M→u）={},#}
SELECT（T→FQ）={（,i}
SELECT（Q→*FQ）={*}
SELECT（Q→u）={+，）,#}
SELECT（F→（E））={（）
SELECT（F→i）={i}
因为：
SELECT（M→+TM）∩SELECT（M→u）=Ф
SELECT（Q→*FQ）∩SELECT（Q→u）=Ф
SELECT（F→（E））∩SELECT（F→i）=Ф
因此可以判断该文法是一个LL
（1）文法可以构造预测分析表。
5.根据可选集构造预测分析表如下：
二.基本的功能
下面主要采用了LL
（1）分析方法来进行语法分析，先通过判断该文法是不是LL
（1）文法，如果不是先将其改写成LL
（1）文法，再将LL
（1）文法改造成等价形式------LL
（1）分析表，通过分析表来进行语法分析，本程序的主要功能是对一个文法句子的生成过程进行分析。
三．总体设计
LL
（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析其功能模型图如下：
LL
（1）语法分析功能模型图
本程序是采用预测的分析方法，因此预测分析方法的基本算法如下：
（1）判断该文法是不是LL
（1）文法，如果该文法不是LL
（1）文法，则修改该文法继续判断该文法是不是LL
（1）文法，如果是则进行第二步，否则不运行。
（2）构造预测分析表：
1．对文法G的每个产生式A->a执行第二步和第三步；
2．对每个终结符a∈FIRST（a）,把A->a加至L[A,a]中；
3．若ε∈FIRST（a）,则对任意b∈FOLLOW（A）把A->a加至L[A,b]中；
4．把所有无定义的L[A,a]标上“出错标志”；
上述算法可应用于任何文法G以构造它的预测分析表L。
但是对于某些文法，有些L[A,a]可能持有若干个产生式，或者说有些L[A,a]可能是多重定义的。
如果G是左递归或是二义的，那么L至少含有一个多重定义入口。
因此，消除左递归和提取左因子将有助于获得无多重定义的分析表L。
本题是在将文法消除左递归和提取左因子等工作之后的基础上进行的，也就是针对LL
（1）文法来构造预测分析表，从而达到预测分析表不含多重定义入口的效果。
本程序的设计只是一个语法分析程序，预测表的部分将被固定在一个二维数。
组中，然后进行预测分析过程。
（3）对一个输入串的预测分析过程
1.将开始符和‘#’进栈输入当前符，进行查表比较，如果不匹配，就将所用产生式进栈然后再进行查表。
2.进行查表后如果匹配则将所用的产生式出栈处理
3.如果所用到的产生式是u（表示空符）那么就将所用到的产生式出栈处理。
4.如果有‘#’与‘#’匹配则表示成功接收字符串，否则就不能成功接收，不能推导
四．详细设计
（1）算法的模块图：
main（）函数模块
（2）主程序的流程图
程序流程图
五.测试数据
（1）i+i*i#
（2）（i*i）+i#（3）E*i+i#
六.源代码
#include"stdafx.h"
#include
#include
#include
usingnamespacestd;
#include
#defineMAX20
charanalyz_sentence[MAX]="";
chars[MAX]="";
charstack[MAX]="";
chartop;
char*tp;
charidenty[MAX]="";
intn=0;
charVn_array[]="EMTQF";
charVt_array[]="i+*（）#";
charVp_array[5][10]={{"E->TM"},{"M->+TM|u"},{"T->FQ"},{"Q->*FQ|u"},{"F->（E）|i"}};
char*LL1_array[][6]={
{"TM","","","TM","",""},
{"","+TM","","","u","u"},
{"FQ","","","FQ","",""},
{"","u","*FQ","","u","u"},
{"i","","","（E）","",""}
};
voidput_setence（）;
voidinit_stack（）;
intll1_analyzing（）;
voidll1array_push（char）;
intis_Vt（）;
intis_ll1array（char）;
intVn_idx（）;
intVt_idx（char）;
voidpop（）;
voidpush（char）;
voidreve（）;
intprinterror（）;
voidmain（）
{inta,b,k,h;
cout<<"*******请输入一个句子*********"<put_setence（）;
init_stack（）;
ll1_analyzing（）;
}
voidput_setence（）
{
charch;
inti=0;
while（（ch=cin.get（））!
='#'）{
analyz_sentence[i]=ch;
i++;
}
analyz_sentence[i]='#';
}
voidinit_stack（）
{
stack[0]='#';
stack[1]=Vn_array[0];
cout<";
}
intll1_analyzing（）
{
top=stack[1];
interror;
for（inti=0;i<=strlen（analyz_sentence）;i++）{
inttet;
tet=is_Vt（）;
if（1==tet）{
if（top==analyz_sentence[i]）{
identy[n++]=top;
pop（）;
continue;
}
else{
printerror（）;
break;
}
}
elseif（'#'==top）{
for（intp=0;pprintf（"%c",analyz_sentence[p]）;
}
break;
}
else{
do{
intjudge=0;
judge=is_ll1array（analyz_sentence[i]）;
if（judge==1）{
if（1==is_Vt（））{
error=printerror（）;
break;
}
ll1array_push（analyz_sentence[i]）;
}
else{
error=printerror（）;
break;
}
}
while（top!
=analyz_sentence[i]）;
if（error==1）
break;
identy[n++]=top;
if（top!
='#'）
pop（）;
}
}
if（error==1）return0;
else
{cout<<"这是一句合法的句子！
"<<"分析成功"<return1;}
}
voidll1array_push（charcutchar）
{
inti,j;
i=Vn_idx（）;
j=Vt_idx（cutchar）;
tp=LL1_array[i][j];
reve（）;
pop（）;
intk;
for（k=0;k{
push（tp[k]）;
}
printf（"%s",identy）;
for（intm=strlen（stack）-1;m>0;m--）
cout<cout<<"=>";
if（top=='u'）
pop（）;
}
voidpop（）
{
inttom;
tom=strlen（stack）-1;
stack[tom]='\0';
top=stack[tom-1];
}
voidpush（charelt）
{
inttom;
tom=strlen（stack）;
stack[tom]=elt;
top=elt;
}
intis_Vt（）
{
inti;
inthot=0;
for（i=0;iif（top==Vt_array[i]）
hot=1;
}
if（top=='#'）
hot=0;
if（hot==1）
return1;
else
return-1;
}
intis_ll1array（charcutchar）
{
inti,j;
i=Vn_idx（）;
j=Vt_idx（cutchar）;
if（LL1_array[i][j]==""）{
return-1;
}
else
return1;
}
intVn_idx（）
{
for（inti=0;iif（top==Vn_array[i]）
returni;
}
return-1;
}
intVt_idx（charidx_array）
{
for（inti=0;iif（idx_array==Vt_array[i]）
returni;
}
return-1;
}
voidreve（）
{
strcpy（s,tp）;
inti,j;
chart;
i=0;
while（s[i]!
='\0'）
++i;
--i;
if（s[i]=='\n'）
--i;
j=0;
while（j{
t=s[j];
s[j]=s[i];
s[i]=t;
--i;
++j;}
tp=s;}
intprinterror（）
{
cout<<"这不是一句合法的句子，无法推导！
"<<"分析不成功"<return1;
}
升级会员 