安徽大学编译原理实验Word文档下载推荐.docx
《安徽大学编译原理实验Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《安徽大学编译原理实验Word文档下载推荐.docx（35页珍藏版）》请在冰点文库上搜索。
2.LL
（1）文法的判别
◆五步判别法
✓求能推出ε的非终结符集
✓计算每个产生式右部α的FIRST（α）集
✓计算每个非终结符A的FOLLOW（A）集
✓计算每个产生式A→α的SELECT（A→α）集
✓按LL
（1）文法的定义判别
☞假定所给文法是经过压缩的（不包含多余规则）
3.算法
◆初始化
置数组X[]中对应每一非终结符的标记为初值“未定”；
◆扫描文法中的产生式
①删除右部含有终结符的产生式，假使以某一非终结符为左部的所有产生式都被删除，并将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出ε；
②删除右部仅为ε的产生式，则将数组中对应该非终结符的标志置为“是”，说明该非终结符能推出ε；
☞本次扫描后仅剩下产生式左右均为非终结符的产生式
◆扫描产生式右部的每一符号
①若所扫描到的非终结符号在数组中对应的标志为“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改“是”，并删除该非终结符为左部的所有产生式
②若所扫描到的非终结符号在数组中对应的标志为“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”
◆重复（3）
直到扫描完毕数组中非终结符对应的特征再没有改变为止。
4.计算每个产生式右部α的FIRST（α）集
◆定义法
Ⅰ、首先对每一文法符号X（XVTVN），求FIRST（A）的算法:
1.对每个aVT，First（a）={a}
2.对每个AVN，若Aε，则First（A）={ε}
3.对每个AVN，若有产生式A→a…,a∈VT,则First（A）={a}
4.对每个产生式A→X1…Xj…Xn做：
First（A）=First（A）SectionFirst（X1…Xj…Xn）
其中：
SectionFirst（X1…Xj…Xn）
=（First（X1）-{ε}）（First（X2）-{ε}）…（First（Xj）-{ε}）First（Xj+1）
Xj+1是产生式右部中第一个不能推出ε的符号
若X1ε
则SectionFirst（X1…Xj…Xn）=First（X1）
若X1…Xn全可推出ε
则SectionFirst（X1…Xn）=FIRST（X1）∪…∪FIRST（Xn）∪{ε}
5.重复4直到每个符号的FIRST集合都不再增大为止。
Ⅱ、利用求出每个文法符号的FIRST集求符号串的FIRST集
设α=X1X2…Xn
1.当X1ε，则FIRST（α）=FIRST（X1）
2.若对任何j（1≤j＜n）都有ε∈FIRST（Xj）,且Xj+1不能导出空串，则
FIRST（α）=（FIRST（X1）-{ε}）∪…∪（FIRST（Xj）-{ε}）∪FIRST（Xj+1）
3.若对所有i（1≤i≤n），都有ε∈FIRST（Xi），
则FIRST（α）=FIRST（X1）∪…∪FIRST（Xn）∪{ε}
◆关系图法
①每个文法符号对应图中一个结点，对应VT的结点时用符号本身标记，对应VN的结点用FIRST（A）标记。
这里A表示VN
②如果文法中有产生式A→VT，则从结点FIRST（A）到结点VT连一条箭弧
③如果文法中有产生式A→αVNβ，且α ε,则从结点FIRST（A）到结点FIRST（VN）连一条箭弧
④凡是从FIRST（A）结点有路径可到达的VT结点所标记的VT都为FIRST（A）的成员
由判别步骤1确定ε是否为某VN的FIRST集的成员，若是则将ε加入该VN的FIRST集中
5.计算每个非终结符A的FOLLOW（A）集
1.对所有AVN令Follow（A）={};
对开始符S，令Follow（S）={#}
2.对每条产生式A→xBy，考察产生式右部的每一非终结符B，x,y∈V*，如果y不能推出ε
Follow（B）=Follow（B）∪First（y）否则
Follow（B）=Follow（B）∪（First（y）-{ε}）∪Follow（A）
☞若a∈FOLLOW（A）,则表明S=>
*…Aa…，由于A→xBy，且y=>
*ε,则有
S=>
*…Aa…=>
…xBya=>
…xBa…，即S=>
*…xBa…,所以a∈FOLLOW（B）
3.重复2，直至对所有AVN，Follow（A）不再扩大为止。
☞FOLLOW集合中不能有ε
①文法G中的每个符号和“#”对应图中的一个结点，对应VT和“#”的结点用符号本身标记。
对应VN的结点，则用FOLLOW（VN）或FIRST（VN）标记
②从结点FOLLOW（S）到“#”号结点连一条箭弧
③如果文法中有产生式A→αBβVN,且β ε,则从结点FOLLOW（B）到结点FIRST（VN）连一条箭弧
4如果文法中有产生式A→αBβVT,且β ε,则从结FOLLOW（B）到结点VT连一条箭弧
5如果文法中有产生式A→αBβ,且β ε，则从
6结点FOLLOW（B）到结点FOLLOW（A）连一条箭弧
7对每一FIRST（A）结点如果有产生式A→αXβ,且
8α ε,则从结点FIRST（A）到结点FIRST（X）连一条箭弧
9凡是从结点FOLLOW（A）有路径可以到达的终结符或“#”号结点，其所标记的终结符或"
#"
号即为FOLLOW（A）的成员
6.计算每个产生式A→α的SELECT（A→α）集
按定义计算SELECT（A→α）：
•
若α\*ε，则SELECT（A→α）=FIRST（α）
若α*ε，则SELECT（A→α）=（FIRST（α）-{ε}）∪FOLLOW（A）
附录：
#include<
stdio.h>
string.h>
intcount=0;
/*分解的产生式的个数*/
intnumber;
/*所有终结符和非终结符的总数*/
charstart;
/*开始符号*/
chartermin[50];
/*终结符号*/
charnon_ter[50];
/*非终结符号*/
charv[50];
/*所有符号*/
charleft[50];
/*左部*/
charright[50][50];
/*右部*/
charfirst[50][50],follow[50][50];
/*各产生式右部的FIRST和左部的FOLLOW集合*/
charfirst1[50][50];
/*所有单个符号的FIRST集合*/
charselect[50][50];
/*各单个产生式的SELECT集合*/
charf[50],F[50];
/*记录各符号的FIRST和FOLLOW是否已求过*/
charempty[20];
/*记录可直接推出^的符号*/
charTEMP[50];
/*求FOLLOW时存放某一符号串的FIRST集合*/
intvalidity=1;
/*表示输入文法是否有效*/
intll=1;
/*表示输入文法是否为LL
（1）文法*/
intM[20][20];
/*分析表*/
charchoose;
/*用户输入时使用*/
charempt[20];
/*求_emp（）时使用*/
charfo[20];
/*求FOLLOW集合时使用*/
intin（charc,char*p）{
inti;
if（strlen（p）==0）
return（0）;
for（i=0;
;
i++）
{
if（p[i]==c）
return
（1）;
/*若在，返回1*/
if（i==strlen（p））
return（0）;
/*若不在，返回0*/
}
}//判断一个字符是否在指定字符串中
charc（）
{
charc='
A'
while（in（c,non_ter）==1）
c++;
return（c）;
}//得到一个不是非终结符的符号
voidrecur（char*point）//分解含有左递归的产生式
{/*完整的产生式在point[]中*/
intj,m=0,n=3,k;
chartemp[20],ch;
ch=c（）;
/*得到一个非终结符*/
k=strlen（non_ter）;
non_ter[k]=ch;
non_ter[k+1]='
\0'
for（j=0;
j<
=strlen（point）-1;
j++）
if（point[n]==point[0]）
{/*如果‘|’后的首符号和左部相同*/
for（j=n+1;
{
while（point[j]!
='
|'
&
point[j]!
）
temp[m++]=point[j++];
left[count]=ch;
memcpy（right[count],temp,m）;
right[count][m]=ch;
right[count][m+1]='
m=0;
count++;
if（point[j]=='
{
n=j+1;
break;
}
}
else
{/*如果‘|’后的首符号和左部不同*/
left[count]=ch;
right[count][0]='
^'
right[count][1]='
count++;
for（j=n;
{
if（point[j]!
temp[m++]=point[j];
left[count]=point[0];
memcpy（right[count],temp,m）;
right[count][m]=ch;
right[count][m+1]='
//printf（"
count=%d"
count）;
m=0;
}
voidnon_re（char*point）//分解不含有左递归的产生式
intm=0,j;
chartemp[20];
for（j=3;
right[count][m]='
chargrammer（char*t,char*n,char*left,charright[50][50]）//读入一个文法
charvn[50],vt[50];
chars;
charp[50][50];
inti,j,k;
printf（"
请输入文法的非终结符号串：
"
）;
scanf（"
%s"
vn）;
getchar（）;
i=strlen（vn）;
memcpy（n,vn,i）;
n[i]='
请输入文法的终结符号串：
vt）;
i=strlen（vt）;
memcpy（t,vt,i）;
t[i]='
请输入文法的开始符号：
%c"
&
s）;
请输入文法产生式的条数：
%d"
i）;
for（j=1;
=i;
请输入文法的第%d条（共%d条）产生式：
j,i）;
p[j-1]）;
=i-1;
if（p[j][1]!
-'
||p[j][2]!
>
'
{printf（"
\ninputerror!
validity=0;
return（'
}/*检测输入错误*/
for（k=0;
k<
k++）
{/*分解输入的各产生式*/
if（p[k][3]==p[k][0]）
recur（p[k]）;
non_re（p[k]）;
return（s）;
voidmerge（char*d,char*s,inttype）//将单个符号或符号串并入另一符号串
{/*d是目标符号串，s是源串，type＝1，源串中的‘^’一并并入目串；
type＝2，源串中的‘^’不并入目串*/
inti,j;
i<
=strlen（s）-1;
if（type==2&
s[i]=='
;
if（j<
strlen（d）&
s[i]==d[j]）
break;
if（j==strlen（d））
d[j]=s[i];
d[j+1]='
voidemp（charc）//求所有能直接推出^的符号
{/*即求所有由‘^’推出的符号*/
chartemp[10];
=count-1;
if（right[i][0]==c&
strlen（right[i]）==1）
temp[0]=left[i];
temp[1]='
merge（empty,temp,1）;
emp（left[i]）;
int_emp（charc）//求某一符号能否推出‘^’
{/*若能推出，返回1；
否则，返回0*/
inti,j,k,result=1,mark=0;
temp[0]=c;
merge（empt,temp,1）;
if（in（c,empty）==1）
return
（1）;
if（i==count）
return（0）;
if（left[i]==c）/*找一个左部为c的产生式*/
j=strlen（right[i]）;
/*j为右部的长度*/
if（j==1&
in（right[i][0],empty）==1）
elseif（j==1&
in（right[i][0],termin）==1）
else
=j-1;
if（in（right[i][k],empt）==1）
mark=1;
if（mark==1）
continue;
result*=_emp（right[i][k]）;
temp[0]=right[i][k];
if（result==0&
count）
elseif（result==1&
intjudge（）//判断读入的文法是否正确
if（in（left[i],non_ter）==0）
{/*若左部不在非终结符中，报错*/
\nerror1!
=strlen（right[i]）-1;
if（in（right[i][j],non_ter）==0&
in（right[i][j],termin）==0&
right[i][j]!
{/*若右部某一符号不在非终结符、终结符中且不为‘^’，报错*/
\nerror2!
voidfirst2（inti）//求单个符号的FIRST
{/*i为符号在所有输入符号中的序号*/
charc,temp[20];
intj,k,m;
charch='
c=v[i];
emp（ch）;
if（in（c,termin）==1）/*若为终结符*/
first1[i][0]=c;
first1[i][1]='
}
elseif（in（c,non_ter）==1）/*若为非终结符*/
if（left[j]==c）
if（in（right[j][0],termin）==1||right[j][0]=='
temp[0]=right[j][0];
merge（first1[i],temp,1）;
elseif（in（right[j][0],non_ter）==1）
if（right[j][0]==c）
if（v[k]==right[j][0]）
if（f[k]=='
0'
first2（k）;
f[k]='
1'
merge（first1[i],first1[k],2）;
=strlen（right[j]）-1;
empt[0]='
if（_emp（right[j][k]）==1&
strlen（right[j]）-1）
for（m=0;
m++）
if（v[m]==right[j][k+1]）
if（f[m]=='
first2（m）;
f[m]='
merge（first1[i],first1[m],2）;
elseif（_emp（right[j][k]）==1&
k==strlen（right[j]）-1）
temp[0]='
f[i]='
voidFIRST（inti,char*p）//求各产生式右部的FIRST
intlength;
length=strlen（p）;
if（length==1）/*如果右部为单个符号*/
if（p[0]=='
if（i>
=0）
first[i][0]='
first[i][1]='
TEMP[0]='
TEMP[1]='
if（v[j]==p[0]）
memcpy（first[i],first1[j],strlen（first1[j]））;
first[i][strlen（first1[j]）]='
memcpy（TEMP,first1[j],strlen（first1[j]））;
TEMP[strlen（first1[j]）]='
else/*如果右部为符号串*/
merge（first[i],first1[j],2）;
merge（TEMP,first1[j],2）;
=length-1;
if（_emp（p[k]）==1&
length-1）
if（v[m]==
升级会员 