【正文】 部的符號，它們組成的集合稱為非終結(jié)符集。 終結(jié)符 ：文法中凡不屬于非終結(jié)符集的符號，它們組成的集合稱為終結(jié)符集。 遞歸 ：同一操作或一組操作的連續(xù)重復(fù)， 其實質(zhì)上是處理過程的性質(zhì)，在這種過程的每一步都要用到它自身的上一步或上幾步的結(jié)果。 遞歸定義 ：在定義某種事物時又用到其本身。 直接左遞歸規(guī)則 ：型如 U：： =Uy 的規(guī)則稱為直接左遞歸規(guī)則。 First 集 ：首符號集。 Follow 集 ：向前看集。 Select 集 ：可選集。 LL（ 1）文法 ：對于文法 G（ S），其每 個非終結(jié)符的不同規(guī)則具有不相交的Select 集，則稱該文法為 LL（ 1）文法。 自頂向下分析 對于文法 G[Z]，給頂一個待分析的句子 (字符串 )，自頂向下分析的基本思想是從識別符號 Z 開始，根據(jù)文法試著建立一個推導(dǎo)序列，若得到所給的句子，則句子得到識別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過各種推導(dǎo)都不能得到所分析的句子，則該符號串不符合文法。 或者說，從根結(jié)點出發(fā)，自上而下地建立一顆語法樹，其未端結(jié)點按從左到右的順序連接起來，構(gòu)成給定的符號串，則符號串得到識別。 例：設(shè)有文法 G[N]和符號串 25 N N::=D|ND D::=0|1|2|?|9 根據(jù)文法有： N?ND?DD?2D?25； 因此我們說 25 符合此文法 圖 1 G[N]過程分析 自頂向下分析的難點及解決辦法： N D D 5 2 第 3 頁 共 22 頁 對于形如 :U::=x1|x2|? |xn 的規(guī)則 ,可能需要對所有的規(guī)則都要試探。 該解決辦法是把文法中每個非終結(jié)符號 A 的右部稱為 A 的候選式，對候選式的選擇，則根據(jù)當(dāng)前輸入符號來決定。 方法： 首先對文法的每個規(guī)則 A::=? 求可選集 Select(A::=?)。 當(dāng) ??? 時，則對于當(dāng)前輸入的符號 a，若有 a?First(?)，則可以選用規(guī)則A::=? 進行推導(dǎo)。 若對于某非終止符號有 n條規(guī)則（即有 n 個候選式）的處理方法： 對于文法，有 A::=x1|x2|? |xn，其右部的 n個候選式的首 符號集均不相同 : 即 First(xi) ∩ First(xj)=? (i?j)，對于待分析的符號串，如果最左的非終結(jié)符號為 A，若其句子中對應(yīng)的下一個符號（當(dāng)前輸入符號）為 a，且有a?First(xk)，則選擇規(guī)則 A::=xk 來作為推導(dǎo)的候選式。 例：設(shè)有文法 G[Z]，和句子 bbabaax Z::=aV|bZ V::=baZ|x Select(Z ::=aV)={a}。 Select(Z ::=bZ)=。 Select(V ::=baZ)=。 Select(V ::=x)={x}。 Z? bZ? bbZ? bbaV? bbabaZ? bbabaaV?bbabaax (babaax) (abaax) (baax) (ax) (x) 對于文法，有 A::= x1|x2|? |xn，若有 First(xi) ∩ First(xj) ??(i?j)，采用試探法：即從首字符中有輸入符號的多個候選式中任選一個來試探，如果不成功，就換另一個接著試。試探法有可能形成回溯現(xiàn)象。對于回溯現(xiàn)象，可以通過 “ 左提因子方法 ” 對文法進行修改來 消除。 遞歸子程序 遞歸子程序方法： 這里講的遞歸子程序方法是一種自頂向下的編譯方法，其思想是通過對源程序的每個語法成分編制一個處理子程序，通過子程序調(diào)用來對源程序進行語法和 第 4 頁 共 22 頁 語義分析。 遞歸子程序及其調(diào)用： 常用的子程序的種類有 3 種： 簡單子程序， 嵌套子程序， 遞歸子程序。 三種子程序的返回地址保護方法： 返回地址保護單元。 ，不得隨意公用。 ，由于返回地址保護單元數(shù)目不明確，一般采用堆棧形式。方法是在內(nèi)存中開辟一個保護棧，每次進入遞歸子程序時，就把當(dāng)前返回地址送入保護棧，相應(yīng)地，每次退出遞歸子程序時，就取棧頂?shù)姆祷氐刂纷鳛槠浞祷氐刂?。同時入棧和出棧的還有相應(yīng)的遞歸子程序中需要保護的工作單元。 遞歸子程序調(diào)用時，入口與出口的工作： (1)遞歸入口工作： ①當(dāng)前返回地址送保護棧； ②遞歸子程序中（調(diào)用程序）不允許被破壞的工作單元內(nèi)容送保護棧。 (2)遞歸出口工作： ①恢復(fù)保護在棧頂中的工作單元的原來內(nèi)容，并上退保護棧； ②取保護在棧頂中的返回地址進行返回，并退保護棧。 LL（ K）分析方法 LL(K)分析方法是一種自頂向下的分析技術(shù)。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看 K 個符號，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。 當(dāng) K=1 時，既是 LL（ 1）分析方法。 LL（ 1）分析方法 （ 1）方法的思想：根據(jù)輸入串的當(dāng)前輸入符號，確定用某規(guī)則進行推導(dǎo)，當(dāng)推導(dǎo)的第一個符號與輸入串的當(dāng)前符號匹配時，就把輸入串的下一個字符作為當(dāng)前輸入字符，直到推導(dǎo)出輸入串。根據(jù)輸入串向前的 1個符號來確定推導(dǎo)規(guī)則時，就是 LL（ 1）方法。 (1)分 析方法的邏輯結(jié)構(gòu) 第 I 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結(jié)構(gòu) (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導(dǎo)所使用的規(guī)則。 (1)分析過程 假設(shè)分析過程中當(dāng)前句型的右端部分為： x1x2? xm， (xi?V) 輸入流（待分析串）的右端部分為： y1y2? yn， (yi?Vt) 此時有以下 3 種情況： (1)當(dāng) x1?Vn，則根據(jù)當(dāng)前輸入符號 y1 選擇相應(yīng)的規(guī)則去替換 x1。 (2)當(dāng) x1?Vt 時，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪 去x1和 y1，然后繼續(xù)向前分析；不相同表示不相配，為出錯。 (3)若上述兩個字符串均為空，則表示全部匹配，輸入串被識別。 現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當(dāng)棧頂符號與輸入串當(dāng)前符號相匹配時，則從棧頂刪除該符號。然后再把相應(yīng)的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。 (1)分析表的構(gòu)造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。如果分析棧中的元素為 A，輸入元素為 a，則其匹配關(guān)系記為 LL(A,a) LL(1)分析矩陣：一種用來 反映這種匹配關(guān)系的矩陣表示，該矩陣稱為 LL(1)分析矩陣。首先進行介紹與 LL(1)分析有關(guān)的 3個操作約定： (1)N 表示繼續(xù)下一個符號； (2)P 表示重讀當(dāng)前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 構(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ù)讀入下一個符號。 當(dāng) ? 為 ? 時，即： A::=a，有： LL(A,a)=R(?)/N A::=D?， (D?Vn)，且有 Select(A::=D?)={b1,b2,? ,bn} ， 則 LL(A,bi)=R(D?)/P， (i=1,2,? ,n) **R(D?)/P：表示用 D? 的逆串替換 A后，重讀當(dāng)前符號 A::=?，且有 Select(A::=?)= {b1,b2,? ,bn} 則 LL(A, bi)=R(?)/P a?Vt， a 不出現(xiàn)于規(guī)則右部的首部， 則令 LL(a,a)=R(?)/N ，令 LL(,)=acc 表示分析結(jié)束，輸入串得到識別。 5種情況，則置出錯，分析表中用空白表示。 2 系統(tǒng)流程 圖 項目的程序流程圖如圖 3所示： 圖 3 程序流程圖 程序開始 調(diào)用打開對話框輸入文法 優(yōu)化輸入的文法并判斷文法合法性 獲取文法的終結(jié)符和非終結(jié)符 對文法求 select 集并判斷 select 集合法性 構(gòu)造文法分析表 輸入并分析句子 結(jié)束 第 III 頁 共 22 頁 系統(tǒng)模塊流程圖 系統(tǒng)的模塊流程圖如圖 4所示 ： 圖 4 系統(tǒng)模塊流程圖 3 系統(tǒng)實施 《 一個編譯原理語法分析器的設(shè)計與實現(xiàn)》 主要分為四個模塊： 1．文件讀取模塊 文件讀取模塊主要完成將記事本中的待分析文法讀入到內(nèi)存中的功能。其中包括了對可能出現(xiàn)的文法 BNF 表示法的判 斷以及對文法中是否存在直接左遞歸規(guī)則的判斷。 2．算法分析模塊 算法分析模塊是《 一個編譯原理語法分析器的設(shè)計與實現(xiàn)》 中的關(guān)鍵模塊。本模塊包含了 LL（ 1）算法中的大部分重要數(shù)據(jù)和信息，其中包括獲取輸入文法的終結(jié)符集和非終結(jié)符集，對文法中每一條規(guī)則求 select集（ select 集的求解又包括求 first 集或者 follow 集），以及對 select 集合法性的判斷，即同一非終結(jié)符所對應(yīng)的不同規(guī)則的 select 集中不能有相同的終結(jié)符。 LL(1)算法 演示系統(tǒng) 文法輸入 文法分析 句子輸入 與分析 文法分析表 構(gòu)造 獲取終結(jié)符和非終結(jié)符 求文法的 select 集 判斷 select 集 的合法性 求 first 集 求 follow 集 第 IV 頁 共 22 頁 3．分析表構(gòu)造模塊 分析表構(gòu)造模塊的主要功能是將算法分析模塊所求解出的符合 LL（ 1）算法規(guī)則的文法的 select 集轉(zhuǎn)化成文法分析表，以便下一模塊的調(diào)用。 4．句子分析模塊 句子分析模塊是整個《 一個編譯原理語法分析器的設(shè)計與實現(xiàn) 》的主體演示模塊，包括句子讀取、句子合法性判斷、句子分析等部分。其中句子合法性的判斷又分為句子中是否有文法終結(jié)符以外的符號和句子是否符合文法規(guī)則的判斷。下面將對以上四個模塊的具體實現(xiàn)技術(shù)、數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵程序片段進行詳細的說明。 本模塊通過調(diào)用 VB 中 CommonDialog 控件的 ShowOpen 方法啟動打開文件對話框，獲取需要讀取的文件的路徑，再調(diào) 用 Open 命令打開文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進行保存。 文件讀取使用的 CommonDialog 控件介紹 CommonDialog 控件提供諸如打開和保存文件、設(shè)置打印選項、選擇顏色和字體等操作的一組標(biāo)準(zhǔn)對話框。調(diào)用打開文件對話框的具體代碼如下： Dim p_name As String 39。 文件路徑 = True On Error GoTo err = Text(*.txt)|*.txt = 1 39。 用 ShowOpen 方法顯示對話框 p_name = 39。 用 FileName 屬性獲取選定文件的名稱 文法左遞歸的判斷 文法中使用遞歸規(guī)則以后，可以用有限的規(guī)則刻劃無限語言，但不利的是對與具有左遞歸性的文法，不能采用自頂向下的分析算法。一般含有左遞歸規(guī)則的文法形式為 U::=xUy， 若 x=?, 則有 U::=Uy，即為左遞歸規(guī)則 。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(shè)計時間所限，所以本軟件沒有這項功能，只是對直接左遞歸進行錯誤判斷。 Do While WF(j, 0) Empty 39。 判斷文法是否有左遞歸 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ù)組中；最后