编译原理实验七LL1文法的判断Word下载.doc
《编译原理实验七LL1文法的判断Word下载.doc》由会员分享,可在线阅读,更多相关《编译原理实验七LL1文法的判断Word下载.doc(11页珍藏版)》请在冰点文库上搜索。
(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];
//初始化产生式数组
for(i=0;
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"
);
11