【正文】 由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯處理程序等成分構(gòu)成。 （ 5）學?？梢怨紝W位論文的全部或部分內(nèi)容（保密學位論文在解密后遵守此規(guī)定）。 （ 3）學?？梢詫W術交流為目的復制、贈送和交換學位論文。 關于學位論文使用權(quán)和研究成果知識產(chǎn)權(quán)的說明： 本人完全 了解成都信息工程學院有關保管使用學位論文的規(guī)定，其中包括： （ 1）學校有權(quán)保管并向有關部門遞交學位論文的原件與復印件。文中除了特別加以標注地方外，不包含他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得成都信息工程學院或其他教學機構(gòu)的學位或證書而使用過的材料。 第 XVII 頁 共 22 頁 致 謝 本文是在 韓斌 老師的熱情關心和指導下完成的，他淵博的知識和嚴謹?shù)闹螌W作風使我受益匪淺，對順利完成本課題起到了極大的作用。 [6] 徐謖 .Visual Basic應用與開發(fā)案例教程 [M].北京：清華大學出版社， 。 [4] 楊克玉 . [M].北京：機械工業(yè)出版社出版， 。 [2] 康慕寧 .編譯原理 [M].西安：西北工業(yè)大學出版社出版， 2020。 通過 《 一個編譯原理語法分析器的設計與實現(xiàn) 》 的使用，希望在提高教學質(zhì)量的同時，也能對同學們在編譯原理的學習中起到幫助，讓大家更好的了解 LL（ 1）算法的整個過程。 尤其對于向前看集的算法實現(xiàn)，我覺得是最難的一部分，因為涉及到的情況太多，循環(huán)和選擇句型的嵌套使用如果不仔細分析就容易出現(xiàn)錯誤。 第 XIII 頁 共 22 頁 圖 8 Open對話框 文法原形如圖 9所示： 圖 9 輸入的文法 對其進行分析，結(jié)果如圖 10 所示： 第 XIV 頁 共 22 頁 圖 10 文法分析結(jié)果 隨后即可得到文法的分析表（圖 11），并以此為依據(jù)，對輸入的句子進行分析（圖 12）。 解決結(jié)果 運行后的結(jié)果如圖 7所示： 圖 7 ListBox的水平滾動條 5 結(jié)果測試 在系統(tǒng)開發(fā)完成后，對系統(tǒng)各個功能做了詳細的測試，對于正確的文法，系統(tǒng)能正常的演示整個文法分析的每一個過程；對于預設置的錯誤處理，系統(tǒng)也能給出正確的判斷，指出文法的錯誤類型。H194 SendMessage , LB_SETHORIZONTALEXTENT, i, 0 其中， List1 為 ListBox 的名稱 ； i為水平滾動條的寬度， 單位是 pixel(像素 )。 解決方案 利用 SendMessage 傳送 LB_SETHORIZONTALEXTENT 訊息給 ListBox，此一 第 XII 頁 共 22 頁 訊息的作用就是要求 ListBox 設定水平 滾動條。當控件中某一行的數(shù)據(jù)超過 ListBox 的寬度時，數(shù)據(jù)會顯示不完整。 解決方案 通過參照編譯原理中 first 集和 follow 集的具體求解步驟，通過多重循環(huán)的嵌套，完成了 select 集的求解過程，具體代碼請參照 節(jié)。即使是人工求解，也經(jīng)常出現(xiàn)錯誤，以至影響最終的結(jié)果。然后再把相應的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。存放句子分析過程中的輸入符號棧 讀取句子 Public Sub juzi_read(str As String) 39。 相關程序片段如下： 程序中所用到的公有數(shù)據(jù)成員有： Dim FXZ(50) As String 39。 當 ? 為 ? 時，即： A::=a，有： LL(A,a)=R(?)/N ::=Dβ規(guī)則 對于 A::=D?， (D?Vn)，且有 Select(A::=D?)={b1,b2,? ,bn} ， 則 LL(A,bi)=RD?)/P， (i=1,2,? ,n) **R(D?)/P：表示用 D? 的 (逆串替換 A后，重讀當前符號 ::=ε規(guī)則 對于 A::=?，且有 Select(A::=?)= {b1,b2,? ,bn} 則 LL(A, bi)=R(?)/P 本部分主要通過 VB 中的 InputBox 對話框讀入待分析句子，并與分析表進行對照，逐步分析所輸入的句子是否符合文法。如圖 5。形如 FXB（ y， x， z），其中， y 表示分析表的第 y 行， x表示第 x列， z表示第 y行第 x 列所對應的格子中的第 z個數(shù)據(jù)。判斷 WF(i,j+1)在 F()中是否已經(jīng)存在 If WF(i, j + 1) = F(p) Then b = 1 Exit For End If Next p If b = 1 Then b = 0 Else F(fo) = WF(i, j + 1) fo = fo + 1 F(fo) = Empty End If c = 1 Exit For 第 VIII 頁 共 22 頁 End If Next m If c = 1 Then c = 0 Else For n = 0 To hs 39。判斷 WF(i,j+1)在 F()中是否已經(jīng)存在 If F(p) = Then b = 1 Exit For 第 VII 頁 共 22 頁 End If Next p If b = 1 Then b = 0 Else F(fo) = fo = fo + 1 F(fo) = Empty End If End If For i = 0 To hs j = 1 Do While WF(i, j) Empty If WF(a, 0) = WF(i, j) Then If WF(i, j + 1) = Empty And a i Then Call follow(i, fo) Else For m = 0 To zj 39。 c = 0: b = 0 If WF(a, 0) = WF(0, 0) Then 39。判斷第 a 條規(guī)則右邊的首符號是否是終結(jié)符 For p = 0 To fo 39。ε為空字符串 Call follow(a, fo) i = 0 Do While F(i) Empty SLT(a, i) = F(i) F(i) = Empty i = i + 1 SLT(a, i) = Empty ??? ?? ??? 為空當 不為空當 F ol low (A ) )F irs t ( 第 VI 頁 共 22 頁 Loop Else Call first(a, fo) 求 first 集 首符號集既求解文法每條規(guī)則右邊的第一個符號并且必須 是終結(jié)符，因為文法使用數(shù)組存放，所以既求文法每行規(guī)則的第 2個字符既可；如果規(guī)則左邊第一個字符為非終結(jié)符，則通過循環(huán)對該非終結(jié)符再求首符號集。 終結(jié)符集 Public NZJ(250) As String 39。 select 集 Dim F(50) As String 39。 終結(jié)符的個數(shù) Public nz As Integer 39。程序中所用到的公有數(shù)據(jù)成員有： Public hs As Integer 39。 Do While WF(j, 0) Empty 39。一般含有左遞歸規(guī)則的文法形式為 U::=xUy， 若 x=?, 則有 U::=Uy，即為左遞歸規(guī)則 。 用 ShowOpen 方法顯示對話框 p_name = 39。調(diào)用打開文件對話框的具體代碼如下： Dim p_name As String 39。 本模塊通過調(diào)用 VB 中 CommonDialog 控件的 ShowOpen 方法啟動打開文件對話框，獲取需要讀取的文件的路徑，再調(diào) 用 Open 命令打開文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進行保存。其中句子合法性的判斷又分為句子中是否有文法終結(jié)符以外的符號和句子是否符合文法規(guī)則的判斷。 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)用。 2．算法分析模塊 算法分析模塊是《 一個編譯原理語法分析器的設計與實現(xiàn)》 中的關鍵模塊。 2 系統(tǒng)流程 圖 項目的程序流程圖如圖 3所示： 圖 3 程序流程圖 程序開始 調(diào)用打開對話框輸入文法 優(yōu)化輸入的文法并判斷文法合法性 獲取文法的終結(jié)符和非終結(jié)符 對文法求 select 集并判斷 select 集合法性 構(gòu)造文法分析表 輸入并分析句子 結(jié)束 第 III 頁 共 22 頁 系統(tǒng)模塊流程圖 系統(tǒng)的模塊流程圖如圖 4所示 ： 圖 4 系統(tǒng)模塊流程圖 3 系統(tǒng)實施 《 一個編譯原理語法分析器的設計與實現(xiàn)》 主要分為四個模塊： 1．文件讀取模塊 文件讀取模塊主要完成將記事本中的待分析文法讀入到內(nèi)存中的功能。 當 ? 為 ? 時，即： 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后，重讀當前符號 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é)束，輸入串得到識別。首先進行介紹與 LL(1)分析有關的 3個操作約定： (1)N 表示繼續(xù)下一個符號； (2)P 表示重讀當前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關系。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當棧頂符號與輸入串當前符號相匹配時，則從棧頂刪除該符號。 (2)當 x1?Vt 時，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪 去x1和 y1，然后繼續(xù)向前分析；不相同表示不相配，為出錯。 (1)分 析方法的邏輯結(jié)構(gòu) 第 I 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結(jié)構(gòu) (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導所使用的規(guī)則。 LL（ 1）分析方法 （ 1）方法的思想：根據(jù)輸入串的當前輸入符號，確定用某規(guī)則進行推導，當推導的第一個符號與輸入串的當前符號匹配時，就把輸入串的下一個字符作為當前輸入字符，直到推導出輸入串。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導（規(guī)范推導），向前看 K 個符號，便能確定當前應選擇怎樣的規(guī)則。 (2)遞歸出口工作： ①恢復保護在棧頂中的工作單元的原來內(nèi)容，并上退保護棧； ②取保護在棧頂中的返回地址進行返回，并退保護棧。同時入棧和出棧的還有相應的遞歸子程序中需要保護的工作單元。 ，由于返回地址保護單元數(shù)目不明確，一般采用堆棧形式。 三種子程序的返回地址保護方法： 返回地址保護單元。 遞歸子程序 遞歸子程序方法： 這里講的遞歸子程序方法是一種自頂向下的編譯方法，其思想是通過對源程序的每個語法成分編制一個處理子程序，通過子程序調(diào)用來對源程序進行語法和 第 4 頁 共 22 頁 語義分析。試探法有可能形成回溯現(xiàn)象。 Select(V ::=x)={x}。 Select(Z