【正文】 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。 在編譯原理的教學(xué)過(guò)程中，算法的講解都需要對(duì)算法進(jìn)行詳細(xì)的分析，包括算法條件的判斷，文法分析表的構(gòu)造過(guò)程，文法分析表的具體生成，針對(duì)文法的句子的分析過(guò)程等， 這些過(guò)程往往需要占用大量時(shí)間來(lái)分析、制表等。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)過(guò)程，以達(dá)到高效，直觀的效果。 grammar analysis。編譯程序一般由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序 、中間代碼生成程序、目標(biāo)代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)過(guò)程，節(jié)約教學(xué)時(shí)間。由若干條規(guī)則組成。運(yùn)用符號(hào)“ |”把相同左部的規(guī)則縮寫(xiě)在一起，這樣顯得文法更為緊湊。 終結(jié)符 ：文法中凡不屬于非終結(jié)符集的符號(hào)，它們組成的集合稱(chēng)為終結(jié)符集。 First 集 ：首符號(hào)集。 自頂向下分析 對(duì)于文法 G[Z]，給頂一個(gè)待分析的句子 (字符串 )，自頂向下分析的基本思想是從識(shí)別符號(hào) Z 開(kāi)始，根據(jù)文法試著建立一個(gè)推導(dǎo)序列，若得到所給的句子，則句子得到識(shí)別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過(guò)各種推導(dǎo)都不能得到所分析的句子，則該符號(hào)串不符合文法。 方法： 首先對(duì)文法的每個(gè)規(guī)則 A::=? 求可選集 Select(A::=?)。 Select(Z ::=bZ)=。試探法有可能形成回溯現(xiàn)象。 三種子程序的返回地址保護(hù)方法： 返回地址保護(hù)單元。同時(shí)入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護(hù)的工作單元。這種分析方法從左到右掃描源程序（輸入串），同時(shí)從識(shí)別符號(hào)開(kāi)始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看 K 個(gè)符號(hào)，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。 (1)分 析方法的邏輯結(jié)構(gòu) 第 I 頁(yè) 共 22 頁(yè) 圖 2 LL(1)分析方法的邏輯結(jié)構(gòu) (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導(dǎo)所使用的規(guī)則。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。首先進(jìn)行介紹與 LL(1)分析有關(guān)的 3個(gè)操作約定： (1)N 表示繼續(xù)下一個(gè)符號(hào)； (2)P 表示重讀當(dāng)前符號(hào)，也即不讀入下一符號(hào)； (3)R(?)表示用 ? 的逆串替換棧頂符號(hào)。 2 系統(tǒng)流程 圖 項(xiàng)目的程序流程圖如圖 3所示： 圖 3 程序流程圖 程序開(kāi)始 調(diào)用打開(kāi)對(duì)話(huà)框輸入文法 優(yōu)化輸入的文法并判斷文法合法性 獲取文法的終結(jié)符和非終結(jié)符 對(duì)文法求 select 集并判斷 select 集合法性 構(gòu)造文法分析表 輸入并分析句子 結(jié)束 第 III 頁(yè) 共 22 頁(yè) 系統(tǒng)模塊流程圖 系統(tǒng)的模塊流程圖如圖 4所示 ： 圖 4 系統(tǒng)模塊流程圖 3 系統(tǒng)實(shí)施 《 一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)》 主要分為四個(gè)模塊： 1．文件讀取模塊 文件讀取模塊主要完成將記事本中的待分析文法讀入到內(nèi)存中的功能。 LL(1)算法 演示系統(tǒng) 文法輸入 文法分析 句子輸入 與分析 文法分析表 構(gòu)造 獲取終結(jié)符和非終結(jié)符 求文法的 select 集 判斷 select 集的合法性 求 first 集 求 follow 集 第 IV 頁(yè) 共 22 頁(yè) 3．分析表構(gòu)造模塊 分析表構(gòu)造模塊的主要功能是將算法分析模塊所求解出的符合 LL（ 1）算法規(guī)則的文法的 select 集轉(zhuǎn)化成文法分析表，以便下一模塊的調(diào)用。 本模塊通過(guò)調(diào)用 VB 中 CommonDialog 控件的 ShowOpen 方法啟動(dòng)打開(kāi)文件對(duì)話(huà)框，獲取需要讀取的文件的路徑，再調(diào) 用 Open 命令打開(kāi)文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進(jìn)行保存。 用 ShowOpen 方法顯示對(duì)話(huà)框 p_name = 39。 Do While WF(j, 0) Empty 39。 終結(jié)符的個(gè)數(shù) Public nz As Integer 39。 終結(jié)符集 Public NZJ(250) As String 39。判斷第 a 條規(guī)則右邊的首符號(hào)是否是終結(jié)符 For p = 0 To fo 39。判斷 WF(i,j+1)在 F()中是否已經(jīng)存在 If F(p) = Then b = 1 Exit For 第 VII 頁(yè) 共 22 頁(yè) 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 列所對(duì)應(yīng)的格子中的第 z個(gè)數(shù)據(jù)。 當(dāng) ? 為 ? 時(shí)，即： A::=a，有： LL(A,a)=R(?)/N ::=Dβ規(guī)則 對(duì)于 A::=D?， (D?Vn)，且有 Select(A::=D?)={b1,b2,? ,bn} ， 則 LL(A,bi)=RD?)/P， (i=1,2,? ,n) **R(D?)/P：表示用 D? 的 (逆串替換 A后，重讀當(dāng)前符號(hào) ::=ε規(guī)則 對(duì)于 A::=?，且有 Select(A::=?)= {b1,b2,? ,bn} 則 LL(A, bi)=R(?)/P 本部分主要通過(guò) VB 中的 InputBox 對(duì)話(huà)框讀入待分析句子，并與分析表進(jìn)行對(duì)照，逐步分析所輸入的句子是否符合文法。存放句子分析過(guò)程中的輸入符號(hào)棧 讀取句子 Public Sub juzi_read(str As String) 39。即使是人工求解，也經(jīng)常出現(xiàn)錯(cuò)誤，以至影響最終的結(jié)果。當(dāng)控件中某一行的數(shù)據(jù)超過(guò) ListBox 的寬度時(shí)，數(shù)據(jù)會(huì)顯示不完整。H194 SendMessage , LB_SETHORIZONTALEXTENT, i, 0 其中， List1 為 ListBox 的名稱(chēng) ； i為水平滾動(dòng)條的寬度， 單位是 pixel(像素 )。 第 XIII 頁(yè) 共 22 頁(yè) 圖 8 Open對(duì)話(huà)框 文法原形如圖 9所示： 圖 9 輸入的文法 對(duì)其進(jìn)行分析，結(jié)果如圖 10 所示： 第 XIV 頁(yè) 共 22 頁(yè) 圖 10 文法分析結(jié)果 隨后即可得到文法的分析表（圖 11），并以此為依據(jù)，對(duì)輸入的句子進(jìn)行分析（圖 12）。 通過(guò) 《 一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn) 》 的使用，希望在提高教學(xué)質(zhì)量的同時(shí)，也能對(duì)同學(xué)們?cè)诰幾g原理的學(xué)習(xí)中起到幫助，讓大家更好的了解 LL（ 1）算法的整個(gè)過(guò)程。 [4] 楊克玉 . [M].北京：機(jī)械工業(yè)出版社出版， 。 第 XVII 頁(yè) 共 22 頁(yè) 致 謝 本文是在 韓斌 老師的熱情關(guān)心和指導(dǎo)下完成的，他淵博的知識(shí)和嚴(yán)謹(jǐn)?shù)闹螌W(xué)作風(fēng)使我受益匪淺，對(duì)順利完成本課題起到了極大的作用。 關(guān)于學(xué)位論文使用權(quán)和研究成果知識(shí)產(chǎn)權(quán)的說(shuō)明： 本人完全 了解成都信息工程學(xué)院有關(guān)保管使用學(xué)位論文的規(guī)定，其中包括： （ 1）學(xué)校有權(quán)保管并向有關(guān)部門(mén)遞交學(xué)位論文的原件與復(fù)印件。 （ 5）學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi)容（保密學(xué)位論文在解密后遵守此規(guī)定）。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)過(guò)程，以達(dá)到高效，直觀的效果。 grammar analysis。編譯程序一般由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、目標(biāo)代碼生成程 序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)過(guò)程，節(jié)約教學(xué)時(shí)間。由若干條規(guī)則組成。運(yùn)用符號(hào)“ |”把相同左部的規(guī)則縮寫(xiě)在一起，這樣顯得文法更為緊湊。 終結(jié)符 ：文法中凡不屬于非終結(jié)符集的符號(hào)，它們組成的集合稱(chēng)為終結(jié)符集。 First 集 ：首符號(hào)集。 自頂向下分析 對(duì)于文法 G[Z]，給頂一個(gè)待分析的句子 (字符串 )，自頂向下分析的基本思想是從識(shí)別符號(hào) Z 開(kāi)始，根據(jù)文法試著建立一個(gè)推導(dǎo)序列，若得到所給的句子，則句子得到識(shí)別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過(guò)各種推導(dǎo)都不能得到所分析的句子，則該符號(hào)串不符合文法。 方法： 首先對(duì)文法的每個(gè)規(guī)則 A::=? 求可選集 Select(A::=?)。 Select(Z ::=bZ)=。試探法有可能形成回溯現(xiàn)象。 三種子程序的返回地址保護(hù)方法： 返回地址保護(hù)單元。同時(shí)入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護(hù)的工作單元。這種分析方法從左到右掃描源程序（輸入串），同時(shí)從識(shí)別符號(hào)開(kāi)始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看 K 個(gè)符號(hào)，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。 (1)分析方法的邏輯結(jié)構(gòu) 第 5 頁(yè) 共 22 頁(yè) 圖 2 LL(1)分析方法的邏輯結(jié)構(gòu) (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導(dǎo)所使用的規(guī)則。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。首先進(jìn)行介紹與 LL(1)分析有關(guān)的 3個(gè)操作約定： (1)N 表示繼續(xù)下一個(gè)符號(hào)； (2)P 表示重讀當(dāng)前符號(hào)，也即不讀入下一符號(hào)； (3)R(?)表示用 ? 的逆串替換棧頂符號(hào)。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來(lái)反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。 (2)當(dāng) x1?Vt 時(shí)，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪去x1和 y1，然后繼續(xù)向前分析；不 相同表示不相配，為出錯(cuò)。