合肥工业大学编译原理实验 LL1分析法.docx
《合肥工业大学编译原理实验 LL1分析法.docx》由会员分享，可在线阅读，更多相关《合肥工业大学编译原理实验 LL1分析法.docx（17页珍藏版）》请在冰点文库上搜索。
合肥工业大学编译原理实验LL1分析法
实验题目：
LL
（1）分析法
免费下载，不客气
班级：
学号：
姓名：
EditedbyMagicYang
完成日期：
2013-5-28
一、实验目的
通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。
使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。
有利于提高学生的专业素质，为培养适应社会多方面需要的能力。
二、实验内容
◆根据某一文法编制调试LL
（1）分析程序，以便对任意输入的符号串进行分析。
◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
◆分析法的功能是利用LL
（1）控制程序根据显示栈栈顶内容、向前看符号以及LL
（1）分析表，对输入符号串自上而下的分析过程。
文法为
（1）E->TG
（2）G->+TG|-TG
（3）G->ε
（4）T->FS
（5）S->*FS|/FS
（6）S->ε
（7）F->（E）
（8）F->i
3、数据结构及生成的算法描述
事先已经构造好的表：
Vn数组------非终结符表
Vt数组------终结符
Gr数组------文法
事先定义的表及变量：
非终结符按照在非终结符中的位置与first集follow集对应
fi二维数组------first集,为真表示该终结符在该行对应的非终结符的first集中
fo二维数组------follow集,为真表示该终结符在该行对应的非终结符的follow集中
M二维数组------预测分析表
用到的方法：
intor（inti,Strings）---返回最近的在其右边一个“|”位置
intvn（charc）---返回c在非终结符表中的位置
intvt（charc）---返回c在终结符表中的位置
voidaddfi（Strings,intj）---求关于某一个产生式的first集
voidfirst（charv）---求非终结符c关于该文法的first集，first调用addfi
voidfir（）---求所以非终结符的first集，fir调用first
voidaddfo（Strings,intj）---求关于某一个产生式的follow集
voidfollow（charv）---求非终结符v关于该文法的follow集，follow调用addfo
voidfol（）---求所以非终结符的follow集,fol调用follow
voidMM（intj,inti,Strings,intm）---将某一个产生式填入预测分析表中
voidbuild_M（）---构造预测分析表，build_M调用MM
voidisright（Strings）---分析一个符号串是否符合该文法
4、算法流程图
5、源程序代码和测试的结果
packagepackage_two;
importjava.util.*;
importjava.io.*;
publicclassLL{
charVn[]={'E','T','G','F','S'};//非终结符
charVt[]={'+','-','*','/','（','）','i','#','ε'};//终结符
//非终结符按照在非终结符中的位置与first集follow集对应
booleanfi[][]=newboolean[Vn.length][Vt.length+1];//first集,为真表示该终结符在该行对应的非终结符的first集中
booleanfo[][]=newboolean[Vn.length][Vt.length+1];//follow集,为真表示该终结符在该行对应的非终结符的follow集中
StringM[][]=newString[Vn.length][Vt.length-1];//预测分析表
StringGr[]={"E->TG","G->+TG|-TG","G->ε","T->FS","S->*FS|/FS","S->ε","F->（E）","F->i"};//文法
LL（）{
fir（）;//求first集
fol（）;//求follow集
build_M（）;//求预测分析表
}
intor（inti,Strings）{//返回最近的在其右边一个“|”位置
for（i=i+1;iif（s.charAt（i）=='|'）
returni;//存在，就返回位置
}
return-1;//返回-1表示没有“|”在其右边
}
intvn（charc）{//返回c在非终结符表中的位置
inti;
for（i=0;iif（c==Vn[i]）returni;//在表中，就返回位置
}
return-1;//返回-1表示不在表中
}
intvt（charc）{//返回c在终结符表中的位置
inti;
for（i=0;iif（c==Vt[i]）returni;//在表中，就返回位置
}
return-1;//返回-1表示不在表中
}
voidaddfi（Strings,intj）{//求关于某一个产生式的first集
intv=vn（s.charAt（0））;//v为产生式左边的非终结符
inti;
if（vt（s.charAt（j））!
=-1）{//产生式右边第一个为终结符
fi[v][vt（s.charAt（j））]=true;//就把s.charAt（j）加入s.charAt（0）的first集
}else{//产生式右边第一个为非终结符
if（!
fi[vn（s.charAt（j））][Vt.length]）{//如果s.charAt（j）的first集没有求，先求s.charAt（j）的first集
first（s.charAt（j））;
}
for（i=0;iif（fi[vn（s.charAt（j））][i]&&Vt[i]!
='ε'）{
fi[v][i]=true;
}
}
if（vt（'ε'）!
=-1）//终结符中有ε
if（fi[vn（s.charAt（j））][vt（'ε'）]）{//如果ε属于当前s.charAt（j）的first集
if（j==s.length（）-1）{//j=s.length（）-1就将ε加入s.charAt（0）的first集
fi[v][vt（'ε'）]=true;
return;
}
if（s.charAt（j+1）!
='|'）{//s.charAt（j+1）不是“|”就将s.charAt（j+1）的first集加入s.charAt（0）的first集
j++;
addfi（s,j）;
}else{//s.charAt（j+1）是“|”就将ε加入s.charAt（0）的first集
fi[v][vt（'ε'）]=true;
}
}
}
}
voidfirst（charv）{//求非终结符v关于该文法的first集
inti,j;
Strings;
for（i=0;is=Gr[i];
if（s.charAt（0）==v）{//产生式的左边是要求的非终结符
j=3;
if（s.charAt（0）!
=s.charAt（j））//要求的非终结符与右边第一个不同时，求first集
addfi（s,j）;//求关于此产生式的first集
while（or（j,s）!
=-1&&j{
j=or（j,s）;//得到‘|’位置
if（s.charAt（0）!
=s.charAt（j+1））//要求的非终结符与右边第一个不同时，求first集
addfi（s,j+1）;//求关于此产生式的first集
}
}
}
fi[vn（v）][Vt.length]=true;//将fi[vn（v）][Vt.length]设为true，表示已求v的first集
}
voidfir（）{//求所以非终结符的first集
inti,j;
for（i=0;iif（!
fi[i][Vt.length]）{
first（Vn[i]）;
}
}
System.out.println（"first集"）;
for（i=0;iSystem.out.println（Vn[i]）;
for（j=0;jif（fi[i][j]）{
System.out.print（""+Vt[j]）;
}
}
System.out.println（）;
}
}
voidaddfo（Strings,intj）{//求关于某一个产生式的follow集
inti;
//考察字符位于产生式末尾时将产生式左边的那个字符的follow集加到考察字符的follow集中
if（j==s.length（）-1||（jif（s.charAt（0）!
=s.charAt（j））{//考察字符与产生式左边的非终结符不同时
if（!
fo[vn（s.charAt（0））][Vt.length]）{//产生式左边的非终结符的follow集未求时，先求产生式左边的非终结符的follow集
follow（s.charAt（0））;
}
for（i=0;iif（fo[vn（s.charAt（0））][i]）{
fo[vn（s.charAt（j））][i]=true;
}
}
}
}
//将考察字符右边第一个字符的first集加到考察字符的follow集中
if（j='|'）{
if（vt（s.charAt（j+1））!
=-1）{//该字符为终结符
if（Vt[vt（s.charAt（j+1））]!
='ε'）//该字符不为ε，将该字符加入考察字符的follow集中
fo[vn（s.charAt（j））][vt（s.charAt（j+1））]=true;
}else{//该字符不为终结符
for（i=0;iif（fi[vn（s.charAt（j+1））][i]&&Vt[i]!
='ε'）{
fo[vn（s.charAt（j））][i]=true;
}
}
if（vt（'ε'）!
=-1）{//非终结符中有ε
//当考察字符右边的字符串的first集中有'ε'将产生式左边的那个字符的follow集加到考察字符的follow集中
if（s.charAt（0）==s.charAt（j））return;////考察字符与产生式左边的非终结符时同时，返回
booleanm=true;//当考察字符右边的字符串的first集中有'ε'，m为真，没有时，m为假
for（i=j+1;iif（vt（s.charAt（i））!
=-1）{//当考察字符右边的字符串中有终结符，m为假
m=false;
break;
}
if（s.charAt（i）=='|'）{//遇到'|'跳出
break;
}
if（!
fi[vn（s.charAt（i））][vt（'ε'）]）{//当考察字符右边的字符串中的有一非终结符的first集中不含ε，m为假
m=false;
}
}
if（m）{//m为真，将产生式左边的那个字符的follow集加到考察字符的follow集中
if（!
fo[vn（s.charAt（0））][Vt.length]）{//产生式左边的非终结符的follow集未求时，先求产生式左边的非终结符的follow集
follow（s.charAt（0））;
}
for（i=0;iif（fo[vn（s.charAt（0））][i]）{
fo[vn（s.charAt（j））][i]=true;
}
}
}
}
}
}
}
voidfollow（charv）{//求非终结符v关于该文法的follow集
if（v=='E'）{//v为开始符号时，将#加入v的follow集中
fo[vn（v）][vt（'#'）]=true;
}
inti,j;
Strings;
for（i=0;is=Gr[i];
for（j=3;jif（s.charAt（j）==v）{//产生式右边有考察字符
addfo（s,j）;//求关于该产生式的follow集
}
}
}
fo[vn（v）][Vt.length]=true;//将fo[vn（v）][Vt.length]设为true，表示已求v的first集
}
voidfol（）{//求所以非终结符的follow集
inti,j;
for（i=0;iif（!
fo[i][Vt.length]）{
follow（Vn[i]）;
}
}
System.out.println（"follow集"）;
for（i=0;iSystem.out.println（Vn[i]）;
for（j=0;jif（fo[i][j]）{
System.out.print（""+Vt[j]）;
}
}
System.out.println（）;
}
}
voidMM（intj,inti,Strings,intm）{//将某一个产生式填入预测分析表中
charu=Gr[i].charAt（0）;
intk;
if（vt（Gr[i].charAt（j））!
=-1）{//Gr[i].charAt（j）为终结符
if（Gr[i].charAt（j）!
='ε'）//Gr[i].charAt（j）不为ε时将s加到M[vn（u）][vt（Gr[i].charAt（j））]中
M[vn（u）][vt（Gr[i].charAt（j））]=s;
else{
for（k=0;kif（fo[vn（u）][k]）M[vn（u）][k]=s;
}
}
}else{//Gr[i].charAt（j）为非终结符
for（k=0;kif（fi[vn（Gr[i].charAt（j））][k]）M[vn（u）][k]=s;
}
if（fi[vn（Gr[i].charAt（j））][vt（'ε'）]）{//当ε属于Gr[i].charAt（j）的first集时，将属于s的follow集的b将s加到M[vn（u）][vt（b）]中
if（j==m-1）{
for（k=0;kif（fo[vn（u）][k]）M[vn（u）][k]=s;
}
}else{
j=j+1;
MM（j,i,s,m）;
}
}
}
}
voidbuild_M（）{//构造预测分析表
inti,j,m;
Strings;
for（i=0;ij=3;
while（jm=or（j,Gr[i]）;
if（m==-1）{
m=Gr[i].length（）;
}
s=Gr[i].substring（j,m）;//将j到m-1赋值到s
MM（j,i,s,m）;
j=m+1;
}
}
}
voidisright（Strings）{//分析一个字符串是否符合该文法
Stacktemp=newStack（）;//分析栈
temp.setSize（20）;
temp.push（newCharacter（'#'））;//初始化将#入栈
temp.push（newCharacter（'E'））;//初始化将E入栈
charu,v;
inti=0,j,k=0;
Stringm,action="初始化",rule="";
while（iu=s.charAt（i）;
System.out.print（k+""）;
for（j=0;jif（temp.get（j）!
=null）System.out.print（temp.get（j））;//输出分析栈内字符
}
System.out.print（""+s.substring（i）+""）;//剩余输入串
System.out.print（""+rule+""）;//所用产生式
System.out.println（action）;//动作
v=temp.pop（）;
action="pop";
if（vn（v）!
=-1）{//栈顶元素为非终结符时
if（M[vn（v）][vt（u）]!
=null）{//分析表中有产生式
m=M[vn（v）][vt（u）];
rule=v+"->"+m;
if（!
m.equals（"ε"））{//产生式不为ε
action=action+",push（";
for（j=m.length（）-1;j>-1;j--）{//将产生式反序入栈
action=action+m.charAt（j）;
temp.push（newCharacter（m.charAt（j）））;
}
action=action+"）";
}
}else{//分析表中没有产生式，提示错误
rule="";
System.out.println（"wrong:
"+u+"不在"+v+"对应的分析表中"）;
return;
}
}else{//栈顶元素为终结符时
rule="";
if（v==u）{//栈顶元素与输入符匹配
if（v=='#'）{//栈顶元素为#时，成功
System.out.println（"accept"）;
return;
}
else{
i++;
action="getnext（I）";
}
}else{//栈顶元素与输入符不匹配，提示错误
System.out.println（"wrong:
"+u+"与"+v+"不等"）;
return;
}
}
k++;
}
}
publicstaticvoidmain（Stringargs[]）throwsIOException{
LLone=newLL（）;
Strings;
BufferedReadersin=newBufferedReader（newInputStreamReader（System.in））;
s=sin.readLine（）;
s=s.concat（"#"）;
System.out.println（s）;
one.isright（s）;
sin.close（）;
}
}
测试方法和测试结果
测试方法：
命令行输入符号串
测试结果：
6、实验的评价、收获与体会
升级会员 