编译原理实验七LL文法的判断Word格式.docx
《编译原理实验七LL文法的判断Word格式.docx》由会员分享，可在线阅读，更多相关《编译原理实验七LL文法的判断Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；
（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V*，则FIRST（y）－{ε}∈FOLLOW（A）；
（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；
四：
数据结构与算法
typedefstructChomsky//定义一个产生式结构体
{
stringleft;
//定义产生式的左部
stringright;
//定义产生式的右部
}Chomsky;
voidapart（Chomsky*p,inti）//分开产生式左右部，i代表产生式的编号
stringis_empty（Chomsky*p）//判断某非终结符能否直接推出空，空用#代替
stringisempty（Chomsky*p）//可以间接推出空的非终结符
voidsearch（Chomsky*p,intn）//提取产生式中的非终结符
voidFirst（Chomsky*p,intn,charm,intmm）//求文法中非终结符的First集
voidFollow（Chomsky*p,intn,intm）//求文法的follow集
stringerase（strings）//去First集及follow集中的重复字符
voidselect（strings1,strings2）//求产生式的select集,s1是产生式左部，s2是产生式右部
五：
出错分析
1:
select集计算不出，关键在于能产生空的非终结符没有求出来
2:
单个符号的first集与一串符号的first集区别
3:
实验最后没能输出select集，没能判断出来是否是LL
（1）文法
六：
实验结果与分析
七：
源代码
#include<
iostream>
string>
usingnamespacestd;
#definemax100
intn;
//产生式总数
stringstrings;
//存储产生式
stringnoend;
//存放文法中的非终结符
stringempty;
//存放可以推出空的非终结符
stringfirst[max];
//存放非终结符的first集
stringfollow[max];
//存放非终结符的follow集
stringselect[max];
//存放产生式的select集
intj;
for（j=0;
j<
strings.length（）;
j++）
if（strings[j]=='
-'
）
{
p[i].left=strings.substr（0,j）;
//从0开始的j长度的子串，即0~j-1
p[i].right=strings.substr（j+1,strings.length（）-j）;
//从j+1开始的后面子串
}
}
/*stringis_empty（Chomsky*p）//判断某非终结符能否直接推出空，空用#代替
//如果可以，返回1
//不可以，返回0
inti;
strings;
for（i=0;
i<
n;
i++）
{
if（p[i].right[0]="
#"
&
p[i].right.length（）==1）//直接推出空的
empty=empty+p[i].left;
}
s=empty;
returns;
//s存放能直接推出空的非终结符
inti,j;
strings1;
if（is_empty（p）.find（p[i].left）>
=0）//若此非终结符已经存在直接推出空那里，在此无需重复计算
else
for（j=0;
（int）p[i].right.length（）;
{
if（is_empty（p）.find（p[i].right.[j]）<
0）
{
}
}
if（j==（int）p[i].right.length（））//如果右部所有符号都在直接推出空那里，则此左部也可以推出空
s1=s1+p[i].left[0];
}*/
if（!
（noend.find（p[i].left[0]）>
=0&
noend.find（p[i].left[0]）<
noend.length（）））
noend=noend+p[i].left;
for（j=0;
p[i].right.length（）;
if（'
A'
<
=p[i].right[j]&
p[i].right[j]<
='
Z'
if（noend.find（p[i].right[j]）>
noend.find（p[i].right[j]）<
noend.length（））
break;
else
noend=noend+p[i].right.substr（j,1）;
intlength=noend.length（）;
stringf;
inti,j,x,y;
intflag=0;
if（m==p[i].left[0]）
a'
=p[i].right[0]&
'
z'
>
=p[i].right[0]）
first[mm]=first[mm]+p[i].right.substr（0,1）;
if（p[i].right[0]=='
#'
for（j=0;
if（'
）flag++;
if（flag==j）//产生式的右部均为非终结符
flag=0;
for（j=0;
{
for（x=0;
x<
x++）
if（p[i].right[j]==p[x].left[0]&
p[x].right[0]=='
{
flag++;
break;
}
}
if（flag==j）//产生式右部的全部非终结符均能推出空
for（j=0;
{
for（x=0;
if（p[i].right[j]==noend[x]）break;
y=x;
if（first[y]=="
"
）First（p,n,p[i].right[j],x）;
f=first[y];
f.length（）;
if（f[x]=='
{
if（x==f.length（）-1）f=f.substr（0,x）;
elsef=f.substr（0,x）+f.substr（x+1）;
}
first[mm]=first[mm]+f;
}
first[mm]=first[mm]+"
;
else
f=first[y];
first[mm]=first[mm]+f;
inti,j,x,y,k;
stringfo;
if（noend[m]==p[i].right[j]）
if（j<
p[i].right.length（）-1&
=p[i].right[j+1]&
p[i].right[j+1]<
follow[m]=follow[m]+p[i].right.substr（j+1,1）;
if（j<
for（y=0;
y<
noend.length（）;
y++）
if（noend[y]==p[i].right[j+1]）break;
fo=first[y];
for（x=0;
first[y].length（）;
if（0<
=first[y].find（'
）&
first[y].find（'
）<
first[y].length（））
fo=first[y].substr（0,first[m].find（'
））+first[y].substr（first[y].find（'
）+1）;
follow[m]=follow[m]+fo;
for（x=0;
if（p[i].right[j+1]==p[x].left[0]&
）break;
if（x!
=n）//非终结符后面的部分可以推出空
for（y=0;
if（p[i].left[0]==noend[y]）break;
k=y;
if（follow[k]=="
）Follow（p,n,y）;
follow[m]=follow[m]+follow[k];
if（j==p[i].right.length（）-1）
for（y=0;
if（p[i].left[0]==noend[y]）break;
k=y;
if（follow[k]=="
follow[m]=follow[m]+follow[k];
s.length（）;
if（i!
=j&
s[i]==s[j]）s=s.substr（0,j）+s.substr（j+1）;
/*voidselect（strings1,strings2）//求产生式的select集,s1是产生式左部，s2是产生式右部
if（）//即s2可以推出空#
cout<
s1<
->
s2<
="
first（s2）<
endl;
else//即s2不可以推出空#
first（s2）-"
+<
follow（s1）<
voidmain（）
cout<
....................编译原理实验七：
LL
（1）文法的判断...................."
inti,j,m;
charf;
//存放文法开始符号
请输入文法产生式个数N以及各产生式（空用#代替，左右部的为-）：
cin>
Chomsky*p=newChomsky[n];
//初始化产生式数组
strings.erase（）;
//清除
cin>
strings;
apart（p,i）;
请输入该文法的开始符号：
f;
search（p,n）;
//提取产生式中的非终结符
//empty=is_empty（p）+isempty（p）;
//可以推出空的所有非终结符
for（m=0;
m<
m++）
if（first[m]=="
First（p,n,noend[m],m）;
该文法非终结符的first集：
first[i]=erase（first[i]）;
noend[i]<
:
first[i]<
if（noend[m]==f）
follow[m]=follow[m]+"
if（follow[m]=="
Follow（p,n,m）;
该文法非终结符的follow集：
follow[i]=erase（follow[i]）;
follow[i]<
该文法的各产生式的select集：
select[i]=erase（select[i]）;
p[i].left<
p[i].right<
select[i]<
system（"
pause"
）;
升级会员 