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