正规文法转换成正规式

正规文法转换成正规式 课 程 名 称: 正规文法转换成正规式 年级/专业/班: 11级计算机类,二,班 姓 名: 徐勇兵 学 号: E01114278 实验名称:正规文法转换成正规式 实验目的: 1. 了解并熟悉词法分析中单词的描述工具正规文法和正规式示单词 的方式及其之间的差异性和等价性。 2. 利用计算机编程实现正规文法转换成等价的正规式。 实验要求: 1. 正规文法的输入应简便。 2. 输出的正规式以利用3条转换规则得出为。 输入:一组产生式所构成的正规文法。 输出:对应的等价的正规式。 实验原理: 1. 多数程序语言的单词的语法都能用正规文法或3型文法来描述。 述形式:A->aB或A->a。2. 3型文法的特征是P中的每一条规则都有下 正规文法所描述的是VT上的正规集。 3. 正规式也称正则表达式，也是表示正规集的工具。也是我们用以描 述单词符号的有效工具。 4. 正规文法和正规式的等价性:一个正规语言可以由正规文法定义， 也可以由正规式定义，对任意一个正规文法，存在一个定义同一个 语言的正规式;反之，对每个正规式，存在一个生成同一语言的正 规文法，有些语言很容易用文法描述，有些语言更容易用正规式定 义。 5. 将正规文法转换成正规式的转换规则有三: (1)A->xB，B->y对应A=xy (2)A->xA，A->y对应A=x*y (3)A->x，A->y对应A=x|y 实验算法: 实验算法定义一个函数实现转换正规文法为正规式。函数根据三 转换规则，首先合并形如B->aA,B->bA的产生式为B->aA|bA的形个 式，其中又包括B=A的形式。然后根据转换规则合并形如S->a,S->b 的产生式为S->a|b的形式。再根据转换规则2 的A->xA，A->y对应 A=x*y和规则3的A->x，A->y对应A=x|y将文法产生式变换为等价 的正规式。 在规则以外还需要另外一个处理，这个处理可以从书本上的例子 中看到，即将公因子提取出来，如A=aA|dA变换为A=(a|d)A。 算法默认开始符号为S且放在第一个产生式，这样就能根据第一 条产生式最终得到等价的一个开始符号定义的正规式。 实验结果: import java.util.Vector; import javax.swing.JOptionPane; class Tools{ public Vector addElements(Vector vs,Vectortemp){ for(int i=0;i addElements(Vector vs,Vectortemp){ public Vector protection(Vector vs){ Vector newvector=new Vector(); for(int i=0;i> doubleprotection(Vector> vs){ Vector> newvector=new Vector>(); for(int i=0;i produce=(Vector)vs.get(i); Vector temp=new Vector(); for(int j=0;j end=new Vector();//表示终结符 Vector noend=new Vector();//表示非终结符 Vector> produce=new Vector>();//产生式 public void setend(){//终结符元素添加 while(true) { String s=JOptionPane.showInputDialog(null,"请输入终结符"); if(s==null) { return; }//if end.add(s); }//while }//public void addend(){//元素添加 public void setnoend(){//非终结符元素添加 while(true) { String s=JOptionPane.showInputDialog(null,"非请输入终结符"); if(s==null) { return; }//if noend.add(s); }//while }//public void addnoend(){// public void setproduce(){ while(true) { String s=JOptionPane.showInputDialog(null,"请输入产生式，->隔开"); if(s==null) return; Vector temp=new Vector(); temp.add(s.split("->")[0]); temp.add(s.split("->")[1]); produce.add(temp); }//while }//public void addproduce() public Vector getend(){ return end; } public Vector getnoend(){ return noend; } public Vector> getproduce(){ return this.produce; } public void run(){ /*************************TEST********************************/ end.add("a"); end.add("d"); noend.add("S"); noend.add("A"); Vector temp=new Vector(); temp.add("S"); temp.add("aA"); produce.add(temp); /*************************/ /*************************/ Vector temp4=new Vector(); temp4.add("S"); temp4.add("a"); produce.add(temp4); // System.out.println("produce.size()="+produce.size()); /***********************TEST**********************************/ /*************************/ Vector temp7=new Vector(); temp7.add("A"); temp7.add("aA"); produce.add(temp7); // System.out.println("produce.size()="+produce.size()); /***********************TEST**********************************/ Vector temp1=new Vector(); temp1.add("A"); temp1.add("dA"); produce.add(temp1); /*************************/ Vector temp2=new Vector(); temp2.add("A"); temp2.add("a"); produce.add(temp2); /*************************/ Vector temp3=new Vector(); temp3.add("A"); temp3.add("d"); produce.add(temp3); // System.out.println("produce.size()="+produce.size()); /***********************TEST**********************************/ /* noend.add("B"); Vector temp6=new Vector(); temp6.add("A"); temp6.add("aB"); produce.add(temp6); Vector temp5=new Vector(); temp5.add("B"); temp5.add("d"); produce.add(temp5);*/ //this.setend(); //this.setnoend(); //this.setproduce(); } public boolean Iscontainend(String s)//判断某个符号是否是终结符 可以是一个字符也可是字符串 { /*System.out.print("输出终结符"); for(int i=0;i temp=(Vector)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 end=null; Vector noend=null; Vector> produce=new Vector>(); Vector newend; Vector newnoend; Vector> newproduce; public void showdelete(Vector> harm,Vector> unreach,Vector> unend){ if(harm.isEmpty()){ System.out.println("没有有害规则被删除"); } else{ System.out.print("被删除的有害产生式输出如下:"); for(int i=0;i temp=(Vector)harm.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("没有不可到达规则被删除"); } else{ System.out.print("被删除的不可到达产生式输出如下:"); for(int i=0;i temp=(Vector)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("没有不可终止规则被删除"); } else{ System.out.print("被删除的不可终止产生式输出如下:"); for(int i=0;i temp=(Vector)unend.get(i); System.out.print((String)temp.get(0)+"->"+(String)temp.get(1)); } System.out.println(); System.out.println("***********************************************"); } } public Vector> deleteharm(Vector> newproduce){//删除 有害规则 Vector> delete=new Vector>(); for(int i=0;i temp=newproduce.get(i); String left=temp.get(0); String right=temp.get(1); if(left.equals(right)){//形如A->A newproduce.remove(temp); delete.add(temp); } } return delete; }//public Vector> deleteharm(Vector> newproduce) public Vector> deleteunreachable(Vector> newproduce){//删除不可到达的规则 boolean tag=true; Vector> delete=new Vector>(); Vector flag=new Vector();//用以记录那些出现在右部的非终结符 String start_character="S"; flag.add(start_character); while(tag){ flag.clear(); flag.add(start_character); tag=false; for(int i=0;i temp=newproduce.get(i); String left=temp.get(0); String right=temp.get(1); for(int j=0;j temp=newproduce.get(i); String left=temp.get(0); String right=temp.get(1); if(flag.contains(left)) continue; else{ tag=true; delete.add(temp); newproduce.remove(temp); } }// for }//while return delete; }//public public void shownewproduce(){ System.out.print("压缩后的产生式输出如下:"); for(int i=0;i temp=(Vector)newproduce.get(i); System.out.print((String)temp.get(0)+"->"+(String)temp.get(1)); } System.out.println(); } public Vector> getproduce(){ return this.newproduce; } public Vector getnoend(){ return this.noend; } public Vector getend(){ return this.end; } class UnEndable{ Vector> thenewproduce; Vector> flagtable=new Vector>(); public UnEndable(){ thenewproduce=tools.doubleprotection(newproduce); //showthenewproduce(); initial_table(); firststep(); secondstep(); thirdstep(); showflagtable(); } public void showthenewproduce(){ System.out.print("最新的产生式输出如下:"); for(int i=0;i temp=(Vector)thenewproduce.get(i); System.out.print((String)temp.get(0)+"->"+(String)temp.get(1)); } System.out.println(); } public String whattag(String noendcharacter ){//判断某个非终结符在表中的状态，只有yes,no unsure三种 for(int i=0;i temp=( Vector)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 temp=new Vector(); temp.add((String)noend.get(i)); temp.add("unsure"); flagtable.add(temp); }//for }//public void initial_table(){ public void updatetable(String left,String tag){ for(int i=0;i temp=(Vector)flagtable.get(i); if(temp.get(0).equals(left)){ temp.set(1,tag); System.out.println("

表格

关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载

已被更新为:"+temp.get(0)+" "+temp.get(1)); } }//for }//public void updatetable(String left,String tag) public void deleteall(String left){//删除以某个字符为左部的所有产生式 boolean flag=true; BlockB: while(flag){ flag=false; for(int i=0;i temp=thenewproduce.get(i); if(temp.get(0).equals(left)){ if(thenewproduce.remove(temp)){ //System.out.println("以"+left+"为左部的产生式 被删除"); } else{ //System.out.println("fail to remove this produce:"+"以"+left+"为左部的产生式 "); } flag=true; continue BlockB; }//if }//for }//while() }//public void deleteall(String left) public Vector> deleteAppointall(Vector> produce,String left){//删除以某个字符为左部的所有产生式 Vector> delete=new Vector>(); boolean flag=true; BlockB: while(flag){ flag=false; for(int i=0;i temp=produce.get(i); if(temp.get(0).equals(left)){ delete.add(temp); if(produce.remove(temp)){ //System.out.println("以"+left+"为左部的产生式 被删除"); } else{ //System.out.println("fail to remove this produce:"+"以"+left+"为左部的产生式 "); } flag=true; continue BlockB; }//if }//for }//while() return delete; }//public void deleteAppointall(String left) public void delete(String left,String right){//删除某条特定的产生式 //System.out.println("欲删除产生式:"+left+"->"+right); Vector temp=new Vector(); temp.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) public boolean Isleftempty(String left){//判断以某个左部为产生式是否为空 for(int i=0;i temp=(Vector)thenewproduce.get(i); if(temp.get(0).equals(left)){ return false; } }//for return true; }//public boolean Isleftempty(String left) public void deleteAppoint(Vector> produce,String left,String right){//删除某条特定的产生式 //System.out.println("欲删除产生式:"+left+"->"+right); Vector temp=new Vector(); temp.add(left); temp.add(right); if(produce.remove(temp)){ //System.out.println(left+"->"+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 temp=thenewproduce.get(i); String left=temp.get(0); String right=temp.get(1); //System.out.println("firststep 产生式:"+left+"->"+right); if((right.length()==1)&&elements.Iscontainend(right)){//r如果长度为1且是终结符 //System.out.println("产生式:"+left+"->"+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 temp=thenewproduce.get(i); String left=temp.get(0); String _right=temp.get(1); StringBuffer right=new StringBuffer(_right); for(int j=0;j 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 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> deleteunendable(Vector> produce){ Vector> delete=new Vector>(); boolean flag=true; BlockE: while(flag){ flag=false; for(int i=0;i temp =produce.get(i); String left=temp.get(0); String right=temp.get(1); if(whattag(left).equals("no")){ Vector> another=deleteAppointall(produce,left); for(int m=0;m vv=another.get(m); delete.add(vv); } flag=true; continue BlockE; } for(int j=0;j> harm=deleteharm(newproduce); Vector> unreach=deleteunreachable(newproduce); UnEndable un=new UnEndable(); Vector>unend=un.deleteunendable(newproduce); showdelete(harm,unreach,unend); shownewproduce(); } } public class Convert { Elements elements=new Elements(); Tools tools=new Tools(); Vector end=null; Vector noend=null; Vector> produce=new Vector>(); public String toString(Vector vv){ String s=""; if(vv.isEmpty()) return s; for(int i=0;i toVector(String s){ Vector temp=new Vector(); for(int i=0;i temp=(Vector)produce.get(i); System.out.print((String)temp.get(0)+"->"+(String)temp.get(1)); } System.out.println(" "); } public String firststep(String _left){ Vector result=new Vector(); for(int i=0;i temp=produce.get(i); String left=temp.get(0); String right=temp.get(1); if(left.equals(_left)){ //System.out.println("第一步右部是"+right); if(elements.Iscontainend(right)){ //System.out.println("第一步产生式是"+left+"->"+right); if(result.isEmpty()){//如果返回结果是空，直接加进来，不需要加上“|”或 result.add(right); } else{ result.add("|"); result.add(right); } }// if(result.isEmpty() }//if extener }//for result.insertElementAt("(",0); result.add(")"); String s=toString(result); if(s=="") System.out.println("求"+_left+"的第一步结果是kong"); System.out.println("求"+_left+"的第一步结果是"+s); return s; }//public Vector firststep(String _left) public Vector secondstep(String _left){ Vector result=new Vector(); Vector vv1=new Vector();//A->xA形式加入 Vector vv2=new Vector();//A->Ax形式加入 for(int i=0;i temp=produce.get(i); String left=temp.get(0); String right=temp.get(1); int length=right.length(); if(left.equals(_left)){ int index=right.indexOf(_left); if(index==(length-1)){//A->xA形式 if(vv1.isEmpty()){//如果返回结果是空，直接加进来，不需要加上“|”或 vv1.add(right.substring(0, index)); //System.out.println("剪切后是"+right.substring(0, index)); } else{ vv1.add("|"); vv1.add(right.substring(0, index)); //System.out.println("剪切后是"+right.substring(0, index)); } }//if(index==right.length()) if(index==0){//A->Ax形式 if(vv2.isEmpty()){//如果返回结果是空，直接加进来，不需要加上“|”或 vv2.add(right.substring(1, length)); } else{ vv2.add("|"); vv2.add(right.substring(1, length)); } }//if(index==right.length()) }//if(left.equals(_left)) }//for if(vv1.isEmpty()==false){//变成(x|y)* result.add("("); for(int i=0;i secondstep(String _left) public Vector thirdstep(String _left){ Vector result=new Vector(); for(int i=0;i temp=produce.get(i); String left=temp.get(0); String right=temp.get(1); if(left.equals(_left)){ boolean flag=false; Vector vs=toVector(right); int length=right.length(); for(int j=0;j*A*B System.out.println("欲求"+ss+"的getresult"); String sb=getresult(ss);//求出A的可推倒串出来 System.out.println(ss+"的结果是"+sb); vs.set(j, sb); flag=true;//如果做了S->*A*B的推导 } }//for j if(flag==true){ String alsosb=toString(vs); System.out.println("对于"+_left+"分布求出结果是"+alsosb); result.add(alsosb); } }//if(left.equals(_left)) }//for i System.out.println("求"+_left+"的第3步结果是"+toString(result)); return result; }//public void thirdsetp(String _left){ public String getresult(String left){ Vector result=new Vector(); Vector temp=new Vector(); String first=""; first=firststep(left); temp=secondstep(left); if(temp.isEmpty()==false){ int index=temp.indexOf(left); if(index==-1) System.out.println("异常"); else{ temp.set(index,first); String ss=toString(temp); result.add(ss); } }// if(temp.isEmpty()==false) else{ result.add(first); } Vector third=thirdstep(left); if(third.isEmpty()==false){ for(int i=0;i