【正文】 and Implementation of A Syntax Analyzer based on Compilation Theory Abstract The piler generally is made up of the lexical analyzer program, the syntax analysis program, the semantics analysis program, the interlanguage production procedure, the goal code production procedure, the code optimization procedure, the form executive program and the procedure of disposing mistakes. In the teaching process of piler principle, all algorithm explanation needs to be explain clearly, including algorithm condition judgment, grammar analytical table structure process, grammar analytical table concrete production, in view of grammar sentence analysis process and so on. These processes often take much time to analyze, the scheduling and so on. This program mainly work is to plete the algorithm which take advantage of the procedure to deal with those above mentioned processes , in order to save time. The paper aims at introducing a syntax analytical method named LL(1) algorithm which from the up to down. The syntax analyzer analyzes the character string beginning from the left to right one word each time and educes the most left deduction of the sentence in the analyze course.. Key words: piler。 在編譯原理的教學過程中，算法的講解都需要對算法進行詳細的分析，包括算法條件的判斷，文法分析表的構造過程，文法分析表的具體生成，針對文法的句子的分析過程等， 這些過程往往需要占用大量時間來分析、制表等。本軟件的主要任務就是利用程序來完成算法的上述相關過程，以達到高效，直觀的效果。 grammar analysis。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序 、中間代碼生成程序、目標代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯處理程序等成分構成。本軟件的主要任務就是利用程序來完成算法的上述相關過程，節(jié)約教學時間。由若干條規(guī)則組成。運用符號“ |”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊。 終結符 ：文法中凡不屬于非終結符集的符號，它們組成的集合稱為終結符集。 First 集 ：首符號集。 自頂向下分析 對于文法 G[Z]，給頂一個待分析的句子 (字符串 )，自頂向下分析的基本思想是從識別符號 Z 開始，根據文法試著建立一個推導序列，若得到所給的句子，則句子得到識別，表明其結構符合文法，如果經過各種推導都不能得到所分析的句子，則該符號串不符合文法。 方法： 首先對文法的每個規(guī)則 A::=? 求可選集 Select(A::=?)。 Select(Z ::=bZ)=。試探法有可能形成回溯現(xiàn)象。 三種子程序的返回地址保護方法： 返回地址保護單元。同時入棧和出棧的還有相應的遞歸子程序中需要保護的工作單元。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導（規(guī)范推導），向前看 K 個符號，便能確定當前應選擇怎樣的規(guī)則。 (1)分 析方法的邏輯結構 第 I 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結構 (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導所使用的規(guī)則。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當棧頂符號與輸入串當前符號相匹配時，則從棧頂刪除該符號。首先進行介紹與 LL(1)分析有關的 3個操作約定： (1)N 表示繼續(xù)下一個符號； (2)P 表示重讀當前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 2 系統(tǒng)流程 圖 項目的程序流程圖如圖 3所示： 圖 3 程序流程圖 程序開始 調用打開對話框輸入文法 優(yōu)化輸入的文法并判斷文法合法性 獲取文法的終結符和非終結符 對文法求 select 集并判斷 select 集合法性 構造文法分析表 輸入并分析句子 結束 第 III 頁 共 22 頁 系統(tǒng)模塊流程圖 系統(tǒng)的模塊流程圖如圖 4所示 ： 圖 4 系統(tǒng)模塊流程圖 3 系統(tǒng)實施 《 一個編譯原理語法分析器的設計與實現(xiàn)》 主要分為四個模塊： 1．文件讀取模塊 文件讀取模塊主要完成將記事本中的待分析文法讀入到內存中的功能。 LL(1)算法 演示系統(tǒng) 文法輸入 文法分析 句子輸入 與分析 文法分析表 構造 獲取終結符和非終結符 求文法的 select 集 判斷 select 集的合法性 求 first 集 求 follow 集 第 IV 頁 共 22 頁 3．分析表構造模塊 分析表構造模塊的主要功能是將算法分析模塊所求解出的符合 LL（ 1）算法規(guī)則的文法的 select 集轉化成文法分析表，以便下一模塊的調用。 本模塊通過調用 VB 中 CommonDialog 控件的 ShowOpen 方法啟動打開文件對話框，獲取需要讀取的文件的路徑，再調 用 Open 命令打開文件，將文件中保存的文法讀入內存，用二維數組進行保存。 用 ShowOpen 方法顯示對話框 p_name = 39。 Do While WF(j, 0) Empty 39。 終結符的個數 Public nz As Integer 39。 終結符集 Public NZJ(250) As String 39。判斷第 a 條規(guī)則右邊的首符號是否是終結符 For p = 0 To fo 39。判斷 WF(i,j+1)在 F()中是否已經存在 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。形如 FXB（ y， x， z），其中， y 表示分析表的第 y 行， x表示第 x列， z表示第 y行第 x 列所對應的格子中的第 z個數據。 當 ? 為 ? 時，即： 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 對話框讀入待分析句子，并與分析表進行對照，逐步分析所輸入的句子是否符合文法。存放句子分析過程中的輸入符號棧 讀取句子 Public Sub juzi_read(str As String) 39。即使是人工求解，也經常出現(xiàn)錯誤，以至影響最終的結果。當控件中某一行的數據超過 ListBox 的寬度時，數據會顯示不完整。H194 SendMessage , LB_SETHORIZONTALEXTENT, i, 0 其中， List1 為 ListBox 的名稱 ； i為水平滾動條的寬度， 單位是 pixel(像素 )。 第 XIII 頁 共 22 頁 圖 8 Open對話框 文法原形如圖 9所示： 圖 9 輸入的文法 對其進行分析，結果如圖 10 所示： 第 XIV 頁 共 22 頁 圖 10 文法分析結果 隨后即可得到文法的分析表（圖 11），并以此為依據，對輸入的句子進行分析（圖 12）。 通過 《 一個編譯原理語法分析器的設計與實現(xiàn) 》 的使用，希望在提高教學質量的同時，也能對同學們在編譯原理的學習中起到幫助，讓大家更好的了解 LL（ 1）算法的整個過程。 [4] 楊克玉 . [M].北京：機械工業(yè)出版社出版， 。 第 XVII 頁 共 22 頁 致 謝 本文是在 韓斌 老師的熱情關心和指導下完成的，他淵博的知識和嚴謹的治學作風使我受益匪淺，對順利完成本課題起到了極大的作用。 關于學位論文使用權和研究成果知識產權的說明： 本人完全 了解成都信息工程學院有關保管使用學位論文的規(guī)定，其中包括： （ 1）學校有權保管并向有關部門遞交學位論文的原件與復印件。 （ 5）學校可以公布學位論文的全部或部分內容（保密學位論文在解密后遵守此規(guī)定）。本軟件的主要任務就是利用程序來完成算法的上述相關過程，以達到高效，直觀的效果。 grammar analysis。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標代碼生成程 序、代碼優(yōu)化程序、表格管理程序和出錯處理程序等成分構成。本軟件的主要任務就是利用程序來完成算法的上述相關過程，節(jié)約教學時間。由若干條規(guī)則組成。運用符號“ |”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊。 終結符 ：文法中凡不屬于非終結符集的符號，它們組成的集合稱為終結符集。 First 集 ：首符號集。 自頂向下分析 對于文法 G[Z]，給頂一個待分析的句子 (字符串 )，自頂向下分析的基本思想是從識別符號 Z 開始，根據文法試著建立一個推導序列，若得到所給的句子，則句子得到識別，表明其結構符合文法，如果經過各種推導都不能得到所分析的句子，則該符號串不符合文法。 方法： 首先對文法的每個規(guī)則 A::=? 求可選集 Select(A::=?)。 Select(Z ::=bZ)=。試探法有可能形成回溯現(xiàn)象。 三種子程序的返回地址保護方法： 返回地址保護單元。同時入棧和出棧的還有相應的遞歸子程序中需要保護的工作單元。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導（規(guī)范推導），向前看 K 個符號，便能確定當前應選擇怎樣的規(guī)則。 (1)分析方法的邏輯結構 第 5 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結構 (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導所使用的規(guī)則。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當棧頂符號與輸入串當前符號相匹配時，則從棧頂刪除該符號。首先進行介紹與 LL(1)分析有關的 3個操作約定： (1)N 表示繼續(xù)下一個符號； (2)P 表示重讀當前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 (1)分析表的構造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關系。 (2)當 x1?Vt 時，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪去x1和 y1，然后繼續(xù)向前分析；不 相同表示不相配，為出錯。