編譯原理實(shí)驗(yàn)報告

1、編譯原理課程設(shè)計報告選題名稱: LL(1)文法 院（系）: 計算機(jī)工程學(xué)院專 業(yè): 計算機(jī)科學(xué)與技術(shù)班 級: 姓 名: 學(xué) 號: 指導(dǎo)教師: 年月號目錄目錄I摘要II1.設(shè)計內(nèi)容及要求12實(shí)現(xiàn)原理 2.1 判斷左遞歸1 2.2 計算first集合算法.2 2.3 計算follow集合算法.3 2.4 預(yù)測分析過程算法.43.詳細(xì)設(shè)計實(shí)現(xiàn)及關(guān)鍵代碼.5 3.1程序總流程圖.63.2導(dǎo)入文件63.3判斷左遞歸63.4 FIRST集合的計算73.5 FOLLOW集的計算93.6構(gòu)造預(yù)測分析表103.7 LL1預(yù)測分析過程114.程序調(diào)試部分截圖145.課設(shè)總結(jié)166.參考文獻(xiàn)18 摘要： 編譯程序一

2、般由詞法分析器、語法分析器、語義分析程序、中間代碼產(chǎn)生程序、目標(biāo)代碼生成程序、代碼優(yōu)化等組成，其中最主要的應(yīng)該是語法分析，它是編譯過程的核心部分。語法分析是在詞法分析識別出的Token單詞符號串的基礎(chǔ)上，分析并判斷程序的語法結(jié)構(gòu)是否符合語法規(guī)則。而語言的語法結(jié)構(gòu)式用上下文無關(guān)文法描述的，這與形式語言的學(xué)習(xí)有很大的關(guān)系。語法分析的本質(zhì)是按文法的產(chǎn)生式，求出First、Follow集以及預(yù)測分析表這就是語法分析也就是此次LL(1)文法分析課程設(shè)計的主要內(nèi)容。具體實(shí)現(xiàn)流程即對讀入文法進(jìn)行初始化的處理，刪除無用的符號句子，然后進(jìn)行相應(yīng)的消除左遞歸，以及消除間接左遞歸，并且對公因子進(jìn)行提取，對文法分析，

3、然后得到文法的First、Follow集以及分析預(yù)測表，然后對輸入的句子進(jìn)行分析，通過出棧入棧進(jìn)行比較得出是否分析成功，然后通過表格將結(jié)果顯示出來，還有分析的過程，每一步入棧出棧等演示出來。關(guān)鍵字：左遞歸、First、Follow集、預(yù)測分析表正文：一 設(shè)計內(nèi)容及要求(1) 基于PL/0語言，通過編程判斷該文法是否為LL(1)文法； (2)計算出文法的First() Follow()(3)構(gòu)造相應(yīng)文法的預(yù)測分析表(4)對某個輸入句子進(jìn)行語法分析二 實(shí)現(xiàn)原理1LL(1)文法LL(1)文法是一類可以進(jìn)行確定的自頂向下語法分析的文法。就是要求描述語言的文法是無左遞歸的和無回溯的。根據(jù)LL(1)文法的

4、定義，對于同一非終結(jié)符A的任意兩個產(chǎn)生式A:=a和A:=b，都要滿足：SELECT(A：=a )SELECT(A:=b)=。（1）文法的左遞歸當(dāng)一個文法是左遞歸文法時，采用自頂向下分析法會使分析過程進(jìn)入無窮循環(huán)之中。所以采用自頂向下語法分析需要消除文法的左遞歸性。文法的左遞歸是指若文法中對任一非終結(jié)符A有推導(dǎo)AA，則稱該文法是左遞歸的。左遞歸又可以分為直接左遞歸和間接左遞歸。 直接左遞歸若文法中的某一產(chǎn)生式形如AA，V*，則稱該文法是直接左遞歸的。消除直接左遞歸的方法：設(shè)有產(chǎn)生式是關(guān)于非終結(jié)符A的直接左遞歸：AA| （,V*，且不以A開頭）對A引入一個新的非終結(jié)符A，把上式改寫為：A A AA

5、| 間接左遞歸若文法中存在某一非終結(jié)符A，使得AA至少需要兩步推導(dǎo)，則稱該文法是間接左遞歸的。消除間接左遞歸的方法：【方法一】采用代入法把間接左遞歸變成直接左遞歸。 【方法二】直接改寫文法：設(shè)有文法G10S： SA| AS 因?yàn)镾AS，所以S是一個間接遞歸的非終結(jié)符。為了消除這種間接左遞歸，將式代入式，即可得到與原文法等價的文法（可以證明）： SS| 式是直接左遞歸的，可以采用前面介紹的消除直接左遞歸的方法，對文法進(jìn)行改寫后可得文法：SSSS|2. 計算First集(1) 若XVT ，則First(X)=X(2) 若XVN ，且有產(chǎn)生式Xa, aVT則First(X)=X(3) 若XVN ，且

6、有產(chǎn)生式X,則First(X)=X(4) 若X，Y1 ，Y2 ，Yn 都VN，而由產(chǎn)生式XY1 Y2 Yn 。當(dāng)Y1 ，Y2 ，Yi-1都能推導(dǎo)出時，（其中1in），則First(Y1)-, First(Y2)-, First(Yi)都包含在First(X)中(5)當(dāng)(4)中所有Yi都能推導(dǎo)出，（i=1，2，n），則First(X)=First(Y1)First(Y2)First(Yn)反復(fù)使用上述步驟直到每個符合的First集合不再增大為止。3. 計算Follow集對文法中的每個AVN，計算Follw(A)：(1) 設(shè)S為文法的開始符合，把#加入Follow(S)中；(2) 若AB是一個產(chǎn)生

7、式，則把First()的非空元素加入Follow(B)中，如果能推導(dǎo)出，則把Follow(A)也加入(B)中；(3) 反復(fù)使用以上步驟直到每個非終結(jié)符號的Follow集不再增大為止。4. 預(yù)測分析方法預(yù)測分析方法是自頂向下分析的另一種方法，一個預(yù)測分析器是由三個部分組成：預(yù)測分析程序；先進(jìn)后出棧；預(yù)測分析表。預(yù)測分析程序的框圖如下：三.設(shè)計實(shí)現(xiàn)：給定一個正規(guī)文法G，在LL(1)預(yù)測分析中，必須先求出First集和Follow集，然后求出Select集，通過Select集判斷是否是LL1文法，如果是的話，構(gòu)造預(yù)測分析表。求出預(yù)測分析表之后，再輸入一個字符串，依據(jù)LL1分析表單步輸出字符串的分析過

8、程。主程序流程圖：模塊1文件導(dǎo)入將存儲在txt文本文件中的文法導(dǎo)出，顯示在界面上，并解析出其中的終結(jié)符和非終結(jié)符存入相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。模塊2判斷是否存在左遞歸用產(chǎn)生式組A1 B|2 B |n BB1 B|2 B |n B|替換產(chǎn)生式組AA1|A2|An|1|2|m 其中：B為新變量，相當(dāng)于A主要代碼為：public static String isZuoDiGui(HashMapString, ArrayListArrayList wenfa2) for (Map.EntryString, ArrayListArrayList entry : wenfa2.entrySet() String

9、leftKey = entry.getKey();ArrayListArrayList value = entry.getValue();for (ArrayList arrayList : value) String rightKey = arrayList.get(0);/ 直接左遞歸if (leftKey.equals(rightKey) return leftKey + - + arrayList.toString() + 含有直接左遞歸; else / 如果arrayList.get(0)是非終結(jié)符if (wenfa2.containsKey(rightKey) ArrayListA

10、rrayList rightValue = wenfa2.get(rightKey);for (ArrayList arrayList2 : rightValue) if (arrayList2.get(0).equals(leftKey) / 間接左遞歸return leftKey + - + arrayList.toString() + n+ rightKey + - + arrayList2.toString()+ 含有間接左遞歸;return null;模塊3First集詳細(xì)設(shè)計實(shí)現(xiàn)代碼：public void getFirst(ArrayList tempList, String k

11、ey) ArrayListArrayList list2 = wenfa2.get(key);for (ArrayList arrayList : list2) / 判斷是否是終結(jié)符String str3 = arrayList.get(0);if (!wenfa2.containsKey(str3) tempList.add(str3); else / 遇到非終結(jié)符的就求該非終結(jié)符的能推出的終結(jié)符的集合getFirst(tempList, str3);模塊4Follow集的詳細(xì)設(shè)計實(shí)現(xiàn)代碼：public void getFollow(ArrayList tempList, String ke

12、y) / 迭代wenfa2的valuefor (EntryString, ArrayListArrayList entry : wenfa2.entrySet() ArrayListArrayList arrayList = entry.getValue();for (ArrayList arrayList2 : arrayList) int index = arrayList2.indexOf(key);/ System.out.println(.+index);if (index = -1) continue;String str = entry.getKey();addFollow(in

13、dex, str, key, arrayList2, tempList);/ continue;模塊5預(yù)測分析表的構(gòu)建檢測該文法是否是LL(1)文法，如果是則將其預(yù)測分析表顯示出來，如果不是則將具有二義性的表達(dá)式顯示出來。LL(1)分析表的作用是對當(dāng)前非終極符和輸入符號確定應(yīng)該選擇用哪個產(chǎn)生式進(jìn)行推導(dǎo)。它的行對應(yīng)文法的非終極符，列對應(yīng)終極符，表中的值有兩種：一是產(chǎn)生式的右部的字符串，一是null。若用M表示LL(1)分析表，則M可表示如下：M: VNVTPErrorM(A, t) = A，當(dāng)tselect(A) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。主要代碼：priv

14、ate void creatTable() table = new HashMapString, HashMapString, ArrayList();for (Map.EntryString, ArrayList entry : first.entrySet() String key = entry.getKey();/ 非終結(jié)符HashMapString, ArrayList hashMap = new HashMapString, ArrayList();for (String firstKey : entry.getValue() / first集合中含有,將follow集合中的終結(jié)符

15、添加分析表中if (firstKey.equals() ArrayList arrayList = new ArrayList();arrayList.add();for (String followKey : follow.get(key) hashMap.put(followKey, arrayList); else ArrayListArrayList wenfaList = wenfa2.get(key);Set leSet = wenfa2.keySet();if (wenfaList.size() = 1) hashMap.put(firstKey, wenfaList.get(0

16、); else for (ArrayList list : wenfaList) / System.out.println(first2.+list.get(0);if (list.get(0).equals(firstKey) hashMap.put(firstKey, list); else if (leSet.contains(wenfaList.get(0) ArrayList firstList = first.get(list.get(0);if (firstList.contains(firstKey) hashMap.put(firstKey, list);table.put(

17、key, hashMap);模塊6預(yù)測分析過程：輸入一條語句，檢測是否是當(dāng)前文法產(chǎn)生的語句，并給出分析過程。預(yù)測分析表的模型示意圖i*i+i# 輸入 XYZ#預(yù)測分析程序 棧 分析表a. 控制程序是依據(jù)分析表和分析棧聯(lián)合控制輸入字符串的識別和分析，它在何時候都是依據(jù)當(dāng)前分析棧的棧頂符號和當(dāng)前輸入字符來執(zhí)行控制功能。對不同文法，控制程序是相同的。b. 輸入緩沖器用來存放被分析的符號串，符號串后跟以標(biāo)志符號#。c. 棧中存放一系列文法符號，符號#存在于棧的底部，分析開始時，棧底先放好#，然后放進(jìn)文法開始符號。d. 分析表是一個二維數(shù)組MA,a，其中A是非終結(jié)符號，a是終結(jié)符號或是符號#，MA,a內(nèi)

18、容為一條關(guān)于A的產(chǎn)生式或出錯標(biāo)志，不同語言使用內(nèi)容不同的分析表。e. 輸出流是在分析中不斷產(chǎn)生的輸出序列。主要實(shí)現(xiàn)代碼：stack.GetLength()-1); /得到棧頂元素public void analyze(String runText) /清空consoleTaconsoleTa.setText();/ 初始化分析棧analStack = new MyStack();analStack.push($);analStack.push(beletter); inStack = new MyStack(); inStack.push($);char chs=runText.toCharA

19、rray();for (int i = chs.length-1; i = 0; i-) / 數(shù)據(jù)壓棧inStack.push(String.valueOf(chsi); consoleTa.append(步驟t + 棧 tt + 輸入 tt + 輸出n);consoleTa.append(1t + analStack.myToStrng(analFlag) + tt+ inStack.myToStrng(inlFlag)+n);String analStr = null;String inStr = null;a: while (!(analStr = analStack.getNext()

20、.equals($)| !(inStr = inStack.getNext().equals($) if (analStr.equals(inStr) analStack.pop();inStack.pop();printProcess(匹配： + inStr); else HashMapString, ArrayList analMap= table.get(analStr);/HashMap map = hashTable.get(analStr);if (analMap = null) consoleTa.append(t + inStr + 無法匹配,去掉該字符n);if (!inSt

21、r.equals($) inStack.pop();flag = false;continue; else break;ArrayList tableStr=analMap.get(inStr);/String tableStr = map.get(inStr);if(tableStr=null)tableStr=new ArrayList();/$代表無法匹配tableStr.add($); switch (tableStr.get(0) case $:consoleTa.append(t + inStr + 無法匹配，去掉該字符n);if (!inStr.equals($) inStack

22、.pop();flag = false;continue; else break a;case :analStack.pop();printProcess(analStr + - + tableStr);break;default:analStack.pop();/String strs = getInfoByTable(tableStr);for (int i=tableStr.size()-1;i=0;i-) analStack.push(tableStr.get(i);printProcess(analStr + - + tableStr);break;/ 下一次分析index+;if

23、(flag) consoleTa.append(根據(jù)LL(1)文法的分析,式子符合文法規(guī)范); else consoleTa.append(根據(jù)LL(1)文法的分析,式子不符合文法規(guī)范);實(shí)驗(yàn)結(jié)果截圖：(a)導(dǎo)入了一個不是LL（1）的文法，截圖如下:(b)導(dǎo)入LL(1)文法后，依次點(diǎn)擊按鈕進(jìn)行文法處理，得出相應(yīng)集合，并輸入句子i+i進(jìn)行分析，過程截圖如下所示：文法內(nèi)容：First集合：follow集合：預(yù)測分析表：輸入i+i分析棧的分析過程：課設(shè)總結(jié)：編譯原理是一門專業(yè)學(xué)科，對于現(xiàn)階段的我來說，只是掌握了它的一些基本原理和概念，對于一些更深層的知識還是有很多難以理解的地方。但在這次課程設(shè)計過程中，讓我對編譯原理有了更深的理解，同時也鍛煉了自己的思考能力，鍛煉了自己的動手編程能力，對于將知識的轉(zhuǎn)化有了很大的幫助。 本次課程設(shè)計的總體思路不是很難，加上前期課程實(shí)驗(yàn)有做過最后的一部分分析過程的實(shí)現(xiàn)減輕了一點(diǎn)難度，在消除左遞歸、求FIRST和FOLLOW集合的時候還好，但是在判斷文法是不是LL（1）文法的時候卡殼了，不知道如可處理。最后通過百度，發(fā)現(xiàn)他們通過一個SELECT集合把判斷LL（1）文法的三個要求全加進(jìn)去解決。在吸收其精華的基礎(chǔ)上，自己做了些改進(jìn)，最終將程序調(diào)出來了。 關(guān)于界面，