编译原理-语法分析程序设计(LL(1)分析法)

1.实验目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的构造方法，掌握LL(1)驱动程序的构造方法。2.实验要求：实现LR分析法（P147,例4.6）或预测分析法（P121,例4.3）。3.实验环境：一台配置为1G的XP操作系统的PC机;VisualC++6.0.4.实验原理：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。自顶向下带递归语法分析：1、首先对所以的生成式消除左递归、提取公共左因子2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终结符函数。4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。5.软件设计与编程：对应源程序代码：#includeiostream.h#includestdio.h#includestackusingnamespacestd;structNode1{charvn;charvt;chars[10];}MAP[20];//存储分析预测表每个位置对应的终结符，非终结符，产生式intk;//用R代表E',W代表T',e代表空charstart='E';intlen=8;charG[10][10]={E-TR,R-+TR,R-e,T-FW,W-*FW,W-e,F-(E),F-i};//存储文法中的产生式charVN[6]={'E','R','T','W','F'};//存储非终结符charVT[6]={'i','+','*','(',')','#'};//存储终结符charSELECT[10][10]={(,i,+,),#,(,i,*,+,),#,(,i};//存储文法中每个产生式对应的SELECT集charRight[10][8]={-TR,-+TR,-e,-FW,-*FW,-e,-(E),-i};stackcharstak;boolcompare(char*a,char*b){inti,la=strlen(a),j,lb=strlen(b);for(i=0;ila;i++){for(j=0;jlb;j++){if(a[i]==b[j])return1;}}return0;}char*Find(charvn,charvt){inti;for(i=0;ik;i++){if(MAP[i].vn==vn&&MAP[i].vt==vt){returnMAP[i].s;}}returnerror;}char*Analyse(char*word){charp,action[10],output[10];inti=1,j,l=strlen(word),k=0,l_act,m;while(!stak.empty()){stak.pop();}stak.push('#');stak.push(start);printf(___________________________________________________________\n);printf(\n对符号串%s的分析过程\n,word);printf(-----------------------------------------------------------------------\n);printf(\n);printf(步骤栈顶元素剩余输入串动作\n);printf(-----------------------------------------------------------------------\n);p=stak.top();while(p!='#'){printf(%7d,i++);p=stak.top();stak.pop();printf(%6c,p);for(j=k,m=0;jl;j++){output[m++]=word[j];}output[m]='\0';printf(%10s,output);if(p==word[k]){if(p=='#'){printf(分析成功\n);returnSUCCESS;}printf(匹配终结符%c\n,p);k++;}else{strcpy(action,Find(p,word[k]));if(strcmp(action,error)==0){printf(没有可用的产生式\n);returnERROR;}printf(展开非终结符%c%s\n,p,action);intl_act=strlen(action);if(action[l_act-1]=='e'){continue;}for(j=l_act-1;j1;j--){stak.push(action[j]);}}}if(strcmp(output,#)!=0)returnERROR;}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;ilen;i++){printf(%s\n,G[i]);}printf(___________________________________________________________\n);printf(\n该文法的SELECT集如下：\n);for(i=0;ilen;i++){printf(SELECT(%s)={%s}\n,G[i],SELECT[i]);}printf(___________________________________________________________\n);//判断是否是LL(1)文法flag=1;for(i=0;i8;i++){for(j=i+1;j8;j++){if(G[i][0]==G[j][0]){if(compare(SELECT[i],SELECT[j])){flag=0;break;}}}if(j!=8){break;}}if(flag){printf(\n有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。\n);}else{printf(\n有相同左部产生式的SELECT集合的交集不为空，所以文法不是LL（1）文法。\n);}printf(___________________________________________________________\n);//预测分析表for(i=0,k=0;i8;i++){l=strlen(SELECT[i]);for(j=0;jl;j+=2){MAP[k].vn=G[i][0];MAP[k].vt=SELECT[i][j];strcpy(MAP[k].s,Right[i]);k++;}}printf(\n表达式文法的预测分析表如下：\n\n);printf();for(i=0;i6;i++){printf(%10c,VT[i]);}printf(\n);for(i=0;i5;i++){printf(---------------------------------------------------------------\n);printf(%10c,VN[i]);for(j=0;j6;j++){for(m=0;mk;m++){if(VN[i]==MAP[m].vn&&VT[j]==MAP[m].vt){printf(%10s,MAP[m].s);break;}}if(m==k){printf();}}printf(\n);}//预测分析程序Analyse函数//输入源文件串while(cinsource){printf(\n分析结果：%s\n\n,Analyse(source));}return0;}6.程序测试结果：