从正规文法构造有穷状态自动机

1、 特至I 学诚H 课程名称：从正规文法构造有夯状态自动机 年级/专业/班:11级计算机类（二）班 姓名：徐勇兵 E01114278 从正规文法构造有穷状态自动机 输入：任意的正规文法 输由：相应的有穷状态自动机 要求：识别有穷状态自动机是确定的还是 非确定的，生成相应的五元组形式。 说明：应检查输入的是否正规文法。 实验截图： 测试一：修结符输出如下；如非终给荷输出如下：5,5,A,B,A,B,产生式输出如下：3 3- -akSakS- -hBShBS- -ee A A- -山-汕4B4B- -a5a5 EE是正规式状态表输出如下；*A,A,比“字母表输出如下；工 6转换函数输出如下：3 3a

2、 aASUBSASUBSe eZkZkaBaBA AkABaSkABaSb btotoA AB*ZB*Z初态是S S终态是工是DFADFA 测试二： t terfninatea?lstLJavaAfpiicationjvrsrogrerfninatea?lstLJavaAfpiicationjvrsrograjwajwr ri iJsJs jav&jav& jrjr然结符输出2 2口木：a,a,6 6 非终结符输出如下；S,AS,Af fB,产生式输出如下： 5 5- -alal S S- -bDbD3 3- -yeye k k- -bAbAB BaSaSB B- -ADADA

3、 AB B- -ytyt 方一AMAM乩4 4不是正规式程序结束 * 测试三： AaB B B- -?aS?aS E E- -bibi BeBe S S- -aBaB 是正规式 状态表输出如下:二，%B勺字母装输出如下：R,匕,转换函数输出如下 5 5日国 SEESEE S Se e2 2 AaEAaE 亚A A EaEaS S EbAEbA BeBe2 2 S Sa aS S 初态是S S： 终态是工 不是NF0NF0 importjava.util.Vector; importjavax.swing.JOptionPane; classTools publicVectorprotectio

4、n(Vectorvs) Vectornewvector=newVector(); for(inti=0;ivs.size();i+) newvector.add(vs.get(i); returnnewvector; doubleprotection(VectorVector vs)( VectorVectornewvector=newVectorVector(); for(inti=0;ivs.size();i+) Vectorproduce=(Vector)vs.get(i); Vectortemp=newVector(); for(intj=0;jproduce.size();j+) t

5、emp.add(String)produce.get(j); /forj newvector.add(temp); /fori returnnewvector; publicVectoraddElements(Vectorvs,Vectortemp) for(inti=0;itemp.size();i+) if(!vs.contains(temp.get(i) vs.add(temp.get(i); /for returnvs; /publicVectoraddElements(Vector vs,Vectortemp)/classtoolsclassElements Vectorend=ne

6、wVector();/表示终结符 Vectornoend=newVector();/表示非终结符 VectorVectorproduce=newVectorVector();/产生式 publicVectorVector publicvoidsetend()/终结符元素添加 while(true) Strings=JOptionPane.showInputDialog(null,请输入终结符)； if(s=null)return;/ifend.add(s);/while/publicvoidaddend()/元素添加 publicvoidsetnoend()/非终结符元素添加 while(tr

7、ue) Strings=JOptionPane.showInputDialog(null,非请输入终结符); if(s=null)return;/ifnoend.add(s); /while /publicvoidaddnoend()/ publicvoidsetproduce() while(true) Strings=JOptionPane.showInputDialog(null,请输入产生式，-隔开); if(s=null) return; Vectortemp=newVector(); temp.add(s.split(-)0); temp.add(s.split(-)1); pro

8、duce.add(temp); /while /publicvoidaddproduce() publicVectorgetend() returnend; publicVectorgetnoend() returnnoend; publicVectorVectorgetproduce() duce; publicvoidrun() /*TEST*/ end.add(a); end.add(b); noend.add(S); noend.add(A); noend.add(B); Vectortemp=newVector(); temp.add(S); temp.a

9、dd(aA); produce.add(temp); /*/ Vectortemp1=newVector(); temp1.add(S); temp1.add(bB); produce.add(temp1); /*/ Vectortemp2=newVector(); temp2.add(S); temp2.add(e); produce.add(temp2); /*/ Vectortemp3=newVector(); temp3.add(A); temp3.add(aB); produce.add(temp3); /*/ Vectortemp4=newVector(); temp4.add(A

10、); temp4.add(bA); produce.add(temp4); /*/ Vectortemp5=newVector(); temp5.add(B); temp5.add(aS); produce.add(temp5); /*/ Vectortemp6=newVector(); temp6.add(B); temp6.add(bA); produce.add(temp6); /*/ Vectortemp7=newVector(); temp7.add(B); temp7.add(e); produce.add(temp7); /*/ Vectortemp8=newVector();

11、temp8.add(S); temp8.add(aB); produce.add(temp8); /*Vectortemp9=newVector(); temp9.add(S); temp9.add(aAA); produce.add(temp9);*/ /System.out.println(produce.size()=+produce.size(); /*TEST*/ /this.setend(); /this.setnoend(); /this.setproduce(); publicbooleanIscontainend(Strings)/正则表达式判断s1是否在END的闭包里面 正

12、则忘了怎么写了 intlength=s.length(); for(inti=0;ilength;i+) ( Stringa=+s.charAt(i); if(end.contains(a) continue; elsereturnfalse; /for returntrue; /publicbooleanisRGPcontain(Strings) publicbooleanIsNoENd(Strings) Stringss=+s.charAt(0); if(!Iscontainend(ss)/如果不含有终结符，则为非终结符 returntrue; returnfalse; /publicbo

13、olean publicvoidshow() System.out.print(终结符输出如下：); for(inti=0;iend.size();i+) System.out.print(String)end.get(i)+,); System.out.println(); System.out.print(非终结符输出如下：); for(inti=0;inoend.size();i+) System.out.print(String)noend.get(i)+,); System.out.println(); System.out.print(产生式输出如下：); for(inti=0;i

14、produce.size();i+) System.out.println(); Vectortemp=(Vector)produce.get(i); System.out.print(String)temp.get(0)+-+(String)temp.get(1); System.out.println(); classElementspublicclassTest Elementselements; Toolstools=newTools(); Vectorend=newVector(); Vectornoend=newVector(); VectorinputTable=newVecto

15、r();/表示输入符号的集合即又 穷字母表 VectorstatusTable=newVector();/状态表 VectorVectorproduce=newVectorVector();/产生式 表示终结符 表示非终结符 VectorVectornewproduce=newVectorVector();/转换 函数 Stringstart=S;/初态 Stringlast=Z;/终态 publicvoidfirststep() if(elements.Iscontainend(aA)=true) System.out.println(yes); for(inti=0;iproduce.si

16、ze();i+) Vectortemp=produce.get(i); Stringleft=temp.get(0); Stringright=temp.get(1); if(right.length()!=1)/S-aA形式 Stringone=+right.charAt(0); Stringtwo=+right.charAt(1); Vectortemp1=newVector(); temp1.add(left); temp1.add(one); temp1.add(two); newproduce.add(templ); /if else/S-a形式 Stringone=+right.c

17、harAt(0); Vectortemp1=newVector(); temp1.add(left); temp1.add(one); temp1.add(last); newproduce.add(temp1); publicbooleaniszhenggui() for(inti=0;iproduce.size();i+) Vectortemp=produce.get(i); Stringleft=temp.get(0); Stringright=temp.get(1); if(right.length()2) returnfalse; if(right.length()=1) if(el

18、ements.IsNoENd(right)=false)/S-A不满足 returnfalse; if(right.length()=2) Stringone=+right.charAt(0); Stringtwo=+right.charAt(1); if(elements.Iscontainend(one)=false) returnfalse; if(elements.IsNoENd(two)=false) returnfalse; ) ) returntrue; ) publicvoidFA()构造自动机 ) publicvoidsetstatusTable()/状态表 for(inti

19、=0;inoend.size();i+) statusTable.add(noend.get(i); )statusTable.add(last); publicvoidsetinputTable()/状态表 for(inti=0;iend.size();i+) inputTable.add(end.get(i); publicvoidshow() System.out.print(状态表输出如下：); for(inti=0;istatusTable.size();i+) System.out.print(String)statusTable.get(i)+,); System.out.pri

20、ntln(); System.out.print(字母表输出如下：); for(inti=0;iinputTable.size();i+) System.out.print(String)inputTable.get(i)+,); System.out.println(); System.out.print(转换函数输出如下：); for(inti=0;inewproduce.size();i+) System.out.println(); Vectortemp=(Vector)newproduce.get(i); System.out.print(String)temp.get(0)+(St

21、ring)temp.get(1)+ +(String)temp.get(2); System.out.println(); System.out.println(初态是+start); System.out.println(终态是+last); ) publicbooleanjudge() booleanflag=true; VectorVectorvs=newVectorVector(); /Vectorvv=newVector(); for(inti=0;inewproduce.size();i+) Vectortemp=newproduce.get(i); Stringleft=temp.get(0); Stringmidle=temp.get(1); if(vs.isEmpty()如果是第一次放入数据 Vectortemp2=newVector(); temp2.add(left); temp2.add(midle);