实验二LL1语法分析器.docx
《实验二LL1语法分析器.docx》由会员分享，可在线阅读，更多相关《实验二LL1语法分析器.docx（40页珍藏版）》请在冰点文库上搜索。
实验二LL1语法分析器
实验二LL
（1）分析法
一、实验目的
通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。
使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。
有利于提高学生的专业素质，为培养适应社会多方面需要的能力。
二、实验内容
◆根据某一文法编制调试LL
（1）分析程序，以便对任意输入的符号串进行分析。
◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
◆分析法的功能是利用LL
（1）控制程序根据显示栈栈顶内容、向前看符号以及LL
（1）分析表，对输入符号串自上而下的分析过程。
三、LL
（1）分析法实验设计思想及算法
◆模块结构：
（1）定义部分：
定义常量、变量、数据结构。
（2）初始化：
设立LL
（1）分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：
从键盘输入一个表达式符号串；
（4）利用LL
（1）分析算法进行表达式处理：
根据LL
（1）分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
四、实验要求
1、编程时注意编程风格：
空行的使用、注释的使用、缩进的使用等。
2、如果遇到错误的表达式，应输出错误提示信息。
3、对下列文法，用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
输出的格式如下：
5、实验源程序
LL1.java
importjava.awt.*;
importjava.awt.event.*;
importjavax.swing.*;
importjavax.swing.table.DefaultTableModel;
importjava.sql.*;
importjava.util.Vector;
publicclassLL1extendsJFrameimplementsActionListener
{
/**
*
*/
privatestaticfinallongserialVersionUID=1L;
JTextFieldtf1;
JTextFieldtf2;
JLabell;
JButtonb0;
JPanelp1,p2,p3;
JTextAreat1,t2,t3;
JButtonb1,b2,b3;
JLabell0,l1,l2,l3,l4;
JTabletable;
Statementsta;
Connectionconn;
ResultSetrs;
DefaultTableModeldtm;
StringVn[]=null;
VectorP=null;
intfirstComplete[]=null;//存储已判断过first的数据
charfirst[][]=null;//存储最后first结果
intfollowComplete[]=null;//存储已判断过follow的数据
charfollow[][]=null;//存储最后follow结果
charselect[][]=null;//存储最后select结果
intLL=0;//标记是否为LL
（1）
Stringvt_tou[]=null;//储存Vt
Objectshuju[][]=null;//存储表达式数据
charyn_null[]=null;//存储能否推出空
LL1（）
{
setLocation（100,0）;
setSize（700,780）;
tf1=newJTextField（13）;
tf2=newJTextField（13）;
l=newJLabel（">>"）;
l0=newJLabel（"输入字符串：
"）;
l1=newJLabel（"输入的文法为：
"）;
l2=newJLabel（""）;
l3=newJLabel（"分析的结果：
"）;
l4=newJLabel（"预测分析表：
"）;
//p1=newJPanel（）;
p2=newJPanel（）;
p3=newJPanel（）;
t1=newJTextArea（24,20）;
t2=newJTextArea（1,30）;
t3=newJTextArea（24,40）;
b0=newJButton（"确定（S为开始）"）;
b1=newJButton（"判断文法"）;
b2=newJButton（"输入"）;
b3=newJButton（"清空"）;
table=newJTable（）;
JScrollPanejp1=newJScrollPane（t1）;
JScrollPanejp2=newJScrollPane（t2）;
JScrollPanejp3=newJScrollPane（t3）;
p2.add（tf1）;
p2.add（l）;
p2.add（tf2）;
p2.add（b0）;
p2.add（b1）;
p2.add（l0）;
p2.add（l2）;
p2.add（jp2）;
p2.add（b2）;
p2.add（b3）;
p2.add（l1）;
p2.add（l3）;
p2.add（jp1）;
p2.add（jp3）;
p3.add（l4）;
p3.add（newJScrollPane（table））;
add（p2,"Center"）;
add（p3,"South"）;
b0.addActionListener（this）;
b1.addActionListener（this）;
b2.addActionListener（this）;
b3.addActionListener（this）;
setDefaultCloseOperation（JFrame.EXIT_ON_CLOSE）;
table.setPreferredScrollableViewportSize（newDimension（660,200））;
setVisible（true）;
}
publicvoidactionPerformed（ActionEvente）
{
if（e.getSource（）==b0）
{
Stringa=tf1.getText（）;
Stringb=tf2.getText（）;
t1.append（a+'→'+b+'\n'）;
}
if（e.getSource（）==b1）
{
t3.setText（""）;
intVnnum=0,k;
Vn=newString[100];
P=newVector（）;
Strings[]=t1.getText（）.split（"\n"）;
for（inti=0;i{
if（s.length<2）{
t3.setText（"文法输入有误，请重新输入"）;//判断长度是否符合
return;
}
if（s[i].charAt（0）<='Z'&&s[i].charAt（0）>='A'&&s[i].charAt
（1）=='→'）
{
for（k=0;k{
if（Vn[k].equals（s[i].substring（0,1）））{
break;
}
}
if（Vnnum==0||k>=Vnnum）
{
Vn[Vnnum]=s[i].substring（0,1）;//存入Vn数据
Vnnum++;
}
P.add（s[i]）;
}
else
{
t3.setText（"文法输入有误，请重新输入"）;
return;
}
}
yn_null=newchar[100];
first=newchar[Vnnum][100];
intflag=0;
StringfirstVn[]=null;
firstComplete=newint[Vnnum];
for（inti=0;Vn[i]!
=null;i++）//依次求FIRST**
{
flag=0;
firstVn=newString[20];
if（（flag=add_First（first[i],Vn[i],firstVn,flag））==-1）return;
firstComplete[i]=1;
}
t3.append（"first集：
"+"\n"）;//显示FIRST**
for（inti=0;Vn[i]!
=null;i++）
{
t3.append（"first（"+Vn[i]+"）={"）;
for（intj=0;first[i][j]!
='\0';j++）
{
t3.append（first[i][j]+","）;
}
t3.append（"}"+"\n"）;
}
follow=newchar[Vnnum][100];
StringfollowVn[]=null;
followComplete=newint[Vnnum];
for（inti=0;Vn[i]!
=null;i++）//求FOLLOW**
{
flag=0;
followVn=newString[20];
if（（flag=tianjiaFollow（follow[i],Vn[i],followVn,flag））==-1）return;
followComplete[i]=1;
}
t3.append（"follow集：
"+"\n"）;//显示FOLLOW**
for（inti=0;Vn[i]!
=null;i++）
{
t3.append（"follow（"+Vn[i]+"）={"）;
for（intj=0;follow[i][j]!
='\0';j++）
{
t3.append（follow[i][j]+","）;
}
t3.append（"}"+"\n"）;
}
select=newchar[P.size（）][100];
for（inti=0;i{
flag=0;
tianjiaSelect（select[i],（String）P.elementAt（i）,flag）;
}
t3.append（"select集：
"+"\n"）;//显示SELECT**
for（inti=0;i{
t3.append（"select（"+（String）P.elementAt（i）+"）={"）;
for（intj=0;select[i][j]!
='\0';j++）
{
t3.append（select[i][j]+","）;
}
t3.append（"}"+"\n"）;
}
for（inti=0;Vn[i]!
=null;i++）//判断select交集是否为空
{
intbiaozhi=0;
charsave[]=newchar[100];
for（intj=0;j{
Stringt=（String）P.elementAt（j）;
if（t.substring（0,1）.equals（Vn[i]））
{
for（k=0;select[j][k]!
='\0';k++）
{
if（puanduanChar（save,select[j][k]））
{
save[biaozhi]=select[j][k];
biaozhi++;
}
else//当有交集时，不为LL
（1）文法
{
t3.append（"不是LL
（1）文法！
！
"+"\n"）;
return;
}
}
}
}
}
charVt[]=newchar[100];
intbiaozhi=0;
for（inti=0;i{
Stringt=（String）P.elementAt（i）;
for（intj=2;j{
if（t.charAt（j）>'Z'||t.charAt（j）<'A'）
{
if（puanduanChar（Vt,t.charAt（j）））
{
Vt[biaozhi]=t.charAt（j）;
biaozhi++;
}
}
}
}
if（puanduanChar（Vt,'#'））//若可推出空集，则将#加入Vt。
{
Vt[biaozhi]='#';
biaozhi++;
}
vt_tou=newString[biaozhi+1];//根据select和表达式生成预测分析表
shuju=newString[Vnnum][biaozhi+1];
Stringf="";
vt_tou[0]=f;
for（inti=0;i{
vt_tou[i+1]=String.valueOf（Vt[i]）;
}
for（inti=0;i{
shuju[i][0]=Vn[i];
}
for（inti=0;i{
Stringt=（String）P.elementAt（i）;
intj;
for（j=0;j{
if（Vn[j].equals（t.substring（0,1）））
{
break;
}
}
for（k=0;select[i][k]!
='\0';k++）
{
inty=puanduanXulie（Vt,select[i][k]）;
shuju[j][y+1]=t.substring
（1）;
}
}
dtm=newDefaultTableModel（shuju,vt_tou）;//显示预测分析表
table.setModel（dtm）;
LL=1;
}
if（e.getSource（）==b3）//清空列表
{
tf1.setText（""）;
tf2.setText（""）;
t1.setText（""）;
t2.setText（""）;
t3.setText（""）;
Vn=null;
P=null;
firstComplete=null;
first=null;
followComplete=null;
follow=null;
select=null;
dtm=newDefaultTableModel（）;
table.setModel（dtm）;
}
if（e.getSource（）==b2）//输入字符串并预测分析
{
t3.setText（""）;
if（LL==1）
{
Strings=t2.getText（）;
for（inti=0;i{
if（s.charAt（i）=='\0'）
{
t3.setText（"字符串中请不要加入空格"+"\n"）;
return;
}
}
charzifu[]=newchar[100];//剩余输入串
charfenxi[]=newchar[100];//分析栈
zifu[0]='#';
fenxi[1]='S';
fenxi[0]='#';
intfzifu=1;
intffenxi=2;
for（inti=s.length（）-1;i>=0;i--）
{
zifu[fzifu]=s.charAt（i）;
fzifu++;
}
intbuzhou=2;
charn[]=newchar[65];//存储要显示的内容
t3.append（"步骤分析栈剩余输入串所用产生式或匹配"+"\n"）;
n[0]='1';
n[15]='#';
n[14]='S';
intu=29;
for（inti=fzifu-1;i>=0;i--）
{
n[u]=zifu[i];
u++;
}
while（!
（fenxi[ffenxi-1]=='#'&&zifu[fzifu-1]=='#'））//剩余输入串不为#则分析
{
inti,j;
chart=zifu[fzifu-1];
chark=fenxi[ffenxi-1];
if（t==k）//产生式匹配
{
n[49]=k;
n[50]='匹';
n[51]='配';
t3.append（String.copyValueOf（n）+"\n"）;
n=newchar[65];
fzifu--;
ffenxi--;
if（buzhou<10）
n[0]=（char）（'0'+buzhou）;//显示步骤数
else
{
n[0]=（char）（'0'+buzhou/10）;
n[1]=（char）（'0'+buzhou%10）;
}
u=14;
for（inty=ffenxi-1;y>=0;y--）//处理分析栈，出栈
{
n[u]=fenxi[y];
u++;
}
u=29;
for（inty=fzifu-1;y>=0;y--）//处理剩余字符串，消除一个字符
{
n[u]=zifu[y];
u++;
}
buzhou++;
continue;
}
for（i=0;Vn[i]!
=null;i++）//搜寻所用产生式的左部
{
if（Vn[i].equals（String.valueOf（k）））break;
}
for（j=0;j{
if（vt_tou[j].equals（String.valueOf（t）））break;
}
if（j>=vt_tou.length）//全部产生式都不能符合则报错
{
t3.append（String.copyValueOf（n））;
t3.append（"\n"+"该串不是该文法的句型"+"\n"）;
return;
}
Objectresult1=shuju[i][j];
if（result1==null）
{
t3.append（String.copyValueOf（n））;
t3.append（"\n"+"该串不是该文法的句型"+"\n"）;
return;
}
else//找到所用产生式
{
n[49]=Vn[i].charAt（0）;
u=50;
Stringresult=（String）result1;
for（inty=0;y{
n[u]=result.charAt（y）;
u++;
}
t3.append（String.copyValueOf（n）+"\n"）;
n=newchar[65];
ffenxi--;
for（i=result.length（）-1;i>0;i--）//将分析栈内非终结符换为右边表达式
{
if（result.charAt（i）!
='#'）
{
fenxi[ffenxi]=result.charAt（i）;
ffenxi++;
}
}
}
if（buzhou<10）//显示“步骤”
n[0]=（char）（'0'+buzhou）;
else
{
n[0]=（char）（'0'+buzhou/10）;
n[1]=（char）（'0'+buzhou%10）;
}
u=14;
for（inty=ffenxi-1;y>=0;y--）
{
n[u]=fenxi[y];
u++;
}
u=29;
for（inty=fzifu-1;y>=0;y--）
{
n[u]=zifu[y];
u++;
}
buzhou++;
}
n=newchar[65];
n[0]='1';
n[14]='#';
n[29]='#';
n[49]='分';
n[50]='析';
n[51]='成';
n[52]='功';
t3.append（String.copyValueOf（n））;
t3.append（"\n"+"该串是此文法的句型"+"\n"）;
return;
}
else
{
t3.setText（"请先依次输入LL
（1）文法，并点击文法判断按钮"+"\n"）;
return;
}
}
}
privateintadd_First（chara[],Stringb,StringfirstVn[],intflag）//计算FIRST**（递归）
{
if（puanduanString（firstVn,b.charAt（0）））{addString（firstVn,b）;}
else
{
returnflag;
}
for（inti=0;i{
Stringt=（String）P.elementAt（i）;
for（intk=2;k{
if（t.substring（0,1）.equals（b））
{
if（t.charAt（k）>'Z'||t.charAt（k）<'A'）//表达式右端第i个不是非终结符
{
if（flag==0||puanduanChar（a,t.charAt（k）））
{
if（t.charAt（k）=='#'）//#时直接加入first
{
if（k+1==t.length（））
{
a[flag]=t.charAt（k）;
flag++;
}
intflag1=0;
for（intj=0;yn_null[j]!
='\0';j++）//所求非
升级会员 