实验二-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输出的格式如下：实验源程序LL1.javaimportjava.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;Vector<String>P=null;intfirstComplete[]=null;//存储已判断过first的数据charfirst[][]=null;//存储最后first结果intfollowComplete[]=null;//存储已判断过follow的数据charfollow[][]=null;//存储最后follow结果charselect[][]=null;//存储最后select结果intLL=0;//标记是否为LL〔1〕Stringvt_tou[]=null;//储存VtObjectshuju[][]=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<String>();Strings[]=t1.getText().split("\n");for(inti=0;i<s.length;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<Vnnum;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<P.size();i++)//求SELECT**{flag=0;tianjiaSelect(select[i],(String)P.elementAt(i),flag);}t3.append("select集："+"\n");//显示SELECT**for(inti=0;i<P.size();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<P.size();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<P.size();i++){Stringt=(String)P.elementAt(i);for(intj=2;j<t.length();j++)//提取表达式右侧的终结符存入Vt{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<biaozhi;i++){vt_tou[i+1]=String.valueOf(Vt[i]);}for(inti=0;i<Vnnum;i++){shuju[i][0]=Vn[i];}for(inti=0;i<P.size();i++){Stringt=(String)P.elementAt(i);intj;for(j=0;j<Vn.length;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<s.length();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<vt_tou.length;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<result.length();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<P.size();i++){Stringt=(String)P.elementAt(i);for(intk=2;k<t.length();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++)//所求非终结符进入yn_null**{if(yn_null[j]==b.charAt(0))//判断能否推出空{flag1=1;break;}}if(flag1==0){intj;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))){intp=firstComplete(t.charAt(k));//当该非终结符的first已经求出if(p!=-1){flag=addElementFirst(a,p,flag);//直接参加所求first}elseif((flag=add_First(a,String.valueOf(t.charAt(k)),firstVn,flag))==-1)return-1;intflag1=0;for(intj=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;}}}}}returnflag;}privateinttianjiaFollow(chara[],Stringb,StringfollowVn[],intflag)//计算FOLLOW**〔递归〕{if(puanduanString(followVn,b.charAt(0))){addString(followVn,b);}else{returnflag;}if(b.equals("S"))//当为S时#存入follow{a[flag]='#';flag++;}for(inti=0;i<P.size();i++){Stringt=(String)P.elementAt(i);for(intj=2;j<t.length();j++){if(t.charAt(j)==b.charAt(0)&&j+1<t.length()){if(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//所求为非终结符{intk;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;k<t.length();k++){if((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集{intp=followComplete(t.charAt(0));if(p!=-1){flag=addElementFollow(a,p,flag);}elseif((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集{intp=followComplete(t.charAt(0));if(p!=-1){flag=addElementFollow(a,p,flag);}elseif((flag=tianjiaFollow(a,String.valueOf(t.charAt(0)),followVn,flag))==-1)return-1;}}}returnflag;}privatevoidtianjiaSelect(chara[],Stringb,intflag)//计算SELECT**{inti=2;intbiaozhi=0;while(i<b.length()){if((b.charAt(i)>'Z'||b.charAt(i)<'A')&&b.charAt(i)!='#')//是终结符{a[flag]=b.charAt(i);//将这个字符参加到Select**，结束Select**的计算break;}elseif(b.charAt(i)=='#')//是空{intj;for(j=0;Vn[i]!=null;j++)//将表达式左侧的非终结符的follow参加select{if(Vn[j].equals(b.substring(0,1))){break;}}for(intk=0;follow[j][k]!='\0';k++){if(puanduanChar(a,follow[j][k])){a[flag]=follow[j][k];flag++;}}break;}elseif(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1<b.length())//是非终结符且有下一个字符{intj;for(j=0;Vn[i]!=null;j++){if(Vn[j].equals(String.valueOf(b.charAt(i)))){break;}}for(intk=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;}}elseif(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1>=b.length())//是非终结符且没有下一个字符{intj;for(j=0;Vn[i]!=null;j++){if(Vn[j].equals(String.valueOf(b.charAt(i)))){break;}}for(intk=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(intk=0;follow[j][k]!='\0';k++){if(puanduanChar(a,follow[j][k])){a[flag]=follow[j][k];//将将表达式左侧的非终结符的follow参加selectflag++;}}break;}else{biaozhi=0;break;}}}}//返回b在Vt[]的位置privateintpuanduanX