【正文】 .......................... XV 結(jié) 論 ................................................................ XVI0 參考文獻 .............................................................. XVI0 致 謝 ............................................................... XVII1 聲 明 .............................................................. XVIII2 第 1 頁 共 22 頁 1 引言 項目背景 編譯原理是計算機專業(yè)中最難的一門課程 ,在理論上它要求學生掌握有關(guān)形勢語言和自動機的抽象概念 ,在技術(shù)上要求學生能夠熟練地利用各種數(shù)據(jù)結(jié)構(gòu)進行編程。 特此聲明！ 第 XIX 頁 共 22 頁 學位論文 一個編譯原理語法 分析器的實現(xiàn)與設(shè)計 論文作者姓名： 申請學位專業(yè)： 申請學位類別： 指導教師姓名（職稱）： 論文提交日期： 一個編譯原理語法分析器的實現(xiàn)與設(shè)計 摘 要 編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯處理程序等成分構(gòu)成。文中除了特別加以標注地方外，不包含他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得成都信息工程學院或其他教學機構(gòu)的學位或證書而使用過的材料。 [2] 康慕寧 .編譯原理 [M].西安：西北工業(yè)大學出版社出版， 2020。 解決結(jié)果 運行后的結(jié)果如圖 7所示： 圖 7 ListBox的水平滾動條 5 結(jié)果測試 在系統(tǒng)開發(fā)完成后，對系統(tǒng)各個功能做了詳細的測試，對于正確的文法，系統(tǒng)能正常的演示整個文法分析的每一個過程；對于預設(shè)置的錯誤處理，系統(tǒng)也能給出正確的判斷，指出文法的錯誤類型。 解決方案 通過參照編譯原理中 first 集和 follow 集的具體求解步驟，通過多重循環(huán)的嵌套，完成了 select 集的求解過程，具體代碼請參照 節(jié)。 相關(guān)程序片段如下： 程序中所用到的公有數(shù)據(jù)成員有： Dim FXZ(50) As String 39。判斷 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。ε為空字符串 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é)符再求首符號集。程序中所用到的公有數(shù)據(jù)成員有： Public hs As Integer 39。調(diào)用打開文件對話框的具體代碼如下： Dim p_name As String 39。 2．算法分析模塊 算法分析模塊是《 一個編譯原理語法分析器的設(shè)計與實現(xiàn)》 中的關(guān)鍵模塊。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。 LL（ 1）分析方法 （ 1）方法的思想：根據(jù)輸入串的當前輸入符號，確定用某規(guī)則進行推導，當推導的第一個符號與輸入串的當前符號匹配時，就把輸入串的下一個字符作為當前輸入字符，直到推導出輸入串。 ，由于返回地址保護單元數(shù)目不明確，一般采用堆棧形式。 Select(V ::=x)={x}。 例：設(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ī)則都要試探。 遞歸定義 ：在定義某種事物時又用到其本身。規(guī)則又稱為產(chǎn)生式。這些過程往往需要占用大量時間來分析、制表等。所謂 LL(1)分析法是指語法分析是按自左至右的順序向前查看一個輸入字符串，并分析過程中產(chǎn)生句子的最左推導 。 本文旨在介紹語法分析方法中的一種自上而下的分析方法 —— LL(1)分析法。 在編譯原理的教學過程中，語法和語義分析階段關(guān)于算法的講解都需要對算法進行詳細的分析，包括算法條件的判斷，文法分析表的構(gòu)造過程，文法分析表的具體生成，針對文法的句子的分析過程等。 規(guī)則 ：為一個二元組，通常格式為 U：： =x 或 U→ x；其中 U 為規(guī)則的左部，是一個符號； x是規(guī)則的右部，是一貫有窮字符串。 遞歸 ：同一操作或一組操作的連續(xù)重復， 其實質(zhì)上是處理過程的性質(zhì)，在這種過程的每一步都要用到它自身的上一步或上幾步的結(jié)果。 或者說，從根結(jié)點出發(fā)，自上而下地建立一顆語法樹，其未端結(jié)點按從左到右的順序連接起來，構(gòu)成給定的符號串，則符號串得到識別。 Select(V ::=baZ)=。 ，不得隨意公用。 當 K=1 時，既是 LL（ 1）分析方法。然后再把相應的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。其中包括了對可能出現(xiàn)的文法 BNF 表示法的判 斷以及對文法中是否存在直接左遞歸規(guī)則的判斷。 文件讀取使用的 CommonDialog 控件介紹 CommonDialog 控件提供諸如打開和保存文件、設(shè)置打印選項、選擇顏色和字體等操作的一組標準對話框。 判斷文法是否有左遞歸 If WF(j, 0) = WF(j, 1) Then 第 V 頁 共 22 頁 MsgBox ！錯誤！文法有左遞歸存在，不符合 LL(1)的要求 , vbApplicationModal, 錯誤 Exit Sub End If j = j + 1 Loop 分析模塊 本模塊首先獲取文法的終結(jié)符集和非終結(jié)符集，分別用一維數(shù)組進行保存；然后在對文法的每一條規(guī)則求 select 集，并將 select 集保存到二維數(shù)組中；最后對 select 集做相關(guān)判斷，以確定所讀入的文法是否符合 LL（ 1）文法的規(guī)則。 非終結(jié)符集 求 select 集 設(shè)有文法 G[S]，并有規(guī)則 A::=?，則該規(guī)則的可選集為： Select(A::=?)= 具體實現(xiàn)代碼如下： If WF(a, 0) = Empty Then Exit For ElseIf WF(a, 1) = ε Then 39。判斷 WF(i,j+1)是不是 終結(jié)符 If WF(i, j + 1) = ZJF(m) Then For p = 0 To fo 39。分析過程均用一維數(shù)組進行保存。要用計算機實現(xiàn)這一復雜的過程，對開發(fā)人員的邏輯思維能力要求甚高。 i 的值由所輸出的最長的一串字符串決定，具體獲取方法為： 添加一個自動縮放大小的 label，將最長的字符串附給其 Caption 屬性，然后取得 label 的寬度除以 15，即為 i 的值。 參考文獻 [1] 錢煥延 .編譯技術(shù)第 2版 [M].南京：東南大學出版社出版， 2020。在此向他表示我最衷心的感謝！ 感謝同班同學在課題研究初期給予 的幫助在他們的幫助下課題才得以很好的展開，有了一個很好的開端，感謝寢室同學在測試中給予的幫助，因為他們的協(xié)助才得以高效率的完成本課題！ 在論文完成過程中，本人還得到了其他老師和許多同學的熱心幫助，本人向他們表示深深的謝意！ 最后向在百忙之中評審本文的各位專家、老師表示衷心的感謝！ 作者簡介： 出生年月： 19821014 性別：男 Email: 民族：漢族 第 XVIII 頁 共 22 頁 聲 明 本論文的工作是 2020年 2月至 2020年 6月在成都信息工程學院 網(wǎng)絡(luò)工程 系完成的。 除非另有科研合同和其他法律文書的制約，本論文的科研成果屬于成都信息工程學院。 LL(1) algorithm。 《 一個編譯原理語法分析器的設(shè)計與實現(xiàn)》 ，并實現(xiàn)以 下相關(guān)操作： LL（ 1）的要求 select集（其中包括 first集和 follow集的求解）并判斷 select集是否符合 LL（ 1）算法的要求 select 集構(gòu)造文法分析表 語法分析 ： 逐一分析詞法分析所得的屬性字，檢查其中的語法錯誤，如果沒有發(fā)現(xiàn)語法錯誤， 則給出正確的語法結(jié)構(gòu)。 第 2 頁 共 22 頁 文法 G[Z]：規(guī)則的非空有窮集合，其中 Z 為文法的 識別符號 或 開始符號 ，它至少要在一條規(guī)則的左部出現(xiàn)。 Follow 集 ：向前看集。 當 ??? 時，則對于當前輸入的符號 a，若有 a?First(?)，則可以選用規(guī)則A::=? 進行推導。對于回溯現(xiàn)象，可以通過 “ 左提因子方法 ” 對文法進行修改來消除。 遞歸子程序調(diào)用時，入口與出口的工作： (1)遞歸入口工作： ①當前返回地址送保護棧； ②遞歸子程序中（調(diào)用程序）不允許被破壞的工作單元內(nèi)容送保護棧。 (1)分析過程 假設(shè)分析過程中當前句型的右端部分為： x1x2? xm， (xi?V) 輸入流（待分析串）的右端部分為： y1y2? yn， (yi?Vt) 此時有以下 3 種情況： (1)當 x1?Vn，則根據(jù)當前輸入符號 y1 選擇相應的規(guī)則去替換 x1。 構(gòu)造 LL(1)分析表的方法如下： A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N ＃ a1 a2 a3 … a i … a m 控制器 分析表 Xn1 …… .. x1 第 6 頁 共 22 頁