編譯原理課程設計lr語法分析構(gòu)造器的設計

1、前言計算機語言之所以能由單一的機器語言發(fā)展到現(xiàn)今的數(shù)千種高級語言，就是因為有了編譯技術(shù)，編譯原理技術(shù)是計算機科學中發(fā)展的最迅速、最成熟的一個分支，它集中體現(xiàn)了計算機發(fā)展成果與精華。未來計算機工作者，都應該掌握這門基礎的專業(yè)基礎知識。“編譯原理”是計算機及其相關(guān)專業(yè)的重要專業(yè)基礎課，主要研究設計和構(gòu)造編譯程序的原理和方法。全面、深入地探討了編譯器設計方面的重要主題，包括詞法分析、語法分析、語法制導定義和語法制導翻譯、運行時刻環(huán)境、目標代碼生成、代碼優(yōu)化技術(shù)、并行性檢測以及過程間分析技。編譯原理蘊涵著計算機學科中解決問題的思路、形式化問題和解決問題的方法，對應用軟件和系統(tǒng)軟件的設計與開發(fā)有一定的啟

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

3、計. 7 3.1 模塊設計.7 3.1.1 LR（1）項目集規(guī)范族的構(gòu)造算法.8 3.1.2 LR（1）分析表的構(gòu)造算法.8 3.2 流程圖.9第4章 總體設計.15 4.1 構(gòu)造項目集規(guī)范族模塊.15 構(gòu)造預測分析表模塊.15 4.3 分析串程序模塊.15第5章 界面設計.16小結(jié).33致謝.34參考文獻.35 附錄 源程序清單.36編譯原理課程設計任務書1、本課題的目的及意義課程設計實踐對學生鞏固所學基礎專業(yè)課程知識、進行編譯系統(tǒng)基本技能訓練、培養(yǎng)實踐動手能力，從而掌握編譯系統(tǒng)的基本工作原理、基本方法和基本開發(fā)技術(shù)，最終達到具有一定的編譯系統(tǒng)的實際開發(fā)能力有重要意義。通過課程設計，主要達到

4、以下目的：1.幫助學生深入理解編譯原理的有關(guān)理論和鞏固編譯原理相關(guān)知識。2. 鞏固學生學習的編譯原理、程序設計語言、數(shù)據(jù)結(jié)構(gòu)等課程的基礎知識，訓練學生分析和解決編譯系統(tǒng)的相關(guān)問題的能力，提高學生的綜合素質(zhì)。3. 從軟件工程的角度來看，編譯原理課程設計是一個很好的實例，可以訓練學生軟件設計的能力以及編碼調(diào)試能力。2、本課題任務的主要內(nèi)容本課程設計主要內(nèi)容包括以下幾點:1、根據(jù)選定的題目，查閱資料，熟悉相關(guān)理論、方法；（1）掌握文獻檢索方法，以獲得編譯系統(tǒng)開發(fā)技術(shù)等相關(guān)資料；（2）學習并熟練使用一種4GL開發(fā)平臺（如VC+、Java、Dephi、PB、VB等）；2、分析問題，確定系統(tǒng)邏輯結(jié)構(gòu)；3、

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

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

7、義和語法制導翻譯、運行時刻環(huán)境、目標代碼生成、代碼優(yōu)化技術(shù)、目標代碼生成。語法分析是整個編譯程序的核心部分，而LR分析方法對文法要求比起其他分析方法能力較強LR（k）分析方法是1965年Knuth提出的，括號中的k表示向右查看輸入串符號的個數(shù)。這種方法比起自頂向下的LL（1）分析方法和自低向上的優(yōu)先分析方法對文法的限制要少的多，也就是說對于大多數(shù)用無二義性上下文無關(guān)文法描述的語言都可以用相應的LR分析器進行識別，而且這種方法還具有分析速度快，能準確、即時地指出出錯位置。自低向上分析的關(guān)鍵問題是在分析過程中如何確定句柄。LR分析法正是給出一種能根據(jù)當前分析棧中的符號串（通常以狀態(tài)表示）和向右順序

8、查看輸入串的k個（k0）符號就可惟一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能惟一地確定句柄。LR分析法的歸約過程是規(guī)范推到的逆過程，所以LR分析過程是一種規(guī)范歸約的過程。因為LR（0）分析過程中不需要向右查看輸入符號，因而它可以對文法的限制較大，對絕大多數(shù)的高級語言的語法分析器是不能適用的，所以，要分析絕大多數(shù)的高級語言編譯程序的需要，采用向后查看一個輸入符號的方法，即LR（1）的方法。（1）掌握并深刻理解有窮自動機在LR分析法中的應用（即LR分析器）。（2）掌握LR分析法的思想，學會特定分析表的構(gòu)造方法，利用給出的分析表進行LR分析。1.3 軟件定義對任意給定的上下文無

9、關(guān)文法G，構(gòu)造其LR（1）項目集規(guī)范族、預測分析表，并且在此基礎上進一步構(gòu)造其LR（1）分析表。1.4 開發(fā)環(huán)境軟件：Windows 7操作系統(tǒng) , Microsof；編程語言：C+第2章 需求分析設計的題目是要對LR（1）類文法判定及其分析器進行構(gòu)造。如果一個文法的LR（1）分析表不含多重入口時，（即任何一個LR（1）項目集中無移進歸約沖突或歸約歸約沖突），則稱該文法為LR（1）文法，所構(gòu)造的相應分析表稱為LR（1）分析，使用LR（1）分析表的分析器稱為LR（1）分析器或稱規(guī)范的LR分析器。所以，要判斷一個文法是否是LR（1）類文法，則主要是看是否存在兩個沖突。2.2 需完成的功能一個LR分

10、析器由3個部分組成：（1）總控程序：也可以成為驅(qū)動程序。對所有的LR分析器總控程序都是相同。（2）分析表或分析函數(shù)：不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表也不同，分析表又可分為動作（ACTION）表和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。（3）分析棧：包括文法符號棧和相應的狀態(tài)棧。它們均是先進后出棧。 分析器的動作由棧頂狀態(tài)和當前輸入符號所決定（LR(0)分析器不需要向前查看輸入符號）。綜上所述，要實現(xiàn)本次設計所需工作主要有以下方面：構(gòu)造項目集規(guī)范族；構(gòu)造預測分析表；設計總控程序，完成分析過程。第3章 邏輯設計3.1 模塊設計 LR分析器工作過程示意

11、圖如圖1.1所示。其中SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系GOTOSi,X=Si確定，該關(guān)系式是指當棧頂狀態(tài)為Si，遇到當前文法符號為X時應轉(zhuǎn)向狀態(tài)Sj。X為終結(jié)符或非終結(jié)符。 ACTIONSi,a規(guī)定了棧頂狀態(tài)Si時遇到輸入符號a應執(zhí)行的動作。動作有4種可能：移進： 當Si=GOTOSi,a成立，則把Si移入到狀態(tài)棧，把a移入到文法符號棧。其中i，j表示狀態(tài)號。SPSnS1XnnX1X0S0. 總控程序ACTION表GOTO表輸入串XXXXXXXX#輸出圖1-1 LR分析器工作過程示意圖歸約： 當在棧頂形成句柄為時，則用歸約為相應的非終結(jié)符A，即當文法中有A的產(chǎn)

12、生式，而的長度為r（即|=r），則從狀態(tài)和文法符號棧中自頂向下去掉r個符號，即棧指針SP減去r。并把A移入文法符號棧內(nèi)，再把滿足Sj=GOTIOSi,A的狀態(tài)移入狀態(tài)棧，其中Si為修改指針后的棧頂狀態(tài)。接受acc： 當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當輸入是#，則為分析成功。報錯： 當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入串不是該文法所能接受的句子。LR分析器的關(guān)鍵部分是分析表的構(gòu)造。構(gòu)造LR分析表，那么先解決LR項目集規(guī)范族的構(gòu)造。 LR項目集規(guī)范族的項目類型分為如下四種：移進項目圓點后為終結(jié)符的項目，形如Aa，其中、V*，aVT，

13、相應狀態(tài)為移進狀態(tài)。規(guī)約項目圓點在產(chǎn)生式右部的最后的項目，形如A其中V*，對于=的項目為A（對應的產(chǎn)生式為A），相應狀態(tài)為歸約狀態(tài)。3、待約項目圓點后為非終結(jié)符的項目，形如AB，其中、V*，BVN，這表明用產(chǎn)生式A的右部歸約時，首先要將B的產(chǎn)生式右部歸約為B，對A的右部才能繼續(xù)進行分析。也就是期待著繼續(xù)分析過程中首先能進行歸約得到B。4、接受項目當歸約項目為SS時則表明已分析成功，即輸入串為該文法的句子，相應狀態(tài)為接受狀態(tài)。.1 LR（1）項目集規(guī)范族的構(gòu)造算法以SS，#屬于初始項目集中，把“#”號作為向前搜索符，表示活前綴為（若是有關(guān)S產(chǎn)生式的某一右部）要歸約成S時，必須面臨輸入符為“#”號

14、才行。我們對初始項目SS，#求閉包后再用轉(zhuǎn)換函數(shù)逐步求出整個文法的LR（1）項目集族。具體構(gòu)造步驟如下：構(gòu)造LR（1）項目集的閉包函數(shù)。假定I是一個項目集，I的任何項目都屬于CLOSURE(I)。AB，a屬于CLOSURE(I)，B是文法中的產(chǎn)生式，若有項目V*，bFIRST(a)，則B，b也屬于CLOSURE(I)中。重復直到CLOSURE(I)不再增大為止。構(gòu)造轉(zhuǎn)換函數(shù)。LR（1）轉(zhuǎn)換函數(shù)的構(gòu)造與LR（0）的相似，GO（I，X）= CLOSURE(J)其中I是LR（1）的項目集，X是文法符號：J=任何形如LR（1）分析表的構(gòu)造AX，a的項目| AX，a I對文法G的LR（1）項目集族的構(gòu)造

15、仍以SS，#為初態(tài)的初始項目，然后對其求閉包和轉(zhuǎn)換函數(shù)，直到項目集不再增大。.2 LR（1）分析表的構(gòu)造算法由于一個LR（1）項目可以看成兩個部分組成，一部分和LR（0）項相同，這部分稱為心，另一部分為向前搜索符合集。因而LR（1）分析表的構(gòu)造與LR（0）分析表的構(gòu)造在形式上基本相同，只是歸約項目的歸約動作取決于歸約項目的向前搜索符集，即只有當面臨的輸入符屬于向前搜索符的集合，才做歸約動作，其他情況均出錯。具體構(gòu)造過程如下：若已構(gòu)造出某文法的LR（1）項目集族C。C=I0，I1，.，In其中的Ik的k為分析器的狀態(tài)，則動作ACTION表和狀態(tài)轉(zhuǎn)換GOTO表構(gòu)造方法如下：(1) 若項目Aa，b屬

16、于Ik，且GO（Ik，a）=Ij，其中aVT，則置ACTIONk，a=Sj。其Sj的含義是把輸入符號a和狀態(tài)j分別移入文法符號棧和狀態(tài)棧。(2) 若項目A，a屬于Ik，則置ACTIONk，a=rj，其中aVT，rj的含義為把當前棧頂符號串歸約為A（即用產(chǎn)生式A歸約）。j為在文法中對產(chǎn)生式A的編號。(3) 若項目SS，#屬于Ik，則置ACTION，=“”，表示接受。(4) 若（Ik，），其中AVN ，則置GOTOk，A=j。表示轉(zhuǎn)入j狀態(tài)，則置當前文法符號棧頂為A，狀態(tài)棧頂為j。(5) 凡不能用規(guī)則（1）（4）填入分析表中的元素，均置“報錯標志”?？梢蕴钊肟瞻滓员硎?。 流程圖圖1-2(a) 構(gòu)造

17、LR（1）項目集規(guī)范族流程圖圖1-2（b） 構(gòu)造LR（1）項目集規(guī)范族流程圖圖1-2（c） 構(gòu)造LR（1）項目集規(guī)范族流程圖圖1-3 構(gòu)造LR（1）分析表流程圖1-4 LR（1）串分析程序流程圖第4章 總體設計功能設計為能實現(xiàn)本次課程設計的功能，同時減小工作量，根據(jù)需求，構(gòu)造LR（1）項目集規(guī)范族需要用到FIRST集，主要思路是采用替換策略以及刪除重復的元素。數(shù)據(jù)結(jié)構(gòu)使用的是鏈表。這不是核心部分，所以不再贅述。將功能分為三個大模塊，即構(gòu)造項目集規(guī)范族、分析表、和分析串程序。以下是對構(gòu)造項目集規(guī)范族、分析表、和分析串程序的設計敘述：4.1 構(gòu)造項目集規(guī)范族模塊項目集規(guī)范族是整個設計的基礎。數(shù)據(jù)結(jié)

18、構(gòu)：實現(xiàn)其構(gòu)造，在數(shù)據(jù)結(jié)構(gòu)選用方面要求能夠方便查找、而且能夠節(jié)省空間。據(jù)此，主要采用了C+中STL中隊列、集合、向量，作為主要數(shù)據(jù)存放的容器，并用結(jié)構(gòu)體存放重要產(chǎn)生式的重要信息。算法設計：由課本上關(guān)于構(gòu)造項目集規(guī)范族的敘述，聯(lián)想到了圖的廣度遍歷，所以將擴展后的文法SS,#作為核放在隊列中，由核求閉包，每求出一個就放入集合中（主要是可以去除重復的）如果插入集合成功，就把結(jié)構(gòu)體插入向量中，插入隊列中，直到隊列空，說明由核產(chǎn)生的項目已經(jīng)構(gòu)造完，下一步只需從向量中取出項目進行閉包運算，直到把向量中所有元素取完，這樣就可以把整個規(guī)范族求出。程序流程主要是一個WHILE循環(huán)和switch語句控制。4.2

19、構(gòu)造預測分析表模塊預測分析是分析過程的依據(jù)。數(shù)據(jù)結(jié)構(gòu)：用的是結(jié)構(gòu)體存放數(shù)據(jù)，數(shù)據(jù)信息主要包括：ACTION表，當前輸入符、是移進還是歸約的控制符號，歸約的產(chǎn)生式編號和移進的狀態(tài)。GOTO表，遇到的非終結(jié)符、轉(zhuǎn)到的狀態(tài)號。算法設計：這里主要是查找，利用上一步求出的項目集規(guī)范族，找出輸入符號以后所轉(zhuǎn)向的狀態(tài)，或者是歸約的產(chǎn)生式編號。4.3 分析串程序模塊 分析串程序是最終功能的具體表示。數(shù)據(jù)結(jié)構(gòu)：用的是兩個先進先出棧，即狀態(tài)棧和符號棧，另外還用一個string類型輸入串。算法設計：根據(jù)預測分析表，開始時把0壓入狀態(tài)棧，把#壓入符號棧中，根據(jù)狀態(tài)棧的棧頂元素和輸入串的串首字符兩個線索，在分析表中查找

20、，找到相應的動作，并實現(xiàn)。如果找到，則繼續(xù)分析，否則，說明該輸入串是不能接受的。根據(jù)題目需要，還要判斷是否是LR（1）文法，我們知道一個二義性文法絕不是LR類文法，對于這一功能也以與實現(xiàn)。主要的實現(xiàn)方法是通過分析表，如果分析表里有兩個入口，也就是存在兩個沖突，那么就說明不是。第5章 界面設計 圖1-5 開始界面輸入產(chǎn)生式文件代碼如下：void main() void First(struct 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

21、i);void project_set(char vn1,int c,struct set2 select,string ft); int Forecast_analyse(char vn1,int 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 vn120,string20,scanout20,s22=-,; FILE *fp; pv1=pv;pv4=pv2; S=Init_seqstack(); cout t * 說明 *n t *本系統(tǒng)設計了一些

22、產(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 *中，請用戶按照上述文件名書寫規(guī)范進*n t *行操作使用 *n t * 制作人：計算機071 李亞龍 *n t *歡迎使用*n t *=*n; printf(請輸入所用產(chǎn)生式的文件名：); scanf(%s,scanout);if(fp=fopen(scanout,r)=NULL)printf(n打開文件出錯了!n);exit(0);getchar(); s22=

23、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)生式項目集規(guī)范族代碼如下：void project_set(char vn1,int c,struct set2 select,string ft)queuequ;/隊列Item product_Item70;/小集合容器setItem_set;/大集合vectorvt; co

24、ntainer 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;product1.s=.S;product1.s2=0;product1.pcode=0;product1.front=#;product1.go=S;product1.point_pos=0;product1.v

25、n=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() product2=qu.front();/隊首元素 qu.pop();/刪除隊首元素 if(isVN(vn1,product2.go,c)/判斷點后是否為非終結(jié)符 k=0; for(i=0,n=0;product2.spr

26、oduct2.point_pos+1!=vn1i;n+=pv2i.tag,i+);/找到非終結(jié)符的下標 k=pv2i.tag;/該非終結(jié)符的產(chǎn)生式個數(shù)n1=n;for(j=0;j+product1.s+,+product1.front).second=true)qu.push(product1);pi.push_back(product1);pi1q1.push_back(product1); flat=0; else flat=1; break;case 1: bl=Item_set.insert(product_Itemq).second; if(bl=true) f+; pi2.push

27、_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:iterator vi=product_It.begin();vi!=product_It.end();vi+) vt.push_back(*vi).vn+-+(*vi).s+,+(*vi).front); fla

28、t=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對應的產(chǎn)生式 product3=*vc; if(product3.vn+-+product3.s+,+product3.front)=str&product3.go!=$&product3.go!=) ch=product3.go;place(product3.point_pos,1,1,product3.go); product3.poin

29、t_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.push(product3); pi.push_back(product3); product_Item+q.insert(product3.vn+-+product3.s+,+product3.front); pi1+q1.push_back(produc

30、t3);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; if(product1.go!=$)if(product1.go=ch&(product1.vn+-+product1.s+,+product1.front)=str1) str3=product1.vn+-+product1.s+,+product1.fr

31、ont; 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.sproduct1.point_pos+1!=0)product1.go=product1.sproduct1.point_pos+1;else product1.go=$;product_Itemq.insert(product1.vn+-+product1.s+,+pr

32、oduct1.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-; break;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打開文件失敗!endl;abort(

33、);cout 構(gòu)造的項目集規(guī)范族是：（按回車鍵繼續(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();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)造預測

34、分析表*/ 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

35、+-+.) 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=selectproduct1.pcode.len) for(k=0;product1.frontk!=0;k+) tablei.actj.ch=product1.frontk; tablei.actj.control=r; tablei.actj.data=product1.pcode;

36、 j+; else if(!isVN(vn1,product1.sproduct1.point_pos+1,c) tablei.actj.ch=product1.go; tablei.actj.control=s; else tablei.to+t.cha=product1.go; str2=product1.s; str2.replace(product1.point_pos,1,1,product1.go); str2.replace(product1.point_pos+1,1,1,.); str3=product1.vn+-+str2+,+product1.front; l=0; fo

37、r(vector:iterator vc4=pi2.begin();vc4!=pi2.end();vc4+,l+) pi3=*vc4; for(vector:iterator ppl=pi3.begin();ppl!=pi3.end();ppl+) if(str3=(*ppl).vn+-+(*ppl).s+,+(*ppl).front) if(!isVN(vn1,product1.sproduct1.point_pos+1,c) tablei.actj.data=l; else tablei.tot.da=l; n=-1; break; if(n=-1) n=0; break; j+; tab

38、lei.a=j; tablei.t=t;/預測分析表 圖1-7 輸入串分析接受的情況 圖1-8 輸入串分析不接受的情況代碼如下： int Forecast_analyse(char vn1,int c)/進行預測分析 FILE* op;stackstate;stacksymbol;char input20,stack20,remain20,remain120,stack120;int i,j=0,l,b=0,z,r=0,n=0,s,ss,k;int sta20,sta120;char x;if(op=fopen(result.txt,a)=NULL) printf(n打開文件出錯了!n); e

39、xit(0); printf(請輸入要分析的串，以#結(jié)束：n);gets(input); printf( 輸入串%s的分析過程 n,input); printf(-n);fprintf(op, 輸入串%s的分析過程 n,input); fprintf(op,-n);for(z=0;inputz!=0;z+)remainz=inputz; remainz=0; state.push(0);symbol.push(#); stack0=#;stack1=0;sta0=0; out(步驟, 0,5); out(狀態(tài)棧,0,10); out(符號棧,0,10);out(輸入串,2,10);out(AC

40、TION,2,8);out(GOTO,2,6);coutendl;fprintf(op,步驟 狀態(tài)棧 符號棧 輸入串 ACTION GOTOn);do b+; s=state.top();x=inputn; for(i=0;i=tables.a;i+) if(tables.acti.control=a) out(b, 0,5);fprintf(op,%-7d,b); out(sta0,0,0);fprintf(op,%-d,sta0); for(k=1;stackk+1!=0;k+) out(stak,0,0);fprintf(op,%-d,stak); out(stak,0,10-k);fp

41、rintf(op,%-8d,stak); out(stack,0,10); fprintf(op,%-10s,stack); out(remain,2,10);fprintf(op,%+10s,remain);out(接受,2,8);fprintf(op, 接受n );coutendl; cout分析成功endl;fprintf(op, 分析成功n ); return 0; else if(tables.acti.ch=x) if(tables.acti.control=s) state.push(tables.acti.data); symbol.push(x); n+; if(b=1) o

42、ut(b, 0,5); fprintf(op,%-7d,b); out(0,0,10);fprintf(op,%-8d,sta0); out(stack,0,10);fprintf(op,%-10s,stack);out(remain,2,10);fprintf(op,%+10s,remain);out(s,2,6);fprintf(op, s);out(tables.acti.data,0,0);fprintf(op,%-dn,tables.acti.data);cout1) out(b, 0,5);fprintf(op,%-7d,b); out(sta10,0,0); fprintf(op

43、,%-d,sta10); for(k=1;stack1k+1!=0;k+) out(sta1k,0,0);fprintf(op,%-d,sta1k); out(sta1k,0,10-k);fprintf(op,%-8d,sta1k); out(stack1,0,10);fprintf(op,%-10s,stack1); out(remain1,2,10);fprintf(op,%+10s,remain1);out(s,2,6);fprintf(op, s);out(tables.acti.data,0,0);fprintf(op,%-dn,tables.acti.data);coutendl;

44、 break; else if(tables.acti.control=r) for(k=0;stackk!=0;k+)stack1k=stackk; sta1k=stak; stack1k=0;l=tables.acti.data;for(k=0;stackk!=0;k+); if(selectl.NVT0=) ss=state.top(); for(i=0;itabless.t&tabless.toi.cha!=vn1selectl.n;i+); state.push(tabless.toi.da); symbol.push(vn1selectl.n); stak-j=tabless.to

45、i.da; stackk-j=vn1selectl.n; stackk-j+1=0; else for(j=0;jselectl.len;j+) state.pop(); symbol.pop(); stackk-j=0; ss=state.top(); for(i=0;itabless.t&tabless.toi.cha!=vn1selectl.n;i+); state.push(tabless.toi.da); symbol.push(vn1selectl.n); stak-j=tabless.toi.da; stackk-j=vn1selectl.n; stackk-j+1=0; if(

46、b=1) out(b, 0,5);fprintf(op,%-7d,b); out(0,0,10);fprintf(op,%-8d,sta0); out(stack,0,10);fprintf(op,%-10s,stack); out(remain,2,10);fprintf(op,%+10s,remain);out(r,2,6);fprintf(op, r);out(tables.acti.data,0,0);fprintf(op,%-5d,tables.acti.data);out(tabless.toi.da,2,6);fprintf(op,%3dn,tabless.toi.da);cou

47、t1) out(b, 0,5);fprintf(op,%-7d,b); out(sta10,0,0);fprintf(op,%-d,sta10); for(k=1;stack1k+1!=0;k+) out(sta1k,0,0);fprintf(op,%-d,sta1k); out(sta1k,0,10-k);fprintf(op,%-8d,sta1k); out(stack1,0,10);fprintf(op,%-10s,stack1); out(remain,2,10);fprintf(op,%+10s,remain);out(r,2,6);fprintf(op, r);out(tables

48、.acti.data,0,0);fprintf(op,%-5d,tables.acti.data);out(tabless.toi.da,2,6);fprintf(op,%3dn,tabless.toi.da);coutendl; if(tables.act0.control=a) out(b, 0,5);fprintf(op,%-7d,b); out(sta10,0,0);fprintf(op,%-d,sta10); for(k=1;stack1k+1!=0;k+) out(sta1k,0,0);fprintf(op,%-d,sta1k); out(sta1k,0,10-k);fprintf

49、(op,%-8d,sta1k); out(stack1,0,10);fprintf(op,%-10s,stack1); out(remain,2,10);fprintf(op,%+10s,remain);out(接受,2,8);fprintf(op, 接受n );couttables.a) out(b, 0,5);fprintf(op,%-7d,b); out(sta0,0,0);fprintf(op,%-d,sta10); for(k=1;stackk+1!=0;k+) out(stak,0,0);fprintf(op,%-d,stak); out(stak,0,10-k);fprintf(

50、op,%-8d,stak); out(stack,0,10);fprintf(op,%-10s,stack); out(remain,2,10);fprintf(op,%+10s,remain);out(不能接受,2,10);fprintf(op, 不能接受n );coutendl; return -1; while(1);圖1-9 對于不是LR（1）文法的判斷代碼如下：for(i=0;iz;i+) for(j=0;jtablei.a;j+) for(l=j+1;l=tablei.a;l+) if(tablei.actj.ch=tablei.actl.ch&tablei.actj.contro

51、l!=tablei.actl.control)| (tablei.actj.ch=tablei.actl.ch&tablei.actj.control=r&tablei.actl.control=r& tablei.actj.data!=tablei.actl.data) cout不是LR(1)文法endl; cout不能繼續(xù)分析，退出程序!endl; exit(0); 小 結(jié)我們班的題目是LR（1）類文法的判定及其分析器的構(gòu)造，要實現(xiàn)這些功能，可謂是絞盡腦汁。實現(xiàn)過程并不是順利的，由不了解到實現(xiàn)，最終還是做到了。對于本次的課程設計，可以說是我做過課程設計以來，收獲最大的一個。我之所以這么說主

52、要是因為，從設計的難度方面，是比較大的。到具體的實現(xiàn)，其中要考慮很多細節(jié)問題，比如說，輸入符是否是終結(jié)符，產(chǎn)生式含空的情況等一些小問題，影響到了設計的進度和功能的完整。如何能方便的進行設計，降低難度，查閱資料，現(xiàn)學一些東西，比如，用C+中標準模板庫STL，還有模板降低難度。當程序遇到問題，最難得是調(diào)試的過程，尤其構(gòu)造項目集規(guī)范族時，進行調(diào)試，花了很長時間，因為對內(nèi)部的一些東西不了解，增加了調(diào)試難度。在這過程中，也曾經(jīng)氣餒過，但是最后還是堅持了下來。其實剛開始時，是不覺的難，到中間階段感到很難。不過現(xiàn)在回頭再看的時候覺的也不是想象的復雜。通過這次課程設計，我學到了很多東西，收獲了很多，對于LR（

53、1）分析有了更深的理解，對C+中泛型編程的實現(xiàn)也有了一些心得體會。在成功的同時我也發(fā)現(xiàn)自己的一些不足。知識的不足，課本上知識掌握的不是很牢。編程能力還很欠缺，思維不是很清晰。缺乏耐心。還有就是做出的程序還不夠完美，界面不是很美觀。總之，雖然實現(xiàn)了最終結(jié)果，但是我對自己并不滿意。還有很多等待完善的地方，當然不僅僅是程序，更重要的是完善自己，提高自己的能力。致 謝在這次課程設計的撰寫過程中，我得到了許多人的幫助。首先我要感謝我的父母，是他們養(yǎng)育了我，父母的愛伴隨著我的成長，每當我遇到挫折和失敗的時候，父母總是能夠給我最大的安慰和幫助，有了他們我才能成長，才能進入大學這個環(huán)境；其次我要感謝我所在的大

54、學安徽工程大學，感謝學校為我們提供了這樣好的學習環(huán)境，再次我要感謝我的老師在課程設計上給予我的指導、提供給我的支持和幫助，這是我能順利完成這次報告的主要原因，在此期間，我不僅學到了許多新的知識，而且也開闊了視野，提高了自己的設計能力。最后，我要感謝幫助過我的同學，他們也為我解決了不少我不太明白的設計上的難題。 李亞龍 2010 年6月10日參考文獻【1】張素琴、呂映芝等.編譯原理（第二版）.清華大學出版社 , 2008年【2】美scott Meyers 著 潘愛民譯. Effective STL中文版 .清華大學出版社 ,2006年【3】陳本林 著 .數(shù)據(jù)結(jié)構(gòu)使用C+標準模板庫（STL）. 機

55、械工業(yè)出版社, 2005年【4】MENGLEE著 王昕譯 .C+ STL中文版. 中國電力出版社 ,2002年【5】陳火旺.程序設計語言編譯原理（第三版）.國防工業(yè)出版社，2000年【6】高伸儀 金茂忠.編譯原理及編譯程序構(gòu)造.北京航空航天大學出版社，2004年【7】鄭莉 董淵.C+語言程序設計.清華大學出版社，2006年【8】錢能.C+程序設計教程.清華大學出版社，2006年【9】William Ford，William Topp 編著，劉衛(wèi)東等譯.數(shù)據(jù)結(jié)構(gòu)C+語言描述.清華大學出版社，2003年 【10】王雷.編譯原理課程設計.機械工業(yè)出版社，2006年附 錄源程序清單#pragma wa

56、rning(disable:4786)#pragma warning(disable:4503)#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define MAX 20#define MAXSIZE 100 typedef struct productstring s;int pcode;string front;char go;int point_pos;string vn;Item_container;typedef s

57、etItem;typedef vectorcontainer;typedef struct chuan/定義一個堆串 char *ch; int length; l,*pl;struct Vn/*產(chǎn)生式結(jié)構(gòu)*/int tag;/每個非終結(jié)符的產(chǎn)生式個數(shù)int info;/標記能否推出空char ch;/標記非終結(jié)符 pl p;pv20,pv220,*pv1,*pv4;struct set2/定義SELECT集int n;/非終結(jié)符的下標int len;/產(chǎn)生式的長度char NVT10;/存放產(chǎn)生式的右部select20,*ss;typedef struct node/*first和follo

58、w集合結(jié)構(gòu)*/int lable;/*表明是否是非終結(jié)符*/int f;/*表明是first還是 follow集*/unionint key;/終結(jié)符的下標char ch;/終結(jié)符的字符val;struct node *next;*sq,sql;typedef structint t,v;info;typedef struct/*定義棧結(jié)構(gòu)，遞歸用*/ info dataMAX; int top; seqstack,*pseqstack;typedef struct/*定義棧結(jié)構(gòu)，遞歸用*/ char tittleMAXSIZE; int top; sign,*psign;typedef st

59、ructchar ch;/遇到的字符char control;/是否歸約還是已經(jīng)int data;/移進的狀態(tài)號或者歸約的產(chǎn)生式action;typedef structchar cha;/遇到的非終結(jié)符int da;/狀態(tài)號go;struct analysisaction act30;go to20;int a;int t;table50;static int visited20;/標記數(shù)組static int y;template void out(T1 t1,T2 t2,T2 t3)if(t2=0)cout.width(t3);cout.setf(ios:left,ios:adjustf

60、ield);coutsetfill( )t1;elseif(t2=1)cout.width(t3);cout.setf(ios:internal,ios:adjustfield);coutsetfill( )t1;elsecout.width(t3);cout.setf(ios:right,ios:adjustfield);coutsetfill( )top=-1; return s;int push_seqstack(pseqstack s,info temp)if(s-top=MAX-1) return 0; else s-top+; s-datas-top.t=temp.t; s-dat