正规文法到正规式转换

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业编译原理实验报告实验名称 消除文法的左递归 实验时间 2015年5月19日 院系 计算机科学与技术学院 班级 学号 姓名 实验目的输入：任意的正规文法。输出：相应的正规式。实验原理3型文法（正则文法，线性文法） 如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = WT其中TVT；U,WVN，则称该文法G为左线性文法。如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = TW其中TVT；U, WVN，则称该文法G为右线性文

2、法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：:=/显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。之所以采用正则表达式来描述，主要基于

3、以下几点原因：词法规则简单，无需上下文无关文法那样严格的表示法，用正则式表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；从正则式构造高效识别程序比上下文无关文法更容易；可以从某个正则式自动地构造识别程序，它可以识别用该正则式表示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。可用于其他各种信息流的处理，例如，已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。正则表达式和正则集设有字母表。上的正则表达式和它所表示的正则集递归地定义如下：和都是上的正则表达式，它们所表示的正则集分别为和，其中是空串，是空集；任意的a是正则表达式，它所表示的正则集是a

4、；如果e1和e2是上的任意的正则表达式，且分别表示的正则集为L（e1）和L（e2），则：e1/e2也是正则表达式，表示的正则集为L（e1 / e2）L（e1）L（e2）。e1 e2也是正则表达式，表示的正则集为L（e1 e2）L（e1）L（e2）。（e1）*也是正则表达式，表示的正则集为L（e1）*）L（e1）*。定义中（1）和（2）定义了原子正则表达式，而（3）则表明字母表上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。正则表达式的性质如果两个正则表达式e1和e2表示的正则集相同，即值相等，则称它们是等价的。记为e1e2。正则表达式与正则文法

5、的关系一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于 := 0/1/2/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/9所定义的字符串集合是相同的。正则集，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。3.实验内容由正规（则）文法构造正规（则）式4.实验心得通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解 5.实验代码与结果#include#includeusing namespace std;struct WF/产生式

6、 string left; /左 string right; /右;/正规文法转换为正规式/转换规则1(A-xB,B-y-A-xy)/转换规则2 (A-x,A|y-A-x*(y)/转换规则3(A-x,A-y,-A-x|y)void transform(WF *p,int n) int i,j,m,flag; /合并产生式 for (i=0; in; i+)for(j=i+1; jaA,A(S)-bA-A(S)-aA|bA的形式 if(pi.left=pj.left)&(pi.right1=pj.right1) pi.right=pi.right+|+pj.right; pj.left=; pj

7、.right=; /合并:转换规则3(合并如S-a,S-b，S-c-S-a|b|c的形式) if(pi.right.length()=1&pj.right.length()=1&pi.left=pj.left) pi.right=pi.right+|+pj.right; pj.left=; pj.right=; /提取公因式:如S-aA|bA-S-(a|b)A的形式 for(i=0; i2&A=pi.right1&pi.right1=Z&pi.right2=|) for(j=1; ja |b ; if(j=flag-1) pi.right=(+pi.right.substr(0,pi.righ

8、t.length()-1)+)+pi.right.substr(pi.right.length()-1);/S-(a|b)A; /转换规则2.1 (A-xA|y-A-x*(y) for(i=0; i(a|d)A(a|d) if(pi.left0=pi.rightpi.right.length()-1&pi.right.length()1) for(j=0; ja|d for(m=0; mpj.right.length(); m+) if(A=pj.rightm&pj.rightm(a|d)*(a|d) pj.right=; pj.left=; /转换规则2.2(S-(xx)A A-aA 转化为

9、S-(xx)a*A) for(i=0; i1 & pi.left0!=pi.rightpi.right.length()-1)/左部的非终结符不等于右部的最后一个 for(j=0; j1 & pi.rightpi.right.length()-1=pj.left0 & pj.left0=pj.rightpj.right.length()-1) pi.right=pi.right.substr(0,pi.right.length()-1)+pj.right.substr(0,pj.right.length()-1)+*+pj.rightpj.right.length()-1; pj.right=

10、; pj.left=; /将表达式右部所有非终结符替换 flag=n; while(flag=0)/当所有产生式的右部均为终结符构成时停止转换 for(i=0,flag=flag-1; in; i+) for(j=0; jpi.right.length(); j+) if(A=pi.rightj&pi.rightj=Z) for(m=0; mn; m+) if(pm.left0=pi.rightj&m!=i) pi.right=pi.right.substr(0,j)+pm.right+pi.right.substr(j+1); pm.left=; pm.right=; break; /再次合

11、并左部相等的产生式 for(i=0; in; i+) for(j=0; j1) pi.right=pi.right+|+(+pj.right+); pj.left=; pj.right=; else pi.right=pi.right+|+pj.right; pj.left=; pj.right=; /判断文法类型bool IsZero(WF *p,int n) /判断0型文法(左部不含非终结符则不是0型文法) int i,j; for(i=0; in; i+) /遍历所有产生式 for(j=0; j=A&pi.leftj=Z) break; if(j=pi.left.length() cou

12、t该文法不是0型文法endl; return false; if(i=n) return true;/如果每个产生式都能找到非终结符bool IsFirst(WF *p,int n) /判断1型文法(右边长度大于等于左边长度) if(IsZero(p,n) /先判断是否是0型文法 int i; for(i=0; ipi.right.length()&pi.right.length()!=0) /判断产生式左部长度是否大于右部 break; if(i=n) return true; cout该文法是一个0型文法endl; return false;bool IsSecond(WF *p,int

13、n) /判断2型文法(左部是一个非终结符) int i; if(IsFirst(p,n) /是否是1型文法 for(i=0; i=A&pi.left0=Z) /判断产生式左部长度是否为一，左部第一个是否是非终结符 break; if(i=n) return true; cout该文法是1型文法endl; return false;bool IsThird(WF *p,int n) /判断3型文法(形如Aa,AaB的形式) int i; if(IsSecond(p,n) /是否是2型文法 for(i=0; i=3)|(pi.right0=A&pi.right0=Z) /判断产生式右部字符个数是否

14、是1或者2，判断右部第一个字符是否是非终结符 break; if(i=n) for(i=0; i=A&pi.right1=Z) break; if(i=n) cout该文法属于3型文法endl; return true; cout该文法属于2型文法endl; return false;int main( ) int i,j,n; string input;/*fstream myFile;myFile.open(1.txt);string q10;int j=0;int i=0;if(myFile.is_open()while(!myFile.eof()getline(myFile,qj);/coutqj+endl;ssi=qj;ss1i=qj;i+;j+;*/ while(true) cout请输入文法产生式个数Nendln; WF *p=new WFn; / 初始化产生式数组 for(i=0; iinput; /输入 for(j=0; jinput.length(); j+) /改变输入数据的形式 if(inputj=-) pi.left=input.substr(0,j); pi.right=input.substr(j+2,input.length(); if(IsThir