一個編譯原理語法分析器的實現與設計一個編譯原理語法分析器的實現與設計—畢業設計論文(編輯修改稿)

　

【文章內容簡介】 select 集做相關判斷，以確定所讀入的文法是否符合 LL（ 1）文法的規則。程序中所用到的公有數據成員有： Public hs As Integer 39。 文法的行數 Public zj As Integer 39。 終結符的個數 Public nz As Integer 39。 非終結符的個數 Public SLT(50, 50) As String 39。 select 集 Dim F(50) As String 39。 用與臨時存放 select 集中元素的數組 Public ZJF(50) As String 39。 終結符集 Public NZJ(250) As String 39。 非終結符集 求 select 集 設有文法 G[S]，并有規則 A::=?，則該規則的可選集為： Select(A::=?)= 具體實現代碼如下： If WF(a, 0) = Empty Then Exit For ElseIf WF(a, 1) = ε Then 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 集 首符號集既求解文法每條規則右邊的第一個符號并且必須 是終結符，因為文法使用數組存放，所以既求文法每行規則的第 2個字符既可；如果規則左邊第一個字符為非終結符，則通過循環對該非終結符再求首符號集。 For i = 0 To zj If WF(a, 1) = ZJF(i) Then 39。判斷第 a 條規則右邊的首符號是否是終結符 For p = 0 To fo 39。判斷 WF(i,j+1)在 F()中是否已經存在 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 集 求向前看集主要分兩種情況，一種是可以直接循環推導出終結符；第二種是推出的還是非終結符的，如果推出的還是非終結符的就循環對該非終結符再求向前看集；第三種情況是不能對該非終結符求向前看集，但是可以通過對該非終結符推導出的第二個非終結符求向前看集 的方法求出終結符。 c = 0: b = 0 If WF(a, 0) = WF(0, 0) Then 39。判斷是不是對文法起始符求 follow 集 For p = 0 To fo 39。判斷 WF(i,j+1)在 F()中是否已經存在 If F(p) = Then b = 1 Exit For 第 VII 頁 共 22 頁 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。判斷 WF(i,j+1)是不是 終結符 If WF(i, j + 1) = ZJF(m) Then For p = 0 To fo 39。判斷 WF(i,j+1)在 F()中是否已經存在 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。查找 WF(i,j+1)對應的非終結符在文法的第幾行 If WF(i, j + 1) = WF(n, 0) Then Call first(n, fo) 分析表構造模塊 在已經得到文法 select 集的前提下，以次為依據，對文法的三種類型的規則： A::=aβ 型、 A::=Dβ 型、 A::=ε 型分別構造分析表，并用一個三維數組保存。形如 FXB（ y， x， z），其中， y 表示分析表的第 y 行， x表示第 x列， z表示第 y行第 x 列所對應的格子中的第 z個數據。 構造文法分析表 在求解 Select 集完成后，結果按照 非終結符放入分析表 Y 軸，沒有出現在對應規則右部首部的終結符放入分析表 Y軸，終結符放入分析表 X軸等規則放置。如圖 5。 圖 5 分析表構造流程 文法分析表 終結符 非終結符 文法可選集 未出現在對應規則右部首部的終結符 放入分析表 X 軸 放入分析表 Y 軸 放入分析表 Y 軸 第 IX 頁 共 22 頁 ::=aβ 規則 對于 A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N **R(?)/N：表示用 ? 的逆串替換Ａ后，繼續讀入下一個符號。 當 ? 為 ? 時，即： A::=a，有： LL(A,a)=R(?)/N ::=Dβ規則 對于 A::=D?， (D?Vn)，且有 Select(A::=D?)={b1,b2,? ,bn} ， 則 LL(A,bi)=RD?)/P， (i=1,2,? ,n) **R(D?)/P：表示用 D? 的 (逆串替換 A后，重讀當前符號 ::=ε規則 對于 A::=?，且有 Select(A::=?)= {b1,b2,? ,bn} 則 LL(A, bi)=R(?)/P 本部分主要通過 VB 中的 InputBox 對話框讀入待分析句子，并與分析表進行對照，逐步分析所輸入的句子是否符合文法。分析過程均用一維數組進行保存。 相關程序片段如下： 程序中所用到的公有數據成員有： Dim FXZ(50) As String 39。存放句子分析過程中的分析棧 Dim FHZ(50) As String 39。存放句子分析過程中的輸入符號棧 讀取句子 Public Sub juzi_read(str 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 分析句子 現在我們把句型的右端部分逆向放入一分析堆棧中，使 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 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 特殊問題 及 解決方法 在程序的開發過程中，遇到的問題及解決辦法如下： 第 XI 頁 共 22 頁 Select集的求解 問題描述 在 LL（ 1）分析方法中， select 集的求解至關重要，其中又涉及到 first 集和 follow 集的求解。即使是人工求解，也經常出現錯誤，以至影響最終的結果。要用計算機實現這一復雜的過程，對開發人員的邏輯思維能力要求甚高。 解決方案 通過參照編譯原理中 first 集和 follow 集的具體求解步驟，通過多重循環的嵌套，完成了 select 集的求解過程，具體代碼請參照 節。 解決結果 在成功獲得 select 集后，對其進行了輸出，結果如圖 6 所示： 圖 6 顯示 select 集 為 ListBox 添加水平滾動條 問題描述 在 VB 中，系統提供的 ListBox 只有垂直滾動條，而沒有水平滾動條。當控件中某一行的數據超過 ListBox 的寬度時，數據會顯示不完整。添加的水平滾動條的寬度也應該能動態的改變，以最寬的一行數據為水平滾動條寬度的依據。 解決方案 利用 SendMessage 傳送 LB_SETHORIZONTALEXTENT 訊息給 ListBox，此一 第 XII 頁 共 22 頁 訊息的作用就是要求 ListBox 設定水平 滾動條。代碼如下： Private Declare Function SendMessage Lib user32 Alias SendMessageA (ByVal hwnd As Long, ByVal wMsg As Long, ByVal wParam As Long, lParam As Any) As Long Private Const LB_SETHORIZONTALEXTENT = amp。H194 SendMessage , LB_SETHORIZONTALEXTENT, i, 0 其中， List1 為 ListBox 的名稱 ； i為水平滾動條的寬度， 單位是 pixel(像素 )。 i 的值由所輸出的最長的一串字符串決定，具體獲取方法為： 添加一個自動縮放大小的 label，將最長的字符串附給其 Caption 屬性，然后取得 label 的寬度除以 15，即為 i 的值。 解決結果 運行后的結果如圖 7所示： 圖 7 ListBox的水平滾動條 5