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

《由正规(则)文法构造正规(则)式.docx》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、由正规(则)文法构造正规(则)式姓名：学号：指导老师：时间：一、实验目的：了解三型文法，正则表达式和正则集的概念；了解正则表达式的性质以及正则表达式和正则文法之间的关系。给出一个文法能判断其文法类型，并且能将一个正规文法转化为正规式。二、实验内容：判断文法是第几类文法，并将正规文法转化为正规式。三、程序流程：1.程序流程图voidmain（）boolIsThird(CSS*p,intn)boolIsSecond(CSS*p,intn)boolIsFirst(CSS*p,intn)boolIsZero(CSS*p,intn)voidtran

2、sfer(CSS*p,intn)true输出表达式2.正规文法转为正规式流程图voidtransfer(CSS*p,intn)合并A->aA,A->bA为A->aA

3、bA合并A->a,A->b,为A->a

4、b合并S->aA

5、bA为S->(a

6、b)A合并A->xA

7、y为A->x*(y)合并S->(…)A,A->aA为S->(…)a*A产生式的右部非终结符直接替换为终结符输出表达式合并左部相等的产生式,右部直接加分隔符’

8、’二、实验代码：#include#includeusingnamespacestd;s

9、tructCSS{stringleft;//产生式左部stringright;//产生式右部};boolIsZero(CSS*p,intn)//判断0型文法(左部不含非终结符则不是0型文法){inti,j;for(i=0;i='A'&&p[i].left[j]<='Z')break;}if(j==p[i].left.length()){cout<<"该文法不是0型文法"<

10、;returnfalse;}}if(i==n)returntrue;//如果每个产生式都能找到非终结符}boolIsFirst(CSS*p,intn)//判断1型文法(右边长度大于等于左边长度){if(IsZero(p,n))//先判断是否是0型文法{inti;for(i=0;ip[i].right.length())&&p[i].right.length()!=0)//判断产生式左部长度是否大于右部break;}if(i==n)returntrue;cout<<"该文法是一个

11、0型文法"<

12、

13、!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))//判断产生式左部长度是否为一，左部第一个是否是非终结符break;}if(i==n)returntrue;cout<<"该文法是

14、1型文法"<

15、

16、(p[i].right.length()>=3)

17、

18、(p[i].right[0]>='A'&&p[i].right[0]<='Z'))//判断产生式右部字符个数是否是1或者2，判断右部第一个字符是否是

19、非终结符break;}if(i==n){for(i=0;i='A'&&p[i].right[1]<='Z'))break;}}if(i==n){cout<<"该文法属于3型文法"<

20、,flag;//合并产生式for(i=0;iaA,A->bA的产生式为A->aA

21、bA的形式if((p[i].left==