资源描述：
《正规文法到正规式转换.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、编译原理实验报告实验名称消除文法的左递归实验时间2015年5月19日院系计算机科学与技术学院班级学号姓名1.实验目的输入：任意的正规文法。输出：相应的正规式。2.实验原理3型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U::=T或U::=WT其中T∈VT；U,W∈VN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U::=T或U::=TW其中T∈VT；U,W∈VN，则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则
2、时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：<标识符>::=<字母>/<标识符><字母>/<标识符><数字>显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。之所以采用正则表达式来描述，主要基于以下几点原因：（1
3、）词法规则简单，无需上下文无关文法那样严格的表示法，用正则式表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；（2）从正则式构造高效识别程序比上下文无关文法更容易；（3）可以从某个正则式自动地构造识别程序，它可以识别用该正则式表示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。（4）可用于其他各种信息流的处理，例如，已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。正则表达式和正则集设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下：（1）ε和Φ都是∑上的正则表达式，它们所表示的正则集分别为{ε}
4、和Φ，其中ε是空串，Φ是空集；（1）任意的a∈∑是正则表达式，它所表示的正则集是{a}；（2）如果e1和e2是∑上的任意的正则表达式，且分别表示的正则集为L（e1）和L（e2），则：·e1/e2也是正则表达式，表示的正则集为L（e1/e2）＝L（e1）∪L（e2）。·e1e2也是正则表达式，表示的正则集为L（e1e2）＝L（e1）L（e2）。·（e1）*也是正则表达式，表示的正则集为L（（e1）*）＝L（e1）*。定义中（1）和（2）定义了原子正则表达式，而（3）则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成
5、一般的正则表达式。正则表达式的性质如果两个正则表达式e1和e2表示的正则集相同，即值相等，则称它们是等价的。记为e1＝e2。正则表达式与正则文法的关系一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于<数字>::=0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。3..实验内容由正规（则）文法构造正规（则）式4.实验
6、心得通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解5.实验代码与结果#include#includeusingnamespacestd;structWF//产生式{stringleft;//左stringright;//右};//正规文法转换为正规式//转换规则1(A->xB,B->y--->A->xy)//转换规则2(A->x,A
7、y--->A->x*(y))//转换规则3(A->x,A-y,--->A->x
8、y)voidtransform(WF*p,intn){inti,j,m,fl
9、ag;//合并产生式for(i=0;iaA,A(S)->bA--->A(S)->aA
10、bA的形式if((p[i].left==p[j].left)&&(p[i].right[1]==p[j].right[1])){p[i].right=p[i].right+"
11、"+p[j].right;p[j].left="";p[j].right="";}//合并:转换规则3(合并如S->a,S->b，S->c--->S->a
12、b
13、c的形式)if(p[i].right.length()==1&
14、&p[j].right.length()==1&&p[i].lef
