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

1、.1. 实验目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的构造方法，掌握LL(1) 驱动程序的构造方法。2.实验要求：实现LR分析法（P147,例4.6）或预测分析法（P121,例4.3）。3.实验环境：一台配置为1G的XP操作系统的PC机;Visual C+6.0.4.实验原理：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语 法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上

2、而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。自顶向下带递归语法分析：1、首先对所以的生成式消除左递归、提取公共左因子2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。 这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终

3、结符函数。4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。 5.软件设计与编程：对应源程序代码： #include #include #include using namespace std;struct Node1 char vn; char vt; char s10;MAP20; /存储分析预测表每个位置对应的终结符，非终结符，产生式 int k; /用R代表E,W代表T,e代表空char start=E;int len=8;charG1010=E-TR,R-+TR,R

4、-e,T-FW,W-*FW,W-e,F-(E),F-i;/存储文法中的产生式 char VN6=E,R,T,W,F; /存储非终结符 char VT6=i,+,*,(,),#; /存储终结符 char SELECT1010=(,i,+,),#,(,i,*,+,),#,(,i;/存储文法中每个产生式对应的SELECT集 char Right108=-TR,-+TR,-e,-FW,-*FW,-e,-(E),-i;stack stak;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;ila;i+)for

5、(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 & MAPi.vt=vt)return MAPi.s; return error;char * Analyse(char * word) char p,action10,output10; int i=1,j,l=strlen(word),k=0,l_act,m; while(!stak.empty() stak.pop(); stak.push(#);stak.push(start);

6、 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;j1;j-)stak.push(actionj); if(strcmp(output,#)!=0)return ERROR; int main () freopen(in.txt,r,stdin)

7、; char source100; int i,j,flag,l,m; printf(n*为了方便编写程序，用R代表E,W代表T,e代表空*nn); printf(该文法的产生式如下：n); for(i=0;ilen;i+)printf( %sn,Gi); printf(_n); printf(n该文法的SELECT集如下：n); for(i=0;ilen;i+) printf( SELECT(%s) = %s n,Gi,SELECTi); printf(_n); /判断是否是LL(1)文法 flag=1; for(i=0;i8;i+) for(j=i+1;j8;j+) if(Gi0=Gj0)

8、 if(compare(SELECTi,SELECTj) 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(SELECTi); for(j=0;jl;j+=2) MAPk.vn=Gi0; MAPk.vt=SELECTij; strcpy(MAPk.s,Righti); k+; printf(n表达式文法的预测分析表如下：nn); printf( ); for(i=0;i6;i+)printf(%10c,VTi); printf(n); for