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

实验二 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。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。三、程序结构描述1、定义的变量初始化预测分析表：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 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用于获取栈顶元素char strTokenLength; 存储规约表达式2、定义的函数class stack 栈的构造及初始化int length(char *c) 输出字符数组的长度void print(int i,char*c) 剩余输入串的输出void run() 分析程序3、LL(1)预测分析程序流程图四、程序源代码及运行结果#includeusing namespace std;const int MaxLen=10; /初始化栈的长度 const int Length=10;/初始化数组长度 char Vn5=E,G,T,S,F;/非终结符数组 char Vt8=i,(,),+,-,*,/,#;/终结符数组 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 S8=error,error,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: int count;/栈长度 char dataMaxLen;/栈中元素 ;stack:stack() count=0;bool stack:empty() const if(count=0) return true; return false;bool stack:full() const if(count=MaxLen) return true; return false;bool stack:get_top(char &c)const if(empty() return false; else c=datacount-1; return true; bool stack:push(const char c) if(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() bool 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=Vt1)|(X=Vt2)|(X=Vt3)|(X=Vt4)|(X=Vt5)|(X=Vt6) /判断是否为终结符（不包括#） if(X=ch)/终结符,识别，进行下一字符规约 s.pop(); s.get_top(X); ch=strTokenpoint+; coutstep+ ; s.out(); print(point-1,strToken); cout GETNEXT(I)endl; else flag=false; couterror!endl; else if(X=#)/规约结束 if(X=ch) coutstep+ ; s.out(); print(point-1,strToken); cout Xch 结束endl; s.pop(); flag=false; else flag=false; couterror!endl; else if(X=Vn0) /非终结符E for(int i=0;i8;i+)/查分析表 if(ch=Vti) if(strcmp(Ei.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) /同上，处理 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); cout X 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-1,strToken); coutXGi.c =0;z-) coutGi.cz; cout)endl; s.get_top(X); else if(X=Vn2) /同上 处理 T for(int i=0;i8;i+) if(ch=Vti) if(strcmp(Ti.c,error)=0) flag=false; couterror=0;j-) s.push(Ti.cj); coutstep+ ; s.out(); print(point-1,strToken); coutXTi.c =0;z-) coutTi.cz; cout)endl; s.get_top(X); else if(X=Vn3)/同上 处理 S for(int i=0;i8;i+) if(ch=Vti) if(strcmp(Si.c,null)=0) s.pop(); coutstep+ ; s.out(); print(point-1,strToken); cout X POPendl; s.get_top(X); else if(strcmp(Si.c,error)=0) flag=false; couterror=0;j-) s.push(Si.cj); coutstep+ ; s.out(); print(point-1,strToken); coutXSi.c =0;z-) coutSi.cz; cout)endl; s.get_top(X); else if(X=Vn4) /同上 处理 F for(int i=0;i7;i+) if(ch=Vti) if(strcmp(Fi.c,error)=0) flag=false; couterror=0;j-) s.push(Fi.cj); coutstep+ ; s.out(); print(point-1,strToken); coutXFi.c =0;z-) coutFi.cz; cout)end