实验二--LL(1)分析法实验报告

实验二LL(1)分析法一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二、实验内容及设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。三、程序结构描述1、定义的变量初始化预测分析表：LLE[8]={TG,TG,error,error,error,error,error,error};LLG[8]={error,error,null,+TG,-TG,error,error,null};LLT[8]={FS,FS,error,error,error,error,error,error};LLS[8]={error,error,null,null,null,*FS,/FS,null};LLF[8]={i,(i),error,error,error,error,error,error};constintMaxLen=10;初始化栈的长度constintLength=10;初始化数组长度charVn[5]={'E','G','T','S','F'};非终结符数组charVt[8]={'i','(',')','+','-','*','/','#'};终结符数组charch,X;/全局变量，ch用于读当前字符，X用于获取栈顶元素charstrToken[Length];存储规约表达式2、定义的函数classstack栈的构造及初始化intlength(char*c)输出字符数组的长度voidprint(inti,char*c)剩余输入串的输出voidrun()分析程序3、LL(1)预测分析程序流程图四、程序源代码及运行结果#includeiostreamusingnamespacestd;constintMaxLen=10;//初始化栈的长度constintLength=10;//初始化数组长度charVn[5]={'E','G','T','S','F'};//非终结符数组charVt[8]={'i','(',')','+','-','*','/','#'};//终结符数组charch,X;//全局变量，ch用于读当前字符，X用于获取栈顶元素charstrToken[Length];//存储规约表达式structLL//ll(1)分析表的构造字初始化{char*c;};LLE[8]={TG,TG,error,error,error,error,error,error};LLG[8]={error,error,null,+TG,-TG,error,error,null};LLT[8]={FS,FS,error,error,error,error,error,error};LLS[8]={error,error,null,null,null,*FS,/FS,null};LLF[8]={i,(i),error,error,error,error,error,error};classstack//栈的构造及初始化{public:stack();//初始化boolempty()const;//是否为空boolfull()const;//是否已满boolget_top(char&c)const;//取栈顶元素boolpush(constcharc);//入栈boolpop();//删除栈顶元素voidout();//输出栈中元素~stack(){}//析构private:intcount;//栈长度chardata[MaxLen];//栈中元素};stack::stack(){count=0;}boolstack::empty()const{if(count==0)returntrue;returnfalse;}boolstack::full()const{if(count==MaxLen)returntrue;returnfalse;}boolstack::get_top(char&c)const{if(empty())returnfalse;else{c=data[count-1];returntrue;}}boolstack::push(constcharc){if(full())returnfalse;data[count++]=c;returntrue;}boolstack::pop(){if(empty())returnfalse;count--;returntrue;}voidstack::out(){for(inti=0;icount;i++)coutdata[i];cout;}intlength(char*c){intl=0;for(inti=0;c[i]!='\0';i++)l++;returnl;}voidprint(inti,char*c)//剩余输入串的输出{for(intj=i;jLength;j++)coutc[j];cout;}voidrun(){boolflag=true;//循环条件intstep=0,point=0;//步骤、指针intlen;//长度cout请输入要规约的字符串：endl;cinstrToken;ch=strToken[point++];//读取第一个字符stacks;s.push('#');//栈中数据初始化s.push('E');s.get_top(X);//取栈顶元素cout步骤分析栈剩余输入串所用产生式动作endl;coutstep++;s.out();print(point-1,strToken);cout初始化endl;while(flag){if((X==Vt[0])||(X==Vt[1])||(X==Vt[2])||(X==Vt[3])||(X==Vt[4])||(X==Vt[5])||(X==Vt[6]))//判断是否为终结符（不包括#）{if(X==ch)//终结符,识别，进行下一字符规约{s.pop();s.get_top(X);ch=strToken[point++];coutstep++;s.out();print(point-1,strToken);coutGETNEXT(I)endl;}else{flag=false;couterror!endl;}}elseif(X=='#')//规约结束{if(X==ch){coutstep++;s.out();print(point-1,strToken);coutX-ch结束endl;s.pop();flag=false;}else{flag=false;couterror!endl;}}elseif(X==Vn[0])//非终结符E{for(inti=0;i8;i++)//查分析表if(ch==Vt[i]){if(strcmp(E[i].c,error)==0)//出错{flag=false;couterrorendl;}else{//对形如X-X1X2的产生式进行入栈操作s.pop();len=length(E[i].c)-1;for(intj=len;j=0;j--)s.push(E[i].c[j]);coutstep++;s.out();print(point-1,strToken);coutX-E[i].cPOP,PUSH(;for(intz=len;z=0;z--)coutE[i].c[z];cout)endl;s.get_top(X);}}}elseif(X==Vn[1])//同上，处理G{for(inti=0;i8;i++)if(ch==Vt[i]){if(strcmp(G[i].c,null)==0){s.pop();coutstep++;s.out();print(point-1,strToken);coutX-εPOPendl;s.get_top(X);}elseif(strcmp(G[i].c,error)==0){flag=false;couterrorendl;}else{s.pop();len=length(G[i].c)-1;for(intj=len;j=0;j--)s.push(G[i].c[j]);coutstep++;s.out();print(point-1,strToken);coutX-G[i].cPOP,PUSH(;for(intz=len;z=0;z--)coutG[i].c[z];cout)endl;s.get_top(X);}}}elseif(X==Vn[2])//同上处理T{for(inti=0;i8;i++)if(ch==Vt[i]){if(strcmp(T[i].c,error)==0){flag=false;couterrorendl;}else{s.pop();len=length(T[i].c)-1;for(intj=len;j=0;j--)s.push(T[i].c[j]);coutstep++;s.out();print(point-1,strToken);coutX-T[i].cPOP,PUSH(;for(intz=len;z=0;z--)coutT[i].c[z];cout)endl;s.get_top(X);}}}elseif(X==Vn[3])//同上处理S{for(inti=0;i8;i++)if(ch==Vt[i]){if(strcmp(S[i].c,null)==0){s.pop();coutstep++;s.out();print(point-1,strToken);coutX-εPOPendl;s.get_top(X);}elseif(strcmp(S[i].c,error)==0){flag=false;couterrorendl;}else{s.pop();len=length(S[i].c)-1;for(intj=len;j=0;j--)s.push(S[i].c[j]);coutstep++;s.out();print(