【正文】 用各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行編程。 字匯表 ：在文法中，由全部規(guī)則的左部和右部中的所有符號(hào)組成的符號(hào)集。 若對(duì)于某非終止符號(hào)有 n條規(guī)則（即有 n個(gè)候選式）的處理方法： 對(duì)于文法，有 A::=x1|x2|? |xn，其右部的 n個(gè)候選式的首符號(hào)集均不相同 : 即 First(xi) ∩ First(xj)=? (i?j)，對(duì)于待分析的符號(hào)串，如果最左的非終結(jié)符號(hào)為 A，若其句子中對(duì)應(yīng)的下一個(gè)符號(hào)（當(dāng)前輸入符號(hào)）為 a，且有a?First(xk)，則選擇規(guī)則 A::=xk 來作為推導(dǎo)的候選式。 (2)遞歸出口工作： ①恢復(fù)保護(hù)在棧頂中的工作單元的原來內(nèi)容，并上退保護(hù)棧； ②取保護(hù)在棧頂中的返回地址進(jìn)行返回，并退保護(hù)棧。首先進(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)。同時(shí)入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護(hù)的工作單元。 方法： 首先對(duì)文法的每個(gè)規(guī)則 A::=? 求可選集 Select(A::=?)。運(yùn)用符號(hào)“ |”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊。 grammar analysis。 第 XVII 頁 共 22 頁 致 謝 本文是在 韓斌 老師的熱情關(guān)心和指導(dǎo)下完成的，他淵博的知識(shí)和嚴(yán)謹(jǐn)?shù)闹螌W(xué)作風(fēng)使我受益匪淺，對(duì)順利完成本課題起到了極大的作用。H194 SendMessage , LB_SETHORIZONTALEXTENT, i, 0 其中， List1 為 ListBox 的名稱 ； i為水平滾動(dòng)條的寬度， 單位是 pixel(像素 )。 當(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 本部分主要通過 VB 中的 InputBox 對(duì)話框讀入待分析句子，并與分析表進(jìn)行對(duì)照，逐步分析所輸入的句子是否符合文法。 終結(jié)符集 Public NZJ(250) As String 39。 本模塊通過調(diào)用 VB 中 CommonDialog 控件的 ShowOpen 方法啟動(dòng)打開文件對(duì)話框，獲取需要讀取的文件的路徑，再調(diào) 用 Open 命令打開文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進(jìn)行保存。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。 三種子程序的返回地址保護(hù)方法： 返回地址保護(hù)單元。 自頂向下分析 對(duì)于文法 G[Z]，給頂一個(gè)待分析的句子 (字符串 )，自頂向下分析的基本思想是從識(shí)別符號(hào) Z 開始，根據(jù)文法試著建立一個(gè)推導(dǎo)序列，若得到所給的句子，則句子得到識(shí)別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過各種推導(dǎo)都不能得到所分析的句子，則該符號(hào)串不符合文法。由若干條規(guī)則組成。本軟件的主要任務(wù)就是利用程序來完成算法的上述相關(guān)過程，以達(dá)到高效，直觀的效果。教學(xué)主要是對(duì)這些過程的講解和分析，沒有必要花這么多的時(shí)間來做這些工作。 直接左遞歸規(guī)則 ：型如 U：： =Uy 的規(guī)則稱為直接左遞歸規(guī)則。 Z? bZ? bbZ? bbaV? bbabaZ? bbabaaV?bbabaax (babaax) (abaax) (baax) (ax) (x) 對(duì)于文法，有 A::= x1|x2|? |xn，若有 First(xi) ∩ First(xj) ??(i?j)，采用試探法：即從首字符中有輸入符號(hào)的多個(gè)候選式中任選一個(gè)來試探，如果不成功，就換另一個(gè)接著試。根據(jù)輸入串向前的 1 個(gè)符號(hào)來確定推導(dǎo)規(guī)則時(shí)，就是 LL（ 1）方法。本模塊包含了 LL（ 1）算法中的大部分重要數(shù)據(jù)和信息，其中包括獲取輸入文法的終結(jié)符集和非終結(jié)符集，對(duì)文法中每一條規(guī)則求 select集（ select 集的求解又包括求 first 集或者 follow 集），以及對(duì) select 集合法性的判斷，即同一非終結(jié)符所對(duì)應(yīng)的不同規(guī)則的 select 集中不能有相同的終結(jié)符。 文法的行數(shù) Public zj As Integer 39。查找 WF(i,j+1)對(duì)應(yīng)的非終結(jié)符在文法的第幾行 If WF(i, j + 1) = WF(n, 0) Then Call first(n, fo) 分析表構(gòu)造模塊 在已經(jīng)得到文法 select 集的前提下，以次為依據(jù)，對(duì)文法的三種類型的規(guī)則： A::=aβ 型、 A::=Dβ 型、 A::=ε 型分別構(gòu)造分析表，并用一個(gè)三維數(shù)組保存。 解決結(jié)果 在成功獲得 select 集后，對(duì)其進(jìn)行了輸出，結(jié)果如圖 6 所示： 圖 6 顯示 select 集 為 ListBox 添加水平滾動(dòng)條 問題描述 在 VB 中，系統(tǒng)提供的 ListBox 只有垂直滾動(dòng)條，而沒有水平滾動(dòng)條。 [3] 賀世娟，陳冀川 .Visual Basic 程序設(shè)計(jì) [M].北京：中國水利水電出版社出版。 在編譯原理的教學(xué)過程中，算法的講解都需要對(duì)算法進(jìn)行詳細(xì)的分析，包括算法條件的判斷，文法分析表的構(gòu)造過程，文法分析表的具體生成，針對(duì)文法的句子的分析過程等，這些過程往往需要占用大量時(shí)間來分析 、制表等。 文法 ：對(duì)語言結(jié)構(gòu)的定 義和描述，即在形式上用于描述和規(guī)定語言結(jié)構(gòu)。 LL（ 1）文法 ：對(duì)于文法 G（ S），其每個(gè)非終結(jié)符的不同規(guī)則具有不相交的Select 集，則稱該文法為 LL（ 1）文法。 遞歸子程序及其調(diào)用： 常用的子程序的種類有 3 種： 簡單子程序， 嵌套子程序， 遞歸子程序。 (3)若上述兩個(gè)字符串均為空，則表示全部匹配，輸入串被識(shí)別。根據(jù)輸入串向前的 1 個(gè)符號(hào)來確定推導(dǎo)規(guī)則時(shí)，就是 LL（ 1）方法。 Z? bZ? bbZ? bbaV? bbabaZ? bbabaaV?bbabaax (babaax) (abaax) (baax) (ax) (x) 對(duì)于文法，有 A::= x1|x2|? |xn，若有 First(xi) ∩ First(xj) ??(i?j)，采用試探法：即從首字符中有輸入符號(hào)的多個(gè)候選式中任選一個(gè)來試探，如果不成功，就換另一個(gè)接著試。 直接左遞歸規(guī)則 ：型如 U：： =Uy 的規(guī)則稱為直接左遞歸規(guī)則。教學(xué)主要是對(duì)這些過程的講解和分析，沒有必要花這么多的時(shí)間來做這些工作。 （ 4）學(xué)?？稍试S學(xué)位論文被查閱或借閱。在數(shù)據(jù)的處理上我采用各模塊全數(shù)組操作，并且將最終結(jié)果通過字符串方式保存，通過字符串來向其他模塊傳送數(shù)據(jù)，這種新的嘗試也讓我的程序帶有個(gè)人的風(fēng)格，讓我對(duì)編程的多樣化有了更 深的了解和認(rèn)識(shí)。 Do While (i, j, k) Empty Select Case (i, j, k) Case acc Exit Sub Case ε FXZ(a) = Empty Case /N FHZ(b) = b = b + 1 a = a 1 Exit For Case /P a = a 1 Exit For Case Else FXZ(a) = (i, j, k) a = a + 1 FXZ(a) = Empty End Select k = k + 1 Loop 4 特殊問題 及 解決方法 在程序的開發(fā)過程中，遇到的問題及解決辦法如下： 第 XI 頁 共 22 頁 Select集的求解 問題描述 在 LL（ 1）分析方法中， select 集的求解至關(guān)重要，其中又涉及到 first 集和 follow 集的求解。判斷是不是對(duì)文法起始符求 follow 集 For p = 0 To fo 39。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(shè)計(jì)時(shí)間所限，所以本軟件沒有這項(xiàng)功能，只是對(duì)直接左遞歸進(jìn)行錯(cuò)誤判斷。 5種情況，則置出錯(cuò)，分析表中用空白表示。 LL（ K）分析方法 LL(K)分析方法是一種自頂向下的分析技術(shù)。 例：設(shè)有文法 G[Z]，和句子 bbabaax Z::=aV|bZ V::=baZ|x Select(Z ::=aV)={a}。 非終結(jié)符 ：文法中出現(xiàn)在規(guī)則左部的符號(hào)，它們組成的集合稱為非終結(jié)符集。 編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一。 grammar analysis。運(yùn)用符號(hào)“ |”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊。 方法： 首先對(duì)文法的每個(gè)規(guī)則 A::=? 求可選集 Select(A::=?)。同時(shí)入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護(hù)的工作單元。首先進(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)。 用 ShowOpen 方法顯示對(duì)話框 p_name = 39。判斷第 a 條規(guī)則右邊的首符號(hào)是否是終結(jié)符 For p = 0 To fo 39。存放句子分析過程中的輸入符號(hào)棧 讀取句子 Public Sub juzi_read(str As String) 39。 第 XIII 頁 共 22 頁 圖 8 Open對(duì)話框 文法原形如圖 9所示： 圖 9 輸入的文法 對(duì)其進(jìn)行分析，結(jié)果如圖 10 所示： 第 XIV 頁 共 22 頁 圖 10 文法分析結(jié)果 隨后即可得到文法的分析表（圖 11），并以此為依據(jù)，對(duì)輸入的句子進(jìn)行分析（圖 12）。 關(guān)于學(xué)位論文使用權(quán)和研究成果知識(shí)產(chǎn)權(quán)的說明： 本人完全 了解成都信息工程學(xué)院有關(guān)保管使用學(xué)位論文的規(guī)定，其中包括： （ 1）學(xué)校有權(quán)保管并向有關(guān)部門遞交學(xué)位論文的原件與復(fù)印件。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標(biāo)代碼生成程 序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。 終結(jié)符 ：文法中凡不屬于非終結(jié)符集的符號(hào)，它們組成的集合稱為終結(jié)符集。 Select(Z ::=bZ)=。這種分析方法從左到右掃描源程序（輸入串），同時(shí)從識(shí)別符號(hào)開始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看 K 個(gè)符號(hào)，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。 ，由于返回地址保護(hù)單元數(shù)目不明確，一般采用堆棧形式。 例：設(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ī)則都要試探。規(guī)則又稱為產(chǎn)生式。所謂 LL(1)分析法是指語法分析是按自左至右的順序向前查看一個(gè)輸入字符串，并分析過程中產(chǎn)生句子的最左推導(dǎo) 。 [6]