Chomsky文法判别.doc

实验名称：生成Chomsky文法 输入：一组任意的文法规则 输出：相应的Chomsky文法 要求：1）文法的输入应简便 2）指明是哪一类Chomsky文法，给出相应的四元组形式。 一 实验原理： 乔姆斯基把文法分成四种类型，即 0型 1型 2型 3型。 设G=(VN, VT, P, S), 如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)* 且至少含有一个非终结符，而β∈(VN∪VT)* 则G是一个0型文法 设G=(VN, VT, P, S)为一文法，若P中的每一个产生式α→β均满足｜β｜≥｜α｜，仅仅S→ε除外，则文法G是1型或上下文有关的。 设G=(VN, VT, P, S)，若P中的每一个产生式α→β满足α是一个非终结符，β∈(VN∪VT)*，则此文法称为2型的或上下文无关的。 设G=(VN, VT, P, S)，若P中的每一个产生式的形式都是A→aB或A→a(右线性)或（A→a, A→Ba 左线性），其中A和B都是非终结符，a∈VT* ，则G是3型文法或正规文法。 二 相关数据结构定义： static char VN[10]={!};//非终结符集合最多10个（假设均为大写字母） static char VT[10]={A};//终结符集合最多为10个（为a,b,c....x,y,z,0,1.....9） static char p[20][20];//产生式规则，最多20个 //记录每个产生式的左右部分的位置结构体 typedef struct { int left; //分别表示产生式左边最后一个字符的位置 int right; //和右边第一个字符的位置 int n; //n为整个产生式字符串的最后一个字符的下标 }position; 三 关键函数： 1. //判断字符str是否在字符串p中存在,存在则返回0 int search_chr(char *p,char str)； 2. //判断文法的类型 int judge_Chomsky(int n,position pp[])； 四 实验代码 #includeiostream #includestring.h using namespace std; static char VN[10]={!};//非终结符集合最多10个（假设均为大写字母） static char VT[10]={A};//终结符集合最多为10个（为a,b,c....x,y,z,0,1.....9） static char p[20][20];//产生式规则，最多20个 //记录每个产生式的左右部分的位置结构体 typedef struct { int left,right; int n; }position; position pp[20]; //判断字符str是否在字符串p中存在,存在则返回0 int search_chr(char *p,char str) { int n=strlen(p); for(int i=0;in;i++) { if(str==p[i]) return 0; } return 1; } //判断文法的类型 int judge_Chomsky(int n,position pp[]) { int flag1,flag2,flag3,flag4,i,j;//各文法的判断标志初始时为0 int left=0,right=0; flag1=flag2=flag3=flag4=0; for(i=0;in;i++) { for(j=0;j=pp[i].left;j++) { if(search_chr(VN,p[i][j])==0) break; } if(jpp[i].left) { return -1; //不满足0型文法条件 } } flag1=1; if(flag1) { for(i=0;in;i++) { int t=pp[i].n-pp[i].right-pp[i].left; if((pp[i].left==0)(p[i][0]==S)) { } else{ if(t0) return 0; } } } flag2=1; if(flag2) { for(i=0;in;i++) { if(pp[i].left!=0) return 1; else{ if(search_chr(VN,p[i][0])==0) continue; else if(sea