實(shí)驗(yàn)3LL1文法構(gòu)造

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程：編譯原理學(xué)生姓名：學(xué) 號(hào)：專(zhuān)業(yè)班級(jí)：計(jì)科實(shí)驗(yàn) 3 LL( 1)文法構(gòu)造一、實(shí)驗(yàn)?zāi)康氖煜L (1 )文法的分析條件，了解 LL (1)文法的構(gòu)造方法。二、實(shí)驗(yàn)內(nèi)容1 、編制一個(gè)能夠?qū)⒁粋€(gè)非 LL( 1 )文法轉(zhuǎn)換為 LL( 1 )文法；2、消除左遞歸；3、消除回溯。三、實(shí)驗(yàn)要求1、 將一個(gè)可轉(zhuǎn)換非 LL (1)文法轉(zhuǎn)換為L(zhǎng)L (1)文法，要經(jīng)過(guò)兩個(gè)階段，1)消除文法 左遞歸， 2)提取左因子，消除回溯。2、提取文法左因子算法：1) 對(duì)文法G的所有非終結(jié)符進(jìn)行排序2) 按上述順序?qū)γ恳粋€(gè)非終結(jié)符Pi 依次執(zhí)行 :for( j=1 ； j Pi a | 3 ，其中B不以Pi開(kāi)頭，

2、則修改產(chǎn)生式為：Pi 3 Pi Pi a Pi I &3) 化簡(jiǎn)上述所得文法。3、提取左因子的算法：A SB 11 S3 2l I SB nl Y 1l Y 2l I 丫 m(其中，每個(gè)丫不以S開(kāi)頭)那么 , 可以把這些產(chǎn)生式改寫(xiě)成A S A 1 Y 11 Y 21 Y mA 3 1l 3 2l I 3n4、利用上述算法，實(shí)現(xiàn)構(gòu)造一個(gè) LL( 1 )文法：1 ) 從文本文件 g.txt 中讀入文法，利用實(shí)驗(yàn) 1 的結(jié)果，存入實(shí)驗(yàn) 1 設(shè)計(jì)的數(shù)據(jù)結(jié) 構(gòu)；2) 設(shè)計(jì)函數(shù) remove_left_recursion ()和 remove_left_gene ()實(shí)現(xiàn)消除左遞歸和 提取左因子算法，分別

3、對(duì)文法進(jìn)行操作，消除文法中的左遞歸和提出左因子；3) 整理得到的新文法；4) 在一個(gè)新的文本文件 newg.txt 輸出文法，文法輸出按照一個(gè)非終結(jié)符號(hào)一行，開(kāi)始符號(hào)引出的產(chǎn)生式寫(xiě)在第一行，同一個(gè)非終結(jié)符號(hào)的候選式用“l(fā)”分隔的方式輸出。四、實(shí)驗(yàn)環(huán)境PC微機(jī)DOS操作系統(tǒng)或 Windows操作系統(tǒng)Turbo C程序集成環(huán)境或 Visual C+程序集成環(huán)境五、實(shí)驗(yàn)步驟1、學(xué)習(xí)LL (1)文法的分析條件；2、學(xué)習(xí)構(gòu)造LL( 1)文法的算法；3、 結(jié)合實(shí)驗(yàn)1給出的數(shù)據(jù)結(jié)構(gòu)，編程實(shí)現(xiàn)構(gòu)造LL( 1)文法的算法；4、 結(jié)合實(shí)驗(yàn)1編程和調(diào)試實(shí)現(xiàn)對(duì)一個(gè)具體文法運(yùn)用上述算法，構(gòu)造它的LL( 1)文法 形式；

4、5、把實(shí)驗(yàn)結(jié)果寫(xiě)入一個(gè)新建立的文本文件。六、測(cè)試數(shù)據(jù)輸入數(shù)據(jù)：編輯一個(gè)文本文文件 g.txt，在文件中輸入如下內(nèi)容：SQc|c|cab;Q-Rb|b;R-Sa|a;正確結(jié)果：本實(shí)驗(yàn)的輸出結(jié)果是不唯一的，根據(jù)消除左遞歸是選擇非終結(jié)符號(hào)的順序不同，或選擇新的非終結(jié)符號(hào)的不同，可能會(huì)得到不同的結(jié)果，下面只是可能的一個(gè)結(jié)果：S-Qc|cT;T-|ab;/由于無(wú)法輸出，用 代替Q-Rb|b;R-bcaU|caU|cabaU|aU;U-bcaU|;七、實(shí)驗(yàn)報(bào)告要求實(shí)驗(yàn)報(bào)告應(yīng)包括以下幾個(gè)部分：1、滿足LL (1)文法的分析條件；2、構(gòu)造LL (1)文法的算法；3、消除左遞歸文法和提取左因子算法實(shí)現(xiàn)方法;4、

5、整個(gè)測(cè)試程序的流程；5、程序的測(cè)試結(jié)果和問(wèn)題；6、實(shí)驗(yàn)總結(jié)。代碼#in clude#in cludeusing n amespace std;typedef struct Chomsky /定義一個(gè)產(chǎn)生式結(jié)構(gòu)體string left; /定義產(chǎn)生式的左部string right; II定義產(chǎn)生式的右部Chomsky;int n;II產(chǎn)生式總數(shù)string strings;存儲(chǔ)產(chǎn)生式char q20;void apart(Chomsky *p,int i) II分開(kāi)產(chǎn)生式左右部 i代表產(chǎn)生式的編號(hào)int j;for(j=0;jstri ngs.len gth();j+)if(stringsj=

6、_)pi.left=strings.substr(Oj);/ 從 0 開(kāi)始的 j 長(zhǎng)度的子串即 0j-1pi.right=strings.substr(j+1,strings.length() -j);II 從 j+1 開(kāi)始的后面子串 int zero(Chomsky *p)II0 型文法int flag(0),cou nt(0);int i,j;for(i=0;i n;i+)for(j=0;j=A&pi.leftj0)/說(shuō)明某一個(gè)產(chǎn)生式左部有非終結(jié)符flag=0;/下個(gè)產(chǎn)生式判斷前清零count+;/左部存在非終結(jié)符的產(chǎn)生式個(gè)數(shù)加1elsebreak; /左部沒(méi)有非終結(jié)符結(jié)束if(co un

7、t=n)return 1; /屬于0型文法elsecoutendl所輸產(chǎn)生式不屬于任何文法。endl;return 0;int on e(Chomsky *p)/1 型文法int flag(0);int i;if(zero(p)for(i=0;i n; i+)if(pi.right.le ngth()0)coutendl此文法屬于0型文法 即短語(yǔ)文法。endl; return 0;/不屬于1型文法elseif(flag=0)return 1; /屬于1型文法elsereturn 0;int two(Chomsky *p)/2 型文法int flag(0);int i;if(o ne(p)for

8、(i=0;i =A&pi.leftO0)coutendl此文法屬于1型文法即上下文有關(guān)文法。endl; return 0;/不屬于2型文法elseif(flag=0)return 1; /屬于2型文法elsereturn 0;int remove(Chomsky *p,int n) 消除左遞歸/把文法的所有非終結(jié)符按某一順序排序int i,j,co un t=1,co un t1= n, flag=0,m,x; qO=pOeftO;for(i=1;in;i+)for(j=0;ji;j+)if(pi.left=pj.left)break;if(j=i)qcount+=pi.left0;count

9、 -;for(i=0;in;i+)/ 判斷第一個(gè)非終結(jié)符是否存在直接左遞歸if(pi.left0=q0&pi.left0=pi.right0)flag+;if(flag!=0)/ 消除第一個(gè)非終結(jié)符的直接左遞歸for(i=0;in;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;elsepi.right=pi.right+pi.left+;pcount1.left=p0.left;pcount1+.right=#;/ 用 #

10、代替空產(chǎn)生式/ 消一切左遞歸for(m=0;m=count;m+)for(i=0;in;i+)if(pi.left0=qm)for(j=0;jcount1;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.right.length();count1=count1+1;for(j=0;jcount1;j+)for(x=m+1;x=count;x+)if(pj.right0=qm&pj.left0=qx)pj.ri

11、ght=;pj.left=;for(x=0,flag=0;xcount1;x+)/ 判斷第 m 個(gè)非終結(jié)符是否存在直接左遞歸if(px.left0=qm&px.left0=px.right0)flag+;/ 消直接左遞歸if(flag!=0)for(i=0;icount1;i+)if(pi.left0=qm)if(pi.left0=pi.right0)pi.left=pi.left+;pi.right=pi.right.substr(1,pi.right.le ngth()+pi.left;pcou nt1.left=pi.left;pcount1.right=#; 用#代替空產(chǎn)生式elsep

12、i.right=pi.right+pi.left+;coun t1=co un t1+1;count1 -;return coun t1;void mai n()int i,j,co un t1;空用#表cout編譯原理實(shí)驗(yàn)非LL文法到LL(1)文法的轉(zhuǎn)換endl;cout請(qǐng)輸入產(chǎn)生式總數(shù)及各產(chǎn)生式e ndl其中左右部之間用-表示示e ndl;cinn;Chomsky *p=new Chomsky50; / 初始化產(chǎn)生式數(shù)組for(i=0;i stri ngs;apart(p,i);if(two(p)cout該文法屬于二型文法實(shí)驗(yàn)繼續(xù).vvendl;coun t1=remove(p ,n);coutvv轉(zhuǎn)換后的文法輸出如下e ndl;for(i=0;i=co un t1;i+)if(pi.leftO!=NULL)cout卩口血6ndl;elsecout該文法不是2型文法 無(wú)需進(jìn)行LL(1)的轉(zhuǎn)換實(shí)驗(yàn)結(jié)束endl