编译原理语法分析器课程设计Word文档下载推荐.docx
《编译原理语法分析器课程设计Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《编译原理语法分析器课程设计Word文档下载推荐.docx（56页珍藏版）》请在冰点文库上搜索。
if产生式右部的第一个符号等于当前字符then
跳到下一条产生式进行查找
求当前非终结符在所有字符集中的位置
if当前非终结符还没求其FIRST集then
查找它的FIRST集并标识此符号已求其FIRST集
求得结果并入到X的FIRST集.
if当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then
获取右部符号下一个字符在所有字符集中的位置
if此字符的FIRST集还未查找then
找其FIRST集,并标其查找状态为1
把求得的FIRST集并入到X的FIRST集.
if当前右部符号串可推出空且是右部符号串的最后一个字符（即产生式为X→Y1Y2…Yk,若对一切1≤i≤k，均有ε∈FIRST（Yi），则将ε∈符号加进FIRST（X））then
把空字加入到当前字符X的FIRST集.
else
不能推出空字则结束循环
标识当前字符X已查找其FIRST集.}
2.计算FOLLOW集
FOLLOW集的构造可用如下方法来求：
对于文法中的符号XVN，其FOLLOW（A）集合可反复应用下列规则计算，直到FOLLOW（A）集合不再增大为止。
（1）对于文法开始符号S，因为SS，故#FOLLOW（S）；
（2）若A→αBβ，其中BVN，α（VTVN）*、β（VTVN）+，则
FIRST（β）-{}FOLLOW（B）；
（3）若A→αB或A→αBβ（β
），则
FOLLOW（A）FOLLOW（B）。
FOLLOW集的算法描述如下：
voidFOLLOW（inti）
X为待求的非终结符
把当前字符放到一临时数组tempFOLLOW[]中,标识求已求其FOLLOW集.避免循环递归
ifX为开始符号then#∈FOLLOW（X）
对全部的产生式找一个右部含有当前字符X的产生式
注：
比如求FOLLOW（B）则找A→αX或A→αXβ（β
ε）的产生式
ifX在产生式右部的最后（形如产生式A→αX）then
查找非终结符A是否已经求过其FOLLOW集.避免循环递归
if非终结符A已求过其FOLLOW集then
FOLLOW（A）∈FOLLOW（X）
继续查下一条产生式是否含有X
else
求A之FOLLOW集，并标识为A已求其FOLLOW集
elseifX不在产生式右部的最后（形如A→αBβ）then
if右部X后面的符号串β能推出空字εthen
查找β是否已经求过其FOLLOW集.避免循环递归
if已求过β的FOLLOW集then
FOLLOW（A）∈FOLLOW（B）
结束本次循环
elseifβ不能推出空字then
求FIRST（β）
把FIRST（β）中所有非空元素加入到FOLLOW（B）中
标识当前要求的非终结符X的FOLLOW集已求过
3.计算SELECT集
SELECT集的构造算法如下：
对所有的规则产生式A→x：
（1）若x不能推出空字，则SELECT（A→x）=FIRST（x）；
（2）若x可推出空字，则SELECT（A→x）=FIRST（x）–{ε}FOLLOW（A）。
算法描述如下：
for（i=0;
i<
=产生式总数-1;
i++）
先把当前产生式右部的FIRST集（一切非空元素,不包括ε）放入到当前产生式的SELECT（i）;
if产生式右部符号串可推出空字then
把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT（i）中
4.判断是否LL
（1）文法
要判断是否为LL
（1）文法，需要输入的文法G有如下要求：
具有相同左部的规则的SELECT集两两不相交，即：
SELECT（A→α）∩SELECT（A→β）=
如果输入的文法都符合以上的要求，则该文法可以用LL
（1）方法分析。
把第一条产生式的SELECT（0）集放到一个临时数组temp[]中
for（i=1;
求temp的长度length
ifi指向的当前产生式的左部等于上一条产生式的左部then
把SELECT（i）并入到temp数组中
Iftemp的长度小于length加上SELECT（i）的长度
返回0
else
把temp清空
把SELECT（i）存放到temp中
结果返回1；
源码
/***************************************************
LL
（1）parsinggrammar
25/4/2007
***************************************************/
#include<
stdlib.h>
stdio.h>
string.h>
iostream>
windows.h>
usingnamespacestd;
/**************************************************/
//用于指向输入输出文件的指针
FILE*inparse,*outparse,*inscan;
//用于接收输入输出文件名
charinparsefile[300],outparsefile[300],inscanfile[300];
/***************定义产生式的语法集结构*************/
typedefstruct
{
charformula[200];
//产生式
}grammarElement;
grammarElementgramOldSet[200];
//原始文法的产生式集
grammarElementgramNewSet[200];
//消除左递归后文法的产生式集
/*********************变量定义*********************/
intgrammarNum=0;
//原始的产生式数目
intPcount=0;
//分解的产生式的个数
charstartSymbol;
//开始符号
charterSymbol[200];
//终结符号
charnon_ter[200];
//非终结符号
charallSymbol[400];
//所有符号
charleftStr[200];
//消除左递归后产生式左部（不包括"
->
"
）
charrightStr[200][200];
//消除左递归后产生式右部（不包括"
/***************************************************/
charfirstSET[100][100];
//各产生式右部的FIRST集合
charfollowSET[100][100];
//各产生式左部的FOLLOW集合
charsingleFIRST[100][100];
//所有单个符号的FIRST集合,函数findSingleFIRST（i）用到
charselectSET[100][100];
//各单个产生式的SELECT集合
chartempFOLLOW[100];
//求FOLLOW集合时使用
charFirstForFollow[100];
//求FOLLOW时存放某一符号串的FIRST集合
charfirsted[100];
//记录各符号的FIRST是否已求过,0和1表示其状态
charfollowed[100];
//记录各符号的FOLLOW是否已求过,0和1表示其状态
charepsilon[100];
//记录可直接推出@（"
ε"
）的符号
chartempEpsilon[100];
//求someDerivateEpsilon（）时使用,标识此字符已查找其是否可推出空字
intvalidity=1;
//表示输入文法是否有效
intisLL1=1;
//表示输入文法是否为LL
（1）文法
intM[200][200];
//分析表
charchoice;
//用户输入时使用
设置彩色文字
voidsetcolor（unsignedshortForeColor=4,unsignedshortBackGroundColor=0）
HANDLEhCon=GetStdHandle（STD_OUTPUT_HANDLE）;
SetConsoleTextAttribute（hCon,ForeColor|BackGroundColor）;
}
/**************************************************
查找字符是否在指定字符串中
**************************************************/
boolFindChar（charch,char*p）
inti;
if（strlen（p）==0）
returnfalse;
for（i=0;
（int）strlen（p）;
{
//若存在，返回真
if（p[i]==ch）
returntrue;
}
returnfalse;
得到一个不在non_ter[]数组的非终结符号（消除左递归用到）
charget_Char（）
charch='
A'
;
//在非终结符non_ter中查找
while（FindChar（ch,non_ter））
ch++;
if（ch>
90）
return（'
$'
）;
//如果大写字母已经用完,出错
return（ch）;
判断输入的文法是直接左递归还是间接左递归
2007-5-6
intjudgeLeftRecursive（char*point）
inti,j,k=3,l;
l=（int）strlen（point）;
=l-1;
if（point[k]=point[0]）
return1;
//含有直接左递归
elseif（point[k]!
=point[0]&
&
FindChar（point[k],non_ter））
{
for（j=0;
j<
grammarNum;
j++）
{
}
}
return1;
分解含有直接左递归的产生式
eliminateleftStrrecursive
产生式A->
Aα|β,可以用非左递归的
A->
βA'
A'
αA'
|ε
来代替.
PS:
这里只是消除直接左递归
voidDirectLetfRecursive（char*point）
{
//point指针指向传递过来的完整的产生式
inti,j;
intm=0,n=3;
chartemp[20],ch;
ch=get_Char（）;
//得到一个非终结符
if（ch=='
printf（"
消除左递归时出错.原因:
没有足够的符号（字母）可用.\n"
fprintf（outparse,"
system（"
pause"
exit（0）;
i=strlen（non_ter）;
non_ter[i]=ch;
//把获得的非终结符加入到保存非终结符的non_ter[]数组中
non_ter[i+1]='
\0'
for（j=0;
=（int）strlen（point）-1;
{
if（point[n]==point[0]）
{
//如果"
|"
后的首符号和左部相同//A->
ABa|Ac
for（j=n+1;
j++）//j指向当前是左递归字符的下一个字符的位置
while（point[j]!
='
|'
point[j]!
）//没到产生式尾部且不等于"
temp[m++]=point[j++];
//把形如A->
ABa的产生式,右部从A以后的字符串存入到临时数组temp[]中
leftStr[Pcount]=ch;
//把得到的字符加入到左部数组leftStr[]中
memcpy（rightStr[Pcount],temp,m）;
//把右部从A以后的字符串存入到新产生式的右部Ba
rightStr[Pcount][m]=ch;
//把得到的字符加入到新产生式右部的结尾.
rightStr[Pcount][m+1]='
//得到新的产生式A'
BaA'
m=0;
Pcount++;
//产生式条数加1
if（point[j]=='
）//把形如A->
ABa|Ac的产生式分解成:
A->
ABa和A->
Ac
{
n=j+1;
//记下符号"
的下一个字符的位置n
break;
}
后的首符号和左部不同--A->
ABa|Cc
leftStr[Pcount]=ch;
rightStr[Pcount][0]='
@'
rightStr[Pcount][1]='
//得到新的产生式A'
@
Pcount++;
for（j=n;
if（point[j]!
temp[m++]=point[j];
else
leftStr[Pcount]=point[0];
m=0;
leftStr[Pcount]=point[0];
memcpy（rightStr[Pcount],temp,m）;
rightStr[Pcount][m]=ch;
rightStr[Pcount][m+1]='
m=0;
分解不含有左递归的产生式A->
Bb|c
voidnonLeftRecursive（char*point）
//指针point指向当前要分解的产生式A->
intm=0,j;
chartemp[20];
for（j=3;
if（point[j]!
）//产生式形如A->
Bb
temp[m++]=point[j];
else//产生式形如A->
Bb|c,分解为A->
Bb和A->
c
leftStr[Pcount]=point[0];
rightStr[Pcount][m]='
m=0;
memcpy（rightStr[Pcount],temp,m）;
rightStr[Pcount][m]='
Pcount++;
m=0;
最终的产生式
voidlastProduce（）
Pcount;
gramNewSet[i].formula[0]=leftStr[i];
gramNewSet[i].formula[1]='
-'
gramNewSet[i].formula[2]='
>
'
strcat（gramNewSet[i].formula,rightStr[i]）;
从文件读入一个文法
voidgetGrammar（char*t,char*n,char*leftStr,charrightStr[200][200]）
charNTtmp;
//保存临时非终结符号
charrightTmp[200];
//产生式右部
charVn[200];
//非终结符集non-terSymbolset
charVt[200];
//终结符集terSymbolset
inttmpIndex;
intvtIndex,vnIndex;
inti,j,k;
intvtLen,vnLen;
//终结符,非终结符
charp[200][200];
//保存产生式
tmpIndex=0;
vtIndex=0;
vnIndex=0;
while（!
feof（inparse））
//查找特定产生式的位置是否含有"
字符串
//检查是否是正确的产生式
if（fscanf（inparse,"
%c->
%s\r\n"
&
NTtmp,&
rightTmp）!
=2）
validity=0;
//产生式无效
break;
//结束循环
//求开始符号
if（tmpIndex==0）
startSymbol=NTtmp;
gramOldSet[tmpIndex].formula[0]=NTtmp;
gramOldSet[tmpIndex].formula[1]='
gramOldSet[tmpIndex].formula[2]='
strcat（gramOldSet[tmpIndex].formula,rightTmp）;
strcpy（p[tmpIndex],gramOldSet[tmpIndex].formula）;
tmpIndex++;
vnIndex;
if（NTtmp==Vn[i]）
break;
//求新非终
升级会员 