實(shí)驗(yàn)二-LL1語法分析器

實(shí)驗(yàn)二LL(1)分析法一、實(shí)驗(yàn)?zāi)康耐ㄟ^完成預(yù)測(cè)分析法的語法分析程序，了解預(yù)測(cè)分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學(xué)生了解語法分析的功能，掌握語法分析程序設(shè)計(jì)的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的根本方法。有利于提高學(xué)生的專業(yè)素質(zhì)，為培養(yǎng)適應(yīng)社會(huì)多方面需要的能力。二、實(shí)驗(yàn)內(nèi)容根據(jù)某一文法編制調(diào)試LL〔1〕分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。構(gòu)造預(yù)測(cè)分析表，并利用分析表和一個(gè)棧來實(shí)現(xiàn)對(duì)上述程序設(shè)計(jì)語言的分析程序。分析法的功能是利用LL〔1〕控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL〔1〕分析表，對(duì)輸入符號(hào)串自上而下的分析過程。三、LL〔1〕分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法模塊結(jié)構(gòu)：〔1〕定義局部：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。〔2〕初始化：設(shè)立LL(1)分析表、初始化變量空間〔包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時(shí)變量等〕；〔3〕控制局部：從鍵盤輸入一個(gè)表達(dá)式符號(hào)串；〔4〕利用LL(1)分析算法進(jìn)行表達(dá)式處理：根據(jù)LL(1)分析表對(duì)表達(dá)式符號(hào)串進(jìn)行堆?！不蚱渌巢僮?，輸出分析結(jié)果，如果遇到錯(cuò)誤那么顯示錯(cuò)誤信息。四、實(shí)驗(yàn)要求1、編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。2、如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息。3、對(duì)以下文法，用LL〔1〕分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析：〔1〕E->TG〔2〕G->+TG|—TG〔3〕G->ε〔4〕T->FS〔5〕S->*FS|/FS〔6〕S->ε〔7〕F->(E)〔8〕F->i輸出的格式如下：實(shí)驗(yàn)源程序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;//存儲(chǔ)已判斷過first的數(shù)據(jù)charfirst[][]=null;//存儲(chǔ)最后first結(jié)果intfollowComplete[]=null;//存儲(chǔ)已判斷過follow的數(shù)據(jù)charfollow[][]=null;//存儲(chǔ)最后follow結(jié)果charselect[][]=null;//存儲(chǔ)最后select結(jié)果intLL=0;//標(biāo)記是否為L(zhǎng)L〔1〕Stringvt_tou[]=null;//儲(chǔ)存VtObjectshuju[][]=null;//存儲(chǔ)表達(dá)式數(shù)據(jù)charyn_null[]=null;//存儲(chǔ)能否推出空LL1(){setLocation(100,0);setSize(700,780);tf1=newJTextField(13);tf2=newJTextField(13);l=newJLabel(">>");l0=newJLabel("輸入字符串：");l1=newJLabel("輸入的文法為：");l2=newJLabel("");l3=newJLabel("分析的結(jié)果：");l4=newJLabel("預(yù)測(cè)分析表：");//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("文法輸入有誤，請(qǐng)重新輸入");//判斷長(zhǎng)度是否符合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數(shù)據(jù)Vnnum++;}P.add(s[i]);}else{t3.setText("文法輸入有誤，請(qǐng)重新輸入");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交集是否為空{(diào)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//當(dāng)有交集時(shí)，不為L(zhǎng)L〔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++)//提取表達(dá)式右側(cè)的終結(jié)符存入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,'#'))//假設(shè)可推出空集，那么將#參加Vt。{Vt[biaozhi]='#';biaozhi++;}vt_tou=newString[biaozhi+1];//根據(jù)select和表達(dá)式生成預(yù)測(cè)分析表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);//顯示預(yù)測(cè)分析表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)//輸入字符串并預(yù)測(cè)分析{t3.setText("");if(LL==1){Strings=t2.getText();for(inti=0;i<s.length();i++){if(s.charAt(i)=='\0'){t3.setText("字符串中請(qǐng)不要參加空格"+"\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];//存儲(chǔ)要顯示的內(nèi)容t3.append("步驟分析棧剩余輸入串所用產(chǎn)生式或匹配"+"\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)//產(chǎn)生式匹配{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);//顯示步驟數(shù)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--)//處理剩余字符串，消除一個(gè)字符{n[u]=zifu[y];u++;}buzhou++;continue;}for(i=0;Vn[i]!=null;i++)//搜尋所用產(chǎn)生式的左部{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)//全部產(chǎn)生式都不能符合那么報(bào)錯(cuò){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//找到所用產(chǎn)生式{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--)//將分析棧內(nèi)非終結(jié)符換為右邊表達(dá)式{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("請(qǐng)先依次輸入LL〔1〕文法，并點(diǎn)擊文法判斷按鈕"+"\n");return;}}}privateintadd_First(chara[],Stringb,StringfirstVn[],intflag)//計(jì)算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')//表達(dá)式右端第i個(gè)不是非終結(jié)符{if(flag==0||puanduanChar(a,t.charAt(k))){if(t.charAt(k)=='#')//#時(shí)直接參加first{if(k+1==t.length()){a[flag]=t.charAt(k);flag++;}intflag1=0;for(intj=0;yn_null[j]!='\0';j++)//所求非終結(jié)符進(jìn)入yn_null**{if(yn_null[j]==b.charAt(0))//判斷能否推出空{(diào)flag1=1;break;}}if(flag1==0){intj;for(j=0;yn_null[j]!='\0';j++){}yn_null[j]=b.charAt(0);}continue;}else//終結(jié)符直接參加first**{a[flag]=t.charAt(k);flag++;break;}}break;}else//非終結(jié)符{if(!puanduanString(Vn,t.charAt(k))){intp=firstComplete(t.charAt(k));//當(dāng)該非終結(jié)符的first已經(jīng)求出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++)//當(dāng)非終結(jié)符的first有空{(diào)if(yn_null[j]==t.charAt(k)){flag1=1;break;}}if(flag1==1)//當(dāng)非終結(jié)符的first能推出空{(diào)if(k+1==t.length()&&puanduanChar(a,'#'))//之后無符號(hào)，且所求first無#{a[flag]='#';//first中參加#flag++;}continue;//判斷下一個(gè)字符}else{break;}}else//錯(cuò)誤{t3.setText("文法輸入有誤"+"\n");return-1;}}}}}returnflag;}privateinttianjiaFollow(chara[],Stringb,StringfollowVn[],intflag)//計(jì)算FOLLOW**〔遞歸〕{if(puanduanString(followVn,b.charAt(0))){addString(followVn,b);}else{returnflag;}if(b.equals("S"))//當(dāng)為S時(shí)#存入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'))//所求為終結(jié)符{if(flag==0||puanduanChar(a,t.charAt(2)))//自身{a[flag]=t.charAt(j+1);flag++;}}else//所求為非終結(jié)符{intk;for(k=0;Vn[k]!=null;k++){if(Vn[k].equals(String.valueOf(t.charAt(j+1)))){break;//找尋下一個(gè)非終結(jié)符的Vn位置}}flag=addElementFirst(a,k,flag);//把下一個(gè)非終結(jié)符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())//下一個(gè)非終結(jié)符可推出空，把表達(dá)式左邊非終結(jié)符的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//錯(cuò)誤{t3.setText("文法輸入有誤,請(qǐng)重新輸入"+"\n");return-1;}}if(t.charAt(j)==b.charAt(0)&&j+1==t.length())//下一個(gè)字符為空，把表達(dá)式左邊非終結(jié)符的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)//計(jì)算SELECT**{inti=2;intbiaozhi=0;while(i<b.length()){if((b.charAt(i)>'Z'||b.charAt(i)<'A')&&b.charAt(i)!='#')//是終結(jié)符{a[flag]=b.charAt(i);//將這個(gè)字符參加到Select**，結(jié)束Select**的計(jì)算break;}elseif(b.charAt(i)=='#')//是空{(diào)intj;for(j=0;Vn[i]!=null;j++)//將表達(dá)式左側(cè)的非終結(jié)符的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())//是非終結(jié)符且有下一個(gè)字符{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]))//把表達(dá)式右側(cè)所有非終結(jié)符的first集參加。{if(first[j][k]=='#')//first中存在空{(diào)biaozhi=1;}else{a[flag]=first[j][k];flag++;}}}if(biaozhi==1)//把右側(cè)所有非終結(jié)符的first中的#去除{i++;biaozhi=0;continue;}else{biaozhi=0;break;}}elseif(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1>=b.length())//是非終結(jié)符且沒有下一個(gè)字符{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;//表達(dá)式右側(cè)能推出空，標(biāo)記}else{a[flag]=first[j][k];//不能推出空，直接將first集參加select集flag++;}}}if(biaozhi==1)//表達(dá)式右側(cè)能推出空{(diào)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];//將將表達(dá)式左側(cè)的非終結(jié)符的follow參加selectflag++;}}break;}else{biaozhi=0;break;}}}}//返回b在Vt[]的位置privateintpuanduanX