精品资料
实验二 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),总控程序每次都执行下述
可编辑修改
精品资料
三种可能的动作之一：
(1) 若X = a = (2) 若X = a
符号。
‘ #'，则宣布分析成功，停止分析过程。
‘ #'，则把＜ 从STACK栈顶弹出，让a指向下一个输入
(3) 若X是一个非终结符，则查看预测分析表 M。若M[A , a]中存放着 关于
X 的一个产生式，那么，首先把 X 弹出 STACK 栈顶，然后，把产生式的 右部符号串按反序一一弹出 STACK栈(若右部符号为 £,则不推什么东西进 STACK栈)。若M[A ,a]中存放着“出错标志”，则调用出错诊断程序ERROR。
三、程序结构描述
1、定义的变量
初始化预测分析表：
LL E[8]={\"TG\LL G[8]={\"error\LL T[8]={\"FS\LL S[8]={\"error\LL F[8]={\"i\
const int MaxLen=10; 初始化栈的长度 const int Length=10; 初始化数组长度 char
Vn[5]={'E','G','T','S','F'}; 非终结符数组 char Vt[8]={'i','(',')','+','-','*','/','#'}; 终结符数组 char ch,X; / 全局
变量， ch 用于读当前字符， X 用于获取栈顶元素 char strToken[Length]; 存储规约表达式
2、定义的函数
可编辑修改
精品资料
class stack 栈的构造及初始化
输出字符数组的长度 剩余输入串的输出
int len gth(char *c) void prin t(i nt i,char*c) void run()
分析程序
3、LL(1)预测分析程序流程图
』和〈程序〉入
取一«入看号曲 1
,
----- r ------------------- 取弋入符^
•岀桂頂苻号能人*
LL(I)SS(分折趕序流程
四、程序源代码及运行结果 #in clude using n amespace std; const int MaxLen=10; //初始化栈的长度
可编辑修改
精品资料
const int Length=10;// 初始化数组长度 char Vn[5]={'E','G','T','S','F'};// 非终结符数组 char Vt[8]={'i','(',')','+','-','*','/','#'};// 终结符数组
char ch,X;// 全局变量， ch 用于读当前字符， X 用于获取栈顶元素 char strToken[Length];// 存储规约表达式 struct LL//ll(1)
{
分析表的构造字初始化
char*c;
};
LL E[8]={\"TG\LL G[8]={\"error\LL T[8]={\"FS\LL S[8]={\"error\LL F[8]={\"i\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 data[MaxLen];// 栈中元素
};
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=data[count-1]; return true;
}
}
bool stack::push(const char c)
{
if(full()) return false; data[count++]=c; return true;
}
bool stack::pop()
if(empty()) return false;
{
可编辑修改
精品资料
count--; return true;
}
void stack::out()
{
for(int i=0;i}int length(char *c)
{
int l=0;
for(int i=0;c[i]!='\\0';i++) l++; return l;
}
void print(int i,char*c)// 剩余输入串的输出
{
for(int j=i;j可编辑修改精品资料
void run()
{
bool flag=true;// 循环条件 int step=0,point=0;// 步骤、指针 int len;// 长度
cout<<\" 请输入要规约的字符串： \"<>strToken;ch=strToken[point++];// 读取第一个字符 stack s;
s.push('#');// 栈中数据初始化 s.push('E');
s.get_top(X);// 取栈顶元素 cout<<\" 步骤
\"<<\" 分析栈
\"<<\" 剩余输入串 \"<<\" 所用产生
式 \"<<\" 动作 \"<cout<print(point-1,strToken); cout<<\"\"<<\" 初始化 \"<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<print(point-1,strToken);cout<<\" \"<<\"GETNEXT(I)\"<}else
{
flag=false;
cout<<\"error!\"<}}
else if(X=='#')// 规约结束
if(X==ch)
{
可编辑修改
精品资料
cout<print(point-1,strToken); cout<<\" \"<\"<}\"<<\" 结束 \"<else{
flag=false;
cout<<\"error!\"<}}
else if(X==Vn[0]) // 非终结符 E
{
for(int i=0;i<8;i++)// if(ch==Vt[i])
{
查分析表
if(strcmp(E[i].c,\"error\")==0)// 出错
{
flag=false;
cout<<\"error\"<可编辑修改精品资料
}
else{ // 对形如 X->X1X2 的产生式进行入栈操
作
s.pop();
len=length(E[i].c)-1; for(int j=len;j>=0;j--) s.push(E[i].c[j]); cout<print(point-1,strToken);cout<\"<=0;z--) cout<}}
}
else if(X==Vn[1]) // 同上，处理 G
for(int i=0;i<8;i++) if(ch==Vt[i])
{
可编辑修改
{
精品资料
if(strcmp(G[i].c,\"null\")==0)
{
s.pop();
cout<print(point-1,strToken); coutvv\" \"<\"<<\" £ \"<<\" s.get_top(X);}
\"<<\"POP\"<else if(strcmp(G[i].c,\"error\")==0){
flag=false;
cout<<\"error\"<}else{
s.pop();
len=length(G[i].c)-1; for(int j=len;j>=0;j--) s.push(G[i].c[j]);
s.out(); print(point-1,strToken); cout<\"<\";可编辑修改
精品资料
z=len;z>=0;z--) cout<}}
}
else if(X==Vn[2]) // 同上 处理 T
{
for(int i=0;i<8;i++) if(ch==Vt[i])
{
if(strcmp(T[i].c,\"error\")==0)
{
flag=false;
cout<<\"error\"<}else{
s.pop();
len=length(T[i].c)-1;
可编辑修改
精品资料
for(int j=len;j>=0;j--)
s.push(T[i].c[j]); cout<print(point-1,strToken); cout<\"<=0;z--) cout<}\"<<\"POP,PUSH(\";
}
}
else if(X==Vn[3])// 同上 处理 S
{
for(int i=0;i<8;i++) if(ch==Vt[i])
{
if(strcmp(S[i].c,\"null\")==0)
{
s.pop();
cout<可编辑修改精品资料
s.out();
print(point-1,strToken); coutvv\"
\"<\"<<\" £ \"<<\"s.get_top(X);
}
else if(strcmp(S[i].c,\"error\")==0)
{
flag=false;
cout<<\"error\"<}else{
s.pop();
len=length(S[i].c)-1; for(int j=len;j>=0;j--) s.push(S[i].c[j]); cout<\";s.out(); print(point-1,strToken); cout<\"<=0;z--) cout<s.get_top(X);}
}
cout<<\")\"<可编辑修改\"<<\"POP\"<\"<<\"POP,PUSH(\";精品资料
}
else if(X==Vn[4]) // 同上 处理 F
{
for(int i=0;i<7;i++) if(ch==Vt[i])
{
if(strcmp(F[i].c,\"error\")==0)
{
flag=false; cout<<\"error\"<}else{
s.pop();
len=length(F[i].c)-1; for(int j=len;j>=0;j--) s.push(F[i].c[j]); cout<print(point-1,strToken);可编辑修改
精品资料
cout<\"<for(int z=len;z>=0;z--) cout<}\"<<\"POP,PUSH(\";
}
}
else // 出错处理
{
flag= false;
cout<<\"error\"<}}
}
int main()
{
run();
system(\"pause\"); return 0;
}
测试：输入 i*i+i#
可编辑修改
精品资料
结果:
请输入要规约的字符串: 分析栈 刑 剌余输人串 所用产生式 E->TG ttE ttGT POP,PUSH 初始化i ItGSF UGSL i*i+ifl I->FS F->i S->*FS POP,FUSH POP,PUSH(1> ttCS GETNEXTCn QETNEMKn ItGSP* ttGEP ttGSl POP,PUSH<£F*> POPrPUSHCi> i+itt i+iit «GS ItG +i# +ilt F->i GETNEXT<1> S-> £ POP 10 11 丄2 #GT + #GT #G£i +i# itt lit itt C->+TG T->FS F->i POP,PUGH GETNEXT POP,PUSH(SF> POP,PUSH GETMEXT<1> POP 13 14 15 16 17 »G S-> £ tt tt tt tt G-> 2 #->tt POP 按任意键维纹- 结束 五、实验总结1. 本实例能利用正确的LL1文法分析表判断任意符号串是否属于该 文法的句子；显示了具体分析过程；支持打开、新建、保存分析表； 保存分析结果。
2. 吸取了上次程序设计的经验教训，优化了代码整洁性，提高了程 序设计效率，尽可能细化函数功能，便于移植、错误查找和修改
可编辑修改
