由正规文法构造正规(则)式

《由正规文法构造正规(则)式》由会员分享，可在线阅读，更多相关《由正规文法构造正规(则)式（14页珍藏版）》请在装配图网上搜索。

1、编译原理实验报告实验名称 由正规（则）文法构造正规（则）式实验时间院系计算机科学与技术学院班级 学号 姓名1.试验目的输入：任意的正规文法。输出：相应的正规式。2.实验原理（一）3型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U : = T 或 U : = WT其中TVt； U,WVn，则称该文法G为左线性文法。如果对于某文法G, P中的每个规则具有下列形式：U : = T 或 U : = TW其中TGVt； U, WGVn，则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状 态文法，简写为RG。按照定义，对于正则文法应用规则

2、时，单个非终结符号只能被替换为单个 终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个 终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3, 3型语言可由确定的有限状态自动机 来识别。程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文 法描述如下：标识符:*字母/标识符 字母/标识符 数字显然，该文法描述了以字母开头的字母数字串的集合。现在要弓1入另一种 适合于描述单词的表示一正则表达式。正则表达式又称为正则式，每个正 则表达式描述的集合称为正则集。之所以采用正则表达式来描述，主要基于以下几点原因：（1）词法规则简单，无需上下文无关文法那样严格的表示

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

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

5、 等价的。记为e1=e2o(四) 正则表达式与正则文法的关系一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出， 除了符号0外，一个正则表达式的含义类似于正则文法的一个非终结符号规则 右部的含义。例如，对于 数字:=0/l/2/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/9所定义的字符串集合是相同的。正则集e, 它对应一个不包含任何句子的语言，弓I进的目的主要是为了理论上的完备性。3.实验内容由正规（则）文法构造正规（则）式4.实验心得函数间的调用关系如下图：5.实验代码与结果1）程序清单：#include#includeusing namespace std;t

6、ypedef struct CSS定义一个产生式结构体string left; /定义产生式的左部 string right; 定义产生式的右部CSS;bool Zero(CSS *p,int n)判断 0 型文法int i,j;for(i=0;in;i+) 循环n次，即遍历所有产生式for(j=0;j=A&pi.leftj=Z)/判断字符是否是非终结符break;if(j=pi.left.length()cout该文法不是0型文法endl;return 0;break;if(i=n)return 1;/如果每个产生时都能找到非终结符bool First(CSS *p,int n)/判断 1

7、型文法int i;if(Zero(p,n)/先判断是否是0型文法for(i=0;ipi.right.length()&pi.right.length()!=NULL) / 判断产生式左部长度是否大于右部break;if(i=n)return 1;elsecout该文法是0型文法endl;return 0;elsereturn 0;bool Second(CSS *p,int n)判断 2 型文法int i;if(First(p,n)同上，先判断低级文法是否成立for(i=0;i=A&pi.left0=Z) /判断产生式左部长度是否为一，左 部第一个是否是非终结符break;if(i=n)ret

8、urn 1;elsecout该文法是1型文法endl;return 0;elsereturn 0;void Third(CSS *p,int n)/判断 3 型文法int i;if(Second(p,n) /同上，先判断是否是2型文法for(i=0;i=3)|(pi.right0=A& &pi.right0=Z) 判断产生式右部字符个数是否在12之间，判断右部第一个字 符是否是非终结符break;if(i=n)for(i=0;i=A&pi.right1=Z)break;if(i=n)cout该文法属于3型文法endl;elsecout该文法属于2型文法“endl;else cout该文法属于2

9、型文法“endl;elsecout结束endl;正规文法转换为正规式void transfer(CSS *p,int n)int i,j,m,flag;合并产生式for (i=0;in;i+)for(j=i+1;jaA,A-bA的产生式为A-aA|bA的形式pi.right=pi.right+|+pj.right;pj.left=;pj.right=”;elseif(pi.right1=pj.right1&pi.left0!=pj.right1)合并形如S-aA,S-bA的产生式为S-aA|bA的形式pi.right=pi.right+|+pj.right;pj.left=;pj.right=

10、”;/*if(pi.left=pj.left&pj.right.length()=1&pi.left0!=pi.right1)/合并形如S-aA,S-a的产生式为S-aA|a的形式pi.right=pi.right+|+pj.right;pj.left=”;pj.right=”;*/正规文法到正规式的转换规则3if(pi.right.length()=1&pj.right.length()=1&pi.left=pj.left)/合并形如S-a,S-b, S-c的产生式为S-a|b|c的形式pi.right=pi.right+|+pj.right;pj.left=”;pj.right=”;提取形

11、如S-aA|bA的公因式为S-(a|b)A的形式for(i=0;i2&A=pi.right1&pi.right1=Z&pi.righ t2=|)for(j=1;jflag-1;j=j+3)pi.rightj=;if(j=flag-1)pi.right=(+pi.right.substr(0,pi.right.length()-1)+)+pi.right.su bstr(pi.right.length()-1);/正规文法到正规式的转换规则2for(i=0;i1)for(j=0;jn;j+)if(pi.left=pj.left&j!=i)for(m=0;mpj.right.length();m+

12、)if(A=pj.rightm&pj.rightm=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;再次合并左部相等的产生式for(i=0;in;i+)for(j=0;j1)pi.

13、right=pi.right+|+(+pj.right+);pj.left=”;pj.right=”;elsepi.right=pi.right+|+pj.right;pj.left=”;pj.right=”;void main()int i,j,n;string input;coutn;CSS *p=new CSSn; /初始化产生式数组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.le

14、ngth();Third(p,n);调用文法类型判断，自顶向下cout该文法属于正规文法，它的正规式如下：endl;transfer(p,n);for(i=0;in;i+)/输出转换后的文法if(pi.left0!=NULL)coutpi.left”=”;for(j=0;jpi.right.length();j+)if(pi.rightj!= )coutaAS-aA-aAA-dAA-aA-d运行结果见下页：I E:MY QQ原理zvDe bu gzv. exerrra 于于 属属d 法法a: d文文文法，它的正规式如下:3请按枝意键继续一-测试用例2： 7S-aAS-dAS-aS-dA-aAA-dBB-c运行结果: