实验二-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)预测分析程序流程图四、程序源代码及运行结果#include<iostream>usingnamespacestd;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;i<count;i++)cout<<data[i];cout<<"";}intlength(char*c){intl=0;for(inti=0;c[i]!='\0';i++)l++;returnl;}voidprint(inti,char*c)//剩余输入串的输出{for(intj=i;j<Length;j++)cout<<c[j];cout<<"";}voidrun(){boolflag=true;//循环条件intstep=0,point=0;//步骤、指针intlen;//长度cout<<"请输入要规约的字符串："<<endl;cin>>strToken;ch=strToken[point++];//读取第一个字符stacks;s.push('#');//栈中数据初始化s.push('E');s.get_top(X);//取栈顶元素cout<<"步骤"<<"分析栈"<<"剩余输入串"<<"所用产生式"<<"动作"<<endl;cout<<step++<<"";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++];cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<"GETNEXT(I)"<<endl;}else{flag=false;cout<<"error!"<<endl;}}elseif(X=='#')//规约结束{if(X==ch){cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<ch<<""<<"结束"<<endl;s.pop();flag=false;}else{flag=false;cout<<"error!"<<endl;}}elseif(X==Vn[0])//非终结符E{for(inti=0;i<8;i++)//查分析表if(ch==Vt[i]){if(strcmp(E[i].c,"error")==0)//出错{flag=false;cout<<"error"<<endl;}else{//对形如X->X1X2的产生式进行入栈操作s.pop();len=length(E[i].c)-1;for(intj=len;j>=0;j--)s.push(E[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<E[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<E[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[1])//同上，处理G{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(G[i].c,"null")==0){s.pop();cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<"ε"<<""<<"POP"<<endl;s.get_top(X);}elseif(strcmp(G[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(G[i].c)-1;for(intj=len;j>=0;j--)s.push(G[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<G[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<G[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[2])//同上处理T{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(T[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(T[i].c)-1;for(intj=len;j>=0;j--)s.push(T[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<T[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<T[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[3])//同上处理S{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(S[i].c,"null")==0){s.pop();cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<"ε"<<""<<"POP"<<endl;s.get_top(X);}elseif(strcmp(S[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(S[i].c)-1;for(intj=len;j>=0;j--)s.push(S[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<S[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<S[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X=