編譯原理實驗報告

1、.編譯原理實驗報告編譯原理實驗報告書 姓名： 專業(yè)： 班級： 學號： 指導老師：一、實驗內容求解一個文法的first、follow、select集合并判斷是不是LL(1)文法。一、 實驗目的通過實驗熟練掌握first、follow、select集合的求解算法，加深對理論知識的理解。二、 實驗原理1.first集的求解：(1)若XVt,則FIRST(X)=X; (2)若XVn,且有產生式X->a,aVt，則aFIRST(X); (3)若XVn,X->,則FIRST(X) (4)若X,Y1,Y2,Y3,Y4Yn都Vn,而產生式X->Y1,Y2Yn.當Y1,Y2,Y3,Y4Yn都能

2、=>那么FIRST(X)=并集的FIRST(Yi)- (0<=i<=n) (5)若Yi=>(i=1,2,3)，則FIRST(X)=并集的FIRST(Yi)- 并上2.follow集的求解:(1)若為文法開始符號S，則FOLLOW(S)=# (2)若為文法A->aBb是一個產生式，則把FIRST（b）的非空元素加入FOLLOW(B)中。如果b->則把FOLLOW(A)也加入FOLLOW(B)中。3.select=(A->a)=(first(a)- )并上follow(A)。三、 設計實現(xiàn)int isJudLegal(Production p) /判斷產生

3、式是否合法int mid1,mid2,right=0;int i; int flag=0;mid1=0;mid2=1;right=0;if(num=0)printf("產生式個數(shù)為零n");return 0;for(i=0;i<num;i+)if(Numi.lData.Ldata>'Z'|Numi.lData.Ldata<'A')printf("產生式左部應該為非終結符（大寫字母）n");return 0;if(Numi.mDatamid1!='-'|p.pr

4、oNumi.mDatamid2!='>')printf("產生式中間->有誤n");return 0;while(Numi.rDataright!='0')if(Numi.rDataright='*')|(Numi.rDataright>='a'&&Numi.rDataright<='z')|(Numi.rDataright>='A'&&(Numi.rData

5、right<='Z')flag=1;if(flag!=1)printf("產生式右部輸入不符合要求！n");return 0;right+;flag=0;right=0;return 1;int leftRecursive(Production p,nonTer nT20) int i,j;char ch1,ch2;for(i=0;i<num;i+)if(Numi.lData.Ldata=Numi.rData0)printf("文法含有直接左遞歸!n");return 1;for(i=0;i<num;

6、i+)ch1=Numi.lData.Ldata;ch2=Numi.rData0;for(j=0;j<num;j+)if(Numj.lData.Ldata=ch2&&Numj.rData0=ch1)printf("文法中含有間接左遞歸!n");return 1;return 0;int First(Production p,nonTer nT20) /計算first集int i,j=0,right=0,k=1,t,m=0,low,n,a=0,b,f,k1,flag,f1,f2;char ch; /中間變量，對fir

7、st集合排序時使用char r10; /臨時存放產生式右邊非終結符memset(r,'0',sizeof(r);t=0; /用來記錄某個產生式右邊非終結符的個數(shù)low=0; /用來標記某一產生式右邊是否是非終結符和終結符的組合for(i=0;i<sum;i+) /初始化FIRST集for(j=0;j<10;j+)nTi.firstj='0'nTi.fir=0;for(i=0;i<sum;i+)k=0;k1=0;right=0;t=0;/memset(r,'0',sizeof(r);for(j=0;j<num;j+)if(n

8、Ti.nonTerminal=Numj.lData.Ldata) /步驟二if(Numj.rData0>='a'&&Numj.rData0<='z')nTi.firstk=Numj.rData0;k+;Numj.lData.tag2=0; /表示該產生式被處理過if(Numj.rData0='*') /步驟三nTi.firstk='*'k+;Numj.lData.tag2=0;if(Numj.rData0>='

9、A'&&Numj.rData0<='Z') Numj.lData.tag2=2;for(i=0;i<sum;i+) /將計算過first集合的非終結符對應的標志位置1for(j=0;j<num;j+)if(Numj.lData.Ldata=nTi.nonTerminal&&Numj.lData.tag2=2)break;if(j=num)nTi.fir=1;/開始處理右邊以大寫字母開頭的產生式while(isEnd(nT)for(i=0;i<num;i+) f2=1;t=0;

10、right=0;memset(r,'0',sizeof(r);k=0;b=0;low=0;if(Numi.lData.tag2=2)for(j=0;j<sum&&f2;j+)if(Numi.lData.Ldata=nTj.nonTerminal)f2=0;right=0;while(Numi.rDataright!='0')rt=Numi.rDataright; /printf("r%d=%cn",t,rt);t+; right+;f=1; /用來標記右邊字符串能否推出空 for(

11、m=0;m<t;m+)while(nTj.firstk!='0')k+;if(rm>='a'&&rm<='z')f=0;continue;for(n=0;n<sum;n+)if(rm=nTn.nonTerminal&&nTn.tag=1)b=0; while(nTn.firstb!='0')if(nTn.firstb!='*')nTj.firstk=nTn.firstb;k+;b+;if(nTn.fir=0)low=1;if(rm=nTn.nonTermina

12、l&&nTn.tag=0)a=0;while(nTn.firsta!='0')nTj.firstk=nTn.firsta;k+;a+;f=0;b=0;if(f) nTj.firstk='*'k+;if(!low)nTj.fir=1;for(i=0;i<sum;i+) /對非終結符的first集合從小到大排序j=0;while(nTi.firstj!='0')k=j;a=j;while(nTi.firsta!='0')if(nTi.firsta<nTi.firstk)k=a;a+;if(k!=j)ch=n

13、Ti.firstk;nTi.firstk=nTi.firstj; nTi.firstj=ch;j+;for(i=0;i<sum;i+) /刪除first集中重復的元素memset(r,'0',sizeof(r); j=1;b=1;k=0;r0=nTi.first0;while(nTi.firstj!='0')if(rk!=nTi.firstj)k+;rk=nTi.firstj;b+;j+;for(a=0;a<b;a+)nTi.firsta=ra;nTi.firsta='0'for(i=0;i<num;i+) /計算字符串的fir

14、st集合f1=0;k=0;j=0;f=0;flag=0;if(Numi.rData0>='a'&&Numi.rData0<='z')nTi.firsts0=Numi.rData0;continue;if(Numi.rData0>='A'&&Numi.rData0<='Z')for(k=0;k<sum;k+)if(Numi.rData0=nTk.nonTerminal)if(nTk.tag=0)f=1;a=0;w

15、hile(nTk.firsta!='0')nTi.firstsa=nTk.firsta;a+;break;if(nTk.tag=1)a=0;while(nTk.firsta!='0')if(nTk.firsta!='*')nTi.firstsj=nTk.firsta;j+;a+;b=1;if(f)continue;while(Numi.rDatab!='0')if(Numi.rDatab>='a'&&Numi.rDatab<='z')nTi.

16、firstsj=Numi.rDatab;j+;f1=1;elsefor(k=0;k<sum;k+)a=0;if(nTk.nonTerminal=Numi.rDatab)if(nTk.tag=1)while(nTk.firsta!='0')if(nTk.firsta!='*')nTi.firstsj=nTk.firsta;j+;a+;if(nTk.tag=0)while(nTk.firsta!='0')nTi.firstsj=nTk.firsta;j+;a+;flag=1;b+;if(!flag&&!f1)

17、nTi.firstsj='*'j+;for(i=0;i<num;i+) /對字符串的first集合從小到大排序j=0;while(nTi.firstsj!='0')k=j;a=j;while(nTi.firstsa!='0')if(nTi.firstsa<nTi.firstsk)k=a;a+;if(k!=j)ch=nTi.firstsk;nTi.firstsk=nTi.firstsj; nTi.firstsj=ch;j+;for(i=0;i<num;i+) memset(r,'0',sizeof(r); j=1;

18、b=1;k=0;r0=nTi.firsts0;while(nTi.firstsj!='0')if(rk!=nTi.firstsj)k+;rk=nTi.firstsj;b+;j+;for(a=0;a<b;a+)nTi.firstsa=ra;nTi.firstsa='0'for(i=0;i<sum;i+)j=0;printf("非終結符%c的first集為:",nTi.nonTerminal);while(nTi.firstj!='0')printf("%c ",nTi.firstj);j+;pri

19、ntf("n");printf("n");for(i=0;i<num;i+)j=0;printf("字符串%s的first集為:",nTi.str);while(nTi.firstsj!='0')printf("%c ",nTi.firstsj);j+;printf("n");printf("n");return 1;void initFollow(nonTer nT20) /初始化follow集合int i,j;for(i=0;i<sum;i+)for(j=0;j<10;j+)nTi.followj='0'nTi.formFollowj='0'nTi.fol=0;int main()Production p,p1;int flag=0,i; nonTer nT20;memset(nT,'0',sizeof(nT);p=input(); p1=c