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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理-语法分析程序设计(LL(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.实验原理：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语 法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。自顶向下带递归语法分析：1、首先对所以的生成式消除左递归、提取公共左因子2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。 这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终结符函数。4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。 5.软件设计与编程：对应源程序代码： #include <iostream.h>#include <stdio.h>#include <stack>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->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 <char> stak;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;i<la;i+)for(j=0;j<lb;j+) if(ai=bj)return 1; return 0;char *Find(char vn,char vt) int i; for(i=0;i<k;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); 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;j<l;j+)outputm+=wordj; outputm='0' printf("%10s",output); if(p=wordk) if(p='#') printf(" 分析成功 n"); return "SUCCESS" printf(" 匹配终结符%cn",p); k+; else strcpy(action,Find(p,wordk); if(strcmp(action,"error")=0) printf(" 没有可用的产生式n"); return "ERROR" printf(" 展开非终结符%c%sn",p,action); int l_act=strlen(action); if(actionl_act-1='e')continue; for(j=l_act-1;j>1;j-)stak.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;i<len;i+)printf(" %sn",Gi); printf("_n"); printf("n该文法的SELECT集如下：n"); for(i=0;i<len;i+) printf(" SELECT(%s) = %s n",Gi,SELECTi); printf("_n"); /判断是否是LL(1)文法 flag=1; for(i=0;i<8;i+) for(j=i+1;j<8;j+) if(Gi0=Gj0) 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;i<8;i+) l=strlen(SELECTi); for(j=0;j<l;j+=2) MAPk.vn=Gi0; MAPk.vt=SELECTij; strcpy(MAPk.s,Righti); k+; printf("n表达式文法的预测分析表如下：nn"); printf(" "); for(i=0;i<6;i+)printf("%10c",VTi); printf("n"); for(i=0;i<5;i+) printf(" -n"); printf("%10c",VNi); for(j=0;j<6;j+) for(m=0;m<k;m+) if(VNi=MAPm.vn && VTj=MAPm.vt) printf("%10s",MAPm.s); break; if(m=k)printf(" "); printf("n"); /预测分析程序Analyse函数 /输入源文件串 while(cin>>source) printf("n分析结果：%snn",Analyse(source); return 0;6. 程序测试结果：-