LR(0)語(yǔ)法分析

1、淮 陰 工 學(xué) 院編譯原理課程設(shè)計(jì)報(bào)告選題名稱： LR(0) 語(yǔ) 法 分 析 系 （院）： 計(jì) 算 機(jī) 工 程 學(xué) 院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 計(jì)算機(jī)1075(單招) 姓 名： 趙俊麗 學(xué)號(hào)： 1071308114 指導(dǎo)老師： 于長(zhǎng)輝 王文豪 高麗 夏森 學(xué)年學(xué)期： 2009 2010 學(xué)年 第 2 學(xué)期設(shè)計(jì)任務(wù)書課題名稱LR(0)語(yǔ)法分析設(shè)計(jì)目的LR(0)分析法是一種移進(jìn)-規(guī)約過(guò)程，能根據(jù)當(dāng)前分析棧中的符號(hào)串，同時(shí)也不用向右查看輸入串的符號(hào)就可唯一確定分析器的動(dòng)作。通過(guò)對(duì)給定的文法構(gòu)造LR(0)分析表和實(shí)現(xiàn)某個(gè)符號(hào)串的分析掌握LR(0)分析法的基本思想。實(shí)驗(yàn)環(huán)境 Windows

2、XP 操作系統(tǒng)，Visual C+6.0以上編譯環(huán)境任務(wù)要求1.錄入合法的LR(0)文法2.構(gòu)造并輸出LR(0)分析表3.對(duì)輸入的符號(hào)串進(jìn)行語(yǔ)法分析工作進(jìn)度計(jì)劃序號(hào)起止日期工 作 內(nèi) 容109.12.14-09.12.14選定題目，明確題目要求209.12.15-09.12.15課題深入調(diào)研、細(xì)化工作，系統(tǒng)方案設(shè)計(jì)309.12.16-09.12.17程序錄入、調(diào)試、整合409.12.18-09.12.20上機(jī)演示，課程設(shè)計(jì)分組答辯，完成課程設(shè)計(jì)報(bào)告指導(dǎo)教師（簽章）： 年 月 日 摘要：編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一，語(yǔ)法分析是編譯程序的核心部分，識(shí)別由語(yǔ)法分析給出的單詞符號(hào)序列是否

3、是給定文法的正確句子，把詞法記號(hào)流按語(yǔ)言的語(yǔ)法結(jié)構(gòu)層次地分組，以形成語(yǔ)法短語(yǔ)。一個(gè)編譯程序的工作過(guò)程一般可以劃分為五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、優(yōu)化、目標(biāo)代碼生成。LR（0）是一種自底向上的語(yǔ)法分析方法，是已知的最一般的無(wú)回溯的移近歸約方法，這一方法能夠識(shí)別所有能用上下文無(wú)關(guān)文法描述的程序語(yǔ)言的結(jié)構(gòu)。本文主要討論LR（0）語(yǔ)法分析的構(gòu)造。著重分析LR(0)分析器的一般原理、實(shí)現(xiàn)思想、基本設(shè)計(jì)方法以及主要實(shí)現(xiàn)技術(shù)和工具。操作員錄入合法的LR(0)文法，則自動(dòng)生成LR(0)分析表，并對(duì)任一輸入串進(jìn)行分析。判斷其是否是給定文法的句子。還可以對(duì)輸入的句子進(jìn)行語(yǔ)法分析。關(guān)鍵詞：自

4、底向上分析；移進(jìn)；規(guī)約目錄1 課題綜述111 課題來(lái)源112 意義113 預(yù)期目標(biāo)114 面對(duì)的問(wèn)題22 系統(tǒng)分析321 涉及的基礎(chǔ)知識(shí)322 總體方案53 系統(tǒng)設(shè)計(jì)531 算法描述633 詳細(xì)流程圖94 代碼編寫105 程序調(diào)試15總 結(jié)19致謝20參考文獻(xiàn)211 課題綜述11 課題來(lái)源編譯器設(shè)計(jì)的編譯程序涉及到編譯五個(gè)階段中的三個(gè)，即詞法分析器、語(yǔ)法分析器和中間代碼生成器。編譯程序的輸出結(jié)果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析過(guò)程顯示及四元式序列程序。整個(gè)編譯程序分為三部分：詞法分析部分、語(yǔ)法分析處理及四元式生成部分、輸出顯示部分。一個(gè)程序設(shè)計(jì)語(yǔ)言就是一個(gè)記號(hào)系統(tǒng)，如同自然語(yǔ)言

5、一樣，它的完整的定義應(yīng)包括語(yǔ)法和語(yǔ)義兩個(gè)方面。所謂一個(gè)語(yǔ)言的語(yǔ)法是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。目前廣泛使用的手段是上下文無(wú)關(guān)文法，即用上下文無(wú)關(guān)文法作為程序設(shè)計(jì)語(yǔ)言語(yǔ)法的描述工具。自底向上分析方法是一種移進(jìn)-規(guī)約過(guò)程，當(dāng)分析的棧頂符號(hào)串形成句柄時(shí)就采取歸約動(dòng)作，因而自底向上分析法的關(guān)鍵問(wèn)題是在分析過(guò)程中如何確定句柄。LR分析法正是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串（通常以狀態(tài)表示）和向右順序查看輸人串的k個(gè)(k=0)符號(hào)就可惟一地確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能惟一地確定句柄。LR分析法的歸約過(guò)程是規(guī)范推導(dǎo)的逆過(guò)程，所以LR分析過(guò)程是一種規(guī)范歸約過(guò)

6、程。12 意義 LR（0）分析方法雖然對(duì)文法的限制比較大，對(duì)絕大多數(shù)高級(jí)語(yǔ)言的語(yǔ)法分析器不能適用，然而他是構(gòu)造其他LR類分析器的基礎(chǔ)，學(xué)習(xí)和掌握LR（0）分析的原理和方法是我們掌握更高級(jí)語(yǔ)言語(yǔ)法分析的基礎(chǔ)。歸納起來(lái)，大體上可分為兩大類，即自頂向下分析方法和自底向上分析方法。自底向上分析方法是一種移進(jìn)-規(guī)約過(guò)程，當(dāng)分析的棧頂符號(hào)串形成句柄時(shí)就采取歸約動(dòng)作，因而自底向上分析法的關(guān)鍵問(wèn)題是在分析過(guò)程中如何確定句柄。LR分析法正是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串(通常以狀態(tài)表示)和向右順序查看輸人串的k個(gè)(k=0)符號(hào)就可惟一地確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能惟一地確定句

7、柄。LR分析法的歸約過(guò)程是規(guī)范推導(dǎo)的逆過(guò)程，所以LR分析過(guò)程是一種規(guī)范歸約過(guò)程。13 預(yù)期目標(biāo)本次課程設(shè)計(jì)的目標(biāo)即是利用所學(xué)過(guò)的編譯原理的知識(shí)，利用LR(0)分析法，用C語(yǔ)言寫出一個(gè)簡(jiǎn)單的LR(0)語(yǔ)法分析器。該語(yǔ)法分析器所要完成的功能是，對(duì)錄入的文法判斷它是否為L(zhǎng)R(0)文法，如果是輸出LR(0)分析表；在給定文法的情況下，能夠利用LR(0)分析表，對(duì)用戶輸入的一串字符串用LR(0)分析法進(jìn)行分析，判斷該字符串是否為符合給定文法的一個(gè)句子，建立文法及其LR分析表表示的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)LR(0)的分析器。14 面對(duì)的問(wèn)題(1)分析表的構(gòu)造。(2)歸約還是移進(jìn)的判斷。(3)接受acc的判

8、斷。(4)編程結(jié)果的輸出。在本次課程設(shè)計(jì)中，主要的是面對(duì)的文法的確定，以及分析其工作過(guò)程如何進(jìn)行。對(duì)于文法確定的問(wèn)題，必須找到一個(gè)符合LR(0)規(guī)范的文法，并且該文法不易太復(fù)雜，否則對(duì)于初次編寫語(yǔ)法分析器的我們來(lái)說(shuō)會(huì)比較復(fù)雜，否則容易出錯(cuò)。第二個(gè)就是分析過(guò)程的問(wèn)題，目前，我們只是了解了理論上LR(0)的分析過(guò)程，但如何將該過(guò)程用程序去實(shí)現(xiàn)，并且能夠?qū)σ粋€(gè)輸入串進(jìn)行實(shí)時(shí)的分析是比較復(fù)雜的。這涉及到對(duì)一個(gè)字符串進(jìn)行一個(gè)字符一個(gè)字符的讀取和操作，并且還要對(duì)幾個(gè)連在一起的字符進(jìn)行合并等操作，要求比較的高，對(duì)我們而言比較困難。在規(guī)范規(guī)約的過(guò)程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，另一方面根據(jù)所用的產(chǎn)

9、生式推測(cè)未來(lái)可能碰到的輸入符號(hào)。當(dāng)一串句柄的符號(hào)串呈現(xiàn)于分析棧的頂端時(shí)，希望能夠根據(jù)上面過(guò)程中的數(shù)據(jù)來(lái)確定棧頂?shù)姆?hào)串是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。能正確初始化狀態(tài)棧，對(duì)棧內(nèi)元素的進(jìn)棧和出棧，取棧頂元素以及遍歷棧元素，LR分析方法是一種自底向上的分析方法，是一種個(gè)移進(jìn)-歸約的過(guò)程。當(dāng)分析的棧頂符號(hào)串形成句柄時(shí)就采取歸約動(dòng)作，因而自底向上分析法的關(guān)鍵問(wèn)題是在分析過(guò)程忠如何確定句柄。LR（0）分析器是在分析過(guò)程中不需要察看輸入符號(hào)，因而它對(duì)文法的限制較大，對(duì)絕大多數(shù)高級(jí)語(yǔ)言的語(yǔ)法分析器是不能使用的，然而，他是構(gòu)造其他LR類分析器的基礎(chǔ)。1.5 需解決的關(guān)鍵技術(shù)（1）詞法編譯器。（2）交互式面向?qū)ο?/p>

10、的詞法編譯器基本功能是。（3）根據(jù)規(guī)約規(guī)則對(duì)字符進(jìn)行歸約。（4）符合條件時(shí)采取移進(jìn)動(dòng)作。2 系統(tǒng)分析21 涉及的基礎(chǔ)知識(shí)2.1.1 詞法編譯器功能（1）導(dǎo)入任意文法，也可以自己輸入。（2）輸出文法的分析過(guò)程，以及判斷是否為L(zhǎng)R(0)文法，輸出分析表。（3）輸入句子，進(jìn)行語(yǔ)法分析。（4）輸出結(jié)構(gòu)樹。2.1.2 詞法分析器的設(shè)計(jì)方法有如下四個(gè)步驟：(1)寫出該語(yǔ)言的詞法規(guī)則。(2)把詞法規(guī)則轉(zhuǎn)換為相應(yīng)的狀態(tài)轉(zhuǎn)換圖。(3)把各轉(zhuǎn)換圖的初態(tài)連在一起，構(gòu)成識(shí)別該語(yǔ)言的自動(dòng)機(jī)。(4)設(shè)計(jì)掃描器；把掃描器作為語(yǔ)法分析的一個(gè)過(guò)程，當(dāng)語(yǔ)法分析需要一個(gè)單詞時(shí)，就調(diào)用掃描器。掃描器從初態(tài)出發(fā)，當(dāng)識(shí)別一個(gè)單詞后便進(jìn)入

11、終態(tài)，送出二元式。2.1.3 動(dòng)態(tài)模擬算法的基本功能（1）輸入LR分析表和一個(gè)句子。（2）輸出LR總控程序。（3）輸出依據(jù)句子構(gòu)對(duì)應(yīng)的語(yǔ)法樹的過(guò)程。（4）設(shè)計(jì)一個(gè)給定LR分析表，輸入一個(gè)句子，能由依據(jù)LR分析表輸出與句子對(duì)應(yīng)的語(yǔ)法樹，能對(duì)語(yǔ)法樹生成過(guò)程進(jìn)行模擬。 表 2-1 LR分析表STATEACTIONGOTOabcd#ETF0S2S311acc2S4S1063S5S474S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6（5）輸入句子：bccd#。（6）根據(jù)文法產(chǎn)生的LR分析表

12、。（7）輸出結(jié)果2.1.4 LR分析器的構(gòu)成一個(gè)LR分析器由個(gè)部分組成（1）總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器，總控程序都是相同的。（2）分析表或分析函數(shù)。不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表也不同，分析表又可以分為動(dòng)作（ACTION）表和狀態(tài)轉(zhuǎn)換（GOTO）表兩個(gè)部分，它們都可用二維數(shù)組表示。（3）分析棧，包括文法符號(hào)和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定（LR(0)分析器不需向前查看輸入符號(hào)）。2.2解決問(wèn)題的基本思路1、用構(gòu)造一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換。2、再通過(guò)函數(shù)構(gòu)造一個(gè)移進(jìn)歸約函數(shù)實(shí)現(xiàn)移進(jìn)規(guī)約動(dòng)作。

13、3、采用構(gòu)造一個(gè)打印LR分析器的工作過(guò)程函數(shù)實(shí)現(xiàn)輸出。在規(guī)范規(guī)約的過(guò)程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，另一方面根據(jù)所用的產(chǎn)生式推測(cè)可能碰到的輸入符號(hào)。每一項(xiàng)ACTION(s，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：（1）移進(jìn)：把（s，a）的下一個(gè)轉(zhuǎn)態(tài)s = GOTO(s，X)和輸入符號(hào)a推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。（2）規(guī)約：指用某一產(chǎn)生式A 進(jìn)行規(guī)約。假若的長(zhǎng)度為r，規(guī)約的動(dòng)作是A，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r 變成棧頂狀態(tài)，然后把（Sm-r，A）的下一狀態(tài)s = GOTO(Sm-r,A)和文法符號(hào)A推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著（= Xm-r

14、+1Xm）已呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于A的句柄。（3）接受：宣布分析成功，停止分析器的工作。（4）報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。23 總體方案本課題是由一個(gè)四人的團(tuán)隊(duì)去完成的，所以，每個(gè)小組成員分配了不同的工作共同完成這個(gè)項(xiàng)目。24 功能模塊框圖運(yùn)行程序給出該程序所運(yùn)用的文法和LR分析表用戶輸入字符串程序給出結(jié)果圖2.2功能模塊框圖3 系統(tǒng)設(shè)計(jì)31 算法描述1、已知文法G(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi2、LR(0)分析表的構(gòu)造算法如下：假設(shè)已構(gòu)造出LR(0)項(xiàng)目集規(guī)范族為：C=I0,I1, , In其中Ik為項(xiàng)目集的名字，k為

15、狀態(tài)名，令包含SS項(xiàng)目的集合Ik的下標(biāo)k為分析器的初始狀態(tài)。那么分析表的ACTION表和GOTO表構(gòu)造步驟為：(1) 若項(xiàng)目Aa屬于Ik且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij，當(dāng)a為終結(jié)符時(shí)則置ACTIONk,a為Sj，其動(dòng)作含意為將終結(jié)符a移進(jìn)符號(hào)棧，狀態(tài)j進(jìn)入狀態(tài)棧，(相當(dāng)狀態(tài)k時(shí)遇a轉(zhuǎn)向狀態(tài)j)。(2) 若項(xiàng)目A 屬于Ik，則對(duì)任何終結(jié)符a 和#號(hào)置ACTIONk,a和ACTIONk,#為rj，j為在文法G中某產(chǎn)生式A的序號(hào)。rj動(dòng)作的含義是把當(dāng)前文法符號(hào)棧頂?shù)姆?hào)串歸約為A，并狀態(tài)棧指針從棧頂向下移動(dòng)|的長(zhǎng)度 , 文法符號(hào)棧從棧頂彈出|個(gè)符號(hào)，非終結(jié)符A變?yōu)楫?dāng)前面臨的符號(hào)。(3) 若GO(

16、Ik,A)Ij，則置GOTOk,A為j，其中A為非終結(jié)符，表示當(dāng)前狀態(tài)為k時(shí)，遇文法符號(hào)A時(shí)狀態(tài)應(yīng)轉(zhuǎn)向j，因此A移入文法符號(hào)棧，j移入狀態(tài)棧。(4) 若項(xiàng)目SS屬于Ik，則置ACTIONk,#為acc，表示接受。(5) 凡不能用上述方法填入的分析表的元素，均應(yīng)填上報(bào)錯(cuò)標(biāo)志。為了表的清晰我們僅用空白表示錯(cuò)誤標(biāo)志。根據(jù)這種方法構(gòu)造的LR(0)分析表不含多重定義時(shí)，稱這樣的分析表為L(zhǎng)R(0)分析表，能用LR(0)分析表的分析器稱為L(zhǎng)R(0)分析器，能構(gòu)造LR(0)分析表的文法稱為L(zhǎng)R(0)文法。3、產(chǎn)生如圖2-1所示的LR分析表這張分析表包括兩個(gè)部分，一是“動(dòng)作”（ACTION）表，另一是“狀態(tài)轉(zhuǎn)換

17、”（GOTO）表。ACTION(S,a)規(guī)定了當(dāng)狀態(tài)S面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。GOTO（S，X）規(guī)定了狀態(tài)S面對(duì)文法符號(hào)X（終結(jié)符或非終結(jié)符）時(shí)下一狀態(tài)是什么。顯然，GOTO(S，X)定義了一個(gè)以文法符號(hào)為字母表的DFA。每一項(xiàng)ACTION(S，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：（1）移進(jìn)把（S，a）的下一個(gè)轉(zhuǎn)態(tài)S=GOTO(S，X)和輸入符號(hào)a推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。（2）規(guī)約指用某一產(chǎn)生式A進(jìn)行規(guī)約。假若的長(zhǎng)度為r，規(guī)約的動(dòng)作是A，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r變成棧頂狀態(tài)，然后把（Sm-r，A）的下一狀態(tài)S=GOTO(Sm-r,A)和文法符號(hào)A推進(jìn)棧。規(guī)約動(dòng)

18、作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著（=Xm-r+1Xm）已呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于A的句柄。（3）接受宣布分析成功，停止分析器的工作。（4）報(bào)錯(cuò)發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。一個(gè)LR分析器的工作過(guò)程可看成是棧里的狀態(tài)序列，已規(guī)約串和輸入串所構(gòu)成的三元式的變化過(guò)程。分析開(kāi)始時(shí)的初始三元式為：(S0, #, a1a2an#)。其中，S0為分析器的初態(tài)；為句子的左括號(hào)；a1a2an為輸入串；其后的為結(jié)束符（句子右括號(hào)）。分析過(guò)程每步的結(jié)果可表示為：（S0S1Sm，#X1X2Xm ai, ai+1an#）。3.2 實(shí)現(xiàn)方法3.2.1 構(gòu)造分析表LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧

19、）的確定有限狀態(tài)自動(dòng)機(jī)。LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。構(gòu)造一個(gè)int型二維數(shù)組table139,用于存放LR分析表。并初始化。作者這樣規(guī)定：011 表示 狀態(tài)Sj，其中0對(duì)應(yīng)S0，1對(duì)應(yīng)S12126 表示 規(guī)約Rj，其中21對(duì)應(yīng)R1，22對(duì)應(yīng)R212 表示 “接受”。-1 表示 規(guī)約出錯(cuò)，報(bào)錯(cuò)。3.2.2程序設(shè)計(jì)關(guān)鍵（1）在輸入串(句子)輸入的過(guò)程中，涉及到一個(gè)壓棧的問(wèn)題。但是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲(chǔ)順序與輸入的字符串相反。采取以下措施：先將輸入的字符串壓入符

20、號(hào)棧symbol中，然后符號(hào)棧彈出的字符再壓入輸入串棧instr中，這樣實(shí)現(xiàn)了輸入串的倒序存儲(chǔ)。（2）狀態(tài)棧和符號(hào)棧輸出（遍歷）過(guò)程均采取自棧底到棧頂?shù)捻樞颍斎氪畻t是采取自棧頂?shù)綏５椎捻樞蜉敵觥?.2.3 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造識(shí)別活前輟的NFA我們可以利用子集法將其確定化。對(duì)確定化后的DFA如果把每個(gè)子集中所含狀態(tài)集對(duì)應(yīng)的項(xiàng)目寫在新的狀態(tài)中。對(duì)于構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族，我們可以分析每個(gè)狀態(tài)中項(xiàng)目集的構(gòu)成，不難發(fā)現(xiàn)如下規(guī)律：若狀態(tài)中包含形如AB的項(xiàng)目，則形如B的項(xiàng)目也在此狀態(tài)內(nèi)。例如：0狀態(tài)中項(xiàng)目集為SE，EaA, E

21、bB。回顧由NFA確定化到DFA時(shí)，EaA和EbB正是屬于SE的閉包中。因而，可引入閉包函數(shù)(CLOSURE)來(lái)求DFA一個(gè)狀態(tài)的項(xiàng)目集。若文法G已拓廣為G，而S為文法G的開(kāi)始符號(hào)，拓廣后增加產(chǎn)生式SS。如果I是文法G的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：(1) I的項(xiàng)目均在CLOSURE(I)中。(2) 若AB屬于CLOSURE(I)，則每一形如B的項(xiàng)目也屬于CLOSURE(I)。(3) 重復(fù)(2)直到不出現(xiàn)新的項(xiàng)目為止。即CLOSURE(I)不再擴(kuò)大。由此，我們可以很容易構(gòu)造出初態(tài)的閉包，即SS屬于I，再按上述三點(diǎn)求其閉包?；仡櫾跇?gòu)造識(shí)別活前綴的NFA時(shí)，其兩個(gè)相鄰狀態(tài)

22、對(duì)應(yīng)的項(xiàng)目是出自同一個(gè)產(chǎn)生式，只是圓點(diǎn)的位置相差1，箭弧上的標(biāo)記為前一個(gè)狀態(tài)和后一個(gè)狀態(tài)對(duì)應(yīng)項(xiàng)目圓點(diǎn)間的符號(hào)，(除了箭弧上標(biāo)記為的外)。由于識(shí)別活前綴的DFA的每個(gè)狀態(tài)是一個(gè)項(xiàng)目集，項(xiàng)目集中的每個(gè)項(xiàng)目都不相同，每個(gè)項(xiàng)目圓點(diǎn)后的符號(hào)不一定相同，因而對(duì)每個(gè)項(xiàng)目圓點(diǎn)移動(dòng)一個(gè)位置后，箭弧上的標(biāo)記也不會(huì)完全相同，這樣，對(duì)于不同的標(biāo)記將轉(zhuǎn)向不同的狀態(tài)。例如初態(tài)SE，EaA,EbB對(duì)第一個(gè)項(xiàng)目圓點(diǎn)右移一個(gè)位置后變?yōu)镾E箭弧標(biāo)記應(yīng)為E，對(duì)第二個(gè)項(xiàng)目EaA，圓點(diǎn)右移一個(gè)位置后，項(xiàng)目變?yōu)镋aA，箭弧標(biāo)記為a,同樣第三個(gè)項(xiàng)目為圓點(diǎn)右移一個(gè)位置后變?yōu)镋bB，箭弧標(biāo)記為b，顯然，初態(tài)可發(fā)出三個(gè)不同標(biāo)記的箭弧，因而轉(zhuǎn)向三

23、個(gè)不同的狀態(tài)，也就由初態(tài)派生出三個(gè)新的狀態(tài)，對(duì)于每個(gè)新的狀態(tài)我們又可以利用前面的方法，若圓點(diǎn)后為非終結(jié)符則可對(duì)其求閉包，得到該狀態(tài)的項(xiàng)目集。圓點(diǎn)后面為終結(jié)符或在一個(gè)產(chǎn)生式的最后，則不會(huì)再增加新的項(xiàng)目。33 詳細(xì)流程圖初始化狀態(tài)棧，符號(hào)棧，輸入串棧輸入串各字符壓棧 求下一狀態(tài)符號(hào)ii = goto_char(status_p,instr_p)規(guī)約出錯(cuò)！異常中止！i = = -1 ?規(guī)約成功！退出i = = 12 ?規(guī)約動(dòng)作：1 求出i對(duì)應(yīng)規(guī)約規(guī)則右部字符串長(zhǎng)度x = ri-21.y2 在符號(hào)棧和狀態(tài)棧中彈出x個(gè)字符。然后將該規(guī)約規(guī)則左部壓入輸入串棧i0 & i=11 移進(jìn)動(dòng)作：1 將現(xiàn)狀態(tài)i壓棧

24、push(status_p,i)2 將當(dāng)前輸入串字符壓入符號(hào)棧a = pop(instr_p)push(symbol_p,a)打印該步工作過(guò)程圖3.2 LR分析器設(shè)計(jì)流程圖4 代碼編寫41 主要模塊的代碼分析4.1.1 生成分析表代碼void CLR0ForWinDlg:OnGtable() CTableDlg dlg;dlg.SetControlInfo(IDC_EXPLORER1, RESIZE_BOTH);dlg.SetControlInfo(IDOK, ANCHORE_BOTTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_EXPORT, ANCH

25、ORE_BOTTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_ANALYZE, ANCHORE_BOTTOM | ANCHORE_RIGHT);string temp = ;CString t;for(int i = 0; i m_vtlist.GetCount(); i+)m_vtlist.GetText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);dlg.g.SetVt(temp);temp = ;for(i = 0; i m_vnlist.GetCount(); i+)m_vnlist.Ge

26、tText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);dlg.g.SetVn(temp);m_startedit.GetWindowText(t);if (t = )MessageBox(輸入的文法有誤，請(qǐng)檢查！, 錯(cuò)誤,MB_OK | MB_ICONSTOP);return;dlg.g.SetStart(t.GetAt(0);temp = ;for(i = 0; i m_plist.GetCount(); i+)temp = ;m_plist.GetText(i,t);for(int j = 0; j m_tree.DeleteAl

27、lItems();for(int i = 0; i m_input.GetLength(); i +)if (!m_g.IsInVt(m_input.GetAt(i)MessageBox(輸入的句子不全部由終結(jié)符組成, 錯(cuò)誤, MB_OK | MB_ICONSTOP);return;assert(TreeStack.empty();m_input += #;char szTempPathMAX_PATH; char szTempNameMAX_PATH; if (m_strTempFilename != ):DeleteFile(m_strTempFilename.c_str();:GetTe

28、mpPath(100,szTempPath);:GetTempFileName(szTempPath,LR0,0,szTempName);m_strTempFilename = szTempName;CStdioFile out;out.Open(szTempName, CFile:modeCreate | CFile:modeWrite);out.WriteString(n);out.WriteString(n);out.WriteString(Untitled Documentn);out.WriteString(n);out.WriteString(n);out.WriteString(

29、n);out.WriteString(n);out.WriteString(n 步驟 n 狀態(tài)棧n 符號(hào)棧 n 輸入串 n ACTION n GOTO n n);vector Status;vector Symbol;int iStep = 1;int iPos = 0;Status.push_back(0);Symbol.push_back(#);Pair ToDo;bool bErrorFlag = false;bool bGoOn = true;while (bGoOn) & (

30、!bErrorFlag)assert(iPos m_input.GetLength();assert(Status.size() = Symbol.size();ToDo = m_g.GetAction(Status.back(), m_input.GetAt(iPos);int i, j;switch (ToDo.one)case S:out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1);Symbol.push_back(m_input.G

31、etAt(iPos);Status.push_back(ToDo.two);iPos+;break;case R:j = m_g.GetGoTo(StatusStatus.size()-m_g.GetPrecept(ToDo.two).GetRight().length()-1, m_g.GetPrecept(ToDo.two).GetLeft()0);assert(j != -1);out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, j);for

32、(i = 0; i m_g.GetPrecept(ToDo.two).GetRight().length(); i+)Status.pop_back();Symbol.pop_back();Symbol.push_back(m_g.GetPrecept(ToDo.two).GetLeft()0);Status.push_back(j);TreeStack.push(ToDo.two);break;case a:if (m_input.GetAt(iPos) = #)out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(

33、m_input.GetLength() - iPos), ToDo, -1);bGoOn = false;elsebErrorFlag = true;break;case 0:bErrorFlag = true;break;default:assert(false);iStep+;out.WriteString();if (bErrorFlag)out.WriteString(分析失敗，輸入的字符串是不符合預(yù)定文法的！n);/m_pTree-m_tree.DeleteAllItems();while(!TreeStack.empty()TreeStack.pop();elseout.Write

34、String(分析完成，輸入的字符串是預(yù)定文法的句子n);/HTREEITEM h = m_pTree-m_tree.GetRootItem();/ExpandTree(h);MakeTree();out.WriteString(n);out.Close();m_web.Navigate(szTempName,NULL,NULL,NULL,NULL);m_edit1.SetFocus();m_edit1.SetSel(0, -1);5 程序調(diào)試編完自己的程序，然后在將其他組員的程序整合起來(lái)后就進(jìn)行了,首先將所有的程序進(jìn)行測(cè)試和編譯檢查有沒(méi)有錯(cuò)誤，有錯(cuò)誤的話先修改正確，在調(diào)試的過(guò)程中，先輸入字符串，進(jìn)行規(guī)約，要注意的是一定要輸入可以規(guī)約的字符串且要在字符串的最后輸入一個(gè)“#”號(hào)作為規(guī)約的結(jié)束標(biāo)志，如果沒(méi)有加上“#”結(jié)束符號(hào)，導(dǎo)致系統(tǒng)認(rèn)為用戶的輸入串并沒(méi)有結(jié)束，不斷的進(jìn)行規(guī)約，并且在規(guī)約的時(shí)候要特別注意各棧的值的情況，因?yàn)樽詈笠敵鼋Y(jié)果，如果輸入的是不可規(guī)約的字符串那系統(tǒng)就會(huì)出錯(cuò)不能完成規(guī)約。6 運(yùn)行與調(diào)試圖