北邮编译原理LL1语法分析程序.docx
- 文档编号:1235509
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:8
- 大小:141.78KB
北邮编译原理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"};
stack
boolcompare(char*a,char*b)
{
inti,la=strlen(a),j,lb=strlen(b);
for(i=0;i for(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;j output[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");//手动生成FOLLOW集合 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++)//通过FOLLOW集合生成预测分析表 { 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代表常量,然后进行预测分析: 如果输入的是错误的表达式(少了一个括号),则:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邮编 原理 LL1 语法分析 程序