LL(1)文法分析參考模板

1、1 / 24編譯原理課程設(shè)計報告編譯原理課程設(shè)計報告選題名稱選題名稱: LL(1)語法分析 系（院）系（院）: 計 算 機 工 程 系專專 業(yè)業(yè): 計算機科學(xué)與技術(shù)學(xué)年學(xué)期學(xué)年學(xué)期: 2010 2011 學(xué)年 第 1 學(xué)期2010年 12 月 30 日設(shè)計任務(wù)書設(shè)計任務(wù)書課題課題名稱名稱LL(1)語法分析設(shè)計設(shè)計目的目的LL(1)分析法的基本思想是：自頂向下分析時從左向右掃描輸入串，分析過程中將采用最左推導(dǎo)，并且只需向右看一個符號就可決定如何推導(dǎo)。通過對給定的文法構(gòu)造預(yù)測分析表和實現(xiàn)某個符號串的分析，掌握 LL(1)分析法的基本思想和實現(xiàn)過程。實驗實驗環(huán)境環(huán)境1. 微型電子計算機（PC）2.

2、Windows XP 操作系統(tǒng)，Visual C+6.0 開發(fā)工具任務(wù)任務(wù)要求要求1. 錄入合法的 LL(1)文法2. 構(gòu)造并輸出預(yù)測分析表3. 對輸入的符號串進行語法分析工作進度計劃工作進度計劃序號序號起止日期起止日期工工 作作 內(nèi)內(nèi) 容容110.12.27-10.12.27選定題目，明確題目要求210.12.28-10.12.28課題深入調(diào)研、細(xì)化工作，系統(tǒng)方案設(shè)計310.12.29-10.12.29程序錄入、調(diào)試、整合410.12.30-10.12.31上機演示，課程設(shè)計分組答辯，完成課程設(shè)計報告指導(dǎo)教師（簽章）：指導(dǎo)教師（簽章）： 年年 月月 日日 摘要： 語法分析是編譯程序的核心部分

3、。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定的文法的正確句子。目前語法分析常用的方法右自頂向下分析和自底向上分析兩大類。確定的自頂向下方法，是從文法的開始符號，考慮如何根據(jù)當(dāng)前的輸入符號（單詞）唯一的確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo)。 LL(1)文法是一種確定的自頂向下的分析方法。LL(1)分析法的功能是利用 LL(1)控制程序根據(jù)顯示棧頂內(nèi)容、向前看符號以及 LL(1)分析表，對輸入符號串自上而下的分析過程。可通過消除左遞歸、提取左因子把非 LL(1)文法改造成 LL(1)文法。當(dāng)文法滿足條件后，分別構(gòu)造出文法的每個非終結(jié)符的 FIRST、FOLLOW 集合和 SE

4、LECT 集，根據(jù) SELECT 集合判斷是否是 LL(1)文法。在 LL(1)預(yù)測分析程序設(shè)計過程中，最重要的兩個問題是預(yù)測分析表的構(gòu)造和相關(guān)數(shù)據(jù)結(jié)構(gòu)的設(shè)計。而預(yù)測分析表的構(gòu)造首先必須計算文法每個非終結(jié)符的 FIRST 集和 FOLLOW 集。要知道一串符號是不是該文法的一個句子，只要判斷是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串。語法分析可以分為兩類，一類是自上而下的分析法，一類是自下而上的分析法。自上而下的主旨是，對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下的為輸入串建立一棵語法樹。或者說，為輸入串尋找一個最左推倒，這種分析過程的本質(zhì)是一種試探過程，是反復(fù)使用不同產(chǎn)生

5、式謀求匹配輸入串的過程我主要是自上而下的過程。關(guān)鍵詞：語法分析；LL(1)分析；FIRST 集合；FOLLOW 集合；自上而下分析 目錄目錄1 課題綜述課題綜述.11.1 課題來源和意義.11.2 預(yù)期目標(biāo).11.3 解決問題.12 系統(tǒng)分析系統(tǒng)分析.12.1 涉及的知識基礎(chǔ).12.1.1 LL(1)文法.12.1.2 確定的自頂向下分析思想.2.2.1.3 左遞歸的消除.32.1.4 消除回溯、提左因子42.1.5 計算FIRST集合、FOLLOW集合和SELECT集合.42.2 解決問題的基本思路.52.3 功能模塊框圖.53 系統(tǒng)設(shè)計系統(tǒng)設(shè)計.53.1 LL(1)文法輸入設(shè)計.63.2

6、LL(1)語法分析詳細(xì)流程圖.63.3 算法描述73.3.1 消除左遞歸的算法.73.4 系統(tǒng)流程圖.84 代碼編寫.9 4.1 相關(guān)代碼.94.4 運行結(jié)果.12總總 結(jié)結(jié) .14致致 謝謝 .15參參 考考 文文 獻獻.161 課題綜述課題綜述編譯原理的設(shè)計一般都是從文法和語言的基礎(chǔ)知識開始，沿著詞法分析、語法分析、語義分析、語法翻譯、中間代碼生成及符號表組織序列進行。本課題的總體設(shè)計完全依據(jù)編譯原理的教學(xué)內(nèi)容，即上下文無關(guān)文法基礎(chǔ)及詞法分析、語法分析技術(shù)研究、語法推導(dǎo)的語義翻譯、代碼優(yōu)化及目標(biāo)代碼生成。但是在本課題中只涉及到了關(guān)于文法分析的相關(guān)知識。1.1 課題來源課題來源和意義和意義L

7、L（1）文法是一種簡單易行的，自頂向下的，且較易實現(xiàn)的文法。它的原理在編譯原理的書上已有詳細(xì)敘述，本文著重于介紹其實現(xiàn)過程中的一些細(xì)節(jié)及思考。LL(1)表明自頂向下分析技術(shù)是從左向右掃描輸入串，分析過程中將用最左推導(dǎo)，以及只需向右看一個符號便可決定如何推導(dǎo)的一種文法。首先必須判斷所給文法是否是 LL(1)文法，然后編寫構(gòu)造 LL(1)語法分析程序。因而對任給文法需計算FIRST、FOLLOW、SELECT 集合，進而判別文法是否為 LL(1)文法。設(shè)計中實現(xiàn)語法分析使用的語言是 C+，使程序能達(dá)到上述目標(biāo)。1.2 預(yù)期目標(biāo)預(yù)期目標(biāo)熟練掌握運用 VC+建立工程，并用 VC+語言進行程序編寫，掌握

8、編程思想和算法。熟練掌握 LL(1) 文法的分析方法，利用 FIRST 集合、FOLLOW 集合以及SELECT 集合得到預(yù)測分析表，并且各集合的計算方法也是設(shè)計的目標(biāo)。1.3 解決解決問題問題(1)對于一個輸入文法，消除文法的左遞歸；(2)理解計算 FIRST、FOLLOW 集合和 SELECT 集合的方法；(3)理解文法分析表的構(gòu)造。2 2 系統(tǒng)分析系統(tǒng)分析 2.1 涉及的知識基礎(chǔ)涉及的知識基礎(chǔ)2.1.1 LL(1)文法LL(1)文法是一類可以進行確定的自頂向下語法分析的文法。一個用來描述語言語法結(jié)構(gòu)的文法G2可形式地定義如下：一個文法GS可表示成形如(VN，VT，P，S)的四元式。其中V

9、N，VT，P均為非空的有限集，分別稱為非終結(jié)符集、終結(jié)符集和產(chǎn)生式集。具體來說：VN，一系列需要定義的語法范疇。VT，若干基本符號，不需要進一步定義。P，用“-“連接起來的有序?qū)?A,)的集合，稱為規(guī)則，也叫產(chǎn)生式。其中A是一個非終結(jié)符，是一個由終結(jié)符或非終結(jié)符組成的符號串，即(VNVT)*。S， 是文法的開始符號。SVN此外 ，我們還將出現(xiàn)在產(chǎn)生式左、右側(cè)的全部符號的集合稱為詞匯表，記為V。顯然：V=VNVT；VNVT =。更確切地說，上面給出的是上下文無關(guān)文法的定義。這是因為由符號串a(chǎn)去替換A時，并不考慮A所處的環(huán)境，即與A的上下文無關(guān)。除非另做說明，我們以后所說的文法均指上下文無關(guān)文法。

10、LL(1)的含義：第一個 L 表示從左至右掃描輸入符號串第二個 L 表示生成輸入串的一個最左推導(dǎo)1 表示在決定分析程序的每步動作時，向前看一個符號2.1.2 確定的自頂向下分析思想LL(1)文法是一類可以進行確定的自頂而下語法分析的文法。而自頂而下分析法的基本思想是從文法的開始符號出發(fā)采用最左推導(dǎo)，根據(jù)當(dāng)前的輸入符號(單詞符號)惟一地確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符以下推導(dǎo)。這種分析過程實質(zhì)是一種試探過程，是反復(fù)使用不同產(chǎn)生式匹配輸入符號串的過程。若有文法：S-cAdA-ab|a輸入串W=cad。為建立分析樹，首先建立只有標(biāo)記S單個結(jié)點樹，輸入指針指向W的第一個符號c。然后用S的第一個產(chǎn)生式

11、來擴展該樹，得到的樹如圖2.1所示：ScAdScAdSabScAda(a)(b)(c)圖2.1.1語法分析樹最左邊的葉子標(biāo)記為c，匹配W的第一個符號。于是，推進輸入指針到W的第二個符號a，并考慮下一個標(biāo)記為A的葉子。用A的第一個選擇來擴展A，得到如圖(b)的樹。現(xiàn)在匹配第二個輸入符號a，再推進輸入指針到d，把它和下一個標(biāo)記為b的葉子比較。因為b和d不匹配，報告失敗，回到A，看它是否還有別的選擇尚未嘗試。在回到A時，必須重置指針于第二個符號，即第一次進入A的位置。現(xiàn)在嘗試A的第二個選擇，得到圖(c)的分析樹。葉子a匹配W的第二個符號，葉子d匹配W的第三個符號。這樣，產(chǎn)生了W的分析樹，從而宣告分析

12、完全成功。2.1.3 左遞歸的消除直接消除產(chǎn)生式中的左遞歸是比較容易的。假定關(guān)于非終結(jié)符P的規(guī)則為P-Pa|b其中，P是開頭。那么我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式：P-bRR-aR| (為空字)這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。一般而言，假定P關(guān)于的全部產(chǎn)生式是P-P1|P2|Pm|1| 2|n其中，每個i(1im)都不等于，1n都不以P開頭，那么消除P的直接左遞歸就是把這些規(guī)則改寫成： P-1R| 2R| nR R-1R|2R|mR|使用這個方法，我們?nèi)菀装岩娭T于表面的所有直接左遞歸都消除掉，也就是說，把直接左遞歸都改成直接右遞歸。對于間接左遞歸

13、的消除需先通過產(chǎn)生式非終結(jié)符置換，把間接左遞歸變成直接左遞歸。例如有文法：S-A| (1) A-S (2)因為S=A=S，所以S是一個間接遞歸的非終結(jié)符。為了消除這種間接左遞歸將(2)式代人(1)式，即可得到與原方法等價的方法: S-S| (3)(3)式是直接左遞歸的，可以采用消除直接左遞歸的方法對文法進行改寫，可的文法：S-S S-S|由此可見，為了消除間接左遞歸，可首先查出那些具有左遞歸的非終結(jié)符號，然后對以這些非終結(jié)符為左部的產(chǎn)生式，通過逐步置換有關(guān)產(chǎn)生式的方法將它們化為直接左遞歸的產(chǎn)生式。最后在消除其中的全部直接左遞歸。2.1.4 消除回溯、提左因子 為了消除回溯就必須保證：對文法的任

14、何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個侯選去執(zhí)行任務(wù)，并且次侯選的工作結(jié)果是確信無疑的。也就是說，若此侯選獲得成功匹配，那么，這種匹配不會是虛假的；若此侯選無法完成任務(wù)，則任何其它侯選也肯定也無法完成任務(wù)。換句話說，假定現(xiàn)在輪到非終結(jié)符 A 去執(zhí)行匹配任務(wù)，A 共有 n 個侯選 1，2，n,即 A-1|2|n。A 能夠根據(jù)不同的輸入符號指派相應(yīng)的 i 作為全權(quán)代表去執(zhí)行任務(wù)，那就肯定無需回溯了。在這里 A 已不再是讓某個侯選去試探地執(zhí)行任務(wù)，而是根據(jù)所面臨的輸入符號 準(zhǔn)確地指派唯一的一個侯選。其次，被指派侯選的工作成敗也完全代表了 A。2.1.52.1.

15、5 計算計算FIRSTFIRST集合、集合、FOLLOWFOLLOW集合和集合和SELECTSELECT集合集合FIRST集合：令GS=(VT,VN,S,P),則 FIRST()= a | * a,aVT ,、V*、若 * ，則FIRST()對每以文法符號X，計算FIRST(X)過程如下： (a)若XVT ,則FIRST(X)=X；(b)若XVN,且有產(chǎn)生式Xa,aVT,則把a加入到FIRST(X)中；(c)若XVN ,若X也是一條產(chǎn)生式,則把也加到FIRST(X)中；(d)若XVN,有產(chǎn)生式XY1Y2Yn,Y1,Yi都是非終結(jié)符，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有，則把FIRS

16、T(Yj)中的所有非元素都加到FIRST(X)中； FIRST(Yi)的元素加入到FIRST(X)特別地，若所有的FIRST(Yj , j=1,2,n)均含有,則把 ,FIRST(Yj)中的所有非元素都加到FRIST(X)中。FOLLOW集合：設(shè)GS=(VT,VN,S,P)是上下文無關(guān)文法, (a)設(shè)S為開始符號,則#FOLLOW(S)(b)若有產(chǎn)生式A B， * 則FIRST()FOLLOW(B)(C)若 (可理解為A B)則FIRST()-FOLLOW(A) FOLLOW(B)SELECT集合：A 的可選集SELECT ，則SELECT(A)=FIRST()，則SELECT(A)=(FIR

17、ST()-) FOLLOW(A)2.22.2 解決問題的基本思路解決問題的基本思路首先根據(jù)一定的規(guī)則輸入一個合法的文法，化簡成LL(1)文法，利用一定的算法消除文法中的左遞歸，然后再利用首先預(yù)定的規(guī)則計算出FIRST和FOLLOW集合，以及算出SELECT集合，然后就是顯示出LL(1)文法的分析表。最后一步是輸入一串字符串，然后對字符串進行分析，輸出分析過程表，這樣系統(tǒng)就成形了。2.32.3 功能模塊框圖功能模塊框圖初始數(shù)據(jù)產(chǎn)生式處理計算機 FOLLOW 集合顯示預(yù)測分析表圖 2.3 功能模塊框圖輸入文法3 系統(tǒng)設(shè)計系統(tǒng)設(shè)計語法分析是編譯過程的核心部分。他的任務(wù)是在詞法分析識別單詞符號串的基礎(chǔ)

18、上，分析并判斷程序的的語法結(jié)構(gòu)是否符合語法規(guī)則。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。因此語法分析器的工作的本質(zhì)上就是按文法的產(chǎn)生式，識別輸入符號串是否為一個句子。對于一個文法，當(dāng)給你一串符號是，如何知道它是不是該文法的一個句子，這是這個課程設(shè)計所要解決的一個問題。其實要知道一串符號是不是該文法的一個句子，只要判斷是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串。語法分析可以分為兩類，一類是自上而下的分析法，一類是自下而上的分析法。自上而下的主旨是，對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下的為輸入串建立一棵語法樹?；蛘哒f，為輸入串尋找一個最左推倒，這種分析過程的本質(zhì)是一種試

19、探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程我主要是自上而下的過程。3.13.1 LL(1)LL(1)文法輸入設(shè)計文法輸入設(shè)計標(biāo)準(zhǔn)的文法有一定的規(guī)則，若在設(shè)計過程中，輸入的文法不正確，則不能正確的實現(xiàn)程序功能，所以首先在編寫程序時，要對輸入文法進行限制，規(guī)則如下：(1) 大寫英文字母表示非終結(jié)符，所以產(chǎn)生式左部一定要輸入大寫字母；(2) e表示空產(chǎn)生式；(3) 除大寫字母、#、| 外的單字符表示終結(jié)符，所以產(chǎn)生右部不能包括以上幾個字符；(4) 不能出現(xiàn)遞歸文法。(如 S-S或S-A, A-S;)；(5) 不能出現(xiàn)多余文法規(guī)則。(如 S-A，A不是非終結(jié)符)； (6) 文法產(chǎn)生式長度不超過1

20、0個字符。3.2.2 LL(1)LL(1)語法分析詳細(xì)流程圖語法分析詳細(xì)流程圖我們知道一個文法要能進行 LL（1）分析，那么這個文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個非終結(jié)符的 FIRST和 FOLLOW 集合，然后根據(jù) FIRST 和 FOLLOW 集合構(gòu)造 LL（1）分析表，最后利用分析表，根據(jù) LL(1)語法分析構(gòu)造一個分析器。LL（1）的語法分析程序包含了三個部分，總控程序，預(yù)測分析表函數(shù)，先進先出的語法分析棧，本程序也是采用了同樣的方法進行語法分析，其結(jié)構(gòu)圖如圖 3.2。開始操作讀源程序字符常數(shù)分析程序關(guān)鍵字標(biāo)識符分析程序其它單詞分析程序輸

21、出單詞內(nèi)部表示開始結(jié)束是字母?有字符?是數(shù)字?YYYNNN圖 3.2 LL(1)語法分析詳細(xì)流圖3.3 算法描述算法描述3.3.1 消除左遞歸的算法(1) 把文法G的所有非終結(jié)符按任一種順序排列成P1，P2,Pn;按此順序執(zhí)行； (2) FOR i:=1 TO n DOBEGIN FOR j:=1 TO i-1 DO 把形如Pi-Pj產(chǎn)生式變?yōu)镻j-1|2|k關(guān)于Pj的所有規(guī)則消除關(guān)于Pi規(guī)則的直接左遞歸性 END(3) 化簡由(2)所得的文法。即去除那些從開始符號出發(fā)永遠(yuǎn)也無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。3.4 系統(tǒng)流程圖系統(tǒng)流程圖整個程序可分為如下幾步：(1) 讀入文法；(2) 判斷正誤；(

22、3) 若無誤，判斷是否為 LL(1)文法；(4) 若是，構(gòu)造分析表；(5) 由總控算法判斷輸入符號串是否為該文法的句型。 開始 讀入文法 文法有效？是LL1文法？生成構(gòu)造分析表報錯判斷句型接受判斷字符Choose=y?結(jié)束ynyynn開始得到一非終結(jié)符chK=strlen(non_ter)有左遞歸？Temp=產(chǎn)生式右部(除首符)讀取文法rightcount=temprightcountm+1=ch;Temp=產(chǎn)生式右部rightcount=tempLeftcount=原左部Count +結(jié)束不含左遞歸的拆分ny 圖 3.4.1 程序主流程圖 圖 3.4.2 消除左遞歸流程圖4 代碼編寫代碼編寫

23、4.1 相關(guān)代碼相關(guān)代碼/* 分解含有左遞歸的產(chǎn)生式*/void recur(char *point)/*完整的產(chǎn)生式在 point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一個非終結(jié)符*/k=strlen(non_ter); /*非終結(jié)符號長度*/non_terk=ch;/得到最后一個非終結(jié)符號non_terk+1=0;for(j=0;j=strlen(point)-1;j+)if(pointn=point0) /*如果|后的首符號和左部相同，含直接左遞歸*/for(j=n+1;j=strlen(point)-1;j+) while(poin

24、tj!=|&pointj!=0) tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(pointj=|)n=j+1;break;else /*如果|后的首符號和左部不同*/leftcount=ch;rightcount0=;rightcount1=0;count+;for(j=n;j=strlen(point)-1;j+) if(pointj!=|) tempm+=pointj; else leftcount=point0; memcpy(r

25、ightcount,temp,m); rightcountm=ch; rightcountm+1=0;printf( count=%d ,count);m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1=0;count+; m=0;/* 分解不含有左遞歸的產(chǎn)生式*/void non_re(char *point) int m=0,j;char temp20;for(j=3;j=0;n-) Sp+=rightmn; Sq+strlen(rightm)=0; printf(符

26、號棧:%s 剩余字符串:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf( n);4.2 運行結(jié)果運行結(jié)果編譯調(diào)試，運行程序。輸入文法，如圖 4.2.1，按回車鍵得到分析結(jié)果，如圖4.2.2，判斷其是否為 LL(1)文法，并得到該文法的分析表；輸入該文法的句型，回車得到句型的預(yù)測分析過程，如圖 4.2.3，再次輸入不是該文法的句型，如圖 4.2.4圖 4.2.1圖 4.2.2圖 4.2.3圖 4.2.4 總總結(jié)結(jié)收獲：通過本次課程設(shè)計，我收獲了很多東西。首先對編譯原理這門課有了進一步的深刻理解，對 LL（1）文法分析的原理和過程有了進一步的鞏固，也鍛煉了我編程的能力，鞏固了平時所學(xué)的知識，真正做到了學(xué)以致用。體會：在做課程設(shè)計的過程中，發(fā)現(xiàn)自己在編寫程序過程中，總是會忽略各種細(xì)節(jié)，從而導(dǎo)致經(jīng)常修改一些很小的低級錯