压缩文法的等价变换.docVIP

 课 程 名 称: 压缩文法的等价转换 实验目的： 了解有关文法的实用限制 实现用计算机判断有害规则和多余规则。 要求： 输入：任意的上下文无关文法 输出：等价的压缩了的文法 实验原理： 有害规则，是指形为U→U的产生式，它对描述语言显然是没有必要的。 多余规则，有两种情况：一种非终结符不在任何产生式右端，这样该产生式无法用到，成为不可到达的。另一是从某个非终结符无法推出，为不终止的。 算法： 非常好判断，只需判断箭头左右两个字符串是否相等。（：其实在上下文无关文法中，箭头左边只有一个非终结符，在程序里把它看成字符串而不是单个字符是因为可以直接使用C++语言里的字符串比较函数来判断，省得增加麻烦） 不可到达时，将所有产生式右边的非终结符收集起来一个数组，再判断左边是否有不含在的非终结符（开始符号S），若有，则为不可到达的。 不可终止时，先假定所有都是不可终止的，再扫描所有产生式，若产生右边不含左边的非终结符，则修改假定为可终止的。 所有有害规则放在一个数组中，所有不可到达规则放在一个数组中，所有不可终止规则放在一个数组中，按实验要求列出要删除的规则压缩的规则从原规则中减去这些规则产生。 结果： import java.util.Vector; import javax.swing.JOptionPane; public class test1 { public class End { VectorString end=new VectorString(); public void add() { while(true) { String s=JOptionPane.showInputDialog(null,请输入终结符 ); if(s==null) { break; }//if end.add(s); }//while }//add() public boolean iscontain(String s) { if(end.contains(s)) return true; else return false; }// iscontain() public boolean isRGPcontain(String s)//正则表达式判断s1是否在END的壁报里面 正则忘了怎么写了 { int length=s.length(); for(int i=0;ilength;i++) { String a=+s.charAt(i); if(end.contains(a)) continue; else return false; }//for return true; } }//class end public class Noend { VectorString noend=new VectorString(); public boolean iscontain(String s) { if(noend.contains(s)) return true; else return false; } public void add() { while(true) { String s=JOptionPane.showInputDialog(null,请输入非终结符 ); if(s==null) return; noend.add(s); } }//addendelement() public boolean isRGPcontain(String s)//正则表达式判断s1是否在END的壁报里面 正则忘了怎么写了 { int length=s.length(); for(int i=0;ilength;i++) { char a=s.charAt(i); if(noend.contains(a)) continue; else return false; }//for return true; } }//class noend public class Produce { VectorString left=