資源描述：
《編譯原理實驗報告3-LL文法構(gòu)造.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。
1、實驗3LL（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；jPiα
2、β
3、，其中β不以Pi開頭，則修改產(chǎn)生式為：Pi—＞βPi′Pi′—＞αPi′
4、ε3）化簡上述所得文法。3、提取左因子的算法：A—＞δβ1
5、δβ2
6、…
7、δβn
8、γ1
9、γ2
10、…
11、γm(其中,每個γ不以δ開頭)那么,可以把這些產(chǎn)生式改寫成A—＞δA′
12、γ1
13、γ2…
14、γmA′—＞β1
15、β2
16、…
17、βn4、利用上述算法，實現(xiàn)構(gòu)造一個LL（1）文法：1）從文本文件g.txt中讀入文法，利用實驗1的結(jié)果，存入實驗1設計的數(shù)據(jù)結(jié)構(gòu)；1）設計函數(shù)remove_left_recursion（）和remove_left_gene（）實現(xiàn)消除左遞歸和提取左因子算法，分別對文法
18、進行操作，消除文法中的左遞歸和提出左因子；2）整理得到的新文法；3）在一個新的文本文件newg.txt輸出文法，文法輸出按照一個非終結(jié)符號一行，開始符號引出的產(chǎn)生式寫在第一行，同一個非終結(jié)符號的候選式用“
19、”分隔的方式輸出。?四、實驗環(huán)境PC微機DOS操作系統(tǒng)或Windows操作系統(tǒng)TurboC程序集成環(huán)境或VisualC++程序集成環(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)造它的L
20、L（1）文法形式；2、把實驗結(jié)果寫入一個新建立的文本文件。?六、測試數(shù)據(jù)輸入數(shù)據(jù)：編輯一個文本文文件g.txt，在文件中輸入如下內(nèi)容：S->Qc
21、c
22、cab;Q->Rb
23、b;R->Sa
24、a;?正確結(jié)果：本實驗的輸出結(jié)果是不唯一的，根據(jù)消除左遞歸是選擇非終結(jié)符號的順序不同，或選擇新的非終結(jié)符號的不同，可能會得到不同的結(jié)果，下面只是可能的一個結(jié)果：S->Qc
25、cT;T->@
26、ab;//由于無法輸出ε，用@代替Q->Rb
27、b;R->bcaU
28、caU
29、cabaU
30、aU;U->bcaU
31、@;?七、實驗報告要求實驗報告應包括以下幾個部分：1、滿足LL（1）文
32、法的分析條件；轉(zhuǎn)換前要求文法中不含回路（經(jīng)過推導有形如P->P之類的），也不含以ε為右部的產(chǎn)生式。一個文法要能進行LL（1）分析，那么這個文法應該滿足：無二義性，無左遞歸，無左公因子。首先需要定義一些規(guī)則：1.在程序運行前文法就必須輸入進文本文件中，輸入的文法只包含其中的所有產(chǎn)生式，并且默認其為可轉(zhuǎn)換的非LL（1）文法，即通過消除左遞歸和反復提取公共左因子，就轉(zhuǎn)換成了LL（1）文法。2.輸入的產(chǎn)生式為原實驗1的結(jié)果，即一個非終結(jié)符只有一條產(chǎn)生式，候選之間用“
33、”隔開。3.產(chǎn)生式與產(chǎn)生式之間只能以換行符或分號隔開。4.開始符號對應的產(chǎn)生式必須第一個
34、輸入，即默認輸入的第一個產(chǎn)生式的左部的大寫字母是開始符號。5.輸入與輸出都會保存在文本文件中文件名分別是g.txt和newg.txt，本實驗測試數(shù)據(jù)時，將兩個文本放在了桌面。6.ε用@代替，輸入與輸出都使用@。7.新產(chǎn)生的非終結(jié)符統(tǒng)一使用沒有在非終結(jié)符集合中出現(xiàn)的大寫字母。8.規(guī)定產(chǎn)生式最多只有20個。2、構(gòu)造LL（1）文法的算法；算法：1)從文本文件g.txt中讀入文法，存入結(jié)構(gòu)體中。將第一個讀到的大寫字母記為開始符號S，將讀到的包括開始符號在內(nèi)的所有大寫字母判定為非終結(jié)符，并將第一次出現(xiàn)的存入文法的非終結(jié)符集合中，終結(jié)符小寫字母也一樣。將以換
35、行符或分號隔開的字符串判斷為一條產(chǎn)生式存入文法中。實現(xiàn)函數(shù)是scanP()。2)對文法中的產(chǎn)生式消除左遞歸。實現(xiàn)函數(shù)是remove_left_recursion()。3)對文法中的產(chǎn)生式反復提取公共左因子。實現(xiàn)函數(shù)是remove_left_gene()。4)向newg.txt中輸出文法的所有產(chǎn)生式。3、消除左遞歸文法和提取左因子算法實現(xiàn)方法；消除左遞歸文法（包括其中用到其它的子函數(shù)）：/*字符串分割函數(shù)，將產(chǎn)生式右部的候選返回,識別‘
36、’，從pos位開始分割*/stringstrsplit(stringstrTok,intpos){strings
37、tr;size_tposition;position=strTok.find("
38、",pos);if(position!=string:
