正规文法转换成正规式正规文法转换成正规式
课 程 名 称: 正规文法转换成正规式 年级/专业/班: 11级计算机类,二,班
姓 名: 徐勇兵
学 号: E01114278
实验名称:正规文法转换成正规式
实验目的:
1. 了解并熟悉词法分析中单词的描述工具正规文法和正规式表示单词
的方式及其之间的差异性和等价性。
2. 利用计算机编程实现正规文法转换成等价的正规式。
实验要求:
1. 正规文法的输入应简便。
2. 输出的正规式以利用3条转换规则得出为标准。
输入:一组产生式所构成的正规文法。
输出:对应的等价的正规式。 ...
正规文法转换成正规式
课 程 名 称: 正规文法转换成正规式 年级/专业/班: 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
本文档为【正规文法转换成正规式】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。