编译原理实验一：chomsky文法类型

《编译原理实验一：chomsky文法类型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理实验报告实验名称Chomsky文法类型判断实验时间2013年10月29日院系计算机科学与电子技术系班级11计算机软件学号JV114001JV114095JP114065姓名唐茹韩强强徐思维1.试验目的：1.熟练掌握四种文法类型的概念及区别。2.设计一个Chomsky文法类型判别器，判断0型、1型、2型和3型文法。2.实验原理：1.设G=(Vn,Vt,P,S)，如果它的每个产生式α->β是这样一种结构：α∈(Vn∪Vt)*且至少含有一个非终结符，而β∈(Vn∪Vt)*，则G是一个0型文法。2.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α->β均满足

2、β

3、>=

4、

5、α

6、,仅仅S->ԑ除外，则文法G是1型或上下文有关的。3.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α->β均满足：α是一个非终结符，β∈(Vn∪Vt)*，则此文法称为2型的或上下文无关的。4.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式的形式都是A->aB或A->a，其中A和B都是非终结符，a∈Vt*,则G是3型文法或正规文法。5.4个文法类的定义是逐渐增加限制的，因此可采用自顶向下的算法。3.实验内容：1.程序清单如下：#include"stdafx.h"#include#includeusingnamespac

7、estd;typedefstructCSS//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}CSS;boolZero(CSS*p,intn)//判断0型文法{inti,j;for(i=0;i='A'&&p[i].left[j]<='Z')//判断字符是否是非终结符break;}if(j==p[i].left.length()){cout<<"该文法

8、不是0型文法"<p[i].right.length())&&p[i].right.length()!=NULL)//判断产生式左部长度是否大于右部break;}if(i==n)return1;else{cout<<"该文法是0型文法"<

9、ereturn0;}boolSecond(CSS*p,intn)//判断2型文法{inti;if(First(p,n))//同上，先判断低级文法是否成立{for(i=0;i

10、

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

12、intn)//判断3型文法{inti;if(Second(p,n))//同上，先判断是否是2型文法{for(i=0;i

13、

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

15、

16、(p[i].right[0]>='A'&&p[i].right[0]<='Z'))//判断产生式右部字符个数是否在12之间，判断右部第一个字符是否是非终结符break;}if(i==n){for(i=0;i

17、='A'&&p[i].right[1]<='Z'))break;}}if(i==n){cout<<"该文法属于3型文法"<>n;CSS*p=newCSS[n];//初始化产生式数组fo