课 程 编译原理 实验名称 实验二 LL(1)分析法 实验目的
1.掌握LL(1)分析法的基本原理;
2.掌握LL(1)分析表的构造方法;
3.掌握LL(1)驱动程序的构造方法。
一.实验内容及要求
根据某一文法编制调试LL(1)分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。
对下列文法,用LL(1)分析法对任意输入的符号串进行分析:
(1)E->TG
(2)G->+TG
(3)G->ε
(4)T->FS
(5)S->*FS
(6)S->ε
(7)F->(E)
(8)F->i
程序输入一以#结束的符号串(包括+*()i#),如:i+i*i#。输出过程如下:
步骤 分析栈 剩余输入串 所用产生式
1 E i+i*i# E->TG
... ... ... ...
二.实验过程及结果
代码如下:
#include
#include "edge.h"
using namespace std;
edge::edge()
{
cin>>left>>right;
rlen=right.length();
if(NODE.find(left)>NODE.length())
NODE+=left;
}
string edge::getlf()
{
return left;
}
string edge::getrg()
{
return right;
}
string edge::getfirst()
{
return first;
}
string edge::getfollow()
{
return follow;
}
string edge::getselect()
{
return select;
}
string edge::getro()
{
string str;
str+=right[0];
return str;
}
int edge::getrlen()
{
return right.length();
}
void edge::newfirst(string w)
{
int i;
for(i=0;i
if(first.find(w[i])>first.length())
first+=w[i];
}
void edge::newfollow(string w)
{
int i;
for(i=0;i
if(follow.find(w[i])>follow.length()&&w[i]!='@')
follow+=w[i];
}
void edge::newselect(string w)
{
int i;
for(i=0;i
if(select.find(w[i])>select.length()&&w[i]!='@')
select+=w[i];
}
void edge::delfirst()
{
int i=first.find('@');
first.erase(i,1);
}
int SUM;
string NODE,ENODE;
//计算first
void first(edge ni,edge *n,int x)
{
int i,j;
for(j=0;j
{
if(ni.getlf()==n[j].getlf())
{
if(NODE.find(n[j].getro())
{
for(i=0;i
if(n[i].getlf()==n[j].getro())
first(n[i],n,x);
}
else
n[x].newfirst(n[j].getro());
}
}
}
//计算follow
void follow(edge ni,edge *n,int x)
{
int i,j,k,s;
string str;
for(i=0;i
{
s=NODE.find(ni.getrg()[i]);
if(s-1) //是非终结符
if(i
for(j=0;j
if(n[j].getlf().find(ni.getrg()[i])==0)
{
if(NODE.find(ni.getrg()[i+1])
{
for(k=0;k
if(n[k].getlf().find(ni.getrg()[i+1])==0)
{
n[j].newfollow(n[k].getfirst());
if(n[k].getfirst().find("@")
n[j].newfollow(ni.getfollow());
}
}
else
{
str.erase();
str+=ni.getrg()[i+1];
n[j].newfollow(str);
}
}
}
}
//计算select
void select(edge &ni,edge *n)
{
int i,j;
if(ENODE.find(ni.getro())
{
ni.newselect(ni.getro());
if(ni.getro()=="@")
ni.newselect(ni.getfollow());
}
else
for(i=0;i
{
for(j=0;j
if(ni.getrg()[i]==n[j].getlf()[0])
{
ni.newselect(n[j].getfirst());
if(n[j].getfirst().find('@')>n[j].getfirst().length())
return;
}
}
}
//输出集合
void out(string p)
{
int i;
if(p.length()==0)
return;
cout
for(i=0;i
{
cout
}
cout
}
//连续输出符号
void outfu(int a,string c)
{
int i;
for(i=0;i
cout
}
//输出预测分析表
void outgraph(edge *n,string (*yc)[50])
{
int i,j,k;
bool flag;
for(i=0;i
{
if(ENODE[i]!='@')
{
outfu(10," ");
cout
}
}
outfu(10," ");
cout
int x;
for(i=0;i
{
outfu(4," ");
cout
outfu(5," ");
for(k=0;k
{
flag=1;
for(j=0;j
{
if(NODE[i]==n[j].getlf()[0])
{
x=n[j].getselect().find(ENODE[k]);
if(x-1)
{
cout"
yc[i][k]=n[j].getrg();
outfu(9-n[j].getrlen()," ");
flag=0;
}
x=n[j].getselect().find('#');
if(k==ENODE.length()-1&&x-1) {
cout"
yc[i][j]=n[j].getrg();
}
}
}
if(flag&&ENODE[k]!='@')
outfu(11," ");
}
cout
}
}
//分析符号串
int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b)
{
char ch,a;
int x,i,j,k; b++; cout9) outfu(8," "); else outfu(9," "); cout-1) { if(ch==a) { fenxi.erase(fenxi.length()-1,1); chuan.erase(0,1); cout
fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b)) return 1;
else
return 0;
}
else
{
i=NODE.find(ch);
if(a=='#')
{
x=ENODE.find('@');
if(x-1) j=ENODE.length()-1; else
j=ENODE.length();
}
else
j=ENODE.find(a);
if(yc[i][j].length())
{
cout"-1;k--) if(yc[i][j][k]!='@')
fenxi+=yc[i][j][k];
if(pipei(chuan,fenxi,yc,b)) return 1;
else
return 0;
}
else
return 0;
}
}
}
void main()
{
edge *n;
string str,(*yc)[50];
int i,j,k;
bool flag=0;
cin>>SUM; coutNODE.length()&&ENODE.find(str[j])>ENODE.length()) ENODE+=str[j]; } //计算first集合 for(i=0;in[j].getfirst().length()) { n[i].delfirst(); break; } } } } }
for(k=0;k
outfu(SUM," "); cout>chuan; fchuan=chuan; fenxi="#"; fenxi+=NODE[0]; i=0; cout
outfu(7," ");
cout
outfu(10," ");
cout
outfu(8," ");
cout
if(pipei(chuan,fenxi,yc,i))
cout
else
cout
}
截屏如下:
三.实验中的问题及心得
这次实验让我更加熟悉了LL(1)的工作流程以及LL(1)分析表的构造方法。以前课堂上搞不懂的算法流程通过实验都能得到进一步的了解。
课 程 编译原理 实验名称 实验二 LL(1)分析法 实验目的
1.掌握LL(1)分析法的基本原理;
2.掌握LL(1)分析表的构造方法;
3.掌握LL(1)驱动程序的构造方法。
一.实验内容及要求
根据某一文法编制调试LL(1)分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。
对下列文法,用LL(1)分析法对任意输入的符号串进行分析:
(1)E->TG
(2)G->+TG
(3)G->ε
(4)T->FS
(5)S->*FS
(6)S->ε
(7)F->(E)
(8)F->i
程序输入一以#结束的符号串(包括+*()i#),如:i+i*i#。输出过程如下:
步骤 分析栈 剩余输入串 所用产生式
1 E i+i*i# E->TG
... ... ... ...
二.实验过程及结果
代码如下:
#include
#include "edge.h"
using namespace std;
edge::edge()
{
cin>>left>>right;
rlen=right.length();
if(NODE.find(left)>NODE.length())
NODE+=left;
}
string edge::getlf()
{
return left;
}
string edge::getrg()
{
return right;
}
string edge::getfirst()
{
return first;
}
string edge::getfollow()
{
return follow;
}
string edge::getselect()
{
return select;
}
string edge::getro()
{
string str;
str+=right[0];
return str;
}
int edge::getrlen()
{
return right.length();
}
void edge::newfirst(string w)
{
int i;
for(i=0;i
if(first.find(w[i])>first.length())
first+=w[i];
}
void edge::newfollow(string w)
{
int i;
for(i=0;i
if(follow.find(w[i])>follow.length()&&w[i]!='@')
follow+=w[i];
}
void edge::newselect(string w)
{
int i;
for(i=0;i
if(select.find(w[i])>select.length()&&w[i]!='@')
select+=w[i];
}
void edge::delfirst()
{
int i=first.find('@');
first.erase(i,1);
}
int SUM;
string NODE,ENODE;
//计算first
void first(edge ni,edge *n,int x)
{
int i,j;
for(j=0;j
{
if(ni.getlf()==n[j].getlf())
{
if(NODE.find(n[j].getro())
{
for(i=0;i
if(n[i].getlf()==n[j].getro())
first(n[i],n,x);
}
else
n[x].newfirst(n[j].getro());
}
}
}
//计算follow
void follow(edge ni,edge *n,int x)
{
int i,j,k,s;
string str;
for(i=0;i
{
s=NODE.find(ni.getrg()[i]);
if(s-1) //是非终结符
if(i
for(j=0;j
if(n[j].getlf().find(ni.getrg()[i])==0)
{
if(NODE.find(ni.getrg()[i+1])
{
for(k=0;k
if(n[k].getlf().find(ni.getrg()[i+1])==0)
{
n[j].newfollow(n[k].getfirst());
if(n[k].getfirst().find("@")
n[j].newfollow(ni.getfollow());
}
}
else
{
str.erase();
str+=ni.getrg()[i+1];
n[j].newfollow(str);
}
}
}
}
//计算select
void select(edge &ni,edge *n)
{
int i,j;
if(ENODE.find(ni.getro())
{
ni.newselect(ni.getro());
if(ni.getro()=="@")
ni.newselect(ni.getfollow());
}
else
for(i=0;i
{
for(j=0;j
if(ni.getrg()[i]==n[j].getlf()[0])
{
ni.newselect(n[j].getfirst());
if(n[j].getfirst().find('@')>n[j].getfirst().length())
return;
}
}
}
//输出集合
void out(string p)
{
int i;
if(p.length()==0)
return;
cout
for(i=0;i
{
cout
}
cout
}
//连续输出符号
void outfu(int a,string c)
{
int i;
for(i=0;i
cout
}
//输出预测分析表
void outgraph(edge *n,string (*yc)[50])
{
int i,j,k;
bool flag;
for(i=0;i
{
if(ENODE[i]!='@')
{
outfu(10," ");
cout
}
}
outfu(10," ");
cout
int x;
for(i=0;i
{
outfu(4," ");
cout
outfu(5," ");
for(k=0;k
{
flag=1;
for(j=0;j
{
if(NODE[i]==n[j].getlf()[0])
{
x=n[j].getselect().find(ENODE[k]);
if(x-1)
{
cout"
yc[i][k]=n[j].getrg();
outfu(9-n[j].getrlen()," ");
flag=0;
}
x=n[j].getselect().find('#');
if(k==ENODE.length()-1&&x-1) {
cout"
yc[i][j]=n[j].getrg();
}
}
}
if(flag&&ENODE[k]!='@')
outfu(11," ");
}
cout
}
}
//分析符号串
int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b)
{
char ch,a;
int x,i,j,k; b++; cout9) outfu(8," "); else outfu(9," "); cout-1) { if(ch==a) { fenxi.erase(fenxi.length()-1,1); chuan.erase(0,1); cout
fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b)) return 1;
else
return 0;
}
else
{
i=NODE.find(ch);
if(a=='#')
{
x=ENODE.find('@');
if(x-1) j=ENODE.length()-1; else
j=ENODE.length();
}
else
j=ENODE.find(a);
if(yc[i][j].length())
{
cout"-1;k--) if(yc[i][j][k]!='@')
fenxi+=yc[i][j][k];
if(pipei(chuan,fenxi,yc,b)) return 1;
else
return 0;
}
else
return 0;
}
}
}
void main()
{
edge *n;
string str,(*yc)[50];
int i,j,k;
bool flag=0;
cin>>SUM; coutNODE.length()&&ENODE.find(str[j])>ENODE.length()) ENODE+=str[j]; } //计算first集合 for(i=0;in[j].getfirst().length()) { n[i].delfirst(); break; } } } } }
for(k=0;k
outfu(SUM," "); cout>chuan; fchuan=chuan; fenxi="#"; fenxi+=NODE[0]; i=0; cout
outfu(7," ");
cout
outfu(10," ");
cout
outfu(8," ");
cout
if(pipei(chuan,fenxi,yc,i))
cout
else
cout
}
截屏如下:
三.实验中的问题及心得
这次实验让我更加熟悉了LL(1)的工作流程以及LL(1)分析表的构造方法。以前课堂上搞不懂的算法流程通过实验都能得到进一步的了解。