等價文法的壓縮存儲實驗報告

1、西北師范大學計算機科學與工程學院學生實驗報告學號：201371020127 2015 年 10 月 1 日學院計算機科學與技術學院專業(yè)軟件工程班級2013級軟件一班姓名王尚課程名稱編譯原理課程類型專業(yè) 學時數(shù)實驗名稱壓縮文法的等價變化實驗目的：1. 了解有關文法的實用限制。 2. 實現(xiàn)用計算機判斷多余規(guī)則。 實驗要求：  l 除了可查看壓縮了的文法，還可查看刪除了哪些規(guī)則  輸入：任意的上下文無關文法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 /將標記數(shù)組置為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("您輸入的規(guī)則：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.規(guī)則輸出：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 /查找單規(guī)則l for(int k=1;k<=count;k+)l l if(rulesk0=rulesk1&&rulesk2='0')l l rulesignk=-1;l l l /查找非引用規(guī)則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