2 0 1 2 / 4 / 2 0 实验一：chomsky 文法类型的判断 实验一：chomsky 文法类型的判断 实验目的： 1. 熟练掌握四种文法类型的概念及区别。 2.设计一个Chomsky 文法类型判别器，判断0 型、1 型、2 型和3 型文法。 实验要求： 输入一组任意的规则，输出相应的Chomsky 文法的类型。 实验原理： 1.设G=(Vn,Vt,P,S)，如果它的每个产生式α->β是这样一种结构： α∈(Vn∪ Vt)*且至少含有一个非终结符，而β∈ (Vn∪ Vt)*，则G是一个0 型文法。 2.设G=(Vn,Vt,P,S)为一文法，若 P 中的每一个产生式α->β均满足 |β|>=|α|,仅仅 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 个文法类的定义是逐渐增加限制的，因此可采用自顶向下的算法。 实验内容： 1. 程序清单如下： #include #include using namespace std; typedef struct CSS //定义一个产生式结构体 { string left; //定义产生式的左部 string right; //定义产生式的右部 }CSS; bool Zero(CSS *p,int n) //判断 0 型文法 { int i,j; for(i=0;i='A'&&p[i].left[j]<='Z') //判断字符是否是非终结符 break; } if(j==p[i].left.length()) { cout<<"该文法不是 0 型文法"<p[i].right.length())&&p[i].right.length()!=NULL) //判断产生式左部长度是否大于右部 break; } if(i==n)return 1; else{ cout<<"该文法是0 型文法"<
