编译原理-语法分析器-(java完美运行版)教学文案

编译原理-语法分析器-(java完美运行版)

精品文档

实验二 语法分析器

一、实验目的

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

二、实验内容

 根据某一文法编制调试 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 输出的格式如下：

五、实验源程序

LL1.java

import java.awt.*;

import java.awt.event.*; import javax.swing.*;

import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector;

public class LL1 extends JFrame implements ActionListener {

/** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l;

收集于网络，如有侵权请联系管理员删除

精品文档

JButton b0;

JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3;

JLabel l0,l1,l2,l3,l4; JTable table; Statement sta; Connection conn; ResultSet rs;

DefaultTableModel dtm; String Vn[]=null;

Vector P=null;

int firstComplete[]=null;//存储已判断过first的数据 char first[][]=null;//存储最后first结果

int followComplete[]=null;//存储已判断过follow的数据 char follow[][]=null;//存储最后follow结果 char select[][]=null;//存储最后select结果 int LL=0;//标记是否为LL（1） String vt_tou[]=null;//储存Vt

Object shuju[][]=null;//存储表达式数据 char yn_null[]=null;//存储能否推出空

LL1() {

setLocation(100,0); setSize(700,780);

tf1=new JTextField(13); tf2=new JTextField(13); l=new JLabel(\">>\");

l0=new JLabel(\"输入字符串：\");

l1=new JLabel(\"输入的文法为：

收集于网络，如有侵权请联系管理员删除

精品文档

\");

l2=new JLabel(\" \");

l3=new JLabel(\"分析的结果： \");

l4=new JLabel(\"预测分析表： \");

//p1=new JPanel(); p2=new JPanel(); p3=new JPanel();

t1=new JTextArea(24,20); t2=new JTextArea(1,30); t3=new JTextArea(24,40); b0=new JButton(\"确定(S为开始)\");

b1=new JButton(\" 判断文法 \" b2=new JButton(\"输入\"); b3=new JButton(\"清空\");

table=new JTable();

JScrollPane jp1=new JScrollPane(t1); JScrollPane jp2=new JScrollPane(t2); JScrollPane jp3=new JScrollPane(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(new JScrollPane(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(new Dimension(660,200));

setVisible(true); }

public void actionPerformed(ActionEvent e) {

if(e.getSource()==b0) {

String a=tf1.getText(); String b=tf2.getText(); t1.append(a+'→'+b+'\\n');

}

if(e.getSource()==b1) {

t3.setText(\"\"); int Vnnum=0,k;

Vn=new String[100];

P=new Vector();

String s[]=t1.getText().split(\"\\n\"); for(int i=0;iif(s.length<2){

t3.setText(\"文法输入有误，请重新输入\");//判断长度是否符合

return; }

if(s[i].charAt(0)<='Z'&&s[i].charAt(0)>='A'&&s[i].charAt(1)=='→')

收集于网络，如有侵权请联系管理员删除

精品文档

{

for(k=0;kif(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=new char[100];

first=new char[Vnnum][100]; int flag=0;

String firstVn[]=null;

firstComplete=new int[Vnnum];

for(int i=0;Vn[i]!=null;i++) //依次求 FIRST**

{

flag=0;

firstVn=new String[20];

if((flag=add_First(first[i],Vn[i],firstVn,flag))==-1)return;

firstComplete[i]=1; }

t3.append(\"first集：\"+\"\\n\"); //显示FIRST** for(int i=0;Vn[i]!=null;i++)

收集于网络，如有侵权请联系管理员删除

精品文档

{

t3.append(\"first(\"+Vn[i]+\")={ \"); for(int j=0;first[i][j]!='\\0';j++) {

t3.append(first[i][j]+\" , \"); }

t3.append(\+\"\\n\"); }

follow=new char[Vnnum][100]; String followVn[]=null;

followComplete=new int[Vnnum];

for(int i=0;Vn[i]!=null;i++) //求FOLLOW** {

flag=0;

followVn=new String[20];

if((flag=tianjiaFollow(follow[i],Vn[i],followVn,flag))==-1)return;

followComplete[i]=1; }

t3.append(\"follow集：\"+\"\\n\"); //显示FOLLOW**

for(int i=0;Vn[i]!=null;i++) {

t3.append(\"follow(\"+Vn[i]+\")={ \"); for(int j=0;follow[i][j]!='\\0';j++) {

t3.append(follow[i][j]+\" , \"); }

t3.append(\+\"\\n\"); }

select=new char[P.size()][100];

for(int i=0;i{

flag=0;

tianjiaSelect(select[i],(String)P.elementAt(i),flag);

收集于网络，如有侵权请联系管理员删除

精品文档

}

t3.append(\"select集：\"+\"\\n\"); //显示SELECT**

for(int i=0;it3.append(\"select(\"+(String)P.elementAt(i)+\")={ \"); for(int j=0;select[i][j]!='\\0';j++) {

t3.append(select[i][j]+\" , \"); }

t3.append(\+\"\\n\"); }

for(int i=0;Vn[i]!=null;i++)//判断select交集是否为空

{

int biaozhi=0;

char save[]=new char[100]; for(int j=0;jString t=(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; } } } } }

char Vt[]=new char[100]; int biaozhi=0;

for(int i=0;iString t=(String)P.elementAt(i); for(int j=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=new String[biaozhi+1];//根据select和表达式生成预测分析表

shuju=new String[Vnnum][biaozhi+1]; String f=\"\"; vt_tou[0]=f;

for(int i=0;i收集于网络，如有侵权请联系管理员删除

精品文档

vt_tou[i+1]=String.valueOf(Vt[i]); }

for(int i=0;ishuju[i][0]=Vn[i]; }

for(int i=0;iString t=(String)P.elementAt(i); int j;

for(j=0;jif(Vn[j].equals(t.substring(0,1))) {

break; } }

for(k=0;select[i][k]!='\\0';k++) {

int y=puanduanXulie(Vt,select[i][k]); shuju[j][y+1]=t.substring(1); } }

dtm=new DefaultTableModel(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=new DefaultTableModel(); table.setModel(dtm); }

if(e.getSource()==b2)//输入字符串并预测分析 {

t3.setText(\"\"); {

String s= {

{

\"+\"\\n\");

} }

zifu[0]= fenxi[1]= fenxi[0]= {

zifu[fzifu]=s.charAt(i); fzifu++; }

if(LL==1) t2.getText();

for(int i=0;ifor(int i=s.length()-1;i>=0;i--) int buzhou=2;

char n[]=new char[65];//存储要显示的内容

t3.append(\"步骤 分析栈收集于网络，如有侵权请联系管理员删除

精品文档

剩余输入串 所用产生式或匹配\"+\"\\n\"); n[0]='1'; n[15]='#'; n[14]='S'; int u=29;

for(int i=fzifu-1;i>=0;i--)

{

n[u]=zifu[i]; u++; }

while(!(fenxi[ffenxi-1]=='#'&&zifu[fzifu-1]=='#'))//剩余输入串不为#则分析 {

int i,j;

char t=zifu[fzifu-1]; char k=fenxi[ffenxi-1]; if(t==k)//产生式匹配 {

n[49]=k; n[50]='匹'; n[51]='配';

t3.append(String.copyValueOf(n)+\"\\n\"); n=new char[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(int y=ffenxi-1;y>=0;y--)//处理分析栈，出栈

{

n[u]=fenxi[y]; u++; }

u=29;

for(int y=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;

收集于网络，如有侵权请联系管理员删除

精品文档

}

Object result1=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;

String result=(String)result1; for(int y=0;y n[u]=result.charAt(y); u++; }

t3.append(String.copyValueOf(n)+\"\\n\"); n=new char[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(int y=ffenxi-1;y>=0;y--) {

n[u]=fenxi[y]; u++; }

u=29;

for(int y=fzifu-1;y>=0;y--) {

n[u]=zifu[y]; u++; }

buzhou++; }

n=new char[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; } } }

private int add_First(char a[],String b,String firstVn[],int flag) //计算FIRST**（递归）

{

if(puanduanString(firstVn,b.charAt(0))){addString(firstVn,b);}

else {

return flag; }

for(int i=0;iString t=(String)P.elementAt(i); for(int k=2;kif(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++; }

收集于网络，如有侵权请联系管理员删除

精品文档

int flag1=0; for(int

j=0;yn_null[j]!='\\0';j++)//所求非终结符进入yn_null** {

if(yn_null[j]==b.charAt(0))//判断能否推出空

{

flag1=1;break; } }

if(flag1==0) {

int j; for(j=0;yn_null[j]!='\\0';j++)

{ }

yn_null[j]=b.charAt(0); }

continue; }

else//终结符直接加入first** {

a[flag]=t.charAt(k); flag++; break; }

}break; }

else//非终结符

{

if(!puanduanString(Vn,t.charAt(k))) {

int

p=firstComplete(t.charAt(k));//当该非终结符的first已经求出 if(p!=-1) {

收集于网络，如有侵权请联系管理员删除

精品文档

flag=addElementFirst(a,p,flag);//直接加入所求first

} else

if((flag=add_First(a,String.valueOf(t.charAt(k)),firstVn,flag))==-1)

return -1; int flag1=0; for(int

j=0;yn_null[j]!='\\0';j++)//当非终结符的first有空

{

if(yn_null[j]==t.charAt(k)) {

flag1=1;break; } }

if(flag1==1)//当非终结符的first能推出空

{

if(k+1==t.length()&&puanduanChar(a,'#'))//之后无符号，且所求first无#

{

a[flag]='#';//first中加入#

flag++; }

continue;//判断下一个字符 } else {

break; } }

else//错误 {

t3.setText(\"文法输入有误\"+\"\\n\");

收集于网络，如有侵权请联系管理员删除

精品文档

return -1; } } } } }

return flag; }

private int tianjiaFollow(char a[],String b,String followVn[],int flag) //计算FOLLOW**（递归）

{

if(puanduanString(followVn,b.charAt(0))){addString(followVn,b);}

else {

return flag; }

if(b.equals(\"S\"))//当为S时#存入follow {

a[flag]='#'; flag++; }

for(int i=0;iString t=(String)P.elementAt(i); for(int j=2;jif(t.charAt(j)==b.charAt(0)&&j+1if(t.charAt(j+1)!='\\0') {

if((t.charAt(j+1)>'Z'||t.charAt(j+1)<'A'))//所求为终结符 {

if(flag==0||puanduanChar(a,t.charAt(2)))//自身

收集于网络，如有侵权请联系管理员删除

精品文档

{

a[flag]=t.charAt(j+1); flag++; } }

else//所求为非终结符

{

int k;

for(k=0;Vn[k]!=null;k++) {

if(Vn[k].equals(String.valueOf(t.charAt(j+1)))) {

break;//找寻下一个非终结符的Vn位置

} }

flag=addElementFirst(a,k,flag);//把下一个非终结符first加入所求follow集

for(k=j+1;kif((t.charAt(j+1)>'Z'||t.charAt(j+1)<'A'))break; else { if(panduan_kong(t.charAt(k)))

{} else {

break; } } }

if(k>=t.length())//下一个非终

收集于网络，如有侵权请联系管理员删除

精品文档

结符可推出空，把表达式左边非终结符的follow集加入所求follow集 {

int p=followComplete(t.charAt(0));

if(p!=-1) { flag=addElementFollow(a,p,flag); } else

if((flag=tianjiaFollow(a,String.valueOf(t.charAt(0)),followVn,flag))==-1)

return -1; } } }

else//错误 {

t3.setText(\"文法输入有误,请重新输入\"+\"\\n\");

return -1; } }

if(t.charAt(j)==b.charAt(0)&&j+1==t.length())//下一个字符为空，把表达式左边非终结符的follow集加入所求follow集

{

int p=followComplete(t.charAt(0)); if(p!=-1) {

flag=addElementFollow(a,p,flag); } else

if((flag=tianjiaFollow(a,String.valueOf(t.charAt(0)),followVn,flag))==-1)

return -1;

收集于网络，如有侵权请联系管理员删除

精品文档

} } }

return flag; }

private void tianjiaSelect(char a[],String b,int flag) //计算SELECT**

{

int i=2;

int biaozhi=0;

while(iif((b.charAt(i)>'Z'||b.charAt(i)<'A')&&b.charAt(i)!='#')//是终结符 {

a[flag]=b.charAt(i);//将这个字符加入到Select**，结束Select**的计算 break; }

else if(b.charAt(i)=='#')//是空 {

int j;

for(j=0;Vn[i]!=null;j++)//将表达式左侧的非终结符的follow加入select

{

if(Vn[j].equals(b.substring(0,1))) {

break; } }

for(int k=0;follow[j][k]!='\\0';k++) {

if(puanduanChar(a,follow[j][k])) {

a[flag]=follow[j][k]; flag++;

收集于网络，如有侵权请联系管理员删除

精品文档

} }

break; } else

if(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1int j;

for(j=0;Vn[i]!=null;j++) {

if(Vn[j].equals(String.valueOf(b.charAt(i)))) {

break; } }

for(int k=0;first[j][k]!='\\0';k++) {

if(puanduanChar(a,first[j][k]))//把表达式右侧所有非终结符的first集加入。 {

if(first[j][k]=='#')//first中存在空

{

biaozhi=1; } else

{

a[flag]=first[j][k]; flag++; } } }

if(biaozhi==1)//把右侧所有非终结符的first中

收集于网络，如有侵权请联系管理员删除

精品文档

的#去除

{

i++;biaozhi=0;continue; } else {

biaozhi=0;break; } } else

if(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1>=b.length())//是非终结符且没有下一个字符 {

int j;

for(j=0;Vn[i]!=null;j++) {

if(Vn[j].equals(String.valueOf(b.charAt(i)))) {

break; } }

for(int k=0;first[j][k]!='\\0';k++) {

if(puanduanChar(a,first[j][k])) {

if(first[j][k]=='#') {

biaozhi=1;//表达式右侧能推出空，标记

} else {

a[flag]=first[j][k];//不能推出空，直接将first集加入select集

flag++; }

}

收集于网络，如有侵权请联系管理员删除

精品文档

}

if(biaozhi==1)//表达式右侧能推出空

{

for(j=0;Vn[i]!=null;j++) {

if(Vn[j].equals(b.substring(0,1)))

{

break; } }

for(int k=0;follow[j][k]!='\\0';k++) {

if(puanduanChar(a,follow[j][k])) {

a[flag]=follow[j][k];//将将表达式左侧的非终结符的follow加入select flag++; } }

break; } else {

biaozhi=0;break; } } } }

//返回b在Vt[]的位置

private int puanduanXulie(char Vt[],char b) {

int i;

for(i=0;Vt[i]!='\\0';i++)

收集于网络，如有侵权请联系管理员删除

精品文档

{

if(Vt[i]==b)break; }

return i; }

//判断b是否在a中，在返回false，不在返回true

private boolean puanduanChar(char a[],char b) {

for(int i=0;a[i]!='\\0';i++) {

if(a[i]==b)return false; }

return true; }

//判断b是否在a中，在返回false，不在返回true

private boolean puanduanString(String a[],char b) {

for(int i=0;a[i]!=null;i++) {

if(a[i].equals(String.valueOf(b)))return false;

}

return true; }

//把b加入字符串组firstVn[]

private void addString(String firstVn[],String b) {

int i;

for(i=0;firstVn[i]!=null;i++) { }

firstVn[i]=b; }

//判断b是否已完成first判断

private int firstComplete(char b) {

收集于网络，如有侵权请联系管理员删除

精品文档

int i;

for(i=0;Vn[i]!=null;i++) {

if(Vn[i].equals(String.valueOf(b))) {

if(firstComplete[i]==1)return i; else return -1; } }

return -1; }

//判断b是否已完成follow判断

private int followComplete(char b) {

for(int i=0;Vn[i]!=null;i++) {

if(Vn[i].equals(String.valueOf(b))) {

if(followComplete[i]==1)return i; else return -1; } }

return -1; }

//把相应终结符添加到first**中

private int addElementFirst(char a[],int p,int flag) {

for(int i=0;first[p][i]!='\\0';i++) {

if(puanduanChar(a,first[p][i])&&first[p][i]!='#') {

a[flag]=first[p][i]; flag++; } }

return flag; }

//把相应终结符添加到follow**中

private int addElementFollow(char a[],int p,int flag)

收集于网络，如有侵权请联系管理员删除

精品文档

{

for(int i=0;follow[p][i]!='\\0';i++) {

if(puanduanChar(a,follow[p][i])) {

a[flag]=follow[p][i]; flag++; } }

return flag; }

//判断a能是否包含空

private boolean panduan_kong(char a) {

int i;

for(i=0;Vn[i]!=null;i++) {

if(Vn[i].equals(String.valueOf(a))) {

break; } }

for(int j=0;first[i][j]!='\\0';j++) {

if(first[i][j]=='#')return true; }

return false; }

public static void main(String[] args) { new LL1();

} }

六、实验结果

收集于网络，如有侵权请联系管理员删除

精品文档

收集于网络，如有侵权请联系管理员删除

精品文档

七、实验心得体会

通过这次的实验，我深入了解了词法分析器和LL(1)文法预测分析法设计和实现，增强了我的自学能力和思考能力，也让我对程序设计有了更大的兴趣，自己通过查找资料、复习课本、编程调试，写实验报告等环节，进一步掌握了以前学到的知识，并且还对编译原理应用有了更深入的认识与掌握。在完成这个程序后，真的很开心，也了使我解到编译原理的魅力所在，激发了我要解决更多更难问题的决心。

收集于网络，如有侵权请联系管理员删除

精品文档

通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习java语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。

收集于网络，如有侵权请联系管理员删除