【正文】 匹配關(guān)系記為L(zhǎng)L(A,a)LL(1)分析矩陣：一種用來(lái)反映這種匹配關(guān)系的矩陣表示，該矩陣稱為L(zhǎng)L(1)分析矩陣。首先進(jìn)行介紹與LL(1)分析有關(guān)的3個(gè)操作約定：(1)N表示繼續(xù)下一個(gè)符號(hào)；(2)P表示重讀當(dāng)前符號(hào)，也即不讀入下一符號(hào)；(3)R(b)表示用b的逆串替換棧頂符號(hào)。構(gòu)造LL(1)分析表的方法如下：::=ab，(a206。Vt)，則 令 LL(A,a)=R(b)/N **R(b)/N：表示用b的逆串替換Ａ后，繼續(xù)讀入下一個(gè)符號(hào)。 當(dāng)b為e時(shí)，即：A::=a，有：LL(A,a)=R(e)/N ::=Db，(D206。Vn)，且有 Select(A::=Db)={b1,b2,…,bn} ， 則 LL(A,bi)=R(Db)/P，(i=1,2,…,n) **R(Db)/P：表示用Db的逆串替換A后，重讀當(dāng)前符號(hào)::=e，且有 Select(A::=e)= {b1,b2,…,bn} 則 LL(A, bi)=R(e)/P，a不出現(xiàn)于規(guī)則右部的首部， 則令 LL(a,a)=R(e)/N，令LL(,)=acc 表示分析結(jié)束，輸入串得到識(shí)別。，則置出錯(cuò)，分析表中用空白表示。2 系統(tǒng)流程圖項(xiàng)目的程序流程圖如圖3所示：程序開始調(diào)用打開對(duì)話框輸入文法優(yōu)化輸入的文法并判斷文法合法性獲取文法的終結(jié)符和非終結(jié)符對(duì)文法求select集并判斷select集合法性構(gòu)造文法分析表輸入并分析句子結(jié)束圖3 程序流程圖 系統(tǒng)模塊流程圖系統(tǒng)的模塊流程圖如圖4所示：LL(1)算法演示系統(tǒng)文法輸入文法分析句子輸入與分析文法分析表構(gòu)造獲取終結(jié)符和非終結(jié)符求文法的select集判斷select集的合法性求first集求follow集圖4系統(tǒng)模塊流程圖3 系統(tǒng)實(shí)施《一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)》主要分為四個(gè)模塊：1．文件讀取模塊文件讀取模塊主要完成將記事本中的待分析文法讀入到內(nèi)存中的功能。其中包括了對(duì)可能出現(xiàn)的文法BNF表示法的判斷以及對(duì)文法中是否存在直接左遞歸規(guī)則的判斷。2．算法分析模塊算法分析模塊是《一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)》中的關(guān)鍵模塊。本模塊包含了LL（1）算法中的大部分重要數(shù)據(jù)和信息，其中包括獲取輸入文法的終結(jié)符集和非終結(jié)符集，對(duì)文法中每一條規(guī)則求select集（select集的求解又包括求first集或者follow集），以及對(duì)select集合法性的判斷，即同一非終結(jié)符所對(duì)應(yīng)的不同規(guī)則的select集中不能有相同的終結(jié)符。3．分析表構(gòu)造模塊分析表構(gòu)造模塊的主要功能是將算法分析模塊所求解出的符合LL（1）算法規(guī)則的文法的select集轉(zhuǎn)化成文法分析表，以便下一模塊的調(diào)用。4．句子分析模塊句子分析模塊是整個(gè)《一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)》的主體演示模塊，包括句子讀取、句子合法性判斷、句子分析等部分。其中句子合法性的判斷又分為句子中是否有文法終結(jié)符以外的符號(hào)和句子是否符合文法規(guī)則的判斷。下面將對(duì)以上四個(gè)模塊的具體實(shí)現(xiàn)技術(shù)、數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵程序片段進(jìn)行詳細(xì)的說(shuō)明。本模塊通過(guò)調(diào)用VB中CommonDialog控件的ShowOpen方法啟動(dòng)打開文件對(duì)話框，獲取需要讀取的文件的路徑，再調(diào)用Open命令打開文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進(jìn)行保存。CommonDialog 控件提供諸如打開和保存文件、設(shè)置打印選項(xiàng)、選擇顏色和字體等操作的一組標(biāo)準(zhǔn)對(duì)話框。調(diào)用打開文件對(duì)話框的具體代碼如下：Dim p_name As String 39。 文件路徑 = TrueOn Error GoTo err = Text(*.txt)|*.txt = 1 39。 用 ShowOpen 方法顯示對(duì)話框p_name = 39。 用 FileName 屬性獲取選定文件的名稱文法中使用遞歸規(guī)則以后，可以用有限的規(guī)則刻劃無(wú)限語(yǔ)言，但不利的是對(duì)與具有左遞歸性的文法，不能采用自頂向下的分析算法。一般含有左遞歸規(guī)則的文法形式為U::=xUy，若x=e, 則有U::=Uy，即為左遞歸規(guī)則。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(shè)計(jì)時(shí)間所限，所以本軟件沒有這項(xiàng)功能，只是對(duì)直接左遞歸進(jìn)行錯(cuò)誤判斷。Do While WF(j, 0) Empty 39。 判斷文法是否有左遞歸 If WF(j, 0) = WF(j, 1) Then MsgBox ！錯(cuò)誤！文法有左遞歸存在，不符合LL(1)的要求, vbApplicationModal, 錯(cuò)誤 Exit Sub End If j = j + 1Loop本模塊首先獲取文法的終結(jié)符集和非終結(jié)符集，分別用一維數(shù)組進(jìn)行保存；然后在對(duì)文法的每一條規(guī)則求select集，并將select集保存到二維數(shù)組中；最后對(duì)select集做相關(guān)判斷，以確定所讀入的文法是否符合LL（1）文法的規(guī)則。程序中所用到的公有數(shù)據(jù)成員有：Public hs As Integer 39。 文法的行數(shù)Public zj As Integer 39。 終結(jié)符的個(gè)數(shù)Public nz As Integer 39。 非終結(jié)符的個(gè)數(shù)Public SLT(50, 50) As String 39。 select集Dim F(50) As String 39。 用與臨時(shí)存放select集中元素的數(shù)組Public ZJF(50) As String 39。 終結(jié)符集Public NZJ(250) As String 39。 非終結(jié)符集設(shè)有文法G[S]，并有規(guī)則A::=b，則該規(guī)則的可選集為：Select(A::=b)= 具體實(shí)現(xiàn)代碼如下： 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 Loop Else Call first(a, fo) 首符號(hào)集既求解文法每條規(guī)則右邊的第一個(gè)符號(hào)并且必須是終結(jié)符，因?yàn)槲姆ㄊ褂脭?shù)組存放，所以既求文法每行規(guī)則的第2個(gè)字符既可；如果規(guī)則左邊第一個(gè)字符為非終結(jié)符，則通過(guò)循環(huán)對(duì)該非終結(jié)符再求首符號(hào)集。For i = 0 To zj If WF(a, 1) = ZJF(i) Then 39。判斷第a條規(guī)則右邊的首符號(hào)是否是終結(jié)符 For p = 0 To fo 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 求向前看集主要分兩種情況，一種是可以直接循環(huán)推導(dǎo)出終結(jié)符；第二種是推出的還是非終結(jié)符的，如果推出的還是非終結(jié)符的就循環(huán)對(duì)該非終結(jié)符再求向前看集；第三種情況是不能對(duì)該非終結(jié)符求向前看集，但是可以通過(guò)對(duì)該非終結(jié)符推導(dǎo)出的第二個(gè)非終結(jié)符求向前看集的方法求出終結(jié)符。c = 0: b = 0If WF(a, 0) = WF(0, 0) Then 39。判斷是不是對(duì)文法起始符求follow集 For p = 0 To fo 39。判斷WF(i,j+1)在F()中是否已經(jīng)存在 If F(p) = Then b = 1 Exit For End If Next p If b = 1 Then b = 0 Else F(fo) = fo = fo + 1 F(fo) = Empty End IfEnd IfFor 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)是不是終結(jié)符 If WF(i, j + 1) = ZJF(m) Then For p = 0 To fo 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 End If Next m If c = 1 Then c = 0 Else For n = 0 To hs 39。查找WF(i,j+1)對(duì)應(yīng)的非終結(jié)符在文法的第幾行 If WF(i, j + 1) = WF(n, 0) Then Call first(n, fo) 在已經(jīng)得到文法select集的前提下，以次為依據(jù)，對(duì)文法的三種類型的規(guī)則：A::=aβ型、A::=Dβ型、A::=ε型分別構(gòu)造分析表，并用一個(gè)三維數(shù)組保存。形如FXB（y，x，z），其中，y表示分析表的第y行，x表示第x列，z表示第y行第x列所對(duì)應(yīng)的格子中的第z個(gè)數(shù)據(jù)。在求解Select集完成后，結(jié)果按照非終結(jié)符放入分析表Y軸，沒有出現(xiàn)在對(duì)應(yīng)規(guī)則右部首部的終結(jié)符放入分析表Y軸，終結(jié)符放入分析表X軸等規(guī)則放置。如圖5。放入分析表Y軸放入分析表X軸終結(jié)符 文法可選集非終結(jié)符文法分析表放入分析表Y軸未出現(xiàn)在對(duì)應(yīng)規(guī)則右部首部的終結(jié)符 圖5 分析表構(gòu)造流程::=aβ規(guī)則對(duì)于A::=ab，(a206。Vt)，則 令 LL(A,a)=R(b)/N **R(b)/N：表示用b的逆串替換Ａ后，繼續(xù)讀入下一個(gè)符號(hào)。當(dāng)b為e時(shí)，即：A::=a，有：LL(A,a)=R(e)/N ::=Dβ規(guī)則對(duì)于A::=Db，(D206。Vn)，且有 Select(A::=Db)={b1,b2,…,bn} ，則 LL(A,bi)=RDb)/P，(i=1,2,…,n) **R(Db)/P：表示用Db的(逆串替換A后，重讀當(dāng)前符號(hào)::=ε規(guī)則對(duì)于A::=e，且有 Select(A::=e)= {b1,b2,…,bn}則 LL(A, bi)=R(e)/P本部分主要通過(guò)VB中的InputBox對(duì)話框讀入待分析句子，并與分析表進(jìn)行對(duì)照，逐步分析所輸入的句子是否符合文法。分析過(guò)程均用一維數(shù)組進(jìn)行保存。相關(guān)程序片段如下：程序中所用到的公有數(shù)據(jù)成員有：Dim FXZ(50) As String 39。存放句子分析過(guò)程中的分析棧Dim FHZ(50) As String 39。存放句子分析過(guò)程中的輸入符號(hào)棧Public Sub juzi_read(str As String) 39。讀取句子FHZ(0) = Emptyi = 0a = Mid(str, 1, 1)Do While a Empty FHZ(i) = a a = Mid(str, i + 2, 1) i = i + 1 FHZ(i) = EmptyLoopIf FHZ(0) = Empty Then Exit SubEnd IfFHZ(i) = FHZ(i + 1) = EmptyCall fenxi_chrEnd Sub現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。然后再把相應(yīng)的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。 Do While (i, j, k) Empty Select Case (i, j, k) Case acc Exit Sub Case ε FXZ(a) = Empty Case /N FHZ(b) =