LL(1)分析法

计算机科学与技术系实验报告专业名称计算科学与技术课程名称编译原理项目名称LL(1)分析法班级14计科一班学号姓名同组人员无实验日期2016.11.11一、实验目的与要求：（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。）目的：根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。要求：对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG|—TG（3）G-ε（4）T-FS（5）S-*FS|/FS（6）S-ε（7）F-(E)（8）F-i相关知识点：LL（1）分析法运用的是自顶向下的分析法，通过显示地维护一个栈进行语法分析。其主要过程就是匹配替换的过程，还设计first集和follow集的算法。二、实验内容（根据本次实验项目的具体任务和要求，完成相关内容，可包括：实验目的、算法原理、实验仪器、设备选型及连线图、算法描述或流程图、源代码、实验运行步骤、关键技术分析、测试数据与实验结果、其他）内容：1、根据上述文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。2、构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析构造。3、分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上向下的分析过程。模块结构：（1）定义部分：定义常量，变量，数据结构。（2）初始化：设立LL（1）分析法、初始化变量空间（包括堆栈、构造体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串。（4）利用LL（1）分析算法进行表达式处理:根据LL（1）分析表达式对表达式符号串进行堆栈（或其它）操作，输出分析结果，如果遇到错误则显示错误信息。流程图如下文字表示如下：从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。在实现LL（1）分析法的过程中必须按照实验的要求给的产生式写出first集和follow集创建预测分析表，用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。才能实现接下来的过程。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号ch过程的。程序中将要用到的几个重要数据如下：一个全局变量ch，存放由文件输入得到的字符。一个函数宏READ(ch)，实现读取文件中的字符。五个处理：非终结符E，G,T,S,F。程序代码如下：#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;//栈初始化长度为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++)//读取栈中元素，不为空即加1l++;returnl;}voidprint(inti,char*c)//剩余输入串的输出{for(intj=i;jLength;j++)coutc[j];cout;}voidrun(){boolflag=true;//循环条件intstep=0,point=0;//步骤、指针intlen;//长度cout请输入要规约的字符串(与i有关的串)：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(point-1,strToken);coutX-S[i].cPOP,PUSH(;for(in