編譯原理課程設(shè)計(jì)LR語(yǔ)法分析構(gòu)造器的設(shè)計(jì)

1、安徽工程科技學(xué)院編譯原理課程設(shè)計(jì)（論文）前言計(jì)算機(jī)語(yǔ)言之所以能由單一的機(jī)器語(yǔ)言發(fā)展到現(xiàn)今的數(shù)千種高級(jí)語(yǔ)言，就是因?yàn)橛辛司幾g技術(shù)，編譯原理技術(shù)是計(jì)算機(jī)科學(xué)中發(fā)展的最迅速、最成熟的一個(gè)分支，它集中體現(xiàn)了計(jì)算機(jī)發(fā)展成果與精華。未來(lái)計(jì)算機(jī)工作者，都應(yīng)該掌握這門(mén)基礎(chǔ)的專(zhuān)業(yè)基礎(chǔ)知識(shí)?！熬幾g原理”是計(jì)算機(jī)及其相關(guān)專(zhuān)業(yè)的重要專(zhuān)業(yè)基礎(chǔ)課，主要研究設(shè)計(jì)和構(gòu)造編譯程序的原理和方法。全面、深入地探討了編譯器設(shè)計(jì)方面的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯、運(yùn)行時(shí)刻環(huán)境、目標(biāo)代碼生成、代碼優(yōu)化技術(shù)、并行性檢測(cè)以及過(guò)程間分析技。編譯原理蘊(yùn)涵著計(jì)算機(jī)學(xué)科中解決問(wèn)題的思路、形式化問(wèn)題和解決問(wèn)題的方法，對(duì)

2、應(yīng)用軟件和系統(tǒng)軟件的設(shè)計(jì)與開(kāi)發(fā)有一定的啟發(fā)和指導(dǎo)作用，編譯程序構(gòu)造的原理和技術(shù)在軟件工程、語(yǔ)言轉(zhuǎn)換等許多領(lǐng)域中有著廣泛應(yīng)用。語(yǔ)法分析是編譯程序的核心部分。語(yǔ)法分析的作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子，目前語(yǔ)法分析常用的方法有自頂向下分析和自頂向上分析兩大類(lèi)。自頂向上分析包括確定分析和不確定分析，自頂向上分析又包括算符優(yōu)先分析和lr分析。鑒于此，運(yùn)用這些分析方法構(gòu)造一個(gè)簡(jiǎn)單的分析程序是很有實(shí)踐意義的。目 錄編譯原理課程設(shè)計(jì)任務(wù)書(shū) .3第1章 概述.5 1.1 背景.5 1.2 目的.5 1.3 軟件定義.51.4 開(kāi)發(fā)環(huán)境.5第2章 需求分析.6 2.1 問(wèn)題陳述.6

3、 2.2 需完成的功能.6第3章 邏輯設(shè)計(jì). 7 3.1 模塊設(shè)計(jì).7 3.1.1 lr（1）項(xiàng)目集規(guī)范族的構(gòu)造算法.8 3.1.2 lr（1）分析表的構(gòu)造算法.8 3.2 流程圖.9第4章 總體設(shè)計(jì).15 4.1 構(gòu)造項(xiàng)目集規(guī)范族模塊.15 4.2 構(gòu)造預(yù)測(cè)分析表模塊.15 4.3 分析串程序模塊.15第5章 界面設(shè)計(jì).16小結(jié).33致謝.34參考文獻(xiàn).35 附錄 源程序清單.36編譯原理課程設(shè)計(jì)任務(wù)書(shū)1、本課題的目的及意義課程設(shè)計(jì)實(shí)踐對(duì)學(xué)生鞏固所學(xué)基礎(chǔ)專(zhuān)業(yè)課程知識(shí)、進(jìn)行編譯系統(tǒng)基本技能訓(xùn)練、培養(yǎng)實(shí)踐動(dòng)手能力，從而掌握編譯系統(tǒng)的基本工作原理、基本方法和基本開(kāi)發(fā)技術(shù)，最終達(dá)到具有一定的編譯系統(tǒng)

4、的實(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開(kāi)發(fā)平臺(tái)（如vc+、java、dephi、pb

5、、vb等）；2、分析問(wèn)題，確定系統(tǒng)邏輯結(jié)構(gòu)；3、確定系統(tǒng)所需模塊及模塊結(jié)構(gòu)，并用流程圖描述各模塊；4、編碼及調(diào)試程序；5、撰寫(xiě)課程設(shè)計(jì)說(shuō)明書(shū)。3、提交的成果1、一份符合課程設(shè)計(jì)說(shuō)明書(shū)撰寫(xiě)規(guī)范的課程設(shè)計(jì)說(shuō)明書(shū)。2、一套系統(tǒng)原型。附錄一：課程設(shè)計(jì)說(shuō)明書(shū)撰寫(xiě)要求1、基本要求：（1）能反映完成了設(shè)計(jì)內(nèi)容要求；（2）要求撰寫(xiě)不少于5000個(gè)文字（20頁(yè)）的文檔；（3）文檔中至少要包括：數(shù)據(jù)流圖、邏輯結(jié)構(gòu)圖、系統(tǒng)功能圖、算法流程圖。（4）用戶界面設(shè)計(jì)：附界面的抓圖或手工繪圖，及其主要核心部分代碼。2、文檔格式要求（參考課程設(shè)計(jì)參考模板）（1）封面（2）前言（3）目錄（4）課程設(shè)計(jì)任務(wù)書(shū)（5）正文（分章、層

6、次等，每一章從新一頁(yè)開(kāi)始）概述 包括項(xiàng)目背景、編寫(xiě)目的、軟件定義、開(kāi)發(fā)環(huán)境等內(nèi)容。需求分析 問(wèn)題陳述、需完成的功能。以數(shù)據(jù)流圖和數(shù)據(jù)字典表達(dá)。邏輯設(shè)計(jì) 描述系統(tǒng)組織和基本工作流程。以總體邏輯結(jié)構(gòu)圖表達(dá)?？傮w設(shè)計(jì) 畫(huà)出軟件功能圖，描述每一個(gè)功能所完成的任務(wù)情況。界面設(shè)計(jì) 界面設(shè)計(jì)要合理，給出主要界面和主要代碼并有適當(dāng)?shù)恼f(shuō)明。（6）小結(jié)（7）參考文獻(xiàn)對(duì)于引用的參考文獻(xiàn)，列出主要參考文獻(xiàn)（至少10篇）的題錄及摘要或參考文獻(xiàn)原文。（8）其他圖表原始資料或參考資料附錄第1章 概述1.1 背景“編譯原理”是計(jì)算機(jī)及其相關(guān)專(zhuān)業(yè)的重要專(zhuān)業(yè)基礎(chǔ)課，主要研究設(shè)計(jì)和構(gòu)造編譯程序的原理和方法。全面、深入地探討了編譯器

7、設(shè)計(jì)方面的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯、運(yùn)行時(shí)刻環(huán)境、目標(biāo)代碼生成、代碼優(yōu)化技術(shù)、目標(biāo)代碼生成。語(yǔ)法分析是整個(gè)編譯程序的核心部分，而lr分析方法對(duì)文法要求比起其他分析方法能力較強(qiáng)lr（k）分析方法是1965年knuth提出的，括號(hào)中的k表示向右查看輸入串符號(hào)的個(gè)數(shù)。這種方法比起自頂向下的ll（1）分析方法和自低向上的優(yōu)先分析方法對(duì)文法的限制要少的多，也就是說(shuō)對(duì)于大多數(shù)用無(wú)二義性上下文無(wú)關(guān)文法描述的語(yǔ)言都可以用相應(yīng)的lr分析器進(jìn)行識(shí)別，而且這種方法還具有分析速度快，能準(zhǔn)確、即時(shí)地指出出錯(cuò)位置。自低向上分析的關(guān)鍵問(wèn)題是在分析過(guò)程中如何確定句柄。lr分析法正是給出一種

8、能根據(jù)當(dāng)前分析棧中的符號(hào)串（通常以狀態(tài)表示）和向右順序查看輸入串的k個(gè)（k0）符號(hào)就可惟一地確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能惟一地確定句柄。lr分析法的歸約過(guò)程是規(guī)范推到的逆過(guò)程，所以lr分析過(guò)程是一種規(guī)范歸約的過(guò)程。1.2目的因?yàn)閘r（0）分析過(guò)程中不需要向右查看輸入符號(hào)，因而它可以對(duì)文法的限制較大，對(duì)絕大多數(shù)的高級(jí)語(yǔ)言的語(yǔ)法分析器是不能適用的，所以，要分析絕大多數(shù)的高級(jí)語(yǔ)言編譯程序的需要，采用向后查看一個(gè)輸入符號(hào)的方法，即lr（1）的方法。（1）掌握并深刻理解有窮自動(dòng)機(jī)在lr分析法中的應(yīng)用（即lr分析器）。（2）掌握l(shuí)r分析法的思想，學(xué)會(huì)特定分析表的構(gòu)造方法，利

9、用給出的分析表進(jìn)行l(wèi)r分析。1.3 軟件定義對(duì)任意給定的上下文無(wú)關(guān)文法g，構(gòu)造其lr（1）項(xiàng)目集規(guī)范族、預(yù)測(cè)分析表，并且在此基礎(chǔ)上進(jìn)一步構(gòu)造其lr（1）分析表。1.4 開(kāi)發(fā)環(huán)境軟件：windows 7操作系統(tǒng) , microsoft visual c+ 6.0；編程語(yǔ)言：c+第2章 需求分析2.1問(wèn)題陳述設(shè)計(jì)的題目是要對(duì)lr（1）類(lèi)文法判定及其分析器進(jìn)行構(gòu)造。如果一個(gè)文法的lr（1）分析表不含多重入口時(shí)，（即任何一個(gè)lr（1）項(xiàng)目集中無(wú)移進(jìn)歸約沖突或歸約歸約沖突），則稱(chēng)該文法為lr（1）文法，所構(gòu)造的相應(yīng)分析表稱(chēng)為lr（1）分析，使用lr（1）分析表的分析器稱(chēng)為lr（1）分析器或稱(chēng)規(guī)范的lr分

10、析器。所以，要判斷一個(gè)文法是否是lr（1）類(lèi)文法，則主要是看是否存在兩個(gè)沖突。2.2 需完成的功能一個(gè)lr分析器由3個(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)）。綜上所述，要實(shí)現(xiàn)本次設(shè)計(jì)所需工作主要有以下方面：1、 構(gòu)造

11、項(xiàng)目集規(guī)范族；2、 構(gòu)造預(yù)測(cè)分析表；3、 設(shè)計(jì)總控程序，完成分析過(guò)程。第3章 邏輯設(shè)計(jì)3.1 模塊設(shè)計(jì) lr分析器工作過(guò)程示意圖如圖1.1所示。其中sp為棧指針，si為狀態(tài)棧，xi為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系gotosi,x=si確定，該關(guān)系式是指當(dāng)棧頂狀態(tài)為si，遇到當(dāng)前文法符號(hào)為x時(shí)應(yīng)轉(zhuǎn)向狀態(tài)sj。x為終結(jié)符或非終結(jié)符。 actionsi,a規(guī)定了棧頂狀態(tài)si時(shí)遇到輸入符號(hào)a應(yīng)執(zhí)行的動(dòng)作。動(dòng)作有4種可能：（1） 移進(jìn)： 當(dāng)si=gotosi,a成立，則把si移入到狀態(tài)棧，把a(bǔ)移入到文法符號(hào)棧。其中i，j表示狀態(tài)號(hào)。spsns1xnnx1x0s0. 總控程序action表goto表輸入

12、串xxxxxxxx#輸出圖1-1 lr分析器工作過(guò)程示意圖（2） 歸約： 當(dāng)在棧頂形成句柄為時(shí)，則用歸約為相應(yīng)的非終結(jié)符a，即當(dāng)文法中有a的產(chǎn)生式，而的長(zhǎng)度為r（即|=r），則從狀態(tài)和文法符號(hào)棧中自頂向下去掉r個(gè)符號(hào)，即棧指針sp減去r。并把a(bǔ)移入文法符號(hào)棧內(nèi)，再把滿足sj=gotiosi,a的狀態(tài)移入狀態(tài)棧，其中si為修改指針后的棧頂狀態(tài)。（3） 接受acc： 當(dāng)歸約到文法符號(hào)棧中只剩文法的開(kāi)始符號(hào)s時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)輸入是#，則為分析成功。（4） 報(bào)錯(cuò)： 當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說(shuō)明輸入串不是該文法所能接受的句子。lr分析器的關(guān)鍵部分是分析表的

13、構(gòu)造。構(gòu)造lr分析表，那么先解決lr項(xiàng)目集規(guī)范族的構(gòu)造。 lr項(xiàng)目集規(guī)范族的項(xiàng)目類(lèi)型分為如下四種：1、 移進(jìn)項(xiàng)目圓點(diǎn)后為終結(jié)符的項(xiàng)目，形如aa，其中、v*，avt，相應(yīng)狀態(tài)為移進(jìn)狀態(tài)。2、 規(guī)約項(xiàng)目圓點(diǎn)在產(chǎn)生式右部的最后的項(xiàng)目，形如a其中v*，對(duì)于=的項(xiàng)目為a（對(duì)應(yīng)的產(chǎn)生式為a），相應(yīng)狀態(tài)為歸約狀態(tài)。3、待約項(xiàng)目圓點(diǎn)后為非終結(jié)符的項(xiàng)目，形如ab，其中、v*，bvn，這表明用產(chǎn)生式a的右部歸約時(shí)，首先要將b的產(chǎn)生式右部歸約為b，對(duì)a的右部才能繼續(xù)進(jìn)行分析。也就是期待著繼續(xù)分析過(guò)程中首先能進(jìn)行歸約得到b。4、接受項(xiàng)目當(dāng)歸約項(xiàng)目為ss時(shí)則表明已分析成功，即輸入串為該文法的句子，相應(yīng)狀態(tài)為接受狀態(tài)。3

14、.1.1 lr（1）項(xiàng)目集規(guī)范族的構(gòu)造算法以ss，#屬于初始項(xiàng)目集中，把“#”號(hào)作為向前搜索符，表示活前綴為（若是有關(guān)s產(chǎn)生式的某一右部）要?dú)w約成s時(shí)，必須面臨輸入符為“#”號(hào)才行。我們對(duì)初始項(xiàng)目ss，#求閉包后再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的lr（1）項(xiàng)目集族。具體構(gòu)造步驟如下：（1） 構(gòu)造lr（1）項(xiàng)目集的閉包函數(shù)。 假定i是一個(gè)項(xiàng)目集，i的任何項(xiàng)目都屬于closure(i)。 ab，a屬于closure(i)，b是文法中的產(chǎn)生式，若有項(xiàng)目v*，bfirst(a)，則b，b也屬于closure(i)中。 重復(fù)直到closure(i)不再增大為止。（2） 構(gòu)造轉(zhuǎn)換函數(shù)。lr（1）轉(zhuǎn)換函數(shù)的構(gòu)造

15、與lr（0）的相似，go（i，x）= closure(j)其中i是lr（1）的項(xiàng)目集，x是文法符號(hào)：j=任何形如lr（1）分析表的構(gòu)造ax，a的項(xiàng)目| ax，a i對(duì)文法g的lr（1）項(xiàng)目集族的構(gòu)造仍以ss，#為初態(tài)的初始項(xiàng)目，然后對(duì)其求閉包和轉(zhuǎn)換函數(shù)，直到項(xiàng)目集不再增大。3.1.2 lr（1）分析表的構(gòu)造算法由于一個(gè)lr（1）項(xiàng)目可以看成兩個(gè)部分組成，一部分和lr（0）項(xiàng)相同，這部分稱(chēng)為心，另一部分為向前搜索符合集。因而lr（1）分析表的構(gòu)造與lr（0）分析表的構(gòu)造在形式上基本相同，只是歸約項(xiàng)目的歸約動(dòng)作取決于歸約項(xiàng)目的向前搜索符集，即只有當(dāng)面臨的輸入符屬于向前搜索符的集合，才做歸約動(dòng)作，其

16、他情況均出錯(cuò)。具體構(gòu)造過(guò)程如下：若已構(gòu)造出某文法的lr（1）項(xiàng)目集族c。c=i0，i1，.，in其中的ik的k為分析器的狀態(tài)，則動(dòng)作action表和狀態(tài)轉(zhuǎn)換goto表構(gòu)造方法如下：(1) 若項(xiàng)目aa，b屬于ik，且go（ik，a）=ij，其中avt，則置actionk，a=sj。其sj的含義是把輸入符號(hào)a和狀態(tài)j分別移入文法符號(hào)棧和狀態(tài)棧。(2) 若項(xiàng)目a，a屬于ik，則置actionk，a=rj，其中avt，rj的含義為把當(dāng)前棧頂符號(hào)串歸約為a（即用產(chǎn)生式a歸約）。j為在文法中對(duì)產(chǎn)生式a的編號(hào)。(3) 若項(xiàng)目ss，#屬于ik，則置action，=“”，表示接受。(4) 若（ik，），其中av

17、n ，則置gotok，a=j。表示轉(zhuǎn)入j狀態(tài)，則置當(dāng)前文法符號(hào)棧頂為a，狀態(tài)棧頂為j。(5) 凡不能用規(guī)則（1）（4）填入分析表中的元素，均置“報(bào)錯(cuò)標(biāo)志”。可以填入空白以表示。3.2 流程圖圖1-2(a) 構(gòu)造lr（1）項(xiàng)目集規(guī)范族流程圖圖1-2（b） 構(gòu)造lr（1）項(xiàng)目集規(guī)范族流程圖圖1-2（c） 構(gòu)造lr（1）項(xiàng)目集規(guī)范族流程圖圖1-3 構(gòu)造lr（1）分析表流程圖1-4 lr（1）串分析程序流程圖第4章 總體設(shè)計(jì)功能設(shè)計(jì)為能實(shí)現(xiàn)本次課程設(shè)計(jì)的功能，同時(shí)減小工作量，根據(jù)需求，構(gòu)造lr（1）項(xiàng)目集規(guī)范族需要用到first集，主要思路是采用替換策略以及刪除重復(fù)的元素。數(shù)據(jù)結(jié)構(gòu)使用的是鏈表。這不是

18、核心部分，所以不再贅述。將功能分為三個(gè)大模塊，即構(gòu)造項(xiàng)目集規(guī)范族、分析表、和分析串程序。以下是對(duì)構(gòu)造項(xiàng)目集規(guī)范族、分析表、和分析串程序的設(shè)計(jì)敘述：4.1 構(gòu)造項(xiàng)目集規(guī)范族模塊項(xiàng)目集規(guī)范族是整個(gè)設(shè)計(jì)的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)：實(shí)現(xiàn)其構(gòu)造，在數(shù)據(jù)結(jié)構(gòu)選用方面要求能夠方便查找、而且能夠節(jié)省空間。據(jù)此，主要采用了c+中stl中隊(duì)列、集合、向量，作為主要數(shù)據(jù)存放的容器，并用結(jié)構(gòu)體存放重要產(chǎn)生式的重要信息。算法設(shè)計(jì)：由課本上關(guān)于構(gòu)造項(xiàng)目集規(guī)范族的敘述，聯(lián)想到了圖的廣度遍歷，所以將擴(kuò)展后的文法ss,#作為核放在隊(duì)列中，由核求閉包，每求出一個(gè)就放入集合中（主要是可以去除重復(fù)的）如果插入集合成功，就把結(jié)構(gòu)體插入向量中，插

19、入隊(duì)列中，直到隊(duì)列空，說(shuō)明由核產(chǎn)生的項(xiàng)目已經(jīng)構(gòu)造完，下一步只需從向量中取出項(xiàng)目進(jìn)行閉包運(yùn)算，直到把向量中所有元素取完，這樣就可以把整個(gè)規(guī)范族求出。程序流程主要是一個(gè)while循環(huán)和switch語(yǔ)句控制。4.2 構(gòu)造預(yù)測(cè)分析表模塊預(yù)測(cè)分析是分析過(guò)程的依據(jù)。數(shù)據(jù)結(jié)構(gòu)：用的是結(jié)構(gòu)體存放數(shù)據(jù)，數(shù)據(jù)信息主要包括：action表，當(dāng)前輸入符、是移進(jìn)還是歸約的控制符號(hào)，歸約的產(chǎn)生式編號(hào)和移進(jìn)的狀態(tài)。goto表，遇到的非終結(jié)符、轉(zhuǎn)到的狀態(tài)號(hào)。算法設(shè)計(jì)：這里主要是查找，利用上一步求出的項(xiàng)目集規(guī)范族，找出輸入符號(hào)以后所轉(zhuǎn)向的狀態(tài)，或者是歸約的產(chǎn)生式編號(hào)。4.3 分析串程序模塊 分析串程序是最終功能的具體表示。數(shù)據(jù)

20、結(jié)構(gòu)：用的是兩個(gè)先進(jìn)先出棧，即狀態(tài)棧和符號(hào)棧，另外還用一個(gè)string類(lèi)型輸入串。算法設(shè)計(jì)：根據(jù)預(yù)測(cè)分析表，開(kāi)始時(shí)把0壓入狀態(tài)棧，把#壓入符號(hào)棧中，根據(jù)狀態(tài)棧的棧頂元素和輸入串的串首字符兩個(gè)線索，在分析表中查找，找到相應(yīng)的動(dòng)作，并實(shí)現(xiàn)。如果找到，則繼續(xù)分析，否則，說(shuō)明該輸入串是不能接受的。根據(jù)題目需要，還要判斷是否是lr（1）文法，我們知道一個(gè)二義性文法絕不是lr類(lèi)文法，對(duì)于這一功能也以與實(shí)現(xiàn)。主要的實(shí)現(xiàn)方法是通過(guò)分析表，如果分析表里有兩個(gè)入口，也就是存在兩個(gè)沖突，那么就說(shuō)明不是。第5章 界面設(shè)計(jì) 圖1-5 開(kāi)始界面輸入產(chǎn)生式文件代碼如下：void main() void first(stru

21、ct vn pv2,int i,sq first,int c,char s2,char vn1); int find(pseqstack s,sq st,int v); void dels(sq st,int i);void project_set(char vn1,int c,struct set2 select,string ft); int forecast_analyse(char vn1,int c);/進(jìn)行預(yù)測(cè)分析 int i,n,t,h=0,j=0,c=0,l;char vn,t=; pl s1;string ft10; pseqstack s;sq first20,p;char

22、 vn120,string20,scanout20,s22=-,; file *fp; pv1=pv;pv4=pv2; s=init_seqstack(); cout t * 說(shuō)明 *n t *本系統(tǒng)設(shè)計(jì)了一些產(chǎn)生式分別存放在 *n t * 以下文件中：1.txt,f.txt,h.txt *n t *in.txt,l.txt,l2.txt,ll.txt,lr.txt *n t *wd.txt結(jié)果輸出存放在文件result.txt*n t *中，請(qǐng)用戶按照上述文件名書(shū)寫(xiě)規(guī)范進(jìn)*n t *行操作使用 *n t * 制作人：計(jì)算機(jī)071 李亞龍 *n t *歡迎使用*n t *=*n; printf

23、(請(qǐng)輸入所用產(chǎn)生式的文件名：); scanf(%s,scanout);if(fp=fopen(scanout,r)=null)printf(n打開(kāi)文件出錯(cuò)了!n);exit(0);getchar(); s22=0; cout 所用的文法是：endl; while(fgets(string,20,fp)!=null&!feof(fp)/從文件讀入產(chǎn)生式 coutlength,s1 ); strinsert(pv2t.p, pv2t.p-length,s1 ); h+; vn1c=0; fclose(fp);/ 圖1-6 構(gòu)造出產(chǎn)生式項(xiàng)目集規(guī)范族代碼如下：void project_set(char

24、 vn1,int c,struct set2 select,string ft)queuequ;/隊(duì)列item product_item70;/小集合容器setitem_set;/大集合vectorvt; container pi,pi3,pi150,product_it;vectorpi2;int i,j,k,n,n1,z=1,v=-1,l=0,q=0,q1=0,flat=0;static f=0;char ch;bool bl;string str,str1,str2,str3;item_container product1,product2,product3; fstream of;pr

25、oduct1.s=.s;product1.s2=0;product1.pcode=0;product1.front=#;product1.go=s;product1.point_pos=0;product1.vn=s;product_itemq.insert (product1.vn+-+product1.s+,+product1.front);qu.push(product1); pi.push_back(product1); pi1q1.push_back(product1);while(flat!=100) switch(flat)case 0:if(!qu.empty() produc

26、t2=qu.front();/隊(duì)首元素 qu.pop();/刪除隊(duì)首元素 if(isvn(vn1,product2.go,c)/判斷點(diǎn)后是否為非終結(jié)符 k=0; for(i=0,n=0;product2.sproduct2.point_pos+1!=vn1i;n+=pv2i.tag,i+);/找到非終結(jié)符的下標(biāo) k=pv2i.tag;/該非終結(jié)符的產(chǎn)生式個(gè)數(shù)n1=n;for(j=0;j+product1.s+,+product1.front).second=true)qu.push(product1);pi.push_back(product1);pi1q1.push_back(product

27、1); flat=0; else flat=1; break;case 1: bl=item_set.insert(product_itemq).second; if(bl=true) f+; pi2.push_back(pi1q1); if(!vt.empty()flat=3;elseif(vq|v=f)/flat=100;else flat=2; v+;break; case 2: if(vq|v=f)flat=100;else i=0; for(vector:iterator it=pi2.begin();iv;it+,i+); product_it=*it; for(vector:it

28、erator vi=product_it.begin();vi!=product_it.end();vi+) vt.push_back(*vi).vn+-+(*vi).s+,+(*vi).front); flat=3; break;case 3: str=vt.back(); vt.pop_back(); flat=4; break; case 4:for(vector:iterator vc=pi.begin();vc!=pi.end();vc+)/找到str對(duì)應(yīng)的產(chǎn)生式 product3=*vc; if(product3.vn+-+product3.s+,+product3.front)=

29、str&product3.go!=$&product3.go!=) ch=product3.go; str2=product3.s; str2.replace(product3.point_pos,1,1,product3.go); product3.point_pos+=1; str2.replace(product3.point_pos,1,1,.); product3.s=str2; if(product3.sproduct3.point_pos+1=0) product3.go=$; else product3.go=product3.sproduct3.point_pos+1; qu

30、.push(product3); pi.push_back(product3); product_item+q.insert(product3.vn+-+product3.s+,+product3.front); pi1+q1.push_back(product3);z=0; break; if(z=0)if(ch!=$)for(vector:iterator vv=vt.begin();vv!=vt.end();vv+)/找到相同輸入符str1=*vv; for(vector:iterator vc1=pi.begin();vc1!=pi.end();vc1+) product1=*vc1;

31、 if(product1.go!=$)if(product1.go=ch&(product1.vn+-+product1.s+,+product1.front)=str1) str3=product1.vn+-+product1.s+,+product1.front; str2=product1.s; str2.replace(product1.point_pos,1,1,product1.go); product1.point_pos+=1; str2.replace(product1.point_pos,1,1,.); product1.s=str2;if(product1.sproduc

32、t1.point_pos+1!=0)product1.go=product1.sproduct1.point_pos+1;else product1.go=$;product_itemq.insert(product1.vn+-+product1.s+,+product1.front); qu.push(product1); pi.push_back(product1); pi1q1.push_back(product1);vector:iterator i=find(vt.begin(),vt.end(),str3); if(i!=vt.end()vt.erase(i); vv-; brea

33、k;else vt.pop_back();l=1; break; z=1; if(l=1) l=0; break; flat=0; break; of.open(result.txt,ios:out);if(!of)cerr打開(kāi)文件失敗!endl;abort();cout 構(gòu)造的項(xiàng)目集規(guī)范族是：（按回車(chē)鍵繼續(xù)）endl;getchar();z=0;for(vector:iterator vc2=pi2.begin();vc2!=pi2.end();vc2+) pi=*vc2;coutiz:endl;ofiz:endl; z+;for(vector:iterator pl=pi.begin();

34、pl!=pi.end();pl+)cout(*pl).vn(*pl).s,(*pl).frontendl;of(*pl).vn(*pl).s,(*pl).frontendl;getchar();coutendl;ofendl;of.close();/*構(gòu)造預(yù)測(cè)分析表*/ i=-1;for(vector:iterator vc3=pi2.begin();vc3!=pi2.end();vc3+) pi=*vc3; i+;j=0; int t=-1; for(vector:iterator pl=pi.begin();pl!=pi.end();pl+) product1=*pl;if(product1.vn+-+product1.s=s-s.)tablei.actj.ch=#; tablei.actj.control=a; tablei.actj.data=0;j+;else if(product1.vn+-+product1.s=product1.vn+-+.) for(k=0;product1.frontk!=0;k+) tablei.actj.ch=product1.frontk; tablei.actj.control=r; tablei.actj.data=product1.pcode; j+; else if(product1.point_pos=selectpr