LL1语法分析程序设计.docx
《LL1语法分析程序设计.docx》由会员分享，可在线阅读，更多相关《LL1语法分析程序设计.docx（35页珍藏版）》请在冰点文库上搜索。
LL1语法分析程序设计
实验二LL
（1）语法分析程序设计
【实验目的】
1．熟悉判断LL
（1）文法的方法及对某一输入串的分析过程。
2．学会构造表达式文法的预测分析表。
【实验内容】
编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。
【实验步骤和要求】
1．从键盘读入输入串，并判断正误；
2．若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL
（1）文法；
3．若符合LL
（1）文法，由程序自动构造LL
（1）分析表；
4．由算法判断输入符号串是否为该文法的句型。
（可参考教材96页的例题1）
【说明】
语法分析主要是将从词法分析那里得来的记号构成一棵语法树。
例：
SHMA#
adbe#
S->aH
H->aMd
H->d
M->Ab
M->
A->aM
A->e
分析例句：
aaabd#
/*-------------------LL
（1）语法分析--------------------*/
#include"stdio.h"
#include"stdlib.h"
#defineMaxRuleNum8
#defineMaxVnNum5
#defineMaxVtNum5
#defineMaxStackDepth20
#defineMaxPLength20
#defineMaxStLength50
structpRNode /*产生式右部结构*/
{
intrCursor; /*右部序号*/
structpRNode*next;
};
structpNode /*产生式结点结构*/
{
intlCursor; /*左部符号序号*/
intrLength; /*右部长度*/
/*注当rLength=1时，rCursor=-1为空产生式*/
structpRNode*rHead; /*右部结点头指针*/
};
charVn[MaxVnNum+1]; /*非终结符集*/
intvnNum;
charVt[MaxVtNum+1]; /*终结符集*/
intvtNum;
structpNodeP[MaxRuleNum]; /*产生式*/
intPNum; /*产生式实际个数*/
charbuffer[MaxPLength+1];
charch; /*符号或stringch;*/
charst[MaxStLength];/*要分析的符号串*/
structcollectNode /*集合元素结点结构*/
{
intnVt; /*在终结符集中的下标*/
structcollectNode*next;
};
structcollectNode*first[MaxVnNum+1]; /*first集*/
structcollectNode*follow[MaxVnNum+1]; /*follow集*/
intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];
/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#（-1）*/
intanalyseStack[MaxStackDepth+1]; /*分析栈*/
inttopAnalyse; /*分析栈顶*/
/*intreverseStack[MaxStackDepth+1]; /*颠倒顺序栈*/
/*inttopReverse; /*倒叙栈顶*/
voidInit（）;/*初始化*/
intIndexCh（charch）;
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
voidInputVt（）; /*输入终结符*/
voidInputVn（）;/*输入非终结符*/
voidShowChArray（char*collect,intnum）;/*输出Vn或Vt的内容*/
voidInputP（）;/*产生式输入*/
boolCheckP（char*st）;/*判断产生式正确性*/
voidFirst（intU）;/*计算first集,U->xx...*/
voidAddFirst（intU,intnCh）; /*加入first集*/
boolHaveEmpty（intnVn）;/*判断first集中是否有空（-1）*/
voidFollow（intV）;/*计算follow集*/
voidAddFollow（intV,intnCh,intkind）;/*加入follow集，
kind=0表加入follow集，kind=1加入first集*/
voidShowCollect（structcollectNode**collect）;/*输出first或follow集*/
voidFirstFollow（）;/*计算first和follow*/
voidCreateAT（）;/*构造预测分析表*/
voidShowAT（）;/*输出分析表*/
voidIdentify（char*st）;/*主控程序,为操作方便*/
/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/
voidInitStack（）;/*初始化栈及符号串*/
voidShowStack（）;/*显示符号栈中内容*/
voidPop（）;/*栈顶出栈*/
voidPush（intr）;/*使用产生式入栈操作*/
#include"LL1.h"
voidmain（void）
{
chartodo,ch;
Init（）;
InputVn（）;
InputVt（）;
InputP（）;
getchar（）;
FirstFollow（）;
printf（"所得first集为：
"）;
ShowCollect（first）;
printf（"所得follow集为：
"）;
ShowCollect（follow）;
CreateAT（）;
ShowAT（）;
todo='y';
while（'y'==todo）
{
printf（"\n是否继续进行句型分析？
（y/n）:
"）;
todo=getchar（）;
while（'y'!
=todo&&'n'!
=todo）
{
printf（"\n（y/n）?
"）;
todo=getchar（）;
}
if（'y'==todo）
{
inti;
InitStack（）;
printf（"请输入符号串（以#结束）:
"）;
ch=getchar（）;
i=0;
while（'#'!
=ch&&i {
if（''!
=ch&&'\n'!
=ch）
{
st[i++]=ch;
}
ch=getchar（）;
}
if（'#'==ch&&i {
st[i]=ch;
Identify（st）;
}
else
printf（"输入出错！
\n"）;
}
}
getchar（）;
}
voidInit（）
{
inti,j;
vnNum=0;
vtNum=0;
PNum=0;
for（i=0;i<=MaxVnNum;i++）
Vn[i]='\0';
for（i=0;i<=MaxVtNum;i++）
Vt[i]='\0';
for（i=0;i {
P[i].lCursor=NULL;
P[i].rHead=NULL;
P[i].rLength=0;
}
PNum=0;
for（i=0;i<=MaxPLength;i++）
buffer[i]='\0';
for（i=0;i {
first[i]=NULL;
follow[i]=NULL;
}
for（i=0;i<=MaxVnNum;i++）
{
for（j=0;j<=MaxVnNum+1;j++）
analyseTable[i][j]=-1;
}
}
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
intIndexCh（charch）
{
intn;
n=0; /*isVn?
*/
while（ch!
=Vn[n]&&'\0'!
=Vn[n]）
n++;
if（'\0'!
=Vn[n]）
return100+n;
n=0; /*isVt?
*/
while（ch!
=Vt[n]&&'\0'!
=Vt[n]）
n++;
if（'\0'!
=Vt[n]）
returnn;
return-1;
}
/*输出Vn或Vt的内容*/
voidShowChArray（char*collect）
{
intk=0;
while（'\0'!
=collect[k]）
{
printf（"%c",collect[k++]）;
}
printf（"\n"）;
}
/*输入非终结符*/
voidInputVn（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的非终结符，注意：
"）;
printf（"请将开始符放在第一位，并以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n {
Vn[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n {
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vn[n++]=ch;
vnNum++;
}
ch=getchar（）;
}
Vn[n]='#'; /*以“#”标志结束用于判断长度是否合法*/
k=n; /*k用于记录n以便改Vn[n]='\0'*/
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
;
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vn[k]='\0';
ShowChArray（Vn）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*输入终结符*/
voidInputVt（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的终结符，注意：
"）;
printf（"以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n {
Vt[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n {
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vt[n++]=ch;
vtNum++;
}
ch=getchar（）;
}
Vt[n]='#'; /*以“#”标志结束*/
k=n; /*k用于记录n以便改Vt[n]='\0'*/
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vt[k]='\0';
ShowChArray（Vt）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*产生式输入*/
voidInputP（）
{
charch;
inti=0,n,num;
printf（"请输入文法产生式的个数：
"）;
scanf（"%d",&num）;
PNum=num;
getchar（）; /*消除回车符*/
printf（"\n请输入文法的%d个产生式,并以回车分隔每个产生式：
",num）;
printf（"\n"）;
while（i {
printf（"第%d个：
",i）;
/*初始化*/
for（n=0;n buffer[n]='\0';
/*输入产生式串*/
ch='';
n=0;
while（'\n'!
=（ch=getchar（））&&n {
if（''!
=ch）
buffer[n++]=ch;
}
buffer[n]='\0';
/* printf（"%s",buffer）;*/
if（CheckP（buffer））
{
/*填写入产生式结构体*/
pRNode*pt,*qt;
P[i].lCursor=IndexCh（buffer[0]）;
pt=（pRNode*）malloc（sizeof（pRNode））;
pt->rCursor=IndexCh（buffer[3]）;
pt->next=NULL;
P[i].rHead=pt;
n=4;
while（'\0'!
=buffer[n]）
{
qt=（pRNode*）malloc（sizeof（pRNode））;
qt->rCursor=IndexCh（buffer[n]）;
qt->next=NULL;
pt->next=qt;
pt=qt;
n++;
}
P[i].rLength=n-3;
i++;
/*调试时使用*/
}
else
printf（"输入符号含非法在成分，请重新输入！
\n"）;
}
}
/*判断产生式正确性*/
boolCheckP（char*st）
{
intn;
if（100>IndexCh（st[0]））
returnfalse;
if（'-'!
=st[1]）
returnfalse;
if（'>'!
=st[2]）
returnfalse;
for（n=3;'\0'!
=st[n];n++）
{
if（-1==IndexCh（st[n]））
returnfalse;
}
returntrue;
}
/*====================first&follow======================*/
/*计算first集,U->xx...*/
voidFirst（intU）
{
inti,j;
for（i=0;i {
if（P[i].lCursor==U）
{
structpRNode*pt;
pt=P[i].rHead;
j=0;
while（j {
if（100>pt->rCursor）
{
/*注:
此处因编程出错,使空产生式时
rlength同样是1,故此处同样可处理空产生式*/
AddFirst（U,pt->rCursor）;
break;
}
else
{
if（NULL==first[pt->rCursor-100]）
{
First（pt->rCursor）;
}
AddFirst（U,pt->rCursor）;
if（!
HaveEmpty（pt->rCursor））
{
break;
}
else
{
pt=pt->next;
}
}
j++;
}
if（j>=P[i].rLength） /*当产生式右部都能推出空时*/
AddFirst（U,-1）;
}
}
}
/*加入first集*/
voidAddFirst（intU,intnCh） /*当数值小于100时nCh为Vt*/
/*当处理非终结符时,AddFirst不添加空项（-1）*/
{
structcollectNode*pt,*qt;
intch; /*用于处理Vn*/
pt=NULL;
qt=NULL;
if（nCh<100）
{
pt=first[U-100];
while（NULL!
=pt）
{
if（pt->nVt==nCh）
break;
else
{
qt=pt;
pt=pt->next;
}
}
if（NULL==pt）
{
pt=（structcollectNode*）malloc（sizeof（structcollectNode））;
pt->nVt=nCh;
pt->next=NULL;
if（NULL==first[U-100]）
{
first[U-100]=pt;
}
else
{
qt->next=pt; /*qt指向first集的最后一个元素*/
}
pt=pt->next;
}
}
else
{
pt=first[nCh-100];
while（NULL!
=pt）
{
ch=pt->nVt;
if（-1!
=ch）
{
AddFirst（U,ch）;
}
pt=pt->next;
}
}
}
/*判断first集中是否有空（-1）*/
boolHaveEmpty（intnVn）
{
if（nVn<100） /*为终结符时（含-1），在follow集中用到*/
returnfalse;
structcollectNode*pt;
pt=first[nVn-100];
while（NULL!
=pt）
{
if（-1==pt->nVt）
returntrue;
pt=pt->next;
}
returnfalse;
}
/*计算follow集,例：
U->xVy,U->xV.（注：
初始符必含#——"-1"）*/
voidFollow（intV）
{
inti;
structpRNode*pt ;
if（100==V） /*当为初始符时*/
AddFollow（V,-1,0）;
for（i=0;i {
pt=P[i].rHead;
while（NULL!
=pt&&pt->rCursor!
=V）/*注此不能处理：
U->xVyVz的情况*/
pt=pt->next;
if（NULL!
=pt）
{
pt=pt->next; /*V右侧的符号*/
if（NULL==pt） /*当V后为空时V->xV，将左符的follow集并入V的follow集中*/
{
if（NULL==follow[P[i].lCursor-100]&&P[i].lCursor!
=V）
{
Follow（P[i].lCursor）;
}
AddFollow（V,P[i].lCursor,0）;
}
else /*不为空时V->xVy,（注意：
y->），调用AddFollow加入Vt或y的first集*/
{
while（NULL!
=pt&&
升级会员 