正规文法到正规式转换

正规文法到正规式转换 编译原理实验 实验名称 消除文法的左递归 实验时间 2015年5月19日 院系 计算机科学与技术学院 班级 学号 姓名 1. 实验目的 输入:任意的正规文法。 输出:相应的正规式。 2. 实验原理 3型文法(正则文法，线性文法) 如果对于某文法G，P中的每个规则具有下列形式: U :: = T 或 U :: = WT 其中T?V;U,W?V，则称该文法G为左线性文法。 NT 如果对于某文法G，P中的每个规则具有下列形式: U :: = T 或 U :: = TW 其中T?V;U, W?V，则称该文法G为右线性文法。 TN 左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。 按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。 3型文法所确定的语言为3型语言L，3型语言可由确定的有限状态自动机3 来识别。 程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下: <标识符>::=<字母>/<标识符><字母>/<标识符><数字> 显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。 之所以采用正则表达式来描述，主要基于以下几点原因: (1) 词法规则简单，无需上下文无关文法那样严格的表示法，用正则式 表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更 为容易; (2) 从正则式构造高效识别程序比上下文无关文法更容易; (3) 可以从某个正则式自动地构造识别程序，它可以识别用该正则式表 示的字符串集合中的字符串，从而减轻后面要介绍的词法时的工作 量。 (4) 可用于其他各种信息流的处理，例如，已经应用于某些模式识别问 题、文献目录检索系统以及正文编辑程序等。 正则表达式和正则集 设有字母表?。?上的正则表达式和它所表示的正则集递归地定义如下: (1) ε和Φ都是?上的正则表达式，它们所表示的正则集分别为{ε}和 Φ，其中ε是空串，Φ是空集; (2) 任意的a??是正则表达式，它所表示的正则集是{a}; (3) 如果e和e是?上的任意的正则表达式，且分别表示的正则集为L12 (e)和L(e)，则: 12 , e/e也是正则表达式，表示的正则集为L(e/ e),L(e)?L(e)。 121 212 , ee也是正则表达式，表示的正则集为L(e e),L(e)L(e)。 1 21212***, (e)也是正则表达式，表示的正则集为L((e)),L(e)。 111 定义中(1)和(2)定义了原子正则表达式，而(3)则表明字母表?上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。 正则表达式的性质 如果两个正则表达式e和e表示的正则集相同，即值相等，则称它们是等12 价的。记为e,e。 12 正则表达式与正则文法的关系 一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于<数字> ::= 0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。 3..实验内容 由正规(则)文法构造正规(则)式 4.实验心得 通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解 5.实验代码与结果 #include #include using namespace std; struct WF//产生式 { 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; iaA,A(S)->bA--->A(S)->aA|bA的形式 if((p[i].left==p[j].left)&&(p[i].right[1]==p[j].right[1])) { p[i].right=p[i].right+"|"+p[j].right; p[j].left=""; p[j].right=""; } //合并:转换规则3(合并如S->a,S->b，S->c--->S->a|b|c的形式) if(p[i].right.length()==1&&p[j].right.length()==1&&p[i].left==p[j].left) { p[i].right=p[i].right+"|"+p[j].right; p[j].left=""; p[j].right=""; } } } //提取公因式:如S->aA|bA--->S->(a|b)A的形式 for(i=0; i2&&'A'<=p[i].right[1]&&p[i].right[1]<='Z'&&p[i].right[2]=='|') { for(j=1; ja |b ; } if(j==flag-1) p[i].right="("+p[i].right.substr(0,p[i].right.length()-1)+")"+p[i].right.substr(p[i].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(p[i].left[0]==p[i].right[p[i].right.length()-1]&&p[i].right.length()>1) { for(j=0; ja|d for(m=0; m(a|d)*(a|d) p[j].right=""; p[j].left=""; } } } } } //转换规则2.2(S->(xx)A A->aA 转化为S->(xx)a*A) for(i=0; i1 && p[i].left[0]!=p[i].right[p[i].right.length()-1])//左部的非 终结符不等于右部的最后一个 { for(j=0; j1 && p[i].right[p[i].right.length()-1]==p[j].left[0] && p[j].left[0]==p[j].right[p[j].right.length()-1]) { p[i].right=p[i].right.substr(0,p[i].right.length()-1)+p[j].right.substr(0,p[j].right.length()-1)+" *"+p[j].right[p[j].right.length()-1]; p[j].right=""; p[j].left=""; } } } } //将表达式右部所有非终结符替换 flag=n; while(flag>=0)//当所有产生式的右部均为终结符构成时停止转换 for(i=0,flag=flag-1; i1) { p[i].right=p[i].right+"|"+"("+p[j].right+")"; p[j].left=""; p[j].right=""; } else { p[i].right=p[i].right+"|"+p[j].right; p[j].left=""; p[j].right=""; } } } } //判断文法类型 bool IsZero(WF *p,int n) //判断0型文法(左部不含非终结符则不是0型文法) { int i,j; for(i=0; i='A'&&p[i].left[j]<='Z') break; } if(j==p[i].left.length()) { cout<<"该文法不是0型文法"<p[i].right.length())&&p[i].right.length()!=0) //判断产生式 左部长度是否大于右部 break; } if(i==n) return true; cout<<"该文法是一个0型文法"<='A'&&p[i].left[0]<='Z')) //判断产生式 左部长度是否为一，左部第一个是否是非终结符 break; } if(i==n) return true; cout<<"该文法是1型文法"<=3)||(p[i].right[0]>='A'&&p[i].right[0]<='Z')) //判断产生式右部字符个数是否是1或者2，判断右部第一个字符是否是非终结符 break; } if(i==n) { for(i=0; i='A'&&p[i].right[1]<='Z')) break; } } if(i==n) { cout<<"该文法属于3型文法"<