等价文法的压缩存储实验报告

1、西北师范大学计算机科学与工程学院学生实验报告学号：201371020127 2015 年 10 月 1 日学院计算机科学与技术学院专业软件工程班级2013级软件一班姓名王尚课程名称编译原理课程类型专业 学时数实验名称压缩文法的等价变化实验目的：1. 了解有关文法的实用限制。 2. 实现用计算机判断多余规则。 实验要求：  l 除了可查看压缩了的文法，还可查看删除了哪些规则  输入：任意的上下文无关文法l 输出：等价的压缩了的文法实验内容：l #include<stdio.h>l #include<string.h>l #

2、include<stdlib.h>l #define rulesLength 20l #define length0 20l int count,vnNum=2,vtNum=1;l int lengthrulesLength;l char vnlength0,vtlength0;l int rulerulesLengthrulesLength=0,rulesignrulesLength=0,vnsignrulesLength=0;l char rules6=l l "000",l "ZE+T",l "EE",l "

3、;ES+F",l "ET",l "FF",l "FFP",l "FP",l "PG",l "GG",l "GGG",l "GF",l "TT*i",l "Ti",l "QE",l "QE+F",l "QT",l "QS",l "Si"l ;l void retrieval();l void

4、 input();l void output1();l void output2();l void tag1();l void tag2();l void copyNewArray();l int main()l l input();l retrieval();l tag1();l tag2();l output1();l copyNewArray();l retrieval();l tag1();l tag2();l output2();l printf("n结束！n");l return 0;l l void input()l l count=18;l length1=

5、4;length2=2;length3=4;length4=2;l length5=2;length6=3;length7=2;length8=2;l length9=2;length10=3;length11=2;length12=4;l length13=2;length14=2;length15=4;length16=2;l length17=2;length18=2;l l void copyNewArray()l l int newcount=1;l char newRulesrulesLengthrulesLength;l vnNum=2,vtNum=1;l for(int c=1

6、;c<=count;c+)l l if(rulesignc=2)l l for(int j=0;j<lengthc;j+)l l newRulesnewcountj=rulescj;l l newcount+;l l l count=newcount-1;l for(int c1=1;c1<=count;c1+)l l for(int j=0;j<lengthc1;j+)l l rulesc1j=newRulesc1j;l l l /将标记数组置为0l for(int c2=1;c2<=rulesLength;c2+)l l for(int j=0;j<ru

7、lesLength;j+)l l rulec2j=0;l l vnsignc2=0;l l for(int p2=1;p2<=count;p2+)l l rulesignp2=0;l l printf("n");l for(int h=0;h<length0-1;h+)l l vnh='1'l vth='1'l l l void output1()l l printf("您输入的规则：n");l for(int c=1;c<=count;c+)l l printf(" %c",rule

8、sc0);l printf(" :=");l for(int j=1;j<lengthc;j+)l l printf(" %c",rulescj);l l printf("n");l l l void output2()l l printf("压缩文法输出:n");l /输出非终结字符l printf("1.非终结字符有：n");l for(int m=1;m<vnNum;m+)l l printf(" %c",vnm);l l printf("n&qu

9、ot;);l /输出终结字符l printf("2.终结字符有：n");l for(int n=1;n<vtNum;n+)l l printf(" %c",vtn);l l printf("n");l printf("3.规则输出：n");l for(int c=1;c<=count;c+)l l if(rulesignc=2)l l printf(" %c",rulesc0);l printf(" :=");l for(int j=1;j<lengthc;

10、j+)l l printf(" %c",rulescj);l l printf("n");l l l printf("4.起始字符：n %cn",vn1);l l void retrieval()l l int vnFlag=1,vtFlagn=1,vtFlagt=1;l /检索非终结字符l vn1=rules10;l for(int i2=2;i2<=count;i2+)l l for(int j=1;j<=vnNum;j+)l l if(vnj=rulesi20)l l vnFlag=0;l break;l l l i

11、f(vnFlag)l l vnvnNum=rulesi20;l vnNum+;l l vnFlag=1;l l /检索终结字符l for(int i3=1;i3<=count;i3+)l l for(int j=1;j<lengthi3;j+)l l for(int k=1;k<vnNum;k+)l l if(vnk=rulesi3j)l l vtFlagn=0;l break;l l l for(int h=1;h<=vtNum;h+)l l if(vth=rulesi3j)l l vtFlagt=0;l break;l l l if(vtFlagn&&

12、;vtFlagt)l l vtvtNum=rulesi3j;l vtNum+;l l vtFlagn=1;l vtFlagt=1;l l l l void tag1()l l int flag=1,num;l /查找单规则l for(int k=1;k<=count;k+)l l if(rulesk0=rulesk1&&rulesk2='0')l l rulesignk=-1;l l l /查找非引用规则l for(int i4=2;i4<=count;i4+)l l num=rulesi40;l for(int m=1;m<=count;m+

13、)l l for(int n=1;n<lengthm;n+)l l if(num=rulesmn)l l flag=1;l break;l l l if(flag)l break;l l if(flag=0)l l rulesigni4=-1;l l flag=0;l l /为起始字符加标l for(int i5=1;i5<=count;i5+)l l for(int j=0;j<lengthi5;j+)l l if(rulesi5j=vn1)l rulei5j=1;l l l /为其他字符加标l for(int i6=1;i6<=count;i6+)l l for(i

14、nt j=0;j<lengthi6;j+)l l for(int k=2;k<vnNum;k+)l l if(rulesi6j=vnk&&rulesigni6!=-1) /第rulesij是非终结字符l l if(rulei6j=1)l break;l for(int m=1;m<=count;m+)l l for(int n=0;n<lengthm;n+)l l if(rulesmn=vnk&&rulesignm!=-1)l l rulemn=1;l rulesignm=1;l l l l l l l l l void tag2()l

15、l /为仅由终结字符组成的串加标l int flaga=0,sum1=0,flagb=0,sum2=0;l for(int i7=1;i7<=count;i7+)l l if(rulesigni7=-1)l continue;l elsel l for(int j=1;j<lengthi7;j+)l l for(int k=1;k<vtNum;k+)l l if(rulesi7j=vtk)l l flaga=1;l break;l l l sum1+=flaga;l flaga=0;l l if(sum1=lengthi7-1)l l rulesigni7=2;l for(i

16、nt p=0;p<lengthi7;p+)l l rulei7p=2;l for(int q=1;q<vnNum;q+)l l if(rulesi7p=vnq)l vnsignq=1;l l l l sum1=0;l l l /为其他串加标l for(int r=1;r<=count;r+)l l for(int i8=1;i8<=count;i8+)l l if(rulesigni8=1)l l for(int j=1;j<=lengthi8;j+)l l for(int k=1;k<vnNum;k+)l l if(rulesi8j=vnk&&vnsignk=1)l l flagb=1;l break;l l l for(int t=1;t<vtNum;t+)l l if(rulesi8j=vtt)l l flagb=1;l break;l l l sum2+=flagb;l flagb=0;l l if(sum2=lengthi8-1)l l ru