实验二 LL分析法实验报告

《实验二 LL分析法实验报告》由会员分享，可在线阅读，更多相关《实验二 LL分析法实验报告（11页珍藏版）》请在装配图网上搜索。

1、实验二LL（1）分析法一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区 别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方 法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培 养适应社会多方面需要的能力。二、实验内容及设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左 推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的 规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义 性，无左递归，

2、无左公因子。当文法满足条件后，再分别构造文法每个非终结符 的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表， 最后利用分析表，根据LL（1）语法分析构造一个分析器。LL（1）的语法分析程 序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程 序也是采用了同样的方法进行语法分析，该程序是采用了 C+语言来编写，其逻 辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当 前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三 种可能的动作之一：（1）若X = a=#，则宣布分析成功，停止分

3、析过程。（2）若X = a #，则把X从STACK栈顶弹出，让a指向下一个输入符 号。（3）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关 于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符 号串按反序一一弹出STACK栈（若右部符号为e，则不推什么东西进STACK栈）。 若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。三、程序结构描述1、定义的变量初始化预测分析表：LL E8=TG,TG,error,error,error,error,error,error;LL G8=error”,error”,null”,+TG”,-TG”,error

4、”,error”,null;LL T8=FS,FS,error,error,error,error,error,error;LL S8=error,error,null”,null”,null”,*FS”,”/FS”,null;LL F8=i,(i),error,error,error,error,error,error);const int MaxLen=10;初始化栈的长度const int Length=10;初始化数组长度char Vn5=E,G,T,S,F;非终结符数组char Vt8=i,(,),+,-,*,/,#;终结符数组char ch,X; /全局变量，ch用于读当前字符，X

5、用于获取栈顶元素char strTokenLength;存储规约表达式2、定义的函数class stack栈的构造及初始化int length(char *c)输出字符数组的长度 void print(int i,char*c)剩余输入串的输出 void run()分析程序3、LL(1)预测分析程序流程图LL1)R测分析程序流程四、程序源代码及运行结果#includeusing namespace std;const int MaxLen=10; 初始化栈的长度const int Length=10;/初始化数组长度char Vn5=E,G,T,S,F;/ 非终结符数组char Vt8=i,(

6、,),+,-,*,/,#;/ 终结符数组char ch,X;/全局变量，ch用于读当前字符，X用于获取栈顶元素char strTokenLength;/存 储规约表达式struct LL/ll(1)分析表的构造字初始化char*c;LL E8=TG”,TG”,error”,error”,error”,error”,error”,error;LL G8=error”,error”,null”,+TG”,-TG”,error”,error”,null;LL T8=FS”,FS”,error”,error”,error”,error”,error”,error;LL S 8=error”,error

7、”,null”,null”,null”,*FS”,”/FS”,null;LL F8=i”,”(i)”,error”,error”,error”,error”,error”,error;class stack/栈的构造及初始化public:stack();/ 初始化bool empty() const;/ 是否为空bool full() const;/ 是否已满bool get_top(char &c)const;/ 取栈顶元素 bool push(const char c);/ 入栈bool pop();/删除栈顶元素 void out();/输出栈中元素stack()/ 析构private:

8、int count;/ 栈长度char dataMaxLen;/ 栈中元素;stack:stack()count=0;bool stack:empty() constif(count=0)return true;return false;bool stack:full() constif(count=MaxLen)return true;return false;bool stack:get_top(char &c)constif(empty()return false;elsec=datacount-1;return true;bool stack:push(const char c)if(

9、full()return false;datacount+=c;return true;bool stack:pop()if(empty() return false;count-;return true;void stack:out()(for(int i=0;icount;i+)coutdatai;cout;int length(char *c)(int l=0;for(int i=0;ci!=0;i+)l+;return l;void print(int i,char*c)/剩余输入串的输出(for(int j=i;jLength;j+)coutcj;cout;void run()(bo

10、ol flag=true;/ 循环条件int step=0,point=0;/ 步骤、指针int len;/ 长度cout请输入要规约的字符串：strToken;ch=strTokenpoint+;/读取第一个字符stack s;s.push(#);/栈中数据初始化s.push(E);s.get_top(X);/取栈顶元素所用产生式cout步骤分析栈剩余输入串动作endl;coutstep+ ;s.out();print(point- 1,strToken);cout初始化endl;while(flag)if(X=Vt0)|(X=Vtl)|(X=Vt2)|(X=Vt3)|(X=Vt4)|(X=

11、Vt5)|(X=V t6)判断是否为终结符(不包括#)if(X=ch)终结符，识别，进行下一字符规约s.popO;s.get_top(X);ch=strT okenpoint+;coutstep+s.out();print(point-1 ,strToken);coutGETNEXT(I)endl;elseflag=false;couterror! endl;else if(X=#)规约结束if(X=ch)coutstep+s.out();print(point- l,strToken);cout ch结束endl;s.pop()；flag=false;elseflag=false;coute

12、rror! endl;else if(X=Vn0) 非终结符 Efor(int i=0;i8;i+) 查分析表if(ch=Vti)if(strcmp(E i.c,error)=0)/ 出错 flag=false;couterrorX1X2的产生式进行入栈操作s.pop();len=length(Ei.c)-1;for(int j=len;j=0;j-)s.push(Ei.cj);coutstep+ ;s.out();print(point- 1,strToken);coutXEi.c=0;z-)coutEi.cz;cout)endl;s.get_top(X);else if(X=Vn1) 同上

13、，处理 G(for(int i=0;i8;i+)if(ch=Vti)(if(strcmp(Gi.c,null)=0)(s.pop();coutstep+ ;s.out();print(point- 1,strToken);coutX”POPendl;s.get_top(X);else if(strcmp(Gi.c,error)=0)(flag=false;couterror=0;j-)s.push(Gi.cj);coutstep+ s.out();print(point- l,strToken);coutX-Gi,c=O;z) coutGi.cz;cout)endl;s.get_top(X);

14、else if(X=Vn2) 同上 处理 Tfor(int i=0;i8;i+)if(ch=Vti)if(strcmp(T i.c,error)=0)flag=false;couterrorendl;else(s.pop();len=length(T i.c)-l;for(intj=len;j=0;j-) s.push(Ti.cj);coutstep+ s.out();print(point- l,strToken);coutX-T i.c for(int z=len;z=0;z) coutTi.cz;cout)endl;s.get_top(X);POP,PUSH(;POP,PUSH(;els

15、e if(X=Vn3)/同上 处理 S for(int i=0;i8;i+)if(ch=Vti)if(strcmp(Si.c,nnuHn)=O) s.popO;coutstep+s.out();print(point- l,strToken);cout POPendl;s.get_top(X);else if(strcmp(Si.c,error)=0)flag=false;couterrorendl;else(s.pop();len=length(S i.c)-l;for(intj=len;j=O;j-)s.push(Si.c|j)；coutstep+s.out();print(point-

16、l,strToken);coutX -S i. cPOP,PUSH(;for(int z=len;z=0;z)coutSi.cz;cout)endl;s.get_top(X);else if(X=Vn4) 同上处理 F for(int i=0;i=0;j-) s.push(Fi.c|j)； coutstep+s.out();print(point- 1,strToken);POP,PUSH(;coutXFi.c=0;z-) coutFi.cz;cout)endl; s.get_top(X);else 出错处理flag= false;couterrorTGPOP,PUSH2#GSFi*i+i#T

17、-FSPOP,PUSHiPOP,PUSH4GETNEXT5#GSF*i+i#S-*FSPOP,PUSH#GSFi+i#GETNEXTttGSii+i#F-iPOP,PUSHttGSGETNEXTttGS- EPOP10#GT +G-+TGPOP,PUSH11#GTittGETNEXT12ttGSFittT-FSPOP,PUSH13ttGSiittF-iPOP,PUSH14ttGttGETNEXT15ttGttS- POP16ttItG- POP17tttt#-#结束*青按任意键继续 .五、实验总结1. 本实例能利用正确的LL1文法分析表判断任意符号串是否属于该 文法的句子；显示了具体分析过程；支持打开、新建、保存分析表； 保存分析结果。2. 吸取了上次程序设计的经验教训，优化了代码整洁性，提高了程 序设计效率，尽可能细化函数功能，便于移植、错误查找和修改