正規(guī)文法轉(zhuǎn)換成正規(guī)式

1、課 程 名 稱: 正規(guī)文法轉(zhuǎn)換成正規(guī)式 年級(jí)/專業(yè)/班: 11級(jí)計(jì)算機(jī)類二班 姓 名: 徐勇兵 學(xué) 號(hào)： E01114278 實(shí)驗(yàn)名稱：正規(guī)文法轉(zhuǎn)換成正規(guī)式實(shí)驗(yàn)?zāi)康模?. 了解并熟悉詞法分析中單詞的描述工具正規(guī)文法和正規(guī)式表示單詞的方式及其之間的差異性和等價(jià)性。2. 利用計(jì)算機(jī)編程實(shí)現(xiàn)正規(guī)文法轉(zhuǎn)換成等價(jià)的正規(guī)式。實(shí)驗(yàn)要求：1. 正規(guī)文法的輸入應(yīng)簡(jiǎn)便。2. 輸出的正規(guī)式以利用3條轉(zhuǎn)換規(guī)那么得出為標(biāo)準(zhǔn)。輸入：一組產(chǎn)生式所構(gòu)成的正規(guī)文法。輸出：對(duì)應(yīng)的等價(jià)的正規(guī)式。實(shí)驗(yàn)原理：1. 多數(shù)程序設(shè)計(jì)語言的單詞的語法都能用正規(guī)文法或3型文法來描述。2. 3型文法的特征是P中的每一條規(guī)那么都有下述形式：A-&g

2、t;aB或A->a。正規(guī)文法所描述的是VT上的正規(guī)集。3. 正規(guī)式也稱正那么表達(dá)式，也是表示正規(guī)集的工具。也是我們用以描述單詞符號(hào)的有效工具。4. 正規(guī)文法和正規(guī)式的等價(jià)性：一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語言的正規(guī)式；反之，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法，有些語言很容易用文法描述，有些語言更容易用正規(guī)式定義。5. 將正規(guī)文法轉(zhuǎn)換成正規(guī)式的轉(zhuǎn)換規(guī)那么有三：1A->xB，B->y對(duì)應(yīng)A=xy2A->xA，A->y對(duì)應(yīng)A=x*y3A->x，A->y對(duì)應(yīng)A=x|y實(shí)驗(yàn)算法：實(shí)驗(yàn)算法定義一

3、個(gè)函數(shù)實(shí)現(xiàn)轉(zhuǎn)換正規(guī)文法為正規(guī)式。函數(shù)根據(jù)三個(gè)轉(zhuǎn)換規(guī)那么，首先合并形如B->aA,B->bA的產(chǎn)生式為B->aA|bA的形式，其中又包括B=A的形式。然后根據(jù)轉(zhuǎn)換規(guī)那么合并形如S->a,S->b的產(chǎn)生式為S->a|b的形式。再根據(jù)轉(zhuǎn)換規(guī)那么2 的A->xA，A->y對(duì)應(yīng)A=x*y和規(guī)那么3的A->x，A->y對(duì)應(yīng)A=x|y將文法產(chǎn)生式變換為等價(jià)的正規(guī)式。在規(guī)那么以外還需要另外一個(gè)處理，這個(gè)處理可以從書本上的例子中看到，即將公因子提取出來，如A=aA|dA變換為A=(a|d)A。算法默認(rèn)開始符號(hào)為S且放在第一個(gè)產(chǎn)生式，這樣就能根據(jù)第一條產(chǎn)

4、生式最終得到等價(jià)的一個(gè)開始符號(hào)定義的正規(guī)式。實(shí)驗(yàn)結(jié)果：import java.util.Vector;import javax.swing.JOptionPane;class Toolspublic Vector<String> addElements(Vector<String> vs,Vector<String>temp)for(int i=0;i<temp.size();i+)/if(!vs.contains(temp.get(i) vs.add(temp.get(i); /forreturn vs;/public Vector<Strin

5、g> addElements(Vector<String> vs,Vector<String>temp)public Vector<String> protection(Vector<String> vs)Vector<String> newvector=new Vector<String>();for(int i=0;i<vs.size();i+)newvector.add(vs.get(i);return newvector;public Vector<Vector<String>>

6、 doubleprotection(Vector<Vector<String>> vs)Vector<Vector<String>> newvector=new Vector<Vector<String>>();for(int i=0;i<vs.size();i+)Vector<String> produce=(Vector<String>)vs.get(i);Vector<String> temp=new Vector<String>();for(int j=0;j&

7、lt;produce.size();j+)temp.add(String)produce.get(j);/for jnewvector.add(temp);/for ireturn newvector;/class toolsclass ElementsVector<String> end=new Vector<String>();/表示終結(jié)符Vector<String> noend=new Vector<String>();/表示非終結(jié)符Vector<Vector<String>> produce=new Vector&

8、lt;Vector<String>>();/產(chǎn)生式public void setend()/終結(jié)符元素添加while(true)String s=JOptionPane.showInputDialog(null,"請(qǐng)輸入終結(jié)符");if(s=null)return;/ifend.add(s);/while/public void addend()/元素添加public void setnoend()/非終結(jié)符元素添加while(true)String s=JOptionPane.showInputDialog(null,"非請(qǐng)輸入終結(jié)符"

9、;);if(s=null)return;/ifnoend.add(s);/while/public void addnoend()/public void setproduce() while(true) String s=JOptionPane.showInputDialog(null,"請(qǐng)輸入產(chǎn)生式，->隔開"); if(s=null)return; Vector<String> temp=new Vector<String>(); temp.add(s.split("->")0); temp.add(s.spli

10、t("->")1); produce.add(temp); /while/public void addproduce()public Vector<String> getend()return end;public Vector<String> getnoend()return noend;public Vector<Vector<String>> getproduce()return duce;public void run() /*TEST*/end.add("a");end.a

11、dd("d");noend.add("S");noend.add("A"); Vector<String> temp=new Vector<String>(); temp.add("S"); temp.add("aA"); produce.add(temp); /*/ /*/ Vector<String> temp4=new Vector<String>(); temp4.add("S"); temp4.add("a&

12、quot;); produce.add(temp4); / System.out.println("produce.size()="+produce.size();/*TEST*/ /*/ Vector<String> temp7=new Vector<String>(); temp7.add("A"); temp7.add("aA"); produce.add(temp7); / System.out.println("produce.size()="+produce.size();/*T

13、EST*/ Vector<String> temp1=new Vector<String>(); temp1.add("A"); temp1.add("dA"); produce.add(temp1); /*/ Vector<String> temp2=new Vector<String>(); temp2.add("A"); temp2.add("a"); produce.add(temp2); /*/ Vector<String> temp3=new

14、Vector<String>(); temp3.add("A"); temp3.add("d"); produce.add(temp3); / System.out.println("produce.size()="+produce.size();/*TEST*/ /* noend.add("B"); Vector<String> temp6=new Vector<String>(); temp6.add("A"); temp6.add("aB&qu

15、ot;); produce.add(temp6); Vector<String> temp5=new Vector<String>(); temp5.add("B"); temp5.add("d"); produce.add(temp5);*/this.setend();/this.setnoend();/this.setproduce();public boolean Iscontainend(String s)/判斷某個(gè)符號(hào)是否是終結(jié)符 可以是一個(gè)字符也可是字符串 /*System.out.print("輸出終結(jié)符&

16、quot;);for(int i=0;i<end.size();i+)System.out.print(end.get(i);System.out.println();System.out.println("傳送過來的需要判斷的是"+s);*/ int length=s.length(); for(int i=0;i<length;i+) String a=""+s.charAt(i); if(end.contains(a) continue; else return false; /for return true;/public boole

17、an isRGPcontain(String s)public boolean IsNoENd(String s)/判斷某個(gè)符號(hào)是否是非終結(jié)符 String ss=""+s.charAt(0); if(! Iscontainend(ss)/如果不含有終結(jié)符,那么為非終結(jié)符 return true; return false; / public booleanpublic void show()System.out.print("終結(jié)符輸出如下：");for(int i=0;i<end.size();i+)System.out.print(Strin

18、g)end.get(i)+", ");System.out.println(" ");System.out.print("非終結(jié)符輸出如下：");for(int i=0;i<noend.size();i+)System.out.print(String)noend.get(i)+", ");System.out.println(" ");System.out.print("產(chǎn)生式輸出如下：");for(int i=0;i<produce.size();i+)Sys

19、tem.out.println(" ");Vector<String> temp=(Vector<String>)produce.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println(" ");/class Elements class Compression Tools tools=new Tools();Elements elements;Vector <String>

20、end=null;Vector<String> noend=null;Vector<Vector<String>> produce=new Vector<Vector<String>>();Vector<String> newend;Vector<String> newnoend;Vector<Vector<String>> newproduce;public void showdelete(Vector<Vector<String>> harm,Vector&l

21、t;Vector<String>> unreach,Vector<Vector<String>> unend)if(harm.isEmpty()System.out.println("沒有有害規(guī)那么被刪除");elseSystem.out.print("被刪除的有害產(chǎn)生式輸出如下：");for(int i=0;i<harm.size();i+)System.out.println(" ");Vector<String> temp=(Vector<String>)h

22、arm.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println();System.out.println("*");if(unreach.isEmpty()System.out.println("沒有不可到達(dá)規(guī)那么被刪除");elseSystem.out.print("被刪除的不可到達(dá)產(chǎn)生式輸出如下：");for(int i=0;i<unreach.size();i+)System.ou

23、t.println(" ");Vector<String> temp=(Vector<String>)unreach.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println();System.out.println("*");if(unend.isEmpty()System.out.println("沒有不可終止規(guī)那么被刪除");elseSystem.out.print

24、("被刪除的不可終止產(chǎn)生式輸出如下：");for(int i=0;i<unend.size();i+)System.out.println(" ");Vector<String> temp=(Vector<String>)unend.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println();System.out.println("*"); public Vect

25、or<Vector<String>> deleteharm(Vector<Vector<String>> newproduce)/刪除有害規(guī)那么Vector<Vector<String>> delete=new Vector<Vector<String>>();for(int i=0;i<newproduce.size();i+)Vector<String> temp=newproduce.get(i);String left=temp.get(0);String right=te

26、mp.get(1);if(left.equals(right)/形如A->Anewproduce.remove(temp);delete.add(temp);return delete;/public Vector<Vector<String>> deleteharm(Vector<Vector<String>> newproduce)public Vector<Vector<String>> deleteunreachable(Vector<Vector<String>> newproduc

27、e)/刪除不可到達(dá)的規(guī)那么boolean tag=true;Vector<Vector<String>> delete=new Vector<Vector<String>>();Vector<String> flag=new Vector<String>();/用以記錄那些出現(xiàn)在右部的非終結(jié)符String start_character="S"flag.add(start_character);while(tag)flag.clear();flag.add(start_character);tag=fa

28、lse;for(int i=0;i<newproduce.size();i+)/掃描產(chǎn)生式右部的非終結(jié)符Vector<String> temp=newproduce.get(i);String left=temp.get(0);String right=temp.get(1);for(int j=0;j<right.length();j+)String s=""+right.charAt(j);if(elements.IsNoENd(s)flag.add(s);/for j/for ifor(int i=0;i<newproduce.size(

29、);i+)/開始進(jìn)行刪除Vector<String> temp=newproduce.get(i);String left=temp.get(0);String right=temp.get(1);if(flag.contains(left)continue;elsetag=true;delete.add(temp);newproduce.remove(temp);/ for/whilereturn delete;/public public void shownewproduce()System.out.print("壓縮后的產(chǎn)生式輸出如下：");for(in

30、t i=0;i<newproduce.size();i+)System.out.println(" ");Vector<String> temp=(Vector<String>)newproduce.get(i);System.out.print(String)temp.get(0)+"->"+(String)temp.get(1);System.out.println();public Vector<Vector<String>> getproduce()return this.newprod

31、uce; public Vector<String> getnoend()return this.noend; public Vector<String> getend()return this.end; class UnEndable Vector<Vector<String>> thenewproduce; Vector<Vector<String>> flagtable=new Vector<Vector<String>>(); public UnEndable() thenewproduce

32、=tools.doubleprotection(newproduce); /showthenewproduce(); initial_table(); firststep(); secondstep(); thirdstep(); showflagtable(); public void showthenewproduce() System.out.print("最新的產(chǎn)生式輸出如下："); for(int i=0;i<thenewproduce.size();i+) System.out.println(" "); Vector<Strin

33、g> temp=(Vector<String>)thenewproduce.get(i); System.out.print(String)temp.get(0)+"->"+(String)temp.get(1); System.out.println(); public String whattag(String noendcharacter )/判斷某個(gè)非終結(jié)符在表中的狀態(tài)，只有yes,no unsure三種 for(int i=0;i<flagtable.size();i+) Vector<String> temp=( Vec

34、tor<String>)flagtable.get(i); if(temp.get(0).equals(noendcharacter) return (String)temp.get(1); /if /for return "error" /public String whattag public void initial_table() for(int i=0;i<noend.size();i+) Vector<String> temp=new Vector<String>(); temp.add(String)noend.get

35、(i); temp.add("unsure"); flagtable.add(temp); /for /public void initial_table() public void updatetable(String left,String tag) for(int i=0;i<flagtable.size();i+) Vector<String> temp=(Vector<String>)flagtable.get(i); if(temp.get(0).equals(left) temp.set(1,tag); System.out.pr

36、intln("表格已被更新為:"+temp.get(0)+" "+temp.get(1); /for /public void updatetable(String left,String tag) public void deleteall(String left)/刪除以某個(gè)字符為左部的所有產(chǎn)生式 boolean flag=true; BlockB: while(flag) flag=false; for(int i=0;i<thenewproduce.size();i+) Vector<String> temp=thenewpro

37、duce.get(i); if(temp.get(0).equals(left) if(thenewproduce.remove(temp) /System.out.println("以"+left+"為左部的產(chǎn)生式 被刪除"); else /System.out.println("fail to remove this produce:"+"以"+left+"為左部的產(chǎn)生式 "); flag=true; continue BlockB; /if /for /while() /public vo

38、id deleteall(String left) public Vector<Vector<String>> deleteAppointall(Vector<Vector<String>> produce,String left)/刪除以某個(gè)字符為左部的所有產(chǎn)生式 Vector<Vector<String>> delete=new Vector<Vector<String>>(); boolean flag=true; BlockB: while(flag) flag=false; for(int

39、 i=0;i<produce.size();i+) Vector<String> temp=produce.get(i); if(temp.get(0).equals(left) delete.add(temp); if(produce.remove(temp) /System.out.println("以"+left+"為左部的產(chǎn)生式 被刪除"); else /System.out.println("fail to remove this produce:"+"以"+left+"為左部

40、的產(chǎn)生式 "); flag=true; continue BlockB; /if /for /while() return delete; /public void deleteAppointall(String left) public void delete(String left,String right)/刪除某條特定的產(chǎn)生式 /System.out.println("欲刪除產(chǎn)生式："+left+"->"+right); Vector<String> temp=new Vector<String>(); t

41、emp.add(left); temp.add(right); if(thenewproduce.remove(temp) /System.out.println(left+"->"+right+" produce has deleted successfuly"); else System.out.println("fail to remove this produce:"+left+"->"+right); /public void delete(String left,String right)

42、public boolean Isleftempty(String left)/判斷以某個(gè)左部為產(chǎn)生式是否為空 for(int i=0;i<thenewproduce.size();i+) Vector<String> temp=(Vector<String>)thenewproduce.get(i); if(temp.get(0).equals(left) return false; /for return true; /public boolean Isleftempty(String left) public void deleteAppoint(Vecto

43、r<Vector<String>> produce,String left,String right)/刪除某條特定的產(chǎn)生式 /System.out.println("欲刪除產(chǎn)生式："+left+"->"+right); Vector<String> temp=new Vector<String>(); temp.add(left); temp.add(right); if(produce.remove(temp) /System.out.println(left+"->"+

44、right+" produce has deleted successfuly"); else System.out.println("fail to remove this produce:"+left+"->"+right); /public void deleteAppoint public void firststep() Boolean flag=true; BlockA: while(flag) flag=false; for(int i=0;i<thenewproduce.size();i+) Vector&

45、lt;String> temp=thenewproduce.get(i); String left=temp.get(0); String right=temp.get(1); /System.out.println("firststep 產(chǎn)生式:"+left+"->"+right); if(right.length()=1)&&elements.Iscontainend(right)/r如果長(zhǎng)度為1且是終結(jié)符 /System.out.println("產(chǎn)生式:"+left+"->"

46、;+right+"滿足條件"); updatetable(left,"yes"); deleteall(left); flag=true; continue BlockA; /for /while /public void firststep() public void secondstep() boolean flag=true; BlockD: while(flag=true) flag=false; for(int i=0;i<thenewproduce.size();i+) Vector<String> temp=thenewp

47、roduce.get(i); String left=temp.get(0); String _right=temp.get(1);StringBuffer right=new StringBuffer(_right); for(int j=0;j<right.length();j+)String s=""+right.charAt(j);/System.out.println("終結(jié)符S為"+s);StringBuffer tag=new StringBuffer(whattag(s);String _tag=tag.toString();/Sy

48、stem.out.println(s+"的tag="+tag);if(_tag.equals("yes")|elements.Iscontainend(s)/如果該字符是終結(jié)符或者是可終止的非終結(jié)符話,刪除該非終結(jié)符/System.out.println("欲刪除字符"+s);int index=right.indexOf(s);if(index!=-1)/System.out.println("index="+index);right.deleteCharAt(index);if(right.length()=0

49、)/如果該產(chǎn)生式的右部為空的話/System.out.println("第三步。左部為空刪除以"+left+"為左部的所有產(chǎn)生式");deleteall(left);/刪除以某個(gè)字符為左部的所有產(chǎn)生式updatetable(left,"yes");String ss=right.toString();temp.set(1,ss);flag=true;continue BlockD;/內(nèi)層if/外層if if(_tag.equals("no")delete(left,_right);/System.out.print

50、ln("get in tag= no step");if(Isleftempty(left)/判斷以某個(gè)左部為產(chǎn)生式是否為空/System.out.println("非終結(jié)符為否，所有產(chǎn)生式刪除完畢，更新表格");updatetable(left,"no");flag=true;continue BlockD;/if/for j / for i /while() / public void secondstep() public void thirdstep() for(int i=0;i<flagtable.size();i+

51、) Vector<String> temp=flagtable.get(i); String left=temp.get(0); String right=temp.get(1); if(right.equals("unsure") updatetable(left,"no"); /for / public void thirdstep() public void showflagtable() System.out.println("flagtable is shown as follows"); for(int i=0;i<flagtable.size();i+) Vector<String> temp=flagtable.get(i); String left=temp.get(0); String right=temp.get(1); System.out.println(left+":"+right); /for / public void showflagtable() public Vector<Vector<String>> deleteunendable(Vector<Vect