北邮编译原理LL1语法分析程序.docx
《北邮编译原理LL1语法分析程序.docx》由会员分享，可在线阅读，更多相关《北邮编译原理LL1语法分析程序.docx（8页珍藏版）》请在冰点文库上搜索。
LL
（1）语法分析程序
2010211306班赵雪莹（10211310）
语法分析程序：
该语法分析程序实现对算术表达式的语法分析，并且在对输入表达式进行分析的过程中，输出所采用的产生式。
该程序使用的是LL
（1）语法分析程序，为给定文法构造预测分析表，并通过预测分析表对输入的表达式进行预测分析，并将栈顶状态和预测分析过程详细输出，如果匹配成功则接受，如果匹配不成功则返回错误信息。
给定文法的产生式：
E->E+T|E-T|T
T->T*F|T/F|F
F->id|（E）|num
源代码：
#include
#include
#include
#include
#include
usingnamespacestd;
structNode1
{
charvn;
charvt;
chars[12];
}MAP[22];//存储分析预测表每个位置对应的终结符，非终结符，产生式
intk;
charG[12][12]={"E->TR","R->+TR","R->-TR","R->e","T->FW","W->*FW","W->/FW","W->e","F->（E）","F->i","F->n"};
//存储文法中的产生式,用R代表E',W代表T',e代表空
charVN[6]={'E','R','T','W','F'};//存储非终结符
charVT[9]={'i','n','+','-','*','/','（','）','#'};//存储终结符
charFOLLOW[12][12]={"（,i,n","+","-","）,#","（,i,n","*","/","+,-,）,#","（","i","n"};//存储文法中每个产生式对应的FOLLOW集合
charRight[12][8]={"->TR","->+TR","->-TR","->e","->FW","->*FW","->/FW","->e","->（E）","->i","->n"};
stackstak,stak1,stak2;
boolcompare（char*a,char*b）
{
inti,la=strlen（a）,j,lb=strlen（b）;
for（i=0;ifor（j=0;j{
if（a[i]==b[j]）
return1;
}
return0;
}
char*Find（charvn,charvt）
{
inti;
for（i=0;i{
if（MAP[i].vn==vn&&MAP[i].vt==vt）
returnMAP[i].s;
}
return"error";
}
char*Analyse（char*word）
{
charp,c,action[10],output[10];
inti=1,l=strlen（word）,j,k=0,l_act,m,x;
printf（"________________________________________________________________________________\n"）;
printf（"\n对符号串%s的分析过程\n",word）;
for（x=0;x{c=word[x];
if（（（c<='z'）&&（c>='a'））||（（c<='Z'）&&（c>='A'）））
word[x]='i';
elseif（c>='0'&&c<='9'）
word[x]='n';
else
word[x]=c;
}
while（!
stak.empty（））//判断栈中是否为空，若不空就将栈顶元素与分析表匹配进行相应操作
stak.pop（）;
stak.push（'#'）;//栈底标志
stak.push（'E'）;//起始符号先入栈
printf（"步骤栈顶元素输入串推到所用产生式或匹配\n"）;
p=stak.top（）;
while（p!
='#'）//查预测分析表将栈顶元素进行匹配，若栈顶元素与输入串匹配成功则向前匹配，否则生成式反序入栈
{
printf（"%7d",i++）;
p=stak.top（）;//从栈中弹出一个栈顶符号，由p记录并输出
stak.pop（）;
printf（"%6c",p）;
for（j=k,m=0;joutput[m++]=word[j];
output[m]='\0';
printf（"%10s",output）;
if（p==word[k]）
{
if（p=='#'）//若最后一个结束符号匹配说明输入表达式被接受，否则继续匹配
{
printf（"接受\n"）;
return"SUCCESS";
}
printf（"“%c”匹配\n",p）;
k++;
}
else
{//将未被匹配的第一个字符与find函数的结果进行比较,在预测分析表中查找相应生成式
strcpy（action,Find（p,word[k]））;
if（strcmp（action,"error"）==0）
{
printf（"没有可用的产生式\n"）;
return"ERROR";
}
printf（"%c%s\n",p,action）;
intl_act=strlen（action）;
if（action[l_act-1]=='e'）
continue;
for（j=l_act-1;j>1;j--）
stak.push（action[j]）;
}
}
if（strcmp（output,"#"）!
=0）//匹配不成功
return"ERROR";
}
intmain（）
{
freopen（"in.txt","r",stdin）;
charsource[100];
inti,j,flag,l,m;
printf（"\n*****R代表E',W代表T',e代表空*****\n\n"）;
printf（"算术表达式对应的文法产生式如下：
\n"）;
for（i=0;i<8;i++）
printf（"%s\n",G[i]）;
printf（"________________________________________________________________________________\n"）;
printf（"\n该文法的FOLLOW集如下：
\n"）;//手动生成ＦＯＬＬＯＷ集合
for（i=0;i<8;i++）
{
printf（"FOLLOW（%s）={%s}\n",G[i],FOLLOW[i]）;
}
printf（"________________________________________________________________________________\n"）;
for（i=0,k=0;i<11;i++）//通过ＦＯＬＬＯＷ集合生成预测分析表
{
l=strlen（FOLLOW[i]）;
for（j=0;j{
MAP[k].vn=G[i][0];
MAP[k].vt=FOLLOW[i][j];
strcpy（MAP[k].s,Right[i]）;
k++;
}
}
printf（"\n表达式文法的预测分析表如下：
\n\n"）;
printf（""）;
for（i=0;i<9;i++）
printf（"%7c",VT[i]）;
printf（"\n"）;
for（i=0;i<5;i++）
{
printf（"---------------------------------------------------------------\n"）;
printf（"%7c",VN[i]）;
for（j=0;j<9;j++）
{
for（m=0;m{
if（VN[i]==MAP[m].vn&&VT[j]==MAP[m].vt）
{
printf（"%7s",MAP[m].s）;
break;
}
}
if（m==k）
printf（""）;
}
printf（"\n"）;
}
while（cin>>source）//输入源文件串进行预测分析
{
printf（"\n分析结果：
%s\n\n",Analyse（source））;
}
while
（1）;
return0;
}
将其改写LL
（1）文法：
手动生成的FOLLOW集合为：
生成的预测分析表为：
输入表达式：
（通过文件输入）
对表达式（（a+b）*3/5）#首先转换为token序列，以i代表标识符，以n代表常量，然后进行预测分析：
如果输入的是错误的表达式（少了一个括号），则：
升级会员 