安徽大学编译原理实验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]==