正规文法转换成正规式 (2)

《正规文法转换成正规式 (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称:正规文法转换成正规式年级/专业/班:11级计算机类（二）班姓名:徐勇兵学号：E01114278实验名称：正规文法转换成正规式实验目的：1.了解并熟悉词法分析中单词的描述工具正规文法和正规式表示单词的方式及其之间的差异性和等价性。2.利用计算机编程实现正规文法转换成等价的正规式。实验要求：1.正规文法的输入应简便。2.输出的正规式以利用3条转换规则得出为标准。输入：一组产生式所构成的正规文法。输出：对应的等价的正规式。实验原理：1.多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。2.3型文法的特征是P

2、中的每一条规则都有下述形式：A->aB或A->a。正规文法所描述的是VT上的正规集。3.正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的有效工具。4.正规文法和正规式的等价性：一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法，有些语言很容易用文法描述，有些语言更容易用正规式定义。5.将正规文法转换成正规式的转换规则有三：（1）A->xB，B->y对应A=xy（2）A->xA，A->y对应A=x*

3、y（3）A->x，A->y对应A=x

4、y实验算法：实验算法定义一个函数实现转换正规文法为正规式。函数根据三个转换规则，首先合并形如B->aA,B->bA的产生式为B->aA

5、bA的形式，其中又包括B=A的形式。然后根据转换规则合并形如S->a,S->b的产生式为S->a

6、b的形式。再根据转换规则2的A->xA，A->y对应A=x*y和规则3的A->x，A->y对应A=x

7、y将文法产生式变换为等价的正规式。在规则以外还需要另外一个处理，这个处理可以从书本上的例子中看到，即将公因子提取出来，如A=aA

8、dA变换为A=(a

9、d

10、)A。算法默认开始符号为S且放在第一个产生式，这样就能根据第一条产生式最终得到等价的一个开始符号定义的正规式。实验结果：importjava.util.Vector;importjavax.swing.JOptionPane;classTools{publicVectoraddElements(Vectorvs,Vectortemp){for(inti=0;i

11、mp.get(i));}//forreturnvs;}//publicVectoraddElements(Vectorvs,Vectortemp){publicVectorprotection(Vectorvs){Vectornewvector=newVector();for(inti=0;i

12、licVector>doubleprotection(Vector>vs){Vector>newvector=newVector>();for(inti=0;iproduce=(Vector)vs.get(i);Vectortemp=newVector();for(intj=0;j

13、.size();j++){temp.add((String)produce.get(j));}//forjnewvector.add(temp);}//forireturnnewvector;}}//classtoolsclassElements{Vectorend=newVector();//表示终结符Vectornoend=newVector();//表示非终结符Vector>produce=newVector

14、>();//产生式publicvoidsetend(){//终结符元素添加while(true){Strings=JOptionPane.showInputDialog(null,"请输入终结符");if(s==null){return;}//ifend.add(s);}//while}//publi