【正文】 s 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。 LL(1) algorithm。 編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一。 在編譯原理的教學(xué)過程中，語法和語義分析階段關(guān)于算法的講解都需要對算法進行詳細的分析，包括算法條件的判斷，文法分析表的構(gòu)造過程，文法分析表的具體生成，針對文法的句子的分析過程等。教學(xué)主要是對這些過程的講解和分析，沒有必要花這么多的時間來做這些工作。 《 一個編譯原理語法分析器的設(shè)計與實現(xiàn)》 通過文本方式獲取相關(guān)文法，并實現(xiàn)以下相關(guān)操作： LL（ 1）的要求 select集（其中包括 first集和 follow集的求解）并判斷 select集是否符合 LL（ 1）算法的要求 select 集構(gòu)造文法分析表 語法分析 ： 逐一分析詞法分析所得的屬性字，檢查其中的語法錯誤，如果沒有發(fā)現(xiàn)語法錯誤， 則給出正確的語法結(jié)構(gòu)。 文法 ：對語言結(jié)構(gòu)的定義和描述，即在形式上用于描述和規(guī)定語言結(jié)構(gòu)。 規(guī)則 ：為一個二元組，通常格式為 U：： =x 或 U→ x；其中 U 為規(guī)則的左部，是一個符號； x是規(guī)則的右部，是一貫有窮字符串。 BNF 表示法 ：即巴科斯范式表示法，它引進了符號“ |”，符號“ |”表示“或”。 第 2 頁 共 22 頁 文法 G[Z]：規(guī)則的非空有窮集合，其中 Z 為文法的 識別符號 或 開始符號 ，它至少要在一條規(guī)則的左部出現(xiàn)。 非終結(jié)符 ：文法中出現(xiàn)在規(guī)則左部的符號，它們組成的集合稱為非終結(jié)符集。 遞歸 ：同一操作或一組操作的連續(xù)重復(fù)， 其實質(zhì)上是處理過程的性質(zhì)，在這種過程的每一步都要用到它自身的上一步或上幾步的結(jié)果。 直接左遞歸規(guī)則 ：型如 U：： =Uy 的規(guī)則稱為直接左遞歸規(guī)則。 Follow 集 ：向前看集。 LL（ 1）文法 ：對于文法 G（ S），其每 個非終結(jié)符的不同規(guī)則具有不相交的Select 集，則稱該文法為 LL（ 1）文法。 或者說，從根結(jié)點出發(fā)，自上而下地建立一顆語法樹，其未端結(jié)點按從左到右的順序連接起來，構(gòu)成給定的符號串，則符號串得到識別。 該解決辦法是把文法中每個非終結(jié)符號 A 的右部稱為 A 的候選式，對候選式的選擇，則根據(jù)當前輸入符號來決定。 當 ??? 時，則對于當前輸入的符號 a，若有 a?First(?)，則可以選用規(guī)則A::=? 進行推導(dǎo)。 例：設(shè)有文法 G[Z]，和句子 bbabaax Z::=aV|bZ V::=baZ|x Select(Z ::=aV)={a}。 Select(V ::=baZ)=。 Z? bZ? bbZ? bbaV? bbabaZ? bbabaaV?bbabaax (babaax) (abaax) (baax) (ax) (x) 對于文法，有 A::= x1|x2|? |xn，若有 First(xi) ∩ First(xj) ??(i?j)，采用試探法：即從首字符中有輸入符號的多個候選式中任選一個來試探，如果不成功，就換另一個接著試。對于回溯現(xiàn)象，可以通過 “ 左提因子方法 ” 對文法進行修改來 消除。 遞歸子程序及其調(diào)用： 常用的子程序的種類有 3 種： 簡單子程序， 嵌套子程序， 遞歸子程序。 ，不得隨意公用。方法是在內(nèi)存中開辟一個保護棧，每次進入遞歸子程序時，就把當前返回地址送入保護棧，相應(yīng)地，每次退出遞歸子程序時，就取棧頂?shù)姆祷氐刂纷鳛槠浞祷氐刂贰? 遞歸子程序調(diào)用時，入口與出口的工作： (1)遞歸入口工作： ①當前返回地址送保護棧； ②遞歸子程序中（調(diào)用程序）不允許被破壞的工作單元內(nèi)容送保護棧。 LL（ K）分析方法 LL(K)分析方法是一種自頂向下的分析技術(shù)。 當 K=1 時，既是 LL（ 1）分析方法。根據(jù)輸入串向前的 1個符號來確定推導(dǎo)規(guī)則時，就是 LL（ 1）方法。 (1)分析過程 假設(shè)分析過程中當前句型的右端部分為： x1x2? xm， (xi?V) 輸入流（待分析串）的右端部分為： y1y2? yn， (yi?Vt) 此時有以下 3 種情況： (1)當 x1?Vn，則根據(jù)當前輸入符號 y1 選擇相應(yīng)的規(guī)則去替換 x1。 (3)若上述兩個字符串均為空，則表示全部匹配，輸入串被識別。然后再把相應(yīng)的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。如果分析棧中的元素為 A，輸入元素為 a，則其匹配關(guān)系記為 LL(A,a) LL(1)分析矩陣：一種用來 反映這種匹配關(guān)系的矩陣表示，該矩陣稱為 LL(1)分析矩陣。 構(gòu)造 LL(1)分析表的方法如下： A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N ＃ a1 a2 a3 … a i … a m 控制器 分析表 Xn1 …… .. x1 第 II 頁 共 22 頁 **R(?)/N：表示用 ? 的逆串替換Ａ后，繼續(xù)讀入下一個符號。 5種情況，則置出錯，分析表中用空白表示。其中包括了對可能出現(xiàn)的文法 BNF 表示法的判 斷以及對文法中是否存在直接左遞歸規(guī)則的判斷。本模塊包含了 LL（ 1）算法中的大部分重要數(shù)據(jù)和信息，其中包括獲取輸入文法的終結(jié)符集和非終結(jié)符集，對文法中每一條規(guī)則求 select集（ select 集的求解又包括求 first 集或者 follow 集），以及對 select 集合法性的判斷，即同一非終結(jié)符所對應(yīng)的不同規(guī)則的 select 集中不能有相同的終結(jié)符。 4．句子分析模塊 句子分析模塊是整個《 一個編譯原理語法分析器的設(shè)計與實現(xiàn) 》的主體演示模塊，包括句子讀取、句子合法性判斷、句子分析等部分。下面將對以上四個模塊的具體實現(xiàn)技術(shù)、數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵程序片段進行詳細的說明。 文件讀取使用的 CommonDialog 控件介紹 CommonDialog 控件提供諸如打開和保存文件、設(shè)置打印選項、選擇顏色和字體等操作的一組標準對話框。 文件路徑 = True On Error GoTo err = Text(*.txt)|*.txt = 1 39。 用 FileName 屬性獲取選定文件的名稱 文法左遞歸的判斷 文法中使用遞歸規(guī)則以后，可以用有限的規(guī)則刻劃無限語言，但不利的是對與具有左遞歸性的文法，不能采用自頂向下的分析算法。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(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ī)則。 文法的行數(shù) Public zj As Integer 39。 非終結(jié)符的個數(shù) Public SLT(50, 50) As String 39。 用與臨時存放 select 集中元素的數(shù)組 Public ZJF(50) As String 39。 非終結(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。 For i = 0 To zj If WF(a, 1) = ZJF(i) Then 39。判斷 WF(i,j+1)在 F()中是否已經(jīng)存在 If WF(a, 1) = F(p) Then b = 1 Exit For End If Next p If b = 1 Then b = 0 Else F(fo) = WF(a, 1) fo = fo + 1 F(fo) = Empty End If 求 follow 集 求向前看集主要分兩種情況，一種是可以直接循環(huán)推導(dǎo)出終結(jié)符；第二種是推出的還是非終結(jié)符的，如果推出的還是非終結(jié)符的就循環(huán)對該非終結(jié)符再求向前看集；第三種情況是不能對該非終結(jié)符求向前看集，但是可以通過對該非終結(jié)符推導(dǎo)出的第二個非終結(jié)符求向前看集 的方法求出終結(jié)符。判斷是不是對文法起始符求 follow 集 For p = 0 To fo 39。判斷 WF(i,j+1)是不是 終結(jié)符 If WF(i, j + 1) = ZJF(m) Then For p = 0 To fo 39。查找 WF(i,j+1)對應(yīng)的非終結(jié)符在文法的第幾行 If WF(i, j + 1) = WF(n, 0) Then Call first(n, fo) 分析表構(gòu)造模塊 在已經(jīng)得到文法 select 集的前提下，以次為依據(jù)，對文法的三種類型的規(guī)則： A::=aβ 型、 A::=Dβ 型、 A::=ε 型分別構(gòu)造分析表，并用一個三維數(shù)組保存。 構(gòu)造文法分析表 在求解 Select 集完成后，結(jié)果按照 非終結(jié)符放入分析表 Y 軸，沒有出現(xiàn)在對應(yīng)規(guī)則右部首部的終結(jié)符放入分析表 Y軸，終結(jié)符放入分析表 X軸等規(guī)則放置。 圖 5 分析表構(gòu)造流程 文法分析表 終結(jié)符 非終結(jié)符 文法可選集 未出現(xiàn)在對應(yīng)規(guī)則右部首部的終結(jié)符 放入分析表 X 軸 放入分析表 Y 軸 放入分析表 Y 軸 第 IX 頁 共 22 頁 ::=aβ 規(guī)則 對于 A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N **R(?)/N：表示用 ? 的逆串替換Ａ后，繼續(xù)讀入下一個符號。分析過程均用一維數(shù)組進行保存。存放句子分析過程中的分析棧 Dim FHZ(50) As String 39。讀取句子 FHZ(0) = Empty i = 0 a = Mid(str, 1, 1) Do While a Empty FHZ(i) = a a = Mid(str, i + 2, 1) i = i + 1 FHZ(i) = Empty Loop If FHZ(0) = Empty Then Exit Sub 第 X 頁 共 22 頁 End If FHZ(i) = FHZ(i + 1) = Empty Call fenxi_chr End Sub 分析句子 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1 成為棧頂，利用分析棧，當棧頂符號與輸入串當前符號相匹配時，則從棧頂刪除該符號。 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