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