編譯原理課程設(shè)計(jì)(LR(0)分析表的構(gòu)造)_圖文

1、引 言編譯原理是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)課程,其中包含大量軟件設(shè)計(jì)思想。 通過(guò)課程設(shè)計(jì),實(shí)現(xiàn)一些重要的算法,或設(shè)計(jì)一個(gè)完整的編譯程序模型,能夠進(jìn)一步加 深理解和掌握所學(xué)知識(shí),對(duì)提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。語(yǔ)法分析是編譯過(guò)程的第二階段,是編譯器前端的核心組成部分,在編譯系統(tǒng)中起 到了至關(guān)重要的作用。自底向上的語(yǔ)法分析與自頂向下的語(yǔ)法分析相比,對(duì)將要分析的 源程序有著更大的分析空間,從而受到了廣泛的運(yùn)用。LR(0分析是自底向上 LR 類語(yǔ)法分析的基礎(chǔ),自底向上語(yǔ)法分析方法是一種移進(jìn) -規(guī)約過(guò)程,在當(dāng)前分析的棧頂符號(hào)串形成句柄時(shí)就采取規(guī)約動(dòng)作,因此最終目標(biāo)是如何 在分析過(guò)程中確定句柄

2、。 LR 分析法是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串和向右順序 查看 k 個(gè)符號(hào)串就可以唯一地確定分析器動(dòng)作:是移進(jìn)還是規(guī)約, 采用哪條產(chǎn)生式。 LR(0分析器是在分析過(guò)程中,不需要向后查看輸入串符號(hào),因此它對(duì)文法的限制較大。對(duì)絕 大多數(shù)高級(jí)語(yǔ)言語(yǔ)法分析器是不適用的,但是它是構(gòu)造其他 LR 分析器的基礎(chǔ)。LR(0最終存在的問(wèn)題和需要解決的問(wèn)題是在構(gòu)造 LR(0分析表的時(shí)候, 在 LR(0項(xiàng) 目集規(guī)范族中,有移進(jìn)項(xiàng)目和規(guī)約項(xiàng)目、規(guī)約項(xiàng)目和規(guī)約項(xiàng)目同時(shí)存在的現(xiàn)象,形成移 進(jìn) -規(guī)約沖突和規(guī)約 -規(guī)約沖突,直接導(dǎo)致語(yǔ)法分析器無(wú)法在某一狀態(tài)進(jìn)行移進(jìn)還是規(guī) 約。為了能夠解決這一問(wèn)題,我們需要再向后查看一

3、個(gè)輸入字符(也就是當(dāng)前字符的 FOLLOW 集以確定下一步操作是否能夠進(jìn)行。我班選擇的是老師給的 LR(1語(yǔ)法分析構(gòu)造器的設(shè)計(jì),即對(duì)任意給定的文法 G 構(gòu)造 LR(1項(xiàng)目集規(guī)范族,其中要實(shí)現(xiàn) CLOSURE(I、 GO(I,X、 FIRST 集合等。在此基礎(chǔ)上, 構(gòu)造了 LR (1分析表。然后對(duì)輸入的句子進(jìn)行語(yǔ)法分析,給出接受或出錯(cuò)報(bào)告。程序 采用文件輸入輸出方式。其中包括兩個(gè)輸入文件:文法 grammar.txt ,以及輸入串 input.txt ; 兩個(gè)輸出文件:項(xiàng)目集 items.txt 和文法的 LR(1分析表 action_table.txt。 由于語(yǔ)法分析的結(jié)果只給出接受或錯(cuò)誤報(bào)告

4、,比較簡(jiǎn)單。所以直接在屏幕上輸出,也便 于用戶查看。在具體編寫程序過(guò)程中,對(duì)文法操作的各個(gè)功能模塊獨(dú)立成為一個(gè)子程序,而對(duì)具 體輸入串的分析則放在 main(函數(shù)中進(jìn)行。 各個(gè)變量及函數(shù)的意義和用法我將在敘述程 序設(shè)計(jì)的總體方案中詳細(xì)給出。程序的總體算法思想來(lái)自 編譯原理 課程。 具體實(shí)現(xiàn)由我獨(dú)立完成。 程序用 C/C+語(yǔ)言編寫。在 Microsoft Visual C+ 2005環(huán)境下調(diào)試通過(guò)。摘 要語(yǔ)法分析的主要任務(wù)是接收詞法分析程序識(shí)別出來(lái)的單詞符由某種號(hào)串, 判斷它們 是否語(yǔ)言的文法產(chǎn)生,即判斷被識(shí)別的符號(hào)串是否為某語(yǔ)法部分。LR分析法是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串 (通常以狀態(tài)

5、表示 和向右順序 查看輸入串的 K 個(gè)(K 0 符號(hào)就可唯一地確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪 個(gè)產(chǎn)生式歸約,因而也就能唯一地確定句柄,所以 LR 分析過(guò)程是一種規(guī)范歸約過(guò)程。 經(jīng)過(guò)分析,我們使用 C 作為前端開(kāi)發(fā)工具,在分析語(yǔ)法成分時(shí)比較方便直觀,更便 于操作。運(yùn)行程序的同時(shí)不斷修正改進(jìn)程序,直至的到最優(yōu)源程序。關(guān) 鍵 字語(yǔ)法分析 文法 LR(1分析 移進(jìn) 歸約- 2 -AbstractGrammatical analysis of the main tasks was to receive lexical analysis procedure to identify the words

6、 from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part.The LR analytic method is gives one kind to be able to act according to current analyzes in stack's string (usually by condition expression

7、 and examined in turn toward right the input string K (K0 the mark may determine only which production pattern selling and buying of real esgate within the same family analyzer's movement is moves to or the selling and buying of real esgate within the same family and uses .Therefore can also det

8、ermine the handle only, therefore the LR parsing process is one kind of standard selling and buying of real esgate within the same family process. After analysis, we use VC + + as a front-end development tool for the analysis of syntax ingredients more convenient visual, more easy to operate. Operat

9、ional procedures at the same time constantly improving procedures, until the source of optimal.Key WordsGrammatical analysis grammar LR (1 AnalysisMoves Selling and buying of real esgate within the same family課程設(shè)計(jì)任務(wù)書(shū)1、本課題的目的及意義課程設(shè)計(jì)實(shí)踐對(duì)學(xué)生鞏固所學(xué)基礎(chǔ)專業(yè)課程知識(shí)、進(jìn)行編譯系統(tǒng)基本技能訓(xùn)練、培養(yǎng)實(shí)踐動(dòng)手 能力,從而掌握編譯系統(tǒng)的基本工作原理、基本方法和基本開(kāi)發(fā)技術(shù),

10、最終達(dá)到具有一定的 編譯系統(tǒng)的實(shí)際開(kāi)發(fā)能力有重要意義。通過(guò)課程設(shè)計(jì),主要達(dá)到以下目的:1. 幫助學(xué)生深入 理解編譯原理的有關(guān)理論和鞏固編譯原理相關(guān)知識(shí)。 2. 鞏固學(xué)生學(xué)習(xí)的編譯原理、 程序設(shè)計(jì) 語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)等課程的基礎(chǔ)知識(shí),訓(xùn)練學(xué)生分析和解決編譯系統(tǒng)的相關(guān)問(wèn)題的能力,提高 學(xué)生的綜合素質(zhì)。 3. 從軟件工程的角度來(lái)看, 編譯原理課程設(shè)計(jì)是一個(gè)很好的實(shí)例,可 以訓(xùn)練學(xué)生軟件設(shè)計(jì)的能力以及編碼調(diào)試能力。2、本課題任務(wù)的主要內(nèi)容本課程設(shè)計(jì)主要內(nèi)容包括以下幾點(diǎn) :1、根據(jù)選定的題目,查閱資料,熟悉相關(guān)理論、方法;(1掌握文獻(xiàn)檢索方法,以獲得編譯系統(tǒng)開(kāi)發(fā)技術(shù)等相關(guān)資料;(2學(xué)習(xí)并熟練使用一種 4GL

11、 開(kāi)發(fā)平臺(tái)(如 VC+、 Java 、 Dephi 、 PB 、 VB 等 ;2、分析問(wèn)題,確定系統(tǒng)邏輯結(jié)構(gòu);3、確定系統(tǒng)所需模塊及模塊結(jié)構(gòu),并用流程圖描述各模塊;4、編碼及調(diào)試程序;5、撰寫課程設(shè)計(jì)說(shuō)明書(shū)。3、提交的成果1、一份符合課程設(shè)計(jì)說(shuō)明書(shū)撰寫規(guī)范的課程設(shè)計(jì)說(shuō)明書(shū)。2、一套系統(tǒng)原型。- 4 -目 錄第 1章 概述 6 1.1 項(xiàng)目背景 6 1.2 編寫目的 7 1.3 軟件定義 7 1.4 開(kāi)發(fā)環(huán)境 7 1.5 編譯環(huán)境簡(jiǎn)介 7第 2章需求分析 8 2.1 問(wèn)題陳述 8 2.2 需完成的功能 8 2.3 數(shù)據(jù)流圖 9 2.4 數(shù)據(jù)字典 10 2.4.1 數(shù)據(jù)項(xiàng) 10 2.4.2數(shù)據(jù)結(jié)構(gòu)

12、 11 2.4.3數(shù)據(jù)流 11 2.4.4數(shù)據(jù)存儲(chǔ) 12 2.4.5處理過(guò)程 12 2.5 E-R圖 14第 3章邏輯設(shè)計(jì) 15 3.1 系統(tǒng)組織基本工作流程 15 3.2 系統(tǒng)設(shè)計(jì)框圖 16第 4章總體設(shè)計(jì) 17 4.1 LR(1 分析器工作流程圖 17 4.2 流程簡(jiǎn)介 17 4.3 LR(1 分 析 思 想 19 4.4 各模塊流程圖 20第 5章詳細(xì)設(shè)計(jì) 22 5.1正規(guī)式構(gòu)造 NFA 22 5.2將 NFA 轉(zhuǎn)化為 DFA 24 5.3把 DFA 最小化 25第 6章 測(cè)試 26小結(jié) 28 致謝 29 參考文獻(xiàn) 30第 1章 概述1. 1 項(xiàng)目背景隨著科學(xué)技術(shù)的不斷提高 , 計(jì)算機(jī)科

13、學(xué)日漸成熟 , 其強(qiáng)大的功能已為人們深刻認(rèn)識(shí) , 它已進(jìn)入人類社會(huì)的各個(gè)領(lǐng)域并發(fā)揮著越來(lái)越重要的作用。作為計(jì)算機(jī)應(yīng)用的一部分 , 使用計(jì)算機(jī)對(duì) LR(1文法判定與預(yù)測(cè)分析器的構(gòu)造系統(tǒng) , 具有比手工運(yùn)算、 構(gòu)造所無(wú)法比 擬的優(yōu)點(diǎn)。 例如 :檢索迅速、 查找方便準(zhǔn)確性高等。 這些優(yōu)點(diǎn)能夠極大地提高判定 LR(1文法的效率 , 也是我們此次課程設(shè)計(jì)的目的。 因此, 開(kāi)發(fā)一套這樣的 LR(1文法判定與預(yù) 測(cè)分析器的構(gòu)造軟件成為很有必要的事情。編譯原理是大學(xué)計(jì)算機(jī)專業(yè)的必修課程。 而詞法分析作為其中的一部分占據(jù)著比較 重要的比重。詞法分析是編譯的第一個(gè)階段,它的主要任務(wù)是從左至右逐個(gè)字符地對(duì)源 程序進(jìn)

14、行掃描,產(chǎn)生一個(gè)個(gè)單詞序列,用以語(yǔ)法分析。通過(guò)本次課程設(shè)計(jì),學(xué)生對(duì)編譯的理解就不只停留在書(shū)本的概念上,而是知道怎樣 把編譯理論應(yīng)用到實(shí)際的編譯程序設(shè)計(jì)的實(shí)踐中。 對(duì)我們今后的學(xué)習(xí)和就業(yè)都是至關(guān)重 要的。1.2 編寫目的課程設(shè)計(jì)實(shí)踐對(duì)學(xué)生鞏固所學(xué)基礎(chǔ)專業(yè)課程知識(shí)、進(jìn)行編譯系統(tǒng)基本技能訓(xùn)練、培 養(yǎng)實(shí)踐動(dòng)手能力,從而掌握編譯系統(tǒng)的基本工作原理、基本方法和基本開(kāi)發(fā)技術(shù),最終 達(dá)到具有一定的編譯系統(tǒng)的實(shí)際開(kāi)發(fā)能力有重要意義。通過(guò)課程設(shè)計(jì),主要達(dá)到以下目 的:1. 幫助深入理解編譯原理的有關(guān)理論和鞏固編譯原理相關(guān)知識(shí)。2. 鞏固學(xué)習(xí)的編譯原理、程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)等課程的基礎(chǔ)知識(shí),訓(xùn)練分析 和解決編譯系

15、統(tǒng)的相關(guān)問(wèn)題的能力,提高我們的綜合素質(zhì)。3. 從軟件工程的角度來(lái)看, 編譯原理課程設(shè)計(jì)是一個(gè)很好的實(shí)例,可以訓(xùn)練我 們軟件設(shè)計(jì)的能力以及編碼調(diào)試能力。通過(guò)本次課程設(shè)計(jì),明白了分析器的原理、構(gòu)造方法及其實(shí)現(xiàn)?；菊莆樟诉f歸這 種有用的分析及實(shí)現(xiàn)方法,加深了對(duì)編譯原理這門課程的理解。通過(guò)本次課程設(shè)計(jì)我們 還可以為以后的畢業(yè)設(shè)計(jì)做準(zhǔn)備,熟悉了做畢業(yè)設(shè)計(jì)的格式、流程、方法。學(xué)會(huì)了怎樣- 6 -在圖書(shū)館查找相關(guān)的資料。提高了我的自學(xué)能力和自制力,我想做課程設(shè)計(jì)不僅是要我 們完成課業(yè)任務(wù),更重要的是教會(huì)了我們學(xué)習(xí)方法,鍛煉我們的意志,學(xué)會(huì)如何在獨(dú)立 的情況下更好的完成任務(wù)。1. 3 軟件定義LR 分析法指

16、從左至右掃描和自底向上的語(yǔ)法分析,且在分析的每一步,只須根據(jù) 分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào),并至多再向前看 k 個(gè)輸入符號(hào),能確定相 對(duì)于某產(chǎn)生式左符號(hào)的句柄是否已在分析棧的頂部形式, 從而就可以確定當(dāng)前所應(yīng)采用 的分析動(dòng)作(是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約 。 LR (0 分析不需要向前看輸入符號(hào) 就能判斷。1. 4 開(kāi)發(fā)環(huán)境本系統(tǒng)使用 TC 開(kāi)發(fā)。適用內(nèi)存不低于 256M 配備有 Windows2000, Windows2003, WindowsXP 系統(tǒng)的計(jì)算機(jī)第 2章 需求分析2.1 問(wèn)題陳述編譯過(guò)程的核心部分是語(yǔ)法分析。他的任務(wù)是在詞法分析識(shí)別單詞符號(hào)串的基礎(chǔ) 上,分析并判斷

17、程序的的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)言的語(yǔ)法結(jié)構(gòu)是用上下文無(wú)關(guān) 文法描述的。因此語(yǔ)法分析器的工作的本質(zhì)上就是按文法的產(chǎn)生式,識(shí)別輸入符號(hào)串是 否為一個(gè)句子。對(duì)于一個(gè)文法,當(dāng)給你一串符號(hào)是,如何知道它是不是該文法的一個(gè)句 子,這是這個(gè)課程設(shè)計(jì)所要解決的一個(gè)問(wèn)題。對(duì)輸入的文法 G ,在程序終實(shí)現(xiàn) CLOSURE(1,GO(I,X, FRIST 等的構(gòu)造,并利用這 些功能函數(shù)構(gòu)造出 LR(1項(xiàng)目集族。并且輸出結(jié)果。在此基礎(chǔ)上構(gòu)造 G 的 LR(1分析表, 并對(duì)輸入的句子進(jìn)行語(yǔ)法分析表,給出分析結(jié)果。LR分析法是給出一種能根據(jù)當(dāng)前分析棧的符號(hào)串和向右順序查看輸入串的 K 個(gè)符 號(hào)就可以唯一地確定分析器

18、的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約, 因而也就能唯 一地確定句柄。 LR 分析法的歸約過(guò)程是規(guī)范推到的逆過(guò)程,所以 LR 分析過(guò)程是一種規(guī) 范歸約過(guò)程。2.2 需完成的功能從鍵盤輸入一個(gè)文法(要求是上下文無(wú)關(guān)文法 ,保存到一個(gè)外部文件(或數(shù)據(jù)庫(kù) 中。判斷是否是 LR(1文法。從鍵盤接受一個(gè)符號(hào)串(源程序或從一個(gè)文本文件中接 受符號(hào)串(源程序 ,對(duì)其進(jìn)行語(yǔ)法分析,并將分析過(guò)程信息和結(jié)果(語(yǔ)法樹(shù)保存到 一個(gè)外部文件(或數(shù)據(jù)庫(kù)中。具體的說(shuō)就是,本課程設(shè)計(jì)所做的工作是建立一個(gè)針對(duì) LR (1文法的編譯器,本 課程設(shè)計(jì)將定義好的文法書(shū)寫的文件或從鍵盤接受的符號(hào)串作為輸入, 其中包括語(yǔ)法及 語(yǔ)義動(dòng)作。

19、然后根據(jù)給定的文法和 LR 分析表,構(gòu)造 LR 分析器,并輸出 LR 工作過(guò)程。 根據(jù) LR 分析器分析過(guò)程算法,通過(guò) action(和 goto(兩個(gè)函數(shù)即可實(shí)現(xiàn)算法的功能。本系統(tǒng)的主要功能包括以下幾個(gè)部分:系統(tǒng)登錄導(dǎo)入文法模塊計(jì)算可歸前綴項(xiàng)目規(guī)范族和文法判定后繼項(xiàng)目求解后繼狀態(tài)生成LR (0的判定若無(wú)錯(cuò)誤則構(gòu)造 LR (0分析表生成 action 表生成 goto 表求 follow 集- 8 - SLR 文法判定計(jì)算出 LR (1項(xiàng)目規(guī)范族生成后跟符運(yùn)算Closure (J 的運(yùn)算傳遞后跟符運(yùn)算生成 DFA構(gòu)造 LR (1分析表設(shè)計(jì)分析算法由分析算法判斷輸入符號(hào)串是否為該文法的句型 生成

20、語(yǔ)法樹(shù)退出2.3數(shù)據(jù)流圖頂層圖: 掃描項(xiàng)目集: 構(gòu)造分析表: 填寫 ACTION 表和 GOTO 表: 2.4 數(shù)據(jù)字典2.4.1 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)名:終結(jié)符別名:VT數(shù)據(jù)類型:CHAR長(zhǎng)度:40取值范圍:T001-T040數(shù)據(jù)項(xiàng)名:非終結(jié)符- 10 -別名:VN數(shù)據(jù)類型:CHAR長(zhǎng)度:30取值范圍:T001-T030數(shù)據(jù)項(xiàng)名:文法產(chǎn)生式序號(hào)別名:Mi數(shù)據(jù)類型:INT長(zhǎng)度:80取值范圍:M001-M080數(shù)據(jù)項(xiàng)名:項(xiàng)目產(chǎn)生式序號(hào)別名:Ij數(shù)據(jù)類型:INT長(zhǎng)度:200取值范圍:I001-I2002.4.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)名:文法產(chǎn)生式說(shuō)明:用來(lái)生成項(xiàng)目集組成:產(chǎn)生式序號(hào),左部,右部 數(shù)據(jù)結(jié)構(gòu)名:項(xiàng)目

21、產(chǎn)生式說(shuō)明:用來(lái)產(chǎn)生移進(jìn)或歸約動(dòng)作組成:項(xiàng)目產(chǎn)生式序號(hào),左部,右部, . 位置 數(shù)據(jù)結(jié)構(gòu)名:文法說(shuō)明:用來(lái)提供文法的信息組成:終結(jié)符,非終結(jié)符,開(kāi)始符, 產(chǎn)生式序號(hào),左部,右部 2.4.3數(shù)據(jù)流數(shù)據(jù)流名:移進(jìn)信息數(shù)據(jù)流來(lái)源:掃描項(xiàng)目集產(chǎn)生式;數(shù)據(jù)流去向:構(gòu)造分析表;數(shù)據(jù)結(jié)構(gòu):項(xiàng)目產(chǎn)生式序號(hào),左部,右部,位置 數(shù)據(jù)流名:歸約信息數(shù)據(jù)流來(lái)源:掃描項(xiàng)目集產(chǎn)生式;數(shù)據(jù)流去向:構(gòu)造分析表;數(shù)據(jù)結(jié)構(gòu):項(xiàng)目產(chǎn)生式序號(hào),左部,右部, . 位置 數(shù)據(jù)流名:終結(jié)符和非終結(jié)符數(shù)據(jù)流來(lái)源:文法數(shù)據(jù)流去向:判斷數(shù)據(jù)流名:核心項(xiàng)目集數(shù)據(jù)流來(lái)源:產(chǎn)生項(xiàng)目集數(shù)據(jù)流去向:項(xiàng)目集規(guī)范族表數(shù)據(jù)結(jié)構(gòu):項(xiàng)目產(chǎn)生式序號(hào),左部,右部, .

22、 位置 數(shù)據(jù)流名; rj數(shù)據(jù)流來(lái)源:填寫 ACTION 表數(shù)據(jù)流去向:分析表數(shù)據(jù)流名; Si數(shù)據(jù)流來(lái)源:填寫 ACTION 表數(shù)據(jù)流去向:分析表數(shù)據(jù)流名:產(chǎn)生式序號(hào)數(shù)據(jù)流來(lái)源:文法數(shù)據(jù)流去向:填寫分析表數(shù)據(jù)流名:項(xiàng)目產(chǎn)生式序號(hào)數(shù)據(jù)流來(lái)源:查找移進(jìn)的下一狀態(tài)數(shù)據(jù)流去向:填寫分析表2.4.4數(shù)據(jù)存儲(chǔ)數(shù)據(jù)存儲(chǔ)名:項(xiàng)目集規(guī)范族表輸入的數(shù)據(jù)流:核心項(xiàng)目集輸出的數(shù)據(jù)流:移進(jìn)的下一狀態(tài)序號(hào)組成:項(xiàng)目產(chǎn)生式序號(hào),左部,右部, . 位置 數(shù)據(jù)存儲(chǔ)名:分析表輸入的數(shù)據(jù)流:rj , Si , i數(shù)據(jù)結(jié)構(gòu):終結(jié)符,非終結(jié)符,項(xiàng)目產(chǎn)生式序號(hào), rj , Si , i2.4.5處理過(guò)程處理過(guò)程名:生成項(xiàng)目集輸入:文法產(chǎn)生

23、式;輸出:項(xiàng)目產(chǎn)生式序號(hào),核心項(xiàng)目集處理:該處理過(guò)程主要是用來(lái)生成項(xiàng)目集規(guī)范族表,以及將文法產(chǎn)生式轉(zhuǎn)化成項(xiàng)目產(chǎn)生 式;處理過(guò)程名:判斷動(dòng)作輸入:項(xiàng)目產(chǎn)生式- 12 -輸出:移進(jìn)信息,歸約信息處理:該處理過(guò)程主要用來(lái)判斷當(dāng)前項(xiàng)目產(chǎn)生式的下個(gè)動(dòng)作是移進(jìn)還是歸約 處理過(guò)程名:查找移進(jìn)的下一狀態(tài)輸入:移進(jìn)信息,項(xiàng)目集輸出:項(xiàng)目產(chǎn)生式序號(hào) i處理:該處理過(guò)程用來(lái)查找移進(jìn)的下個(gè)產(chǎn)生式的序號(hào)處理過(guò)程名:填寫分析表輸入:項(xiàng)目產(chǎn)生式序號(hào) i ,文法產(chǎn)生式序號(hào) j ;處理:最終生成分析表處理過(guò)程名:判斷輸入:項(xiàng)目產(chǎn)生式序號(hào) i ,終結(jié)符集和非終結(jié)集輸出:終結(jié)符,非終結(jié)符處理:判斷移進(jìn)項(xiàng)目是終結(jié)符還是非終結(jié)符2.5

24、E-R 圖文法的 E-R 圖: 項(xiàng)目產(chǎn)生式的 E-R 圖:- 14 -第 3章 邏輯設(shè)計(jì) 3. 1系統(tǒng)組織基本工作流程(以總體邏輯結(jié)構(gòu)圖表達(dá) 3. 2 系統(tǒng)設(shè)計(jì)框圖 - 16 -第 4章 總體設(shè)計(jì)4. 1 LR(1 分析器工作流程圖 圖 4.1 LR(1分析器工作流程圖4.2 流程簡(jiǎn)介所謂 LR (1分析法,就是指如果一個(gè)文法的 LR(1分析表中不含多重入口時(shí), (即 任何一個(gè) LR(1項(xiàng)目集中無(wú)移近規(guī)約沖突或規(guī)約規(guī)約沖突 , 則該文法為 LR(1文法。 實(shí)現(xiàn) LR (1分析的程序又稱為 LR (1分析程序或 LR (1分析器。如果一個(gè)文法能滿 足以下特性:無(wú)二義性,無(wú)左遞歸,無(wú)有害產(chǎn)生式,無(wú)

25、多余產(chǎn)生式,無(wú) 產(chǎn)生式,那 么就可以構(gòu)造 LR (1分析表。當(dāng)文法滿足條件后,先構(gòu)造出 LR(0項(xiàng)目規(guī)范族,然后 構(gòu)造 LR(0分析表,當(dāng)此分析表中含有移近規(guī)約沖突或規(guī)約規(guī)約沖突時(shí),便計(jì)算 FIRST 和 FOLLOW 集合,構(gòu)造 SLR(1分析表,如果此分析表中還出現(xiàn)移近規(guī)約沖突或 規(guī)約規(guī)約沖突時(shí),則運(yùn)用 closure 算法,構(gòu)造 LR(1項(xiàng)目規(guī)范族,最后構(gòu)造 LR(1分 析表,利用分析表,構(gòu)造 LR(1分析器模擬構(gòu)造器。 LR (1的語(yǔ)法分析程序包含了四個(gè) 部分,總控程序, LR(1分析表,先進(jìn)后出的狀態(tài)棧,先進(jìn)先出的掃描隊(duì)列。本程序也 是采用了同樣的方法進(jìn)行語(yǔ)法分析,該程序是采用了 C

26、+語(yǔ)言來(lái)編寫,其邏輯結(jié)構(gòu)圖如 下: - 18 -圖 4.2 各模塊調(diào)用關(guān)系圖對(duì)一個(gè)文法構(gòu)造了它的 LR(1分析表后就可以在 LR 分析器的總控程序 (驅(qū)動(dòng)程序 控制下對(duì)輸入串進(jìn)行分析,即根據(jù)輸入串的當(dāng)前符號(hào)和分析棧的棧頂狀態(tài)查找 LR(1分 析表應(yīng)采取的動(dòng)作,對(duì)狀態(tài)棧進(jìn)行相應(yīng)的操作即移進(jìn)、歸約、接受或報(bào)錯(cuò)。具體說(shuō)明如 下:1 若 ACTIONS,a= Sj , a 為終結(jié)符, j 移入狀態(tài)棧。 2 若 ACTIONS,a= r j , a 為終結(jié)符或 #號(hào),則用第 j 個(gè)產(chǎn)生式歸約,并將兩個(gè)棧的 指針減去 k ,其中 k 為第 j 個(gè)產(chǎn)生式右部的符號(hào)串長(zhǎng)度,這時(shí)當(dāng)前面臨符號(hào)為第 j 個(gè)產(chǎn) 生式

27、左部的非終結(jié)符。3 若 ACTIONS,a=acc, a 應(yīng)為 '#'號(hào),則為接受,表示分析成功。4 若 GOTOS,A=j, A 為非終結(jié)符,表明前一動(dòng)作是用關(guān)于 A 的產(chǎn)生式歸約的,當(dāng) 前面臨非終結(jié)符 A 應(yīng)移入符號(hào)棧, j 移入狀態(tài)棧。對(duì)于終結(jié)符的 GOTOS,a已和 ACTIONS,a重合。5 若 ACTIONS,a=空白,則轉(zhuǎn)向出錯(cuò)處理。4.3 LR(1 分 析 思 想LR(1分 析 的 基 本 思 想 :LR(1方 法 按 每 個(gè) 具 體 的 句 型 設(shè) 置 展 望 信 息 。例 :如 果 存 在 如 下 的 一 些 句 型 Aa , Ab , Ac , 則 FOL

28、LOW(A=a,b,c處 理 到 句 型 A , 只 當(dāng) 輸 入 符 號(hào) 為 a 時(shí) 歸 約 ;處 理 到 句 型 A , 只 當(dāng) 輸 入 符 號(hào) 為 b 時(shí) 歸 約 ;處 理 到 句 型 A , 只 當(dāng) 輸 入 符 號(hào) 為 c 時(shí) 歸 約LR(1分 析若 A a Bb屬 于 項(xiàng) 目 集 I 時(shí) , 則 B g也 屬 于 I , 把 FIRST(b作 為 用 產(chǎn) 生 式 B g 歸 約 的 搜 索 符 (用 以 代 替 SLR(1分 析 中 的 FOLLOW(B , 并 把 此 搜 索 符 號(hào) 的 集 合 也 放 在 相 應(yīng) 項(xiàng) 目 的 后 面 , 這 種 處 理 方 法 即 為 LR(1方

29、法(1 I的 任 何 項(xiàng) 目 屬 closure(I;(2若 A 1. B 2, a closure(I, B 是 一 產(chǎn) 生 式 , 那 么 對(duì) 于 FIRST(2a 中 的 每 個(gè) 終 結(jié) 符 b , 如 果 B . ,b不 在 closure(I中 , 則 把 它 加 進(jìn) 去 ;(3重 復(fù) (1 (2 , 直 至 closure(I不 再 增 大 。GO 函 數(shù)若 I 是 一 個(gè) 項(xiàng) 目 集 , X 是 一 個(gè) 文 法 符 號(hào)GO(I, X= closure(J其 中 J= 任 何 形 如 A X . ,a的 項(xiàng) 目 A .X ,a ILR(I項(xiàng) 目 規(guī) 范 族 C 的 構(gòu) 造 算 法

30、類 同 LR(0的 , 只 是初 始 時(shí) :C= closure(S . S,#;LR(1的 優(yōu) 缺 點(diǎn) :優(yōu) 點(diǎn) :LR(1分 析 對(duì) 搜 索 符 的 計(jì) 算 方 法 比 較 確 切 , 沒(méi) 有 無(wú) 效 歸 約 , 適 應(yīng) 的 文 法 更 廣缺 點(diǎn) :LR(1分 析 表 的 狀 態(tài) 數(shù) 目 龐 大4.4 各模塊流程圖LR(1分析器構(gòu)造及輸入串分析流程: 求項(xiàng)目集規(guī)范族:分析表構(gòu)造流程- 20 -總控程序流程 第 5章 詳細(xì)設(shè)計(jì)負(fù)責(zé)模塊:DFA 生成算法其中包括三個(gè)步驟:(1由正規(guī)式構(gòu)造 NFA ,(2把 NFA 轉(zhuǎn)化為與其等價(jià)的 DFA ,(3把 DFA 最小化。5.1 正規(guī)式構(gòu)造 NFAI

31、nput : 一個(gè)字母表 ( 上的 Regular Experssion rOutput : 一個(gè)接受 L(r 的 NFA NMethod : 把 r 解析成為子表達(dá)式 (subexpressions,然后使用下面的 1,2 規(guī)則,為 r 中 的基本符號(hào) (basic symbols, 基本符號(hào)就是 和 中的字符 構(gòu)建 NFA ,基本符號(hào)符合 1,2 關(guān)于正 規(guī)式的定義,注意,假如 symbol a 出現(xiàn)多次,那么它每次出現(xiàn)都要構(gòu)建一個(gè) NFA 。之后,我們需 要通過(guò) r 的語(yǔ)法結(jié)構(gòu),通過(guò)規(guī)則 3 組合前面構(gòu)建的 NFA ,直到得到整個(gè) NFA 為止。對(duì)于中間產(chǎn)生 的 NFA ,它只有一個(gè)終態(tài)

32、,沒(méi)有進(jìn)入開(kāi)始裝狀態(tài)的邊,也沒(méi)有離開(kāi)接受狀態(tài)的邊。規(guī)則 1對(duì)于空記號(hào) ,生成下面的 NFA 。 每次構(gòu)建時(shí), i,f 的值都不一樣,因此可見(jiàn)構(gòu)造一個(gè)識(shí)別 的 NFA ,會(huì)產(chǎn)生 2個(gè)新的狀態(tài)規(guī)則 2對(duì)于 的字母表中的元素 a ,生成下面的 NFA 。 同樣, 對(duì)于 aaa , 第一個(gè) a 構(gòu)造的 NFA 中的 i,f 不會(huì)和第 2個(gè) a 構(gòu)造的 i,f 一樣, 因此可見(jiàn)構(gòu)造一個(gè)識(shí) 別 中的每個(gè)字符 a 的 NFA ,會(huì)產(chǎn)生 2個(gè)新的狀態(tài)- 22 -規(guī)則 3令正規(guī)表達(dá)式 s 和 t 的 NFA 分別為 N(s和 N(t。a 對(duì)于表達(dá)式 s|t 構(gòu)建 NFA N(s|t b 對(duì)于表達(dá)式 st ,構(gòu)建

33、 N(st c 對(duì)于正規(guī)式 s*,構(gòu)造 N(s* d 對(duì) 于 (s,使用 N(s本身作為它的 NFA ,也就是不用構(gòu)造新的 NFA5.2將 NFA 轉(zhuǎn)化為 DFAInput : 一個(gè) NFA NOutput : 接受相同語(yǔ)言的 DFA DMethod : 為 D 構(gòu)架一個(gè) transition table(轉(zhuǎn)換表 Dtran,每個(gè) DFA 的狀態(tài)是一個(gè) NFA 的 狀態(tài)集合 (這里一定要注意前面說(shuō)過(guò)的 12 兩點(diǎn) 。定義以下的操作:-closure(s 從 NFA 的狀態(tài) s 出發(fā),僅通過(guò) 遷移能夠到達(dá)的 NFA 的狀態(tài)集 合-closure(T 從 T 中包含的某個(gè) NFA 的狀態(tài) s 出發(fā)

34、,僅通過(guò) 遷移能夠到達(dá) 的 NFA 的狀態(tài)集合move(T, a 從 T 中包含的某個(gè) NFA 的狀態(tài) s 出發(fā),通過(guò)輸入符號(hào) a 遷移能夠 到達(dá)的 NFA 的狀態(tài)集合a. 構(gòu)造 NFA N的狀態(tài) K 的子集算法:令 Dstates 中僅包含 -closure(s, 并設(shè)置狀態(tài)為未標(biāo)記 ; while Dstates中包含未標(biāo)記的狀態(tài) T dobegin標(biāo)記 T;for 各輸入記號(hào) a dobeginU := -closure(move(T, a;if U不在 Dstates 中 then將 U 追加到 Dstates 中,設(shè)置狀態(tài)為未標(biāo)記 ; DtransT, a := U;endendb.

35、 -closure(T的計(jì)算方法如下:將 T 中的所有狀態(tài)入棧 ;設(shè)置 -closure(T的初始值為 T;while 棧非空 dobegin從棧頂取出元素 t;for 從 t 出發(fā)以 為邊能夠到達(dá)的各個(gè)狀態(tài) u doif u不在 -closure(T中 thenbegin將 u 追加到 -closure(T中 ; 將 u 入棧 ;endend- 24 -5.3把 DFA 最小化通過(guò) NFA 轉(zhuǎn)化而成的 DFA 不一定是最簡(jiǎn)的,也就是說(shuō),有多余的狀態(tài)可以被刪除, 對(duì)于每一個(gè)正規(guī)定義,我們一定可以得到一個(gè)唯一的最簡(jiǎn)的 DFA我們回顧一下 Move 函數(shù), DFA 的 move 函數(shù):move :

36、 (state, symbol -> S注意,這里 (state, symbol表示的是一個(gè)集合,這里規(guī)范的數(shù)學(xué)表達(dá)應(yīng)該是: move : (state, symbol | 所有屬于 DFA 的 state 和 symbol -> S 或者 move : S × -> S假如一個(gè) DFA 的 move 函數(shù)不是全函數(shù), 那么必須引入死狀態(tài)。 假如某個(gè) DFA 的 move 函數(shù)是全函數(shù),那么每個(gè)狀態(tài)在所有 input symbol下都有出邊,比如: 這個(gè) DFA 每個(gè)狀態(tài)都可以接受所有的 input symbol,這里是 a , b 。而下面的 DFA : 先不要看

37、紅色部分,那么這個(gè) DFA 的狀態(tài) c , d ,它們無(wú)法通過(guò) input symbol b 進(jìn)入下 一個(gè)狀態(tài),我們可以加上紅色的部分,把這個(gè) move 函數(shù),轉(zhuǎn)化成為一個(gè)全函數(shù),并且, 經(jīng)過(guò)轉(zhuǎn)化操作之后, 新的 DFA 與原 DFA 等價(jià)。 這個(gè)紅色部分標(biāo)識(shí)的狀態(tài), 被叫做死狀態(tài)。第 6章 測(cè)試測(cè)試數(shù)據(jù)放在 1.txt (任意文本文件中,測(cè)試結(jié)果放在 2.txt (任意文本文件 中。測(cè)試數(shù)據(jù):b(ab*運(yùn)行界面如下: - 26 - 測(cè)試的字符串: 檢驗(yàn)的匹配結(jié)果: 小 結(jié)編譯原理是一門很重要的課程。我們平常寫小的 C 語(yǔ)言程序會(huì)感到困難,而編譯原 理則是關(guān)于編寫編譯器的技術(shù),難度之大可想而知

38、。編譯器的編寫一直被認(rèn)為是十分困 難的事情,難怪第一 Fortran 的編譯器據(jù)說(shuō)花了 18年的時(shí)間才完成。當(dāng)然編譯原理和 編譯技術(shù)并不是相同的,編譯原理更注重理論方面的知識(shí),編譯技術(shù)更注重實(shí)際編寫編 譯器過(guò)程中用到的技術(shù)。在編程序的過(guò)程中,有時(shí)會(huì)和一個(gè)小小的錯(cuò)誤較上半天的勁, 等到最后才發(fā)現(xiàn)只是由于語(yǔ)法用的不正確,算法是可行的。這樣在一個(gè)小小的語(yǔ)法錯(cuò)誤 上浪費(fèi)許多時(shí)間是很不值得,所以在今后的語(yǔ)言學(xué)習(xí)中,我會(huì)重視語(yǔ)法的細(xì)節(jié)。另外在 程序設(shè)計(jì)上, 以前自己傾向于直接寫程序, 很少使用流程圖。 后來(lái)發(fā)現(xiàn)先設(shè)計(jì)出流程圖, 那么程序的結(jié)構(gòu)就會(huì)清晰的多,編寫的時(shí)候也會(huì)更節(jié)省時(shí)間。我在編程過(guò)程中花的時(shí)間五天左右,因?yàn)樽约褐皇蔷帉懞透膭?dòng)了部分代碼,因?yàn)檎?規(guī)式轉(zhuǎn)為 NFA 以及 NFA 的確定化和最小化, 在書(shū)上和網(wǎng)上都有大量的資料可以讓我們參 考,不過(guò)我還是深入研究了程序代碼及原理。原理其實(shí)是最重要的,因?yàn)樵砼? 流程圖出來(lái)后,代碼的