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

编译原理实验报告实验名称由正规（则）文法构造正规（则）式实验时间院系计算机科学与技术学院班级学号姓名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。按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：标识符::=字母/标识符字母/标识符数字显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。之所以采用正则表达式来描述，主要基于以下几点原因：（1）词法规则简单，无需上下文无关文法那样严格的表示法，用正则式表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；（2）从正则式构造高效识别程序比上下文无关文法更容易；（3）可以从某个正则式自动地构造识别程序，它可以识别用该正则式表示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。（4）可用于其他各种信息流的处理，例如，已经应用于某些模式识别问题、文献目录检索系统以及正文编辑程序等。（二）正则表达式和正则集设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下：ε和Φ都是∑上的正则表达式，它们所表示的正则集分别为{ε}和Φ，其中ε是空串，Φ是空集；任意的a∈∑是正则表达式，它所表示的正则集是{a}；如果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）则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。（三）正则表达式的性质如果两个正则表达式e1和e2表示的正则集相同，即值相等，则称它们是等价的。记为e1＝e2。（四）正则表达式与正则文法的关系一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于数字::=0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。3..实验内容由正规（则）文法构造正规（则）式4.实验心得函数间的调用关系如下图：5.实验代码与结果1）程序清单：#includeiostream#includestringvoidmain（）voidThird(CSS*p,intn)boolSecond(CSS*p,intn)boolFirst(CSS*p,intn)boolZero(CSS*p,intn)voidtransfer(CSS*p,intn)usingnamespacestd;typedefstructCSS//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}CSS;boolZero(CSS*p,intn)//判断0型文法{inti,j;for(i=0;in;i++)//循环n次，即遍历所有产生式{for(j=0;jp[i].left.length();j++)//遍历产生式左部每一个字符{if(p[i].left[j]='A'&&p[i].left[j]='Z')//判断字符是否是非终结符break;}if(j==p[i].left.length()){cout该文法不是0型文法endl;return0;break;}}if(i==n)return1;//如果每个产生时都能找到非终结符}boolFirst(CSS*p,intn)//判断1型文法{inti;if(Zero(p,n))//先判断是否是0型文法{for(i=0;in;i++){if((p[i].left.length()p[i].right.length())&&p[i].right.length()!=NULL)//判断产生式左部长度是否大于右部break;}if(i==n)return1;else{cout该文法是0型文法endl;return0;}}elsereturn0;}boolSecond(CSS*p,intn)//判断2型文法{inti;if(First(p,n))//同上，先判断低级文法是否成立{for(i=0;in;i++)//同上，遍历所有文法产生式{if((p[i].left.length()!=1)||!(p[i].left[0]='A'&&p[i].left[0]='Z'))//判断产生式左部长度是否为一，左部第一个是否是非终结符break;}if(i==n)return1;else{cout该文法是1型文法endl;return0;}}elsereturn0;}voidThird(CSS*p,intn)//判断3型文法{inti;if(Second(p,n))//同上，先判断是否是2型文法{for(i=0;in;i++)//同上，遍历文法所有的产生式{if((p[i].right.length()==0)||(p[i].right.length()=3)||(p[i].right[0]='A'&&p[i].right[0]='Z'))//判断产生式右部字符个数是否在12之间，判断右部第一个字符是否是非终结符break;}if(i==n){for(i=0;in;i++){if(p[i].right.length()==2){if(!(p[i].right[1]='A'&&p[i].right[1]='Z'))break;}}if(i==n){cout该文法属于3型文法endl;}elsecout该文法属于2型文法endl;}elsecout该文法属于2型文法endl;}elsecout结束endl;}//正规文法转换为正规式voidtransfer(CSS*p,intn){inti,j,m,flag;//合并产生式for(i=0;in;i++)for(j=i+1;jn;j++){if((p[i].left==p[j].left)&&(p[i].right[1]==p[j].right[1])){if(p[i].right[1]==p[j].right[1]&&p[i].left[0]==p[j].right[1])//合并形如A-aA,A-bA的产生式为A-aA|bA的形式{p[i].right=p[i].right+|+p[j].right;p[j].left=;p[j].right=;}elseif(p[i].right[1]==p[j].right[1]&&p[i].left[0]!=p[j].right[1])//合并形如S-aA,S-bA的产生式为S-aA|bA的形式{p[i].right=p[i].right+|+p[j].right;p[j].left=;p[j].right=;}}/*if(p[i].left==p[j].left&&p[j].right.length()==1&&p[i].left[0]!=p[i].right[1])//合并形如S-aA,S-a的产生式为S-aA|a的形式{p[i].right=p[i].right+|+p[j].right;p[j].left=;p[j].right=;}*///正规文法到正规式的转换规则3if(p[i].right.length()==1&&p[j].right.length()==1&&p[i].left==p[j].left)//合并形如S-a,S-b，S-c的产生式为S-a|b|c的形式{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;in;i++){flag=p[i].right.length();if(p[i].right.length()2&&'A'=p[i].right[1]&&p[i].right[1]='Z'&&p[i].right[2]=='|'){for(j=1;jflag-1;j=j+3){p[i].right[j]='';}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);}}//正规文法到正规式的转换规则2for(i=0;in;i++){if(p[i].left[0]==p[i].right[p[i].right.length()-1]&&p[i].right.length()1){for(j=0;jn;j++)if(p[i].left==p[j].left&&j!=i){for(m=0;mp[j].right.length();m++)if('A'=p[j].right[m]&&p[j].right[m]='Z')break;if(m==p[j].right.length()){p[i].right=p[i].right.substr(0,p[i].right.length()-1)+*+(+p[j].right+);p[j].right=;p[j].left=;}}}}//正规文法到正规式的转换规则3flag=n;while(flag=0)//当所有产生式的右部均为终结符构成时停止转换for(i=0,flag=flag-1;in;i++)for(j=0;jp[i].right.length();j++)if('A'=p[i].right[j]&&p[i].right[j]='Z'){for(m=0;mn;m++){if(p[m].left[0]==p[i].right[j]&&m!=i){p[i].right=p[i].right.substr(0,j)+p[m].right+p[i].right.substr(j+1);p[m].left=;p[m].right=;break;}}}//再次合并左部相等的产生式for(i=0;in;i++)for(j=0;jn;j++){if(p[i].left[0]==p[j].left[0]&&i!=j){if(p[j].right.length()1){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=;}}}}voidmain(){inti,j,n;stringinput;c