编译原理实验Chomsky文法类型判断.doc

实验目的

输入：一组任意的规那么。

输出：相应的Chomsky文法的类型。

实验原理

1．0型文法〔短语文法〕

如果对于某文法G，P中的每个规那么具有以下形式：

u::=v

其中u∈V＋，v∈V*，那么称该文法G为0型文法或短语文法，简写为PSG。

0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机〔Turning〕来识别。

2．1型文法〔上下文有关文法〕

如果对于某文法G，P中的每个规那么具有以下形式：

xUy::=xuy

其中U∈VN；u∈V＋；x，y∈V*，那么称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。

1型文法的规那么左部的U和右部的u具有相同的上文x和下文y，利用该规那么进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。

1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。

3．2型文法〔上下文无关文法〕

如果对于某文法G，P中的每个规那么具有以下形式：

U::=u

其中U∈VN；u∈V＋，那么称该文法G为2型文法或上下文无关文法，简写为CFG。

按照这条规那么，对于上下文无关文法，利用该规那么进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。

2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。

一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。

4．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型语言可由确定的有限状态自动机来识别。

在常见的程序设计语言中，多数与词法有关的文法属于3型文法。

可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：

0型1型2型3型；即L0L1L2L3

.实验内容

输入一组规那么，指明是哪一类Chomsky文法，并给出相应的四元组形式：G=(VN,VT,P,S)。

实验心得

通过本次实验，我了解到了如何判断一组产生式是属于哪种文法。文法的定义是逐渐增加限制的，

5.实验代码与结果

#includeiostream

#includestring

usingnamespacestd;

typedefstructString

{

stringleft,right;//记录当前产生式的左边和右边

}String;

intleftlength,rightlength;//记录当前产生式的左边和右边的长度

Stringcreate(stringt,Strings)//建立结构体，记录当前规那么的左边和右边

{

inti=0;

for(i=0;it.length();i++)

{

if(t[i]==-t[i+1]==)

{

s.left=t.substr(0,i);

leftlength=i;

s.right=t.substr(i+2,t.length());

rightlength=t.length()-leftlength-2;

break;

}

}

if(i==t.length())

cout输入有误。endl;

returns;

}

intflag=0;//记录3型文法中产生式是否同为左线型或右线性

intzero=0,first=0,second=0,third=0,low=6;//记录当前产生式属于哪种类型，low用来记录当前所有产生式中最低级

intZero(Strings)//判断是否为0型文法

{

inti;

for(i=0;ileftlength;i++)//