實驗3：LL(1)文法構(gòu)造

1、實 驗 報 告實驗課程： 編譯原理 學生姓名： 學 號： 專業(yè)班級： 計科 實驗3 LL（1）文法構(gòu)造一、實驗目的熟悉LL（1）文法的分析條件，了解LL（1）文法的構(gòu)造方法。 二、實驗內(nèi)容1、編制一個能夠?qū)⒁粋€非LL（1）文法轉(zhuǎn)換為LL（1）文法；2、消除左遞歸；3、消除回溯。 三、實驗要求1、 將一個可轉(zhuǎn)換非LL（1）文法轉(zhuǎn)換為LL（1）文法，要經(jīng)過兩個階段，1）消除文法左遞歸，2）提取左因子，消除回溯。2、 提取文法左因子算法：1）對文法G的所有非終結(jié)符進行排序2）按上述順序?qū)γ恳粋€非終結(jié)符Pi依次執(zhí)行:for( j=1； j< i-1；j+)將Pj代入Pi的產(chǎn)生

2、式（若可代入的話）；消除關(guān)于Pi的直接左遞歸：Pi -> Pi| ，其中不以Pi開頭，則修改產(chǎn)生式為：Pi PiPi Pi|3）化簡上述所得文法。3、 提取左因子的算法： A 1|2|n|1|2|m (其中,每個不以開頭)那么,可以把這些產(chǎn)生式改寫成 A A|1| 2|m A1|2|n4、 利用上述算法，實現(xiàn)構(gòu)造一個LL（1）文法：1） 從文本文件g.txt中讀入文法，利用實驗1的結(jié)果，存入實驗1設(shè)計的數(shù)據(jù)結(jié)構(gòu)；2） 設(shè)計函數(shù)remove_left_recursion（）和remove_left_gene（）實現(xiàn)消除左遞歸和提取左因子算法，分別對文法進行操作，消除文法中的左遞歸和提出左因

3、子；3） 整理得到的新文法；4） 在一個新的文本文件newg.txt輸出文法，文法輸出按照一個非終結(jié)符號一行，開始符號引出的產(chǎn)生式寫在第一行，同一個非終結(jié)符號的候選式用“|”分隔的方式輸出。 四、實驗環(huán)境PC微機DOS操作系統(tǒng)或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(huán)境 五、實驗步驟 1、學習LL（1）文法的分析條件； 2、學習構(gòu)造LL（1）文法的算法；3、結(jié)合實驗1給出的數(shù)據(jù)結(jié)構(gòu)，編程實現(xiàn)構(gòu)造LL（1）文法的算法；4、結(jié)合實驗1編程和調(diào)試實現(xiàn)對一個具體文法運用上述算法，構(gòu)造它的LL（1）文法形式；5、 把實驗結(jié)果寫入一個新建

4、立的文本文件。 六、測試數(shù)據(jù) 輸入數(shù)據(jù)：編輯一個文本文文件g.txt，在文件中輸入如下內(nèi)容：S->Qc|c|cab;Q->Rb|b;R->Sa|a; 正確結(jié)果： 本實驗的輸出結(jié)果是不唯一的，根據(jù)消除左遞歸是選擇非終結(jié)符號的順序不同，或選擇新的非終結(jié)符號的不同，可能會得到不同的結(jié)果，下面只是可能的一個結(jié)果：S->Qc|cT;T->|ab; /由于無法輸出，用代替Q->Rb|b;R->bcaU|caU|cabaU|aU;U->bcaU|;  七、實驗報告要求實驗報告應包括以下幾個部分：1、 滿足LL（1）文法的分析條件；

5、2、 構(gòu)造LL（1）文法的算法；3、 消除左遞歸文法和提取左因子算法實現(xiàn)方法；4、 整個測試程序的流程；5、 程序的測試結(jié)果和問題；6、 實驗總結(jié)。代碼#include<iostream> #include<string> using namespace std; typedef struct Chomsky /定義一個產(chǎn)生式結(jié)構(gòu)體 string left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部 Chomsky; int n;/產(chǎn)生式總數(shù) string strings;/存儲產(chǎn)生式 char q20; void apart(Chomsky

6、*p,int i) /分開產(chǎn)生式左右部i代表產(chǎn)生式的編號 int j; for(j=0;j<strings.length();j+) if(stringsj='-') pi.left=strings.substr(0,j);/從0開始的j長度的子串即0j-1 pi.right=strings.substr(j+1,strings.length()-j);/從j+1開始的后面子串 int zero(Chomsky *p)/0型文法 int flag(0),count(0); int i,j; for(i=0;i<n;i+) for(j=0;j<(int)pi.l

7、eft.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z') /有否非終結(jié)符 flag+;/非終結(jié)符個數(shù)加1 if(flag>0)/說明某一個產(chǎn)生式左部有非終結(jié)符 flag=0;/下個產(chǎn)生式判斷前清零 count+;/左部存在非終結(jié)符的產(chǎn)生式 個數(shù)加1 else break; /左部沒有非終結(jié)符結(jié)束 if(count=n) return 1; /屬于0型文法 else cout<<endl<<"所輸產(chǎn)生式不屬于任何文法。"<<endl;

8、 return 0; int one(Chomsky *p)/1型文法 int flag(0); int i; if(zero(p) for(i=0;i<n;i+) if(pi.right.length()<pi.left.length() /右部長度是否小于左部不是1型 flag+; break; else /即不是0型文法 flag-;/flag=-1 if(flag>0) cout<<endl<<"此文法屬于0型文法即短語文法。"<<endl; return 0; /不屬于1型文法 else if(flag=0)

9、return 1; /屬于1型文法 else return 0; int two(Chomsky *p)/2型文法 int flag(0); int i; if(one(p) for(i=0;i<n;i+) if(pi.left.length()!=1)|!(pi.left0>='A'&&pi.left0<='Z') /左部不屬于一個字符或不屬于非終結(jié)符 flag+;/則不為2型 break; else/不為1型flag=-1 flag-; if(flag>0) cout<<endl<<"

10、此文法屬于1型文法即上下文有關(guān)文法。"<<endl; return 0; /不屬于2型文法 else if(flag=0) return 1; /屬于2型文法 else return 0; int remove(Chomsky *p,int n)/消除左遞歸 /把文法的所有非終結(jié)符按某一順序排序 int i,j,count=1,count1=n,flag=0,m,x; q0=p0.left0; for(i=1;i<n;i+) for(j=0;j<i;j+) if(pi.left=pj.left)break; if(j=i)qcount+=pi.left0; c

11、ount-; for(i=0;i<n;i+)/判斷第一個非終結(jié)符是否存在直接左遞歸 if(pi.left0=q0&&pi.left0=pi.right0) flag+; if(flag!=0)/消除第一個非終結(jié)符的直接左遞歸 for(i=0;i<n;i+) if(pi.left0=q0) if(pi.left0=pi.right0) pi.left=pi.left+"'" pi.right=pi.right.substr(1,pi.right.length()+pi.left; else pi.right=pi.right+pi.left

12、+"'" pcount1.left=p0.left; pcount1+.right="#"/用#代替空產(chǎn)生式 /消一切左遞歸 for(m=0;m<=count;m+) for(i=0;i<n;i+) if(pi.left0=qm) for(j=0;j<count1;j+) for(x=m+1;x<=count;x+) if(pj.left0=qx&&pj.right0=qm) pcount1.left=pj.left; pcount1.right=pi.right+pj.right.substr(1,pj.

13、right.length(); count1=count1+1; for(j=0;j<count1;j+) for(x=m+1;x<=count;x+) if(pj.right0=qm&&pj.left0=qx) pj.right="" pj.left="" for(x=0,flag=0;x<count1;x+)/判斷第m個非終結(jié)符是否存在直接左遞歸 if(px.left0=qm&&px.left0=px.right0) flag+; /消直接左遞歸 if(flag!=0) for(i=0;i<co

14、unt1;i+) if(pi.left0=qm) if(pi.left0=pi.right0) pi.left=pi.left+"'" pi.right=pi.right.substr(1,pi.right.length()+pi.left; pcount1.left=pi.left; pcount1.right="#"/用#代替空產(chǎn)生式 else pi.right=pi.right+pi.left+"'" count1=count1+1; count1-; return count1; void main( ) in

15、t i,j,count1; cout<<".編譯原理實驗非LL(1)文法到LL(1)文法的轉(zhuǎn)換."<<endl; cout<<"請輸入產(chǎn)生式總數(shù)及各產(chǎn)生式"<<endl<<"其中左右部之間用'-'表示空用'#'表示"<<endl; cin>>n; Chomsky *p=new Chomsky50; / 初始化產(chǎn)生式數(shù)組 for(i=0;i<n;i+) cin>>strings; apart(p,i); if(two(p) cout<<"該文法屬于二型文法實驗繼續(xù)."<<endl; count1=remove(p,n); cout<<"轉(zhuǎn)換后的文法輸出如下"<<endl; for(i=0;i<=count1;i+) if(pi.left0!=NULL) cout<<pi.left<<"