北邮编译原理LL1语法分析程序.docx

1、LL(1)语法分析程序2010211306班 赵雪莹（10211310）语法分析程序：该语法分析程序实现对算术表达式的语法分析，并且在对输入表达式进行分析的过程中，输出所采用的产生式。该程序使用的是LL（1）语法分析程序，为给定文法构造预测分析表，并通过预测分析表对输入的表达式进行预测分析，并将栈顶状态和预测分析过程详细输出，如果匹配成功则接受，如果匹配不成功则返回错误信息。给定文法的产生式：E-E+T | E-T | TT-T*F | T/F | FF- id | (E) | num源代码：#include #include #include #include #include using

2、namespace std;struct Node1 char vn; char vt; char s12;MAP22;/存储分析预测表每个位置对应的终结符，非终结符，产生式 int k;char G1212=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代表空char VN6=E,R,T,W,F;/存储非终结符 char VT9=i,n,+,-,*,/,(,),#;/存储终结符 char FOLLOW1212=(,i,n,+,-,),#,(,i,n,*,/,+,-,),#,(,i,

3、n;/存储文法中每个产生式对应的FOLLOW集合 char Right128=-TR,-+TR,-TR,-e,-FW,-*FW,-/FW,-e,-(E),-i,-n;stack stak,stak1,stak2;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;ila;i+) for(j=0;jlb;j+) if(ai=bj) return 1; return 0;char *Find(char vn,char vt) int i; for(i=0;ik;i+) if(MAPi.vn=vn & MA

4、Pi.vt=vt) return MAPi.s; return error;char * Analyse(char * word) char p,c,action10,output10; int i=1,l=strlen(word),j,k=0,l_act,m,x; printf(_n); printf(n 对符号串%s的分析过程n,word); for(x=0;xl;x+)/把用字母数字表示的输入串转换为token序列的表示方法 c=wordx; if(c=a)|(c=A) wordx=i; else if(c=0&c=9) wordx=n; else wordx=c; while(!sta

5、k.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;j1;j-) sta

6、k.push(actionj); if(strcmp(output,#)!=0)/匹配不成功 return ERROR; int main () freopen(in.txt,r,stdin); char source100; int i,j,flag,l,m; printf(n*R代表E,W代表T,e代表空*nn); printf(算术表达式对应的文法产生式如下：n); for(i=0;i8;i+) printf( %sn,Gi); printf(_n); printf(n该文法的FOLLOW集如下：n); /手动生成集合 for(i=0;i8;i+) printf( FOLLOW(%s)

7、= %s n,Gi,FOLLOWi); printf(_n); for(i=0,k=0;i11;i+)/通过集合生成预测分析表 l=strlen(FOLLOWi); for(j=0;jl;j+=2) MAPk.vn=Gi0; MAPk.vt=FOLLOWij; strcpy(MAPk.s,Righti); k+; printf(n表达式文法的预测分析表如下：nn); printf( ); for(i=0;i9;i+) printf(%7c,VTi); printf(n); for(i=0;i5;i+) printf( -n); printf(%7c,VNi); for(j=0;j9;j+) for(m=0;msource)/输入源文件串进行预测分析 printf(n分析结果：%snn,Analyse(source); while(1); return 0;将其改写LL（1）文法：手动生成的FOLLOW集合为：生成的预测分析表为：输入表达式：（通过文件输入）对表达式（(a+b)*3/5）#首先转换为token序列，以i代表标识符，以n代表常量，然后进行预测分析：如果输入的是错误的表达式（少了一个括号），则：