【正文】 ....................... XVI0 參考文獻(xiàn) .............................................................. XVI0 致 謝 ............................................................... XVII1 聲 明 .............................................................. XVIII2 第 1 頁 共 22 頁 1 引言 項目背景 編譯原理是計算機專業(yè)中最難的一門課程 ,在理論上它要求學(xué)生掌握有關(guān)形勢語言和自動機的抽象概念 ,在技術(shù)上要求學(xué)生能夠熟練地利用各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行編程。 句子的分析 ：句子的分析實際就是分析源程序中的語句是否符合 給定的文法。 字匯表 ：在文法中，由全部規(guī)則的左部和 右部中的所有符號組成的符號集。 Select 集 ：可選集。 若對于某非終止符號有 n條規(guī)則（即有 n 個候選式）的處理方法： 對于文法，有 A::=x1|x2|? |xn，其右部的 n個候選式的首 符號集均不相同 : 即 First(xi) ∩ First(xj)=? (i?j)，對于待分析的符號串，如果最左的非終結(jié)符號為 A，若其句子中對應(yīng)的下一個符號（當(dāng)前輸入符號）為 a，且有a?First(xk)，則選擇規(guī)則 A::=xk 來作為推導(dǎo)的候選式。 遞歸子程序 遞歸子程序方法： 這里講的遞歸子程序方法是一種自頂向下的編譯方法，其思想是通過對源程序的每個語法成分編制一個處理子程序，通過子程序調(diào)用來對源程序進(jìn)行語法和 第 4 頁 共 22 頁 語義分析。 (2)遞歸出口工作： ①恢復(fù)保護(hù)在棧頂中的工作單元的原來內(nèi)容，并上退保護(hù)棧； ②取保護(hù)在棧頂中的返回地址進(jìn)行返回，并退保護(hù)棧。 (2)當(dāng) x1?Vt 時，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪 去x1和 y1，然后繼續(xù)向前分析；不相同表示不相配，為出錯。 當(dāng) ? 為 ? 時，即： A::=a，有： LL(A,a)=R(?)/N A::=D?， (D?Vn)，且有 Select(A::=D?)={b1,b2,? ,bn} ， 則 LL(A,bi)=R(D?)/P， (i=1,2,? ,n) **R(D?)/P：表示用 D? 的逆串替換 A后，重讀當(dāng)前符號 A::=?，且有 Select(A::=?)= {b1,b2,? ,bn} 則 LL(A, bi)=R(?)/P a?Vt， a 不出現(xiàn)于規(guī)則右部的首部， 則令 LL(a,a)=R(?)/N ，令 LL(,)=acc 表示分析結(jié)束，輸入串得到識別。其中句子合法性的判斷又分為句子中是否有文法終結(jié)符以外的符號和句子是否符合文法規(guī)則的判斷。一般含有左遞歸規(guī)則的文法形式為 U::=xUy， 若 x=?, 則有 U::=Uy，即為左遞歸規(guī)則 。 select 集 Dim F(50) As String 39。 c = 0: b = 0 If WF(a, 0) = WF(0, 0) Then 39。如圖 5。然后再把相應(yīng)的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。 解決方案 利用 SendMessage 傳送 LB_SETHORIZONTALEXTENT 訊息給 ListBox，此一 第 XII 頁 共 22 頁 訊息的作用就是要求 ListBox 設(shè)定水平 滾動條。 尤其對于向前看集的算法實現(xiàn)，我覺得是最難的一部分，因為涉及到的情況太多，循環(huán)和選擇句型的嵌套使用如果不仔細(xì)分析就容易出現(xiàn)錯誤。 [6] 徐謖 .Visual Basic應(yīng)用與開發(fā)案例教程 [M].北京：清華大學(xué)出版社， 。 （ 3）學(xué)?？梢詫W(xué)術(shù)交流為目的復(fù)制、贈送和交換學(xué)位論文。所謂 LL(1)分析法是指語法分析是按自左至右的順序向前查看一個輸入字符串，并分析過程中產(chǎn)生句子的最左推導(dǎo) 。這些過程往往需要占用大量時間來分析、制表等。規(guī)則又稱為產(chǎn)生式。 遞歸定義 ：在定義某種事物時又用到其本身。 例：設(shè)有文法 G[N]和符號串 25 N N::=D|ND D::=0|1|2|?|9 根據(jù)文法有： N?ND?DD?2D?25； 因此我們說 25 符合此文法 圖 1 G[N]過程分析 自頂向下分析的難點及解決辦法： N D D 5 2 第 3 頁 共 22 頁 對于形如 :U::=x1|x2|? |xn 的規(guī)則 ,可能需 要對所有的規(guī)則都要試探。 Select(V ::=x)={x}。 ，由于返回地址保護(hù)單元數(shù)目不明確，一般采用堆棧形式。 LL（ 1）分析方法 （ 1）方法的思想：根據(jù)輸入串的當(dāng)前輸入符號，確定用某規(guī)則進(jìn)行推導(dǎo)，當(dāng)推導(dǎo)的第一個符號與輸入串的當(dāng)前符號匹配時，就把輸入串的下一個字符作為當(dāng)前輸入字符，直到推導(dǎo)出輸入串。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當(dāng)棧頂符號與輸入串當(dāng)前符號相匹配時，則從棧頂刪除該符號。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看 K 個符號，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。 三種子程序的返回地址保護(hù)方法： 返回地址保護(hù)單元。 Select(Z ::=bZ)=。 自頂向下分析 對于文法 G[Z]，給頂一個待分析的句子 (字符串 )，自頂向下分析的基本思想是從識別符號 Z 開始，根據(jù)文法試著建立一個推導(dǎo)序列，若得到所給的句子，則句子得到識別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過各種推導(dǎo)都不能得到所分析的句子，則該符號串不符合文法。 終結(jié)符 ：文法中凡不屬于非終結(jié)符集的符號，它們組成的集合稱為終結(jié)符集。由若干條規(guī)則組成。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標(biāo)代碼生成程 序、代碼優(yōu)化程序、表格管理程序和出錯處理程序等成分構(gòu)成。本軟件的主要任務(wù)就是利用程序來完成算法的上述相關(guān)過程，以達(dá)到高效，直觀的效果。 關(guān)于學(xué)位論文使用權(quán)和研究成果知識產(chǎn)權(quán)的說明： 本人完全 了解成都信息工程學(xué)院有關(guān)保管使用學(xué)位論文的規(guī)定，其中包括： （ 1）學(xué)校有權(quán)保管并向有關(guān)部門遞交學(xué)位論文的原件與復(fù)印件。 [4] 楊克玉 . [M].北京：機械工業(yè)出版社出版， 。 第 XIII 頁 共 22 頁 圖 8 Open對話框 文法原形如圖 9所示： 圖 9 輸入的文法 對其進(jìn)行分析，結(jié)果如圖 10 所示： 第 XIV 頁 共 22 頁 圖 10 文法分析結(jié)果 隨后即可得到文法的分析表（圖 11），并以此為依據(jù)，對輸入的句子進(jìn)行分析（圖 12）。當(dāng)控件中某一行的數(shù)據(jù)超過 ListBox 的寬度時，數(shù)據(jù)會顯示不完整。存放句子分析過程中的輸入符號棧 讀取句子 Public Sub juzi_read(str As String) 39。形如 FXB（ y， x， z），其中， y 表示分析表的第 y 行， x表示第 x列， z表示第 y行第 x 列所對應(yīng)的格子中的第 z個數(shù)據(jù)。判斷第 a 條規(guī)則右邊的首符號是否是終結(jié)符 For p = 0 To fo 39。 終結(jié)符的個數(shù) Public nz As Integer 39。 用 ShowOpen 方法顯示對話框 p_name = 39。 LL(1)算法 演示系統(tǒng) 文法輸入 文法分析 句子輸入 與分析 文法分析表 構(gòu)造 獲取終結(jié)符和非終結(jié)符 求文法的 select 集 判斷 select 集的合法性 求 first 集 求 follow 集 第 IV 頁 共 22 頁 3．分析表構(gòu)造模塊 分析表構(gòu)造模塊的主要功能是將算法分析模塊所求解出的符合 LL（ 1）算法規(guī)則的文法的 select 集轉(zhuǎn)化成文法分析表，以便下一模塊的調(diào)用。首先進(jìn)行介紹與 LL(1)分析有關(guān)的 3個操作約定： (1)N 表示繼續(xù)下一個符號； (2)P 表示重讀當(dāng)前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 (1)分 析方法的邏輯結(jié)構(gòu) 第 I 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結(jié)構(gòu) (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導(dǎo)所使用的規(guī)則。同時入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護(hù)的工作單元。試探法有可能形成回溯現(xiàn)象。 方法： 首先對文法的每個規(guī)則 A::=? 求可選集 Select(A::=?)。 First 集 ：首符號集。運用符號“ |”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊。本軟件的主要任務(wù)就是利用程序來完成算法的上述相關(guān)過程，節(jié)約教學(xué)時間。 grammar analysis。 在編譯原理的教學(xué)過程中，算法的講解都需要對算法進(jìn)行詳細(xì)的分析，包括算法條件的判斷，文法分析表的構(gòu)造過程，文法分析表的具體生成，針對文法的句子的分析過程等， 這些過程往往需要占用大量時間來分析、制表等。 編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一。 文法 ：對語言結(jié)構(gòu)的定義和描述，即在形式上用于描述和規(guī)定語言結(jié)構(gòu)。 非終結(jié)符 ：文法中出現(xiàn)在規(guī)則左部的符號，它們組成的集合稱為非終結(jié)符集。 LL（ 1）文法 ：對于文法 G（ S），其每 個非終結(jié)符的不同規(guī)則具有不相交的Select 集，則稱該文法為 LL（ 1）文法。 例：設(shè)有文法 G[Z]，和句子 bbabaax Z::=aV|bZ V::=baZ|x Select(Z ::=aV)={a}。 遞歸子程序及其調(diào)用： 常用的子程序的種類有 3 種： 簡單子程序， 嵌套子程序， 遞歸子程序。 LL（ K）分析方法 LL(K)分析方法是一種自頂向下的分析技術(shù)。 (3)若上述兩個字符串均為空，則表示全部匹配，輸入串被識別。 5種情況，則置出錯，分析表中用空白表示。下面將對以上四個模塊的具體實現(xiàn)技術(shù)、數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵程序片段進(jìn)行詳細(xì)的說明。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(shè)計時間所限，所以本軟件沒有這項功能，只是對直接左遞歸進(jìn)行錯誤判斷。 用與臨時存放 select 集中元素的數(shù)組 Public ZJF(50) As String 39。判斷是不是對文法起始符求 follow 集 For p = 0 To fo 39。 圖 5 分析表構(gòu)造流程 文法分析表 終結(jié)符 非終結(jié)符 文法可選集 未出現(xiàn)在對應(yīng)規(guī)則右部首部的終結(jié)符 放入分析表 X 軸 放入分析表 Y 軸 放入分析表 Y 軸 第 IX 頁 共 22 頁 ::=aβ 規(guī)則 對于 A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N **R(?)/N：表示用 ? 的逆串替換Ａ后，繼續(xù)讀入下一個符號。 Do While (i, j, k) Empty Select Case (i, j, k) Case acc Exit Sub Case ε FXZ(a) = Empty Case /N FHZ(b) = b = b + 1 a = a 1 Exit For Case /P a = a 1 Exit For