編譯原理試驗(yàn)課程教案

1、安徽大學(xué)實(shí)驗(yàn)課程教案課程名稱(chēng)編譯原埋課程屬性專(zhuān)業(yè)基礎(chǔ)開(kāi)課學(xué)年開(kāi)課學(xué)期年級(jí)專(zhuān)業(yè)主講教師課程所屬院系部計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程所屬系（教研室）實(shí)驗(yàn)一名稱(chēng)Chomsky文法類(lèi)型判斷一、背景帽料1956年，N.Chomsky首先對(duì)形式語(yǔ)言進(jìn)行了描述。N.Chomsky在對(duì)某些自然語(yǔ) 言進(jìn)行研究的基礎(chǔ)上，提出了一種用于描述語(yǔ)言和文法的數(shù)學(xué)系統(tǒng)， 按照對(duì)文法 規(guī)則的不同定義形式，對(duì)語(yǔ)言和文法分成了 4類(lèi)，對(duì)每一類(lèi)語(yǔ)言，讓它與一種特 定種類(lèi)的自動(dòng)機(jī)那樣的識(shí)別器聯(lián)系起來(lái)。 形式語(yǔ)言理論的形成與發(fā)展，對(duì)計(jì)算機(jī) 科學(xué)的發(fā)展是一個(gè)推動(dòng)，在程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與編譯實(shí)現(xiàn)以及計(jì)算復(fù)雜性等方 面都有著重大影響。二、實(shí)驗(yàn)?zāi)康?/p>

2、要求輸入：一組任意的規(guī)則。輸出：相應(yīng)的Chomsky文法的類(lèi)型。三、實(shí)驗(yàn)原理0型文法（短語(yǔ)文法）如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式： u: = v其中uCV + , vCV*,則稱(chēng)該文法G為0型文法或短語(yǔ)文法，簡(jiǎn)寫(xiě)為 PSG。0型文法或短語(yǔ)結(jié)構(gòu)文法的相應(yīng)語(yǔ)言稱(chēng)為 0型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言L0o這種 文法由于沒(méi)有其他任何限制，因此0型文法也稱(chēng)為無(wú)限制文法，其相應(yīng)的語(yǔ)言稱(chēng) 為無(wú)限制性語(yǔ)言。任彳0型語(yǔ)言都是遞歸可枚舉的，故0型語(yǔ)言又稱(chēng)遞歸可枚舉 集。這種語(yǔ)言可由圖靈機(jī)（Turning）來(lái)識(shí)別。1型文法（上下文有關(guān)文法）如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式： xUy二=xuy其中U

3、CVn; u V+; x, yCV*,則稱(chēng)該文法G為1型文法或上下文有關(guān) 文法，也稱(chēng)上下文敏感文法，簡(jiǎn)寫(xiě)為 CSG。1型文法的規(guī)則左部的U和右部的u具有相同的上文x和下文y,利用該規(guī) 則進(jìn)行推導(dǎo)時(shí)，要用u替換U,必須在前面有x和后面有y的情況下才能進(jìn)行， 顯示了上下文有關(guān)的特性。1型文法所確定的語(yǔ)言為1型語(yǔ)言Li,1型語(yǔ)言可由線(xiàn)性有界自動(dòng)機(jī)來(lái)識(shí)別。2型文法（上下文無(wú)關(guān)文法）如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式： U : = u其中UCVn； uCV+,則稱(chēng)該文法G為2型文法或上下文無(wú)關(guān)文法，簡(jiǎn)寫(xiě)為 CFGo按照這條規(guī)則，對(duì)于上下文無(wú)關(guān)文法，利用該規(guī)則進(jìn)行推導(dǎo)時(shí)，無(wú)需考慮非 終結(jié)符U所

4、在的上下文，總能用u替換U,或者將u歸約為U,顯示了上下文 無(wú)關(guān)的特點(diǎn)。2型文法所確定的語(yǔ)言為2型語(yǔ)言L2, 2型語(yǔ)言可由非確定的下推自動(dòng)機(jī)來(lái) 識(shí)別。一般定義程序設(shè)計(jì)語(yǔ)言的文法是上下文無(wú)關(guān)的。如C語(yǔ)言便是如此。因此，上下文無(wú)關(guān)文法及相應(yīng)語(yǔ)言引起了人們較大的興趣與重視。3型文法(正則文法，線(xiàn)性文法)如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = WT其中TCVt; U,WCVn,則稱(chēng)該文法G為左線(xiàn)性文法。如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = TW其中TCVt; U, WCVn,則稱(chēng)該文法G為右線(xiàn)性文法。左線(xiàn)性文法和右線(xiàn)性文

5、法通稱(chēng)為 3型文法或正則文法，有時(shí)又稱(chēng)為有窮狀態(tài) 文法，簡(jiǎn)寫(xiě)為RGo按照定義，對(duì)于正則文法應(yīng)用規(guī)則時(shí)，單個(gè)非終結(jié)符號(hào)只能被替換為單個(gè)終 結(jié)符號(hào)，或被替換為單個(gè)非終結(jié)符號(hào)加上單個(gè)終結(jié)符號(hào)， 或者被替換為單個(gè)終結(jié) 符號(hào)加上單個(gè)非終結(jié)符號(hào)。3型文法所確定的語(yǔ)言為3型語(yǔ)言L3, 3型語(yǔ)言可由確定的有窮狀態(tài)自動(dòng)機(jī) 來(lái)識(shí)別。在常見(jiàn)的程序設(shè)計(jì)語(yǔ)言中，多數(shù)與詞法有關(guān)的文法屬于3型文法?？梢钥闯?，上述4類(lèi)文法，從0型到3型，產(chǎn)生式限制越來(lái)越強(qiáng)，其后一 類(lèi)都是前一類(lèi)的子集，而描述語(yǔ)言的功能越來(lái)越弱，四類(lèi)文法及其表示的語(yǔ)言 之間的關(guān)系可表示為：0 型二1 型二2 型二3 型；即 Lon Lin L2n L3四、注意

6、事項(xiàng) 文法的輸入應(yīng)簡(jiǎn)便。 指明是哪一類(lèi)Chomsky文法，并給出相應(yīng)的四元組 形式：G = ( Vn,V t , P , S)。說(shuō)明：簡(jiǎn)單起見(jiàn)， 可以不考慮0型文法類(lèi)。實(shí)驗(yàn)二名稱(chēng) I正規(guī)文法和正規(guī)式等價(jià)轉(zhuǎn)換一、背景資料一個(gè)文法可以定義某種語(yǔ)言，而一個(gè)特定的語(yǔ)言也可以由文法來(lái)描述。但文法與語(yǔ)言之間并不存在對(duì)應(yīng)的關(guān)系。形式語(yǔ)言理論已經(jīng)證明：(1)給定一個(gè)文法，就能從結(jié)構(gòu)上惟一地確定其語(yǔ)言，即CAL (G)(2)給出文法后，語(yǔ)言也就相應(yīng)地確定了，其語(yǔ)言可以是有窮的，也可以是無(wú) 限的。二、實(shí)驗(yàn)?zāi)康囊筝斎耄喝我獾恼?guī)文法。輸出：相應(yīng)的正規(guī)式。三、實(shí)驗(yàn)原理3型文法(正則文法，線(xiàn)性文法)如果對(duì)于某文法G,

7、 P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = WT其中TCVt; U,WCVn,則稱(chēng)該文法G為左線(xiàn)性文法。如果對(duì)于某文法G, P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = TW其中TCVt; U, WCVn,則稱(chēng)該文法G為右線(xiàn)性文法。左線(xiàn)性文法和右線(xiàn)性文法通稱(chēng)為 3型文法或正則文法，有時(shí)又稱(chēng)為有窮狀態(tài) 文法，簡(jiǎn)寫(xiě)為RGo按照定義，對(duì)于正則文法應(yīng)用規(guī)則時(shí)，單個(gè)非終結(jié)符號(hào)只能被替換為單個(gè)終 結(jié)符號(hào)，或被替換為單個(gè)非終結(jié)符號(hào)加上單個(gè)終結(jié)符號(hào)， 或者被替換為單個(gè)終結(jié) 符號(hào)加上單個(gè)非終結(jié)符號(hào)。3型文法所確定的語(yǔ)言為3型語(yǔ)言L3, 3型語(yǔ)言可由確定的有窮狀態(tài)自動(dòng)機(jī) 來(lái)識(shí)別。程

8、序設(shè)計(jì)語(yǔ)言的單詞可由正則文法產(chǎn)生， 例如，標(biāo)識(shí)符的定義可由正則文法 描述如下：標(biāo)識(shí)符 := 字母/標(biāo)識(shí)符 字母/標(biāo)識(shí)符 數(shù)字顯然，該文法描述了以字母開(kāi)頭的字母數(shù)字用的集合。 現(xiàn)在要引入另一種適 合于描述單詞的表示法 一一正則表達(dá)式。正則表達(dá)式又稱(chēng)為正則式，每個(gè)正則表 達(dá)式描述的集合稱(chēng)為正則集。之所以采用正則表達(dá)式來(lái)描述，主要基于以下幾點(diǎn)原因：(1)詞法規(guī)則簡(jiǎn)單，無(wú)需上下文無(wú)關(guān)文法那樣嚴(yán)格的表示法，用正則式表示法來(lái)理解被定義的符號(hào)集合比理解由重寫(xiě)規(guī)則集合定義的語(yǔ)言更為容 易；(2)從正則式構(gòu)造高效識(shí)別程序比上下文無(wú)關(guān)文法更容易；(3)可以從某個(gè)正則式自動(dòng)地構(gòu)造識(shí)別程序， 它可以識(shí)別用該正則式表示

9、 的字符串集合中的字符串，從而減輕后面要介紹的詞法分析時(shí)的工作量。(4)可用于其他各種信息流的處理，例如，已經(jīng)應(yīng)用于某些模式識(shí)別問(wèn)題、 文獻(xiàn)目錄檢索系統(tǒng)以及正文編輯程序等。正則表達(dá)式和正則集設(shè)有字母表B E上的正則表達(dá)式和它所表示的正則集遞歸地定義如下：e和都是E上的正則表達(dá)式，它們所表示的正則集分別為 e和， 其中e是空用，是空集；(2)任意的aC上是正則表達(dá)式，它所表示的正則集是a;(3)如果ei和e2是工上的任意的正則表達(dá)式，且分別表示的正則集為L(zhǎng) (ei) 和 L (e2),貝1:ei/女也是正則表達(dá)式，表示的正則集為L(zhǎng) (ei/ e2)=L (ei) UL (金)。ei e2也是正則

10、表達(dá)式，表示的正則集為 L (ei e2)=L (ei) L (e?)。(ei)也是正則表達(dá)式，表小的正則集為 L (ei) ) = L (ei)。定義中(i)和(2)定義了原子正則表達(dá)式，而(3)則表明字母表H上的正 則表達(dá)式可由原子正則表達(dá)式或較簡(jiǎn)單的正則表達(dá)式通過(guò)聯(lián)合、 連接與閉包運(yùn)算 構(gòu)成一般的正則表達(dá)式。正則表達(dá)式的性質(zhì)如果兩個(gè)正則表達(dá)式ei和金表示的正則集相同，即值相等，則稱(chēng)它們是等 價(jià)的。記為ei = &。正則表達(dá)式與正則文法的關(guān)系一個(gè)正則表達(dá)式的值是正則集，它是正則語(yǔ)言的另一種表示法。不難看出， 除了符號(hào)外，一個(gè)正則表達(dá)式的含義類(lèi)似于正則文法的一個(gè)非終結(jié)符號(hào)規(guī)則 右部的含義。例

11、如，對(duì)于 數(shù)字 :k0/i/2/；/9非終結(jié)符數(shù)字所產(chǎn)生的字符串集合與正則表達(dá)式0/i/2/所定義的字符串集合是相同的。正則集 ，它對(duì)應(yīng) 一個(gè)不包含任何句子的語(yǔ)言，引進(jìn)的目的主要是為了理論上的完備性。四、注意事項(xiàng)要求：輸出界面為：正規(guī)文法正規(guī)式實(shí)驗(yàn)三名稱(chēng)|不確定有窮自動(dòng)機(jī)的確定化一、背景資料有窮自動(dòng)機(jī)(FA)可以看作是由一個(gè)帶有讀頭的有窮控制器和一條字符輸 入帶組成，如圖所示。a a a b b b c c輸入帶控制器FA的示意圖控制器的讀頭從左至右順次掃描輸入帶，每當(dāng)從輸入帶上讀到一個(gè)符號(hào)時(shí)， 便引起控制器狀態(tài)的改變，同時(shí)讀頭右移一個(gè)符號(hào)位。控制器包括有窮個(gè)狀態(tài)，狀態(tài)和狀態(tài)之間存在轉(zhuǎn)換關(guān)系。

12、當(dāng)處于某個(gè)狀態(tài)， 讀入一個(gè)字符時(shí)，則使?fàn)顟B(tài)改變?yōu)榱硪粋€(gè)狀態(tài)，從而形成狀態(tài)轉(zhuǎn)換，改變后的狀 態(tài)稱(chēng)為后繼狀態(tài)。狀態(tài)轉(zhuǎn)換后的后繼狀態(tài)有三種可能情況：(1)后繼狀態(tài)為自身；(2)后繼狀態(tài)為一個(gè)；(3)后繼狀態(tài)為若干個(gè)。某個(gè)有窮自動(dòng)機(jī)，如果每次狀態(tài)轉(zhuǎn)換的后繼狀態(tài)都是惟一的，則稱(chēng)它是 確定有窮自動(dòng)機(jī)(DFA);如果轉(zhuǎn)換后的后繼狀態(tài)并不都是惟一的，則稱(chēng)它是 不確定有窮自動(dòng)機(jī)(NFA)。有窮自動(dòng)機(jī)的開(kāi)始工作狀態(tài)稱(chēng)為初始狀態(tài)，結(jié)束工作的狀態(tài)稱(chēng)為終止工作 狀態(tài)或接收狀態(tài)。如果把上一小節(jié)中的狀態(tài)轉(zhuǎn)換圖的各個(gè)結(jié)點(diǎn)看成是某一個(gè)狀 態(tài)，初始結(jié)點(diǎn)為初始狀態(tài)，終止結(jié)點(diǎn)為終止?fàn)顟B(tài)，并且每一條邊表示一個(gè)轉(zhuǎn)換 關(guān)系，這樣一個(gè)有窮自

13、動(dòng)機(jī)的工作狀態(tài)就可以采用狀態(tài)轉(zhuǎn)換圖來(lái)描述了，從而 可以把前面的圖看成是一個(gè)有窮自動(dòng)機(jī)。對(duì)于上圖，有窮自動(dòng)機(jī)處在初始狀態(tài) 0,當(dāng)讀入符號(hào)a后，自動(dòng)機(jī)便從狀態(tài) 0轉(zhuǎn)換到后繼狀態(tài)1中，再讀入一個(gè)符號(hào)b后，自動(dòng)機(jī)便從狀態(tài)1轉(zhuǎn)換到后繼狀 態(tài)2。當(dāng)自動(dòng)機(jī)讀入一個(gè)符號(hào)用，自動(dòng)機(jī)則從初始狀態(tài)開(kāi)始，經(jīng)過(guò)一系列狀態(tài)轉(zhuǎn) 換，最終若能夠到達(dá)終止?fàn)顟B(tài)，則稱(chēng)這一符號(hào)用被該自動(dòng)機(jī)所接收或識(shí)別， 否則 不能被該自動(dòng)機(jī)所接收。二、實(shí)驗(yàn)?zāi)康囊筝斎耄悍谴_定有窮(窮)狀態(tài)自動(dòng)機(jī)。輸出：確定化的有窮(窮)狀態(tài)自動(dòng)機(jī)三、實(shí)驗(yàn)原理一個(gè)確定的有窮自動(dòng)機(jī)(DFA M可以定義為一個(gè)五元組，M= (K,三,F, S, Z),其中：K是一個(gè)有窮非

14、空集，集合中的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；匯是一個(gè)有窮字母表，匯中的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)；F是一個(gè)從KX匯一 K的單值轉(zhuǎn)換函數(shù)，即 F (R, a) =Q (R, QC K)表示當(dāng)前 狀態(tài)為R,如果輸入字符 a,則轉(zhuǎn)到狀態(tài) Q,狀態(tài)Q稱(chēng)為狀態(tài)R的后繼狀態(tài)；SC K,是惟一的初態(tài)；ZGK,是一個(gè)終態(tài)集。由定義可見(jiàn)，確定有窮自動(dòng)機(jī)只有惟一的一個(gè)初態(tài)，但可以有多個(gè)終態(tài)，每個(gè)狀態(tài)對(duì)字母表中的任一輸入符號(hào)，最多只有一個(gè)后繼狀態(tài)。對(duì)于DFAM,若存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，則稱(chēng)這條通路上的所有弧的標(biāo)記符連接形成的字符串可為 DFAM所接受。若M的初態(tài)結(jié) 點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則稱(chēng)e可為M所接

15、受(或識(shí)別)，DFA M所能接受的全部 字符串(字)組成的集合記作L (Mo一個(gè)不確定有窮自動(dòng)機(jī)(NFA M可以定義為一個(gè)五元組，(K,三，F(xiàn), S, Z),其中：k是一個(gè)有窮非空集，集合中的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；匯是一個(gè)有窮字母表，匯中的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)；F是一個(gè)從KX匯一 K的子集的轉(zhuǎn)換函數(shù)；S 三 K,是一一個(gè)非空的初態(tài)集；ZJK,是一個(gè)終態(tài)集。由定義可見(jiàn)，不確定有窮自動(dòng)機(jī) NFA與確定有窮自動(dòng)機(jī)DFA的主要區(qū)別是：NFAB初始狀態(tài)S為一個(gè)狀態(tài)集，即允許有多個(gè)初始狀態(tài)；NFA中允許狀態(tài)在某輸出邊上有相同的符號(hào)，即對(duì)同一個(gè)輸入符號(hào)可 以有多個(gè)后繼狀態(tài)。即 DFA中的F是單值函數(shù)，而

16、NFA中的F是多值函數(shù)。因此，可以將確定有窮自動(dòng)機(jī)DFA看作是不確定有窮自動(dòng)機(jī) NFAB特例。和 DFA一樣，NFA也可以用矩陣和狀態(tài)轉(zhuǎn)換圖來(lái)表示。對(duì)于NFAM,若存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，則稱(chēng)這 條通路上的所有弧的標(biāo)記(除外)連接形成的字符串可為 M所接受。NFAM所 能接受的全部字符串(字)組成的集合記作 L (M)o由于DFA NFA的特例，所以能被DFA聽(tīng)接受的符號(hào)用必能被NFMT接受。設(shè)M和M是同一個(gè)字母集匯上的有窮自動(dòng)機(jī)，若 L (M) =L (M2),則稱(chēng)有 窮自動(dòng)機(jī)M和M等價(jià)。由以上定義可知，若兩個(gè)自動(dòng)機(jī)能夠接受相同的語(yǔ)言，則稱(chēng)這兩個(gè)自動(dòng)機(jī)等 價(jià)。DFA N

17、FAB特例，因此對(duì)于每一個(gè) NFAM總存在一個(gè)DFAM,使得L (M) =L (M)。即一個(gè)不確定有窮自動(dòng)機(jī)能接受的語(yǔ)言總可以找到一個(gè)等價(jià)的確定有 窮自動(dòng)機(jī)來(lái)接受該語(yǔ)言。NFA確定化為DFA同一個(gè)字符串a(chǎn)可以由多條通路產(chǎn)生，而在實(shí)際應(yīng)用中，作為描述控制過(guò)程 的自動(dòng)機(jī)，通常都是確定有窮自動(dòng)機(jī) DFA因此這就需要將不確定有窮自動(dòng)機(jī)轉(zhuǎn) 換成等價(jià)的確定有窮自動(dòng)機(jī)，這個(gè)過(guò)程稱(chēng)為不確定有窮自動(dòng)機(jī)的確定化，即 NFA 確定化為DFA下面介紹一種NFA的確定化算法，這種算法稱(chēng)為子集法：(1)若NFA的全部初態(tài)為 Si, 5, , S,則令DFA的初態(tài)為：S= Si, S2, , S,其中方括號(hào)用來(lái)表示若干個(gè)狀

18、態(tài)構(gòu)成的某一狀態(tài)。(2)設(shè)DFA的狀態(tài)集K中有一狀態(tài)為Si, S+i , , , S,若對(duì)某符號(hào) aE,在NFA 中有 F ( Si, Si+i，Sj , a) = S i , Si+i，& 則令 F ( S , S+i , , , S , a) = S , S+i , , , Sk 為 DFA的一個(gè)轉(zhuǎn)換函數(shù)。若S i , S+1 , , , Sk 不在K中，則將其作為新的狀態(tài)加入到K中。(3)重復(fù)第2步，直到K中不再有新的狀態(tài)加入為止。(4)上面得到的所有狀態(tài)構(gòu)成 DFA的狀態(tài)集K,轉(zhuǎn)換函數(shù)構(gòu)成 DFA的F, DFA的字母表 仍然是NFA的字母表匯。(5) DFA中凡是含有 NFA終態(tài)的狀態(tài)

19、都是 DFA的終態(tài)。對(duì)于上述NFA確定化算法一一子集法，還可以采用另一種操作性更強(qiáng)的描述 方式，下面我們給出其詳細(xì)描述。首先給出兩個(gè)相關(guān)定義。假設(shè)I是NFA M狀態(tài)集K的一個(gè)子集(即I C K ,則定義 -closure (I)(1)若 QC I ,則 QC e -closure (I );(2)若QC I ,則從 Q出發(fā)經(jīng)過(guò)任意條e弧而能到達(dá)的任何狀態(tài)Q ,則 Q e e-closure (I )。狀態(tài)集e -closure (I )稱(chēng)為狀態(tài)I的e閉包。假設(shè) NFAMk (K,三，F(xiàn), S, Z),若I CK, aE,則定義 Ia= closure (J), 其中J是所有從c -closur

20、e (I)出發(fā)，經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集。NFAft定化的實(shí)質(zhì)是以原有X態(tài)集上的子集作為 DFA上的一個(gè)狀態(tài)，將原狀 態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有窮自動(dòng)機(jī)確定化。經(jīng)過(guò)確定化后， 狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)就需要簡(jiǎn)化。四、注意事項(xiàng)(1)實(shí)現(xiàn)計(jì)算閉包c(diǎn)losure (I)的算法；實(shí)現(xiàn)轉(zhuǎn)換函數(shù)move (q, a)的算法;輸出界面如下：NFA的圖形形式DFA的圖形形式實(shí)驗(yàn)四名稱(chēng)|確定有窮自動(dòng)機(jī)的最小化一、背景資料NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的子集作為 DFA上的一個(gè)狀態(tài)，將原 狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有窮自動(dòng)機(jī)確定化。經(jīng)過(guò)確定化 后，狀態(tài)數(shù)

21、可能增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)就需要簡(jiǎn)化。、實(shí)驗(yàn)?zāi)康囊筝斎耄篋FA。輸出：最小化的DFA 三、實(shí)驗(yàn)原理所謂自動(dòng)機(jī)的化簡(jiǎn)問(wèn)題即是對(duì)任何一個(gè)確定有窮自動(dòng)機(jī)DFAM,構(gòu)造另一個(gè)確定有窮自動(dòng)機(jī)DFA M ,有L (M =L (MT ),并且MT的狀態(tài)個(gè)數(shù)不多于 M 的狀態(tài)個(gè)數(shù)，而且可以肯定地說(shuō)，能夠找到一個(gè)狀態(tài)個(gè)數(shù)為最小的M。下面首先來(lái)介紹一些相關(guān)的基本概念。設(shè)S是自動(dòng)機(jī)M的一個(gè)狀態(tài)，從S出發(fā)能導(dǎo)出的所有符號(hào)用集合記為L(zhǎng)(S)0 設(shè)有兩個(gè)狀態(tài)S和S ,若有L (S) = L (S),則稱(chēng)S和S是等價(jià)狀態(tài)。下圖所示的自動(dòng)機(jī)中L (B) =L (C) =1,所有狀態(tài)B和狀態(tài)C是等價(jià) 狀態(tài)。又例

22、如終態(tài)導(dǎo)出的符號(hào)用集合中必然包含空用 8,而非終止?fàn)顟B(tài)導(dǎo)出的符號(hào) 用集合中不可能包含空用 ,所以終態(tài)和非終止?fàn)顟B(tài)是不等價(jià)的。對(duì)于等價(jià)的概念，我們還可以從另一個(gè)角度來(lái)給出定義。給定一個(gè)DFA M如果從某個(gè)狀態(tài)P開(kāi)始，以字符用w作為輸入，DFA M# 結(jié)束于終態(tài)，而從另一狀態(tài) Q開(kāi)始，以字符用w作為輸入，DFAM將結(jié)束于非終 止?fàn)顟B(tài)，則稱(chēng)字符串w把狀態(tài)P和狀態(tài)Q區(qū)分開(kāi)來(lái)。把不可區(qū)分開(kāi)來(lái)的兩個(gè)狀態(tài)稱(chēng)為等價(jià)狀態(tài)。設(shè)S是自動(dòng)機(jī)M的一個(gè)狀態(tài)，如果從開(kāi)始狀態(tài)不可能達(dá)到該狀態(tài)S,則稱(chēng)S為無(wú)用狀態(tài)。設(shè)S是自動(dòng)機(jī)M的一個(gè)狀態(tài)，如果對(duì)任何輸入符號(hào) a都轉(zhuǎn)到其本身，而不 可能達(dá)到終止?fàn)顟B(tài)，則稱(chēng)S為死狀態(tài)?；?jiǎn)DFA關(guān)

23、鍵在于把它的狀態(tài)集分成一些兩兩互不相交的子集，使得任何兩 個(gè)不相交的子集間的狀態(tài)都是可區(qū)分的，而同一個(gè)子集中的任何兩個(gè)狀態(tài)都是等 價(jià)的，這樣可以以一個(gè)狀態(tài)作為代表而刪去其他等價(jià)的狀態(tài)，然后將無(wú)關(guān)狀態(tài)刪 去，也就獲得了狀態(tài)數(shù)最小的 DFA下面具體介紹DFA的化簡(jiǎn)算法：(1)首先將DFA M的狀態(tài)劃分出終止?fàn)顟B(tài)集 K和非終止?fàn)顟B(tài)集K= KiU K2由上述定義知，Ki和&是不等價(jià)的。(2)對(duì)各狀態(tài)集每次按下面的方法進(jìn)一步劃分，直到不再產(chǎn)生新的劃分。設(shè)第i次劃分已將狀態(tài)集劃分為k組，即：K= Ki(i) U ( U , U K(i)對(duì)于狀態(tài)集K(i)(j=1,2, , ,k)中的各個(gè)狀態(tài)逐個(gè)檢查，設(shè)有

24、兩個(gè)狀態(tài) K、KJ C K，且對(duì)于輸入符號(hào)a,有：F (K , a) =KmF (K , a) = K.如果?？?屬于同一個(gè)狀態(tài)集合，則將 K和K放到同一集合中, 否則將K和K分為兩個(gè)集合。(3)重復(fù)第(2)步，直到每一個(gè)集合不能再劃分為止，此時(shí)每個(gè)狀態(tài)集合 中的狀態(tài)均是等價(jià)的。(4)合并等價(jià)狀態(tài)，即在等價(jià)狀態(tài)集中取任意一個(gè)狀態(tài)作為代表，刪去其 他一切等價(jià)狀態(tài)。(5)若有無(wú)關(guān)狀態(tài)，則將其刪去。根據(jù)以上方法就將確定有窮自動(dòng)機(jī)進(jìn)行了簡(jiǎn)化，而且簡(jiǎn)化后的自動(dòng)機(jī)是原自動(dòng)機(jī)的狀態(tài)最少的自動(dòng)機(jī)。四、注意事項(xiàng)要求： 實(shí)現(xiàn)子集劃分算法;輸出界面如下：DFA的圖形形式最小DFA的圖形形式實(shí)驗(yàn)五名稱(chēng) | LL(1)

25、文法的轉(zhuǎn)換和判斷一背景資料如果一個(gè)文法具有以下兩個(gè)特點(diǎn)：每個(gè)產(chǎn)生式的右部都由終結(jié)符開(kāi)始；如果兩個(gè)產(chǎn)生式有相同的左部，那么他們的右部則由不同的終結(jié)符 開(kāi)始。顯然對(duì)于這樣的文法，其推導(dǎo)過(guò)程完全可以根據(jù)當(dāng)前的輸入符號(hào)，決定選哪 個(gè)產(chǎn)生式往下推導(dǎo)，分析過(guò)程是惟一確定的，可以采用不帶回溯的自上而下的預(yù) 測(cè)分析方法。如果兩個(gè)產(chǎn)生式的左部相同，而右部都由非終結(jié)符開(kāi)始，例如，存在A-a/ 3 a和B均以非終結(jié)符開(kāi)始，那么就很難決定何時(shí)使用 A-a選項(xiàng)，何時(shí)使用A 一 B選項(xiàng)。二、實(shí)驗(yàn)?zāi)康囊筝斎耄喝我獾纳舷挛臒o(wú)關(guān)文法。輸出：(1)是否為L(zhǎng)L 文法；若是LL(1)文法，輸出每條產(chǎn)生式的select集；(3)若不

26、是LL(1)文法，看看是否含有左公共因子或者含有左遞歸，并 用相應(yīng)的算法將非LL(1)文法變成LL(1)文法，并輸出新文法中每條產(chǎn)生 式的select集。對(duì)于文法GS的開(kāi)始符號(hào)S,有# FOLLOW (S);若文法GS中有形如B-xAy的規(guī)則，其中x, y V ,則FIRST(y) e忙 FOLLOW (A);若文法GS中有形如B-xA的規(guī)則，或形如B-xAy的規(guī)則且 FIRST (y),其中 x, y V *,貝 U FOLLOW (B) FOLLOW (A);.計(jì)算每個(gè)產(chǎn)生式 A- a的SELECT(A - a )集按定義計(jì)算 SELECT(A - a ):(1)若 a 永遠(yuǎn)推導(dǎo)不出 s

27、,則 SELECT(A 一 a )=FIRST( a )(2)若 a 可能推導(dǎo)出 s ,貝U SELECT(A 一 a )=(FIRST( a )- s ) U FOLLOW(A). 一個(gè)上下文無(wú)關(guān)文法 G是LL(1)文法，當(dāng)且僅當(dāng)對(duì) G中每個(gè)非終結(jié)符 A的任何兩個(gè)不 同的規(guī)則 A- a | 3 ,滿(mǎn)足SELECT(A 一 a ) A SELECT(A - 3 )=，其中a、3中至多只有 一個(gè)能推出串。四、材料、試劑及儀器微機(jī)五、實(shí)驗(yàn)步驟(包括操作方法、數(shù)據(jù)處理) 六、注意事項(xiàng) 能處理含e 一產(chǎn)生式的上下文無(wú)關(guān)文法； 程序的輸出應(yīng)包括巾rst集合、follow集合以及所給定的文法是否為 LL

28、(1) 文法的信息，輸出界面如下：非終結(jié)符firstfollow判定結(jié)論實(shí)驗(yàn)六名稱(chēng) |自動(dòng)生成LR (0)分析表一、背景資料LR (K)分析方法是1965年Knuth首先提出的，這里的L是指從左至右掃 描輸入符號(hào)用，R是指構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程，K是指為了做出分析決定而 向前看的輸入符號(hào)的個(gè)數(shù)。LR (K)分析方法是當(dāng)前最廣義的無(wú)回溯的“移進(jìn)-歸 約”方法。根據(jù)棧中的符號(hào)用和向右順序查看輸入用的K(KM)個(gè)符號(hào)，就能惟一確定分析器的動(dòng)作是移進(jìn)還是歸約，以及用哪個(gè)產(chǎn)生式進(jìn)行歸約。自下而上分析方法是一種移進(jìn)-歸約過(guò)程，當(dāng)分析棧的棧頂符號(hào)用形成句柄 時(shí)就采取歸約動(dòng)作，因而自下而上分析法的關(guān)鍵問(wèn)題是

29、在分析過(guò)程中如何確定句 柄。LR分析法根據(jù)分析棧中的符號(hào)用(通常以狀態(tài)表示)和向右順序查看輸入 用的K個(gè)(K0)符號(hào)就可惟一地確定分析器的動(dòng)作是移進(jìn)還是歸約以及用哪 個(gè)產(chǎn)生式歸約，因而也就能惟一地確定句柄。LR分析法的歸約過(guò)程是規(guī)范推導(dǎo) 的逆過(guò)程，所以LR的分析過(guò)程是一種規(guī)范歸約過(guò)程。LR分析方法的基本思想是，在規(guī)范歸約過(guò)程中，一方面記住已移進(jìn)和歸約 出的整個(gè)符號(hào)用，即記住“歷史”，另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能碰 到的輸入符號(hào)，即對(duì)未來(lái)進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)用呈現(xiàn)于分析棧 的頂端時(shí)，我們希望能夠根據(jù)所記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入 符號(hào)這3方面的材料，來(lái)確定棧頂

30、的符號(hào)用是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。LR分析法的基本思想是符合哲理的。所以，這種分析法也是非常一般的。 因此，實(shí)現(xiàn)起來(lái)也就非常困難。作為歸約過(guò)程的“歷史”材料的積累雖不困難(實(shí) 際上，這些材料都保存在分析棧中)，但是，“展望”材料的匯集卻是一件很不容 易的事情。這種困難不是理論上的，而是實(shí)際實(shí)現(xiàn)上的。因?yàn)椋鶕?jù)歷史推測(cè)未 來(lái)，即使是推測(cè)未來(lái)的一個(gè)符號(hào)，也常常存在著很多可能性。所以，當(dāng)把“歷史”和“展望”材料綜合在一起時(shí)，復(fù)雜性就大大增加。如果簡(jiǎn)化對(duì)“展望”材 料的要求，我們就可能獲得實(shí)際可行的分析算法。LR分析法比起自上向下的LL分析法和自下向上的優(yōu)先分析方法對(duì)文法的 限制要少得多，也就是說(shuō)

31、，對(duì)于大多數(shù)用無(wú)二義性上下文無(wú)關(guān)文法描述的語(yǔ)言都 可以用相應(yīng)的LR分析器進(jìn)行識(shí)別，而且這種方法還具有分析速度快、準(zhǔn)確、及 時(shí)地指出出錯(cuò)位置的優(yōu)點(diǎn)。LR分析法的一個(gè)主要缺點(diǎn)是，若用手工構(gòu)造分析程 序，則工作量相當(dāng)大，因此，必須求助于自動(dòng)產(chǎn)生這種分析程序的產(chǎn)生器。這種 產(chǎn)生器稱(chēng)為L(zhǎng)R分析程序自動(dòng)產(chǎn)生器。本章我們將討論這樣一類(lèi)產(chǎn)生器，利用這 種產(chǎn)生器，我們不僅能自動(dòng)產(chǎn)生一大類(lèi)上下文無(wú)關(guān)文法的LR分析程序，還能指出文法含二義的情形或難于分析的特殊結(jié)構(gòu)。、實(shí)驗(yàn)?zāi)康囊筝斎耄喝我獾膲嚎s了的上下文無(wú)關(guān)文法輸出：相應(yīng)的LR (0)分析表。我們需要定義一個(gè)重要概念一一文法的規(guī)范句型“活前綴”。這種句柄之后不含任

32、何符號(hào)的前綴稱(chēng)為活前綴。在LR分析工作過(guò)程中的任何時(shí)候，棧里的文法符號(hào)(自棧底而上)X1X2,Xm應(yīng)該構(gòu)成活前綴，把輸入用的剩余部分配上之后即應(yīng)成為規(guī)范句型(如果整 個(gè)輸入用確實(shí)構(gòu)成一個(gè)句子)。因此，只要輸入用的已掃描部分保持可歸約成一 個(gè)活前綴，那就意味著所掃描過(guò)的部分沒(méi)有錯(cuò)誤。對(duì)于一個(gè)文法G,我們可以構(gòu)造一個(gè)有窮自動(dòng)機(jī)，它能識(shí)別 G的所有活前 綴，然后把這個(gè)自動(dòng)機(jī)轉(zhuǎn)變成 LR分析表，按照該LR分析表進(jìn)行LR分析，就 能保證在分析的過(guò)程中，如果分析的句子是正確的，棧里的文法符號(hào)(自棧底而 上)始終構(gòu)成活前綴。假若一個(gè)文法G的拓廣文法G，的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)(項(xiàng)目集) 不存在下述情況

33、：(1)既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目；(2)含有多個(gè)歸約項(xiàng)目，則 稱(chēng)G是一個(gè)LR (0)文法。該自動(dòng)機(jī)的狀態(tài)集合即為該文法的 LR (0)項(xiàng)目集 規(guī)范族。構(gòu)造識(shí)別文法活前綴DFA有3種方法：(1)根據(jù)形式定義求出活前綴的正則表達(dá)式， 然后由此正則表達(dá)式構(gòu)造NFA 再確定為DFA;(2)求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA;(3)使用閉包函數(shù)(CLOSURE)和轉(zhuǎn)向函數(shù)(GO(I,X)構(gòu)造文法G的LR(0) 的項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系來(lái)得到識(shí)別活前綴的 DFA。符號(hào)用的前綴是指該符號(hào)用的任意首部，包括空用一例如，對(duì)于符號(hào)用abc, 其前綴有 ,

34、 a, ab, abc。如果輸入用沒(méi)有錯(cuò)誤的話(huà)，一個(gè)規(guī)范句型的活前綴是 該句型的一個(gè)前綴，但它不含句柄之后的任何符號(hào)。之所以稱(chēng)為活前綴，是因?yàn)?在該前綴后聯(lián)接尚未輸入的符號(hào)用可以構(gòu)成一個(gè)規(guī)范句型?；钋熬Y與句柄的關(guān)系如下：(1)活前綴已含有句柄的全部符號(hào)，表明產(chǎn)生式 A- B的右部B已出現(xiàn)在 棧頂。(2)活前綴只含句柄的一部分符號(hào)，表明 A- B 1 B 2的右部子用B 1已出現(xiàn) 在棧頂，期待從輸入用中看到0 2推出的符號(hào)。(3)活前綴不含有句柄的任何符號(hào)，此時(shí)期望 A- B的右部所推出的符號(hào)在文法G的每個(gè)產(chǎn)生式的右部(候選式)的任何位置上添加一個(gè)圓點(diǎn)，所構(gòu) 成的每個(gè)產(chǎn)生式稱(chēng)為L(zhǎng)R (0)項(xiàng)目。

35、如產(chǎn)生式At xyz有如下項(xiàng)目：At .xyz, At x.yz, At xy.z , At xyz.。為刻劃分析過(guò)程中的文法的每一個(gè)產(chǎn)生式的右部 符號(hào)已有多大一部分被識(shí)別(出現(xiàn)在棧頂)，可以用這種標(biāo)有圓點(diǎn)的產(chǎn)生式來(lái)確 定。A- B .刻劃產(chǎn)生式A B的右部B已出現(xiàn)在棧頂。A B 1邛2刻劃A B 1 B 2的右部子用B 1已出現(xiàn)在棧頂，期待從輸入用 中看到0 2推出的符號(hào)。A-.B刻劃沒(méi)有句柄的任何符號(hào)在棧頂，此時(shí)期望 A-B的右部所推出 的符號(hào)用。(4)對(duì)于A一 &的LR(0)項(xiàng)目只有A 一.。設(shè)文法G= (Vt, Vn, S, P)是一個(gè)上下文無(wú)關(guān)文法，若存在一個(gè)規(guī)范推導(dǎo)S aAw=m

36、dlMw (其中A/ 1p2P),則稱(chēng)項(xiàng)目A.P 1?2對(duì)活前綴尸(#1是有 效的，即LR(0)有效項(xiàng)目。從直觀意義上講，一個(gè)LR(0)項(xiàng)目指明了在分析過(guò)程中的某一步我們看到產(chǎn) 生式的多大部分被識(shí)別，LR(0)項(xiàng)目中的圓點(diǎn)可看成是分析棧棧頂與輸入用的分 界線(xiàn)，圓點(diǎn)左邊為已進(jìn)入分析棧的部分，右邊是當(dāng)前輸入或繼續(xù)掃描的符號(hào)用。不同的LR(0)項(xiàng)目，反映了分析棧頂?shù)牟煌闆r。我們根據(jù)LR(0)項(xiàng)目的作用不同，將其分為四類(lèi)：(1)歸約項(xiàng)目：表現(xiàn)形式：A一a.這類(lèi)LR(0)項(xiàng)目表示句柄a恰好包含在棧中，即當(dāng)前棧頂?shù)牟糠謨?nèi)容構(gòu)成了 所期望的句柄，應(yīng)按A-a進(jìn)行歸約。(2)接受項(xiàng)目：表現(xiàn)形式：S-a.其中S

37、是文法惟一的開(kāi)始符號(hào)。這類(lèi) LR(0)項(xiàng)目實(shí)際是特殊的歸約項(xiàng)目，表 示分析棧中內(nèi)容恰好為a,用S-a進(jìn)行歸約，則整個(gè)分析成功。(3)移進(jìn)項(xiàng)目：表現(xiàn)形式：A一a.bP (ZVt)這類(lèi)LR(0)項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句 柄的活前級(jí)，需將b移進(jìn)分析棧。(4)待約項(xiàng)目：表現(xiàn)形式：A-a.BB(BwVn)這類(lèi)LR(0)項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句 柄的活前綴，應(yīng)把當(dāng)前輸入字符串中的相應(yīng)內(nèi)容先歸約到B。在給出LR(0)項(xiàng)目的定義和分類(lèi)之后，我們從這些 LR(0)項(xiàng)目出發(fā)，來(lái)構(gòu)造 能識(shí)別文法所有前綴的有窮自動(dòng)機(jī)。 其步驟是：首先構(gòu)造能識(shí)別文法所有活

38、前綴 的非確定的有窮自動(dòng)機(jī)，再將其確定化和最小化，最終得到所需的確定的有窮自 動(dòng)機(jī)。由文法G的LR(0)項(xiàng)目構(gòu)造識(shí)別文法G的所有活前綴的非確定有窮自動(dòng)機(jī) 的方法：(1)規(guī)定含有文法開(kāi)始符號(hào)的產(chǎn)生式 (設(shè)S-A)的第一個(gè)LR(0)項(xiàng)目(即 S - .A)為NFA的惟一初態(tài)。(2)令所有LR(0)項(xiàng)目分別對(duì)應(yīng)NFA的一個(gè)狀態(tài)且LR(0)項(xiàng)目為歸約項(xiàng)目 的對(duì)應(yīng)狀態(tài)為終態(tài)。(3)若狀態(tài)i和狀態(tài)j出自同一文法G的產(chǎn)生式且兩個(gè)狀態(tài)LR(0)項(xiàng)目的圓 點(diǎn)只相差一個(gè)位置，即：若 i 為 X-X1X2, Xi-1 Xi, Xn, j 為 X-X1X2, Xi-Xi+1, Xn,則從狀態(tài)i引一條標(biāo)記為Xi的弧到狀

39、態(tài)j0(4)若狀態(tài)i為待約項(xiàng)目(設(shè)X-a AB ),則從狀態(tài)i引e弧到所有A 一 - r的狀態(tài)。為了使“接受”狀態(tài)易于識(shí)別，我們通常將文法G進(jìn)行拓廣。假定文法G是一個(gè)以S為開(kāi)始符號(hào)的文法，我們構(gòu)造一個(gè) G它包含了整 個(gè)G,但它引進(jìn)了一個(gè)不出現(xiàn)在 G中的非終結(jié)符S ,，并加進(jìn)一個(gè)新產(chǎn)生式S-S, 以S，-SG 為開(kāi)始符號(hào)。那么，我們稱(chēng) G，是G的拓廣文法。這樣，便會(huì)有一個(gè)僅含項(xiàng)目S，一S的狀態(tài)，這就是惟一的“接受”態(tài)。如果I是文法G，的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：I的項(xiàng)目者B在CLOSURE(I)中。若A - ot.BP屬于CLOSURE(I),則每一形如B一.珀勺項(xiàng)

40、目也屬于 CLOSURE(I)。重復(fù)(2)直至UCLOSURE(I)不再擴(kuò)大。定義轉(zhuǎn)換函數(shù)如下：GO (I, X) = CLOSURE (J)其中：I為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào)，J= AaX .P | A-s.X PCI。圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱(chēng)為核，惟一的例外是S 一.S,因此用GOTO (I, X)狀態(tài)轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)閉包項(xiàng)目集的核。使用閉包函數(shù)(CLOSURE)和轉(zhuǎn)換函數(shù)(GO(I,X)構(gòu)造文法G的LR(0)的項(xiàng) 目集規(guī)范族，步驟如下：置項(xiàng)目S 一.S為初態(tài)集的核，然后對(duì)核求閉包CLOSURE (S一.S)得到初態(tài)的閉包項(xiàng)目集。對(duì)初態(tài)集或其他所構(gòu)造的項(xiàng)目集

41、應(yīng)用轉(zhuǎn)換函數(shù)GO(I , X)= CLOSURE(J)求出新?tīng)顟B(tài)J的閉包項(xiàng)目集。重復(fù)(2)直到不出現(xiàn)新的項(xiàng)目集為止。計(jì)算LR (0)項(xiàng)目集規(guī)范族C=I 0, Ii , . In 的算法偽代碼如下：Procedure itemsets(G );Begin C := CLOSURE (S .S)RepeatFor C中每一項(xiàng)目集I和每一文法符號(hào)XDo if GO(I,X)非空且不屬于C Then把 GO(I,X)放入C中 Until C不再增大End;一個(gè)項(xiàng)目集可能包含多種項(xiàng)目，若移進(jìn)和歸約項(xiàng)目同時(shí)存在，則稱(chēng)移進(jìn)-歸約 沖突，若歸約和歸約項(xiàng)目同時(shí)存在，則稱(chēng)歸約 -歸約沖突。下面看一個(gè)具體的例我們希

42、望能根據(jù)識(shí)別文法的活前綴的 DFA建立LR分析器，因此，需要研 究這個(gè)DFA的每個(gè)項(xiàng)目集(狀態(tài))中的項(xiàng)目的不同作用。我們說(shuō)項(xiàng)目A- B 1. B 2對(duì)活前綴a B 1是有效的，具條件是存在規(guī)范推導(dǎo) SoAoPio 一般而言，同一項(xiàng)目可能對(duì)幾個(gè)活前綴都是有效的(當(dāng)一個(gè)項(xiàng)目出現(xiàn)在幾個(gè)不同的集合中時(shí)便是這種情形)。若歸約項(xiàng)目A-B1.對(duì)活前綴 P1是有效的，則它告訴我們應(yīng)把符號(hào)用1歸約為A ,即把活前綴aP 1變成a A。若移進(jìn)項(xiàng)目A-0 1.02對(duì)活前綴a3是有效的，則它告訴我們，句柄尚未形成， 因此，下一步動(dòng)作應(yīng)是移進(jìn)。但是，可能存在這樣的情形，對(duì)同一活前綴，存在 若干項(xiàng)目對(duì)它都是有效的。而且它

43、們告訴我們應(yīng)做的事情各不相同，互相沖突。 這種沖突通過(guò)向前多看幾個(gè)輸入符號(hào)，或許能夠獲得解決。對(duì)于每個(gè)活前綴，我們可以構(gòu)造它的有效項(xiàng)目集。 實(shí)際上，一個(gè)活前綴丫的 有效項(xiàng)目集正是從上述的DFA的初態(tài)出發(fā)，經(jīng)讀出丫后而到達(dá)的那個(gè)項(xiàng)目集(狀 態(tài))。換言之，在任何時(shí)候，分析棧中的活前綴X1X2, Xm的有效項(xiàng)目集正是棧頂狀態(tài)Sm所代表的那個(gè)集合。這是LR分析理論的一條基本定理。實(shí)際上，棧 頂?shù)捻?xiàng)目集(狀態(tài))體現(xiàn)了棧里的一切有用信息一一歷史。前面我們已經(jīng)對(duì)LR (0)文法進(jìn)彳T了定義，下面我們來(lái)看一下LR (0)分析 表是如何構(gòu)造的。對(duì)于LR (0)文法，我們可以直接從它的項(xiàng)目集規(guī)范族C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR (0)分析表的算法。假定C=l0, Ii，In,令每個(gè)項(xiàng)目集Ik的