编译原理课设正规式r与正规文法g相互转换的程序设计.doc

目录
1、引言 1
2、设计原理 1
、正规文法的定义 1
、正规式的定义 2
、正规文法和正规式的等价性 2
、将正规式转换成正规文法 2
、将正规文法转换成正规式 3
3、总体算法设计 3
、正规式转化为正规文法的算法 3
、正规文法转化为正规式的算法 4
4、详细设计 5
、算法涉及到的各个结构体 5
、每个文法规则右部非终结符前面的终结符串 5
、每个文法规则右部结构体 6
、每条文法规则结构体 6
、文法规则结合 6
、主要函数 7
、创建文法的一条规则 7
、合并规则右部相同非终结符的项 8
、规则的替换 9
5、调试与运行结果 10
、调试方法记录 10
、实验结果记录 10
、第一组测试数据 10
、第二组测试数据 11
、第三组测试数据 12
6、课程设计总结与心得体会 13
7、参考文献 13
正规式r与正规文法G相互转换的程序设计
摘要:在计算机编译理论中,正规式、正规文法、自动机的理论以及它们之间的等价性问题是编译理论的等价基础,其中正规式和自动机,正规文法和自动机之间的等价性问题,已经得到了比较圆满的解决。本文主要讨论正规式和正规文法之间相互转换的方法。
关键字:编译原理正规式正规文法相互转换
引言
程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述,并且基于这类描述工具,可以建立词法分析技术,进而可以建立词法分析程序的自动构造方法。多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。正规式也称正则表达式,是表示正规集的工具,也是我们用以描述单词符号的方便工具。因此,熟练掌握正规文法、正规式以及它们之间的相互转化是非常必要的。
设计原理
、正规文法的定义
正规文法是左线性文法和右线性文法的统称。它们都是Chomsky分类下的3型文法。由正规文法产生的语言称为正规集。
、右线性文法
设G[S]=(VN,VT,P,S),若P中的产生或均有如下的形式:
A→aB或A→a(A∈VN,a∈VT),则称G为右线性文法。
例如,文法G1[S]=({S,A,B},{a,b},P1,S)
其中P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b},由定义可知该文法为一右线性文法。
、左线性文法
若一个文法G[S]=(VN,VT,P,S)中的产生式均有如下的形式:
A→Ba或A→a(A,B∈VN,a∈VT),则称G为左线性文法。
例如,文法G2[S]=({S,A},{a,b},P2,S)
其中P2={S→Sb,S→Ab,A→Aa,A→a},由定义可知该文法为一左线性文法。
[注:]由于左线性文法和右线性文法是等价的,本次课程设计为简化需要,只考虑右线性文法和正规式之间的转换。
、正规式的定义
正规式是描述程序语言单词的表达式,对于字母∑,其上的正规式及其表示的正规集可以递归定义如下:
①ε是一个正规式,它表示集合L(ε)={ε}。
②若a是∑上的字符,则a是一个正则式,它所表示的正规集L(a)={a}。
③若正规式r和s分别表示正规集L(r)=L(s),则
(a)r|s是正规式,表示集合L(r)∪L(s);
(b)r·s是正规式,表示集合L(r)L(s);
(c)r*是正规式,表示集合(L(r))*;
(d)(r)是正规式,表示集合L(r)。
仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中,连接运算符“·”可省略。运算符的优先级从高到低顺序排列为:“*”、“·”、“|”。
、正规文法和正规式的等价性
一个正规语言可以由正规文法定义,也可以由正规式定义,对任意一个正规文法,存在一个定义同一个语言的正规式;反之,对每个正规式,存在一个生成同一语言的正规文法,有些正规语言很容易用文法定义,有些语言更容易用正规式定义,这里两者间的转换,从结构上建立它们的等价性。
、将正规式转换成正规文法
将∑上的一个正规式r转换成文法G=(VN,VT,S,P)。令VT =∑,确定产生式和VN 的元素用如下办法。
选择一个非终结符S生成类似产生式的形式S→r,并将S定位G的识别符号。为表述方便,我们将S→r称作正规式产生式,因为在“→”的右部含有:“*”、“·”或“|”等正规式符号。不是V中的符号。
若x和y都是正规式,对形如A→xy的正规式产生