安徽大学编译原理实验一Chomsky文法类型判断

实验一:文法类型判断

实验日期：2023.4.13教师签字：成绩：名称:Chomsky文法类型判断

实验目的:一.掌握四种文法类型的定义,及其区别；二.熟悉各种文法类型的判断,能够快速按照要求写出对应文法类型的文法用例.

实验原理:一.0型文法,产生式左右部可以使用"非终结符"和"终结符"随意组合,但左部不能为空；二.1型文法,在0型文法的根底上,要求右部的符号长度大于左部(空除外)；三.2型文法,在1型文法的根底上,要求左部必须由非终结符号组成,且左部只能拥有一个非终结符；

四.3型文法,在2型文法的根底上,产生式必须型如:A->Aa|a或A->aA|a；实验内容：

１.实验要求：

输入一组任意的规那么,输出相应的Chomsky文法的类型。0型文法判别:1型文法判别:2型文法判别:3型文法判别:程序代码:/*SID:E10914012NAME:杨翔宇PROG:CHINT:判断Chomsky文法类型*/#include<stdio.h>#include<string.h>#include<ctype.h>structnode{charleft[30],right[30];intleftlen,rightlen,startleft,startright;}n[1000];intt0=0,t1=0,t2=0,t3=0;intmain(){inti,j,k,p,q,count=0,pos=0,poslowlast=0,countflag=0,flag0=0,flag1=0,flag2=0,flag3=0,true3=0,ff=0,rnew=0,ll; charleft[30],right[30],flagprogram[100],flag[100];printf("请输入合法的文法表达式，直到文件结束,其中\"定义为\"符号用\"->\"表示\"，空子用'^'表示:\n"); while(~scanf("%s",flagprogram))//等价于EOF结束 {for(i=0;i<strlen(flagprogram);i++) {if(flagprogram[i]=='-') {pos=i;break; } }for(j=0;j<pos;j++)n[count].left[n[count].leftlen++]=flagprogram[j]; for(k=pos+2;k<strlen(flagprogram);k++)n[count].right[n[count].rightlen++]=flagprogram[k];count++; }for(i=0;i<count;i++){if(isupper(n[i].left[0]))flag0=1;//如果至少有一个产生式左部中至少含有一个非终结符，那么为0型n[i].leftlen=strlen(n[i].left);n[i].rightlen=strlen(n[i].right);if(n[i].leftlen<=n[i].rightlen)flag1++;//如果每个产生式的右部长度均大于等于左部长度，这为1型if(n[i].leftlen==1&&isupper(n[i].left[0]))flag2++;//如果每个产生式左部都为一个非终结符，那么此文法为2型的poslowlast=0;if(isupper(n[i].right[0])||n[i].right[0]=='^')true3=1;else {while(!isupper(n[i].right[poslowlast])&&poslowlast<n[i].rightlen)poslowlast++; }for(k=poslowlast;k<n[i].rightlen;k++)if(!isupper(n[i].right[k])||isupper(n[i].right[0]))true3=1;}if(flag0)t0=1;//判断0型文法else{printf("输入错误，左部无非终结符\n");return0;}if(flag1==count)t1=1;if(flag2==count)t2=1;if(flag2==count&&!true3)t3=1;if(t0==1&&!t1&&!t2&&!t3)printf("此文法是一个0型文法\n");if(t1==1&&!t2&&!t3)printf(