編譯原理課程設(shè)計報告 算符優(yōu)先分析表

1、課程設(shè)計(論文)任務(wù)書 軟件學(xué)院 學(xué) 院 軟件工程 專 業(yè) 07-1 班 一、課程設(shè)計(論文)題目算符優(yōu)先分析表生成模擬 二、課程設(shè)計(論文)工作自2010年6月20 日起至 2010 年 6月 25日止。三、課程設(shè)計(論文) 地點: 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的1、使學(xué)生增進(jìn)對編譯原理的認(rèn)識，加強(qiáng)用程序設(shè)計語言實現(xiàn)編譯算法能力。2、進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點和難點內(nèi)容進(jìn)行編程，獨立完成有一定工作量的程序設(shè)計任務(wù)，同時強(qiáng)調(diào)好的程序設(shè)計風(fēng)格，并綜合使用程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識，熟悉使用開發(fā)工具VC6.0 或

2、JAVA。2課程設(shè)計的任務(wù)及要求1）基本要求：動態(tài)模擬算法的基本功能是：（1）輸入一個給定文法，及FIRSTVT和LASTVT集；（2）輸出算符優(yōu)先分析表生成算法； （3）輸出算法優(yōu)先分析表構(gòu)造過程的過程。2）課程設(shè)計論文編寫要求1）要按照書稿的規(guī)格打印謄寫課設(shè)報告；2）報告分為封面、課程設(shè)計任務(wù)書（本文檔）分析、總結(jié)和附錄；3）報告正文包括以下部分： 問題描述：題目要解決的問題是什么； 分析、設(shè)計、實現(xiàn)：解決問題的基本方法說明，包括主要算法思想，算法的流程圖，程序中主要函數(shù)或過程的功能說明； 運(yùn)行結(jié)果分析：分析程序的運(yùn)行結(jié)果是否正確以及出現(xiàn)的問題； 總結(jié)：遇到的主要問題是如何解決的、對設(shè)計和

3、編碼的回顧討論和分析、進(jìn)一步改進(jìn)設(shè)想、經(jīng)驗和體會等； 附錄，包括源程序清單和運(yùn)行結(jié)果。學(xué)生簽名： 2009 年6 月25 日課程設(shè)計(論文)評審意見（1）編譯器思想的正確性（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）程序?qū)崿F(xiàn)的正確性（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）程序功能的完善程度（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）學(xué)生的態(tài)度（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）課程設(shè)計報告（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性、設(shè)計態(tài)度及考勤是否降等級：是（）、否（）評閱人： 職稱：

4、 教授 2010 年 6 月 28 日目 錄1、 課設(shè)題目42、 概要設(shè)計53、 詳細(xì)設(shè)計74、 運(yùn)行結(jié)果5、 總結(jié)6、 附錄1、 課設(shè)題目1、問題描述設(shè)計一個給定文法和對應(yīng)FIRSTVT和LASTVT集，能依據(jù)依據(jù)文法和FIRSTVT和LASTVT生成算符優(yōu)先分析表。(算法參見教材)2、基本要求動態(tài)模擬算法的基本功能是：（1）輸入一個給定文法，及FIRSTVT和LASTVT集；（2）輸出算符優(yōu)先分析表生成算法；（3）輸出算法優(yōu)先分析表構(gòu)造過程的過程；3、測試數(shù)據(jù)輸入文法：E-TEE-+TE|T-FTT-*FT|F-(E)|i二、概要設(shè)計 用結(jié)構(gòu)體數(shù)組存儲多行正規(guī)式，用LIST控件顯示算法，用

5、CDC類依據(jù)進(jìn)行算法進(jìn)行作圖。并實現(xiàn)算法與生成過程的關(guān)聯(lián)。 根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保存，設(shè)置符號棧S，算法步驟如下： 1、將輸入符號串a(chǎn)1a2a3.an#依次逐個存入符號棧S中，直到遇到棧頂符號ai的優(yōu)先性下一個待輸入符號aj時為止。 2、棧頂當(dāng)前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1ak為止。3、由句柄ak.ai在文法的產(chǎn)生式中查找右部為ak.ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯，這時可斷定輸入串不是該文法的句子。重復(fù)這三步，直到歸約完輸入符號串，棧中只剩文法的開始符號為止。 求出該文法的優(yōu)先關(guān)系表，在程序中用

6、2維數(shù)組表示，-1表示小于或者等于，大于為1，其它為0表示錯誤。 在輸入一串字符串以后進(jìn)行按照文法一步一步的進(jìn)行規(guī)約，我所進(jìn)行的是直接規(guī)約到文法的符號而不是規(guī)約到N。數(shù)據(jù)結(jié)構(gòu)使用的是鏈表，用一個STRUCT來表示一個元素，其中包含符號和下一個符號的指針。計算優(yōu)先符關(guān)系，1) =關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或A aBb,則a=b2)關(guān)系求出每個非終結(jié)符B的FIRSTVT(B)若AaB,則bFIRSTVT(B),a關(guān)系求出每個非終結(jié)符B的LASTVT(B)若ABb,則aLASTVT(B),ab構(gòu)造分析表M對每個產(chǎn)生式A 1| n執(zhí)行,.對FIRST(A)中每個終結(jié)符a, 把A i加入到

7、MA,a,其中 為終結(jié)首符集中含a的候選式 i或唯一候選式.若FIRST(A), 則對任何屬于FOLLOW(A)的終結(jié)符b,將A加入MA,b.把所有無定義的MA,a標(biāo)記為出錯.三、詳細(xì)設(shè)計1、優(yōu)先關(guān)系矩陣的構(gòu)造過程：（1） = 關(guān)系由產(chǎn)生式 F-(E) 知 （=）FIRSTVT集 FIRSTVT(E)= +,-,*,/,(,i FIRSTVT(F)= (,i FIRSTVT(T)= *,/,(,i LASTVT(E)= +,-,*,/,),i LASTVT(F)= ),i LASTVT(T)= *,/,),i (2) 關(guān)系 +T 則有：+ FIRSTVT(T) -T 則有：- FIRSTVT(

8、T) *F 則有：* FIRSTVT(F) /F 則有：/ FIRSTVT(F) (E 則有：( 關(guān)系 E+ 則有： LASTVT(E) + E- 則有： LASTVT(E) - T* 則有： LASTVT(T) * T/ 則有： LASTVT(T) / E) 則有： LASTVT(E) )終結(jié)符之間的優(yōu)先關(guān)系是唯一的，該文法是算符優(yōu)先文法。2、程序的功能描述：程序由文件讀入字符串（以#結(jié)束），然后進(jìn)行算符優(yōu)先分析，分析過程中如有錯誤，則終止程序并報告錯誤位置，最終向屏幕輸出移近規(guī)約過程。主程序流程圖：功能模塊：3、程序所調(diào)用的函數(shù)清單及其功能private bool TestGrammar(

9、) /測試是否為算符優(yōu)先文法/構(gòu)造語法規(guī)則集合（去除“|”符號）private void AddToGrammarRules(string LeftPart, string RightPart) private void AddToVtVn(string LeftPart, string RightPart) /構(gòu)造終結(jié)符與非終結(jié)符public string RetJudgement() /返回對于輸入語法規(guī)則的判斷/是FirstVt()函數(shù)和LastVt()函數(shù)所調(diào)用的一個過程，作用是入棧private void Insert(char Vn, char Vt, bool, TempArr)

10、private string FirstVt() /計算FIRSTVT集合private string LastVt() /計算LASTVT集合public string RetFirstLastVt() /返回FIRSTVT集合與LASTVT集合private void RetPreRelationTable() /計算優(yōu)先關(guān)系表public StringCollection DrawPreRelationTable()/返回優(yōu)先關(guān)系表private string TraceBack(string s, int m, int n) /分析過程所調(diào)用的歸約函數(shù)private bool Anal

11、ysisProcess(string InputSentence)/分析過程public StringCollection RetAnalysisProcess(string InputSentence)/返回分析（歸約移進(jìn)）過程/*構(gòu)造函數(shù)，參數(shù)為規(guī)則數(shù)組，構(gòu)造函數(shù)將規(guī)則分為兩部分， 分別存于LeftPartRuleTemp和RightPartRuleTemp中*/public Grammar(String GrammarRules) foreach (String ruleTemp in GrammarRules) if (!ruleTemp.Contains(-) return; els

12、e ruleTemp.Replace(-, ); String temp = ruleTemp.Split(); LeftPartRuleTemp.Add(temp0); RightPartRuleTemp.Add(temp1); /*測試是否為算符優(yōu)先文法， 若是返回true，否則返回false*/private bool TestGrammar() foreach (String tempRule in RightPartRuleTemp) for (int i = 0; i = A & tempRulei = A & tempRulei + 1 = Z) return false; re

13、turn true; /*構(gòu)造語法規(guī)則集合（去除“|”符號）*/private void AddToGrammarRules(string LeftPart, string RightPart) String partTemp = String.Empty; for(int i=0;i=RightPart.Length-1;i+) char vt = RightParti; if (vt != |) partTemp += vt.ToString(); else RightPartRule.Add(partTemp);LeftPartRule.Add(LeftPart0.ToString();

14、 partTemp = String.Empty; if (i = (RightPart.Length -1 ) RightPartRule.Add(partTemp); LeftPartRule.Add(LeftPart0.ToString(); partTemp = String.Empty; /*構(gòu)造終結(jié)符集合和非終結(jié)符集合， 輸入的字符串應(yīng)不包含|符號*/private void AddToVtVn(string LeftPart, string RightPart) if (!VN.Contains(LeftPart0) VN.Add(LeftPart0); foreach (cha

15、r vt in RightPart) if (vt Z) & !VT.Contains(vt) & vt != |) VT.Add(vt); /*返回對于輸入語法規(guī)則的判斷*/public string RetJudgement() string RetString = string.Empty; if (TestGrammar() RetString += 這是一個算符優(yōu)先文法！rn; for (int i = 0; i = LeftPartRuleTemp.Count - 1; i+) AddToGrammarRules(LeftPartRuleTempi.ToString(), Righ

16、tPartRuleTempi.ToString(); AddToVtVn(LeftPartRuleTempi.ToString(), RightPartRuleTempi.ToString(); RetString += 非終結(jié)符為：rn; foreach (char vn in VN) RetString += vn.ToString(); RetString += rn終結(jié)符為：rn; foreach (char vt in VT) RetString += vt.ToString(); else RetString += 這不是一個算符優(yōu)先算法！; return RetString; 四

17、、運(yùn)行結(jié)果執(zhí)行程序彈出算符優(yōu)先分析表生成的界面：輸入或者讀取文法執(zhí)行，運(yùn)行出FIRSTVT集和LASTVT集并得出算符優(yōu)先關(guān)系表五、總結(jié) 由于編譯原理課學(xué)的并不好，開始看見題目不知該如何下手，后面把課本復(fù)習(xí)了一下，才開始算符優(yōu)先文法的設(shè)計。通過設(shè)計，對算符優(yōu)先文法有了更深入的了解，原來并不理解算符優(yōu)先文法為什么會設(shè)計成那樣，后面經(jīng)過程序的逐步調(diào)試，也逐步理解算符文法的設(shè)計原理。通過編寫語法分析這樣一個程序，讓我對于算符優(yōu)先分析有了更加深刻和直觀的了解，對于整個過程也變得非常清晰，去除了當(dāng)初學(xué)習(xí)過程中似是而非的理解。 此次試驗最終能夠完成，程序能夠運(yùn)行且能實現(xiàn)預(yù)計功能，但有些地方還有待改進(jìn)，比如

18、輸出結(jié)果框應(yīng)改變一下顯示模式，以便能夠?qū)Τ绦蜻\(yùn)行結(jié)果一目了然。通過此次課程設(shè)計實驗，我加深了對算符優(yōu)先文法的理解，鞏固了編程技術(shù)和對C#的使用。通過這次學(xué)課設(shè)，我發(fā)現(xiàn)有很多東西，很多細(xì)節(jié)沒注意，如經(jīng)常漏大小寫問題等很小的問題，真正自己動手做了才發(fā)現(xiàn)了自己的理論知識是如此的不扎實。有時候一個很小的問題卡一下就要處理很久，細(xì)節(jié)方面會帶來很大的問題等等。我深刻體會到這給我?guī)淼恼系K。不過也因為通過這次的課程設(shè)計鞏固了我的知識，查漏補(bǔ)缺，鞏固我已有的知識，把那些遺忘掉的知識再重新學(xué)習(xí)一遍，使我學(xué)到很多，得到很多。在算符優(yōu)先程序設(shè)計過程中，我覺得比較復(fù)雜，其中在優(yōu)先關(guān)系矩陣的構(gòu)造時遇到了非常大的困難，由

19、于最初對程序的總體流程不是十分清晰，而且實驗中因本人馬虎將優(yōu)先關(guān)系矩陣輸入錯誤，造成了設(shè)計與調(diào)試的困難。這個課程設(shè)計的思路我能掌握，但要不參考任何資料完全靠自己編確有不小的難度。在編程之前，我參考了很多網(wǎng)上的一個程序和同學(xué)的程序，在吸收其精華的基礎(chǔ)上，自己做了些改進(jìn)，最終將程序調(diào)出來了。但經(jīng)過自己的努力，通過多次調(diào)試，最終構(gòu)造出優(yōu)先關(guān)系矩陣并調(diào)試成功。通過本次實驗一定程度上提高了軟件開發(fā)能力，對編譯原理這一門課程也有了比較深刻的了解。最后，由于所學(xué)知識不夠全面，實驗在很多方面還有待完善，在以后的學(xué)習(xí)過程中，會掌握更多知識，力求做到更好。六、附錄1、參考文獻(xiàn)1程序設(shè)計語言編譯原理 陳火旺等. 國

20、防工業(yè)出版社 2編譯原理 張素琴 呂映芝 蔣維杜 戴桂蘭. 清華大學(xué)出版社3編譯原理及編譯程序構(gòu)造 高仲儀. 北京航天航空大學(xué)出版社2、部分代碼using System;using System.Collections;using System.Collections.Specialized;using System.Windows.Forms;namespace GrammarAnalyzer class Grammar StringCollection LeftPartRuleTemp = new StringCollection(); StringCollection RightPart

21、RuleTemp = new StringCollection(); StringCollection LeftPartRule = new StringCollection(); StringCollection RightPartRule = new StringCollection(); ArrayList VT = new ArrayList(); ArrayList VN = new ArrayList(); bool, FirstVtTable; bool, LastVtTable; char, PreRelationTable; StringCollection ProcessS

22、tr = new StringCollection(); Stack stack = new Stack(); public Grammar(String GrammarRules) /略 private bool TestGrammar() /略 private void AddToGrammarRules(string LeftPart, string RightPart) /略 private void AddToVtVn(string LeftPart, string RightPart) /略 public string RetJudgement() /略 private void

23、Insert(char Vn, char Vt, bool, TempArr) int VnNum = VN.IndexOf(Vn); int VtNum = VT.IndexOf(Vt); if (!TempArrVnNum, VtNum) TempArrVnNum, VtNum = true; stack.Push(Vn.ToString() + Vt.ToString(); private string FirstVt() /計算FIRSTVT集合 string strFirst = 以下為FIRSTVT集合：rn; stack.Clear(); FirstVtTable = new b

24、oolVN.Count, VT.Count; for (int i = 0; i = 2 & VT.Contains(RightPartRulei1) Insert(LeftPartRulei0, RightPartRulei1, FirstVtTable); while (stack.Count = 1) string tempQa = stack.Pop().ToString(); string tempQ = tempQa0.ToString(); string tempa = tempQa1.ToString(); for (int i = 0; i = LeftPartRule.Co

25、unt - 1; i+) if (RightPartRulei0.ToString() = tempQ) Insert(LeftPartRulei0, tempa0, FirstVtTable); for (int i = 0; i = VN.Count - 1; i+) strFirst += FIRSTVT( + VNi.ToString() + )= ; for (int j = 0; j = VT.Count - 1; j+) if (FirstVtTablei, j = true) strFirst += VTj.ToString() + ; strFirst += rn; retu

26、rn strFirst; private string LastVt() string strLast = 以下為LASTVT集合：rn; stack.Clear(); LastVtTable = new boolVN.Count, VT.Count; for (int i = 0; i = 2 & VT.Contains(RightPartRuleij - 2) Insert(LeftPartRulei0, RightPartRuleij - 2, LastVtTable); while (stack.Count = 1) string tempQa = stack.Pop().ToStri

27、ng(); string tempQ = tempQa0.ToString(); string tempa = tempQa1.ToString(); for (int i = 0; i = LeftPartRule.Count - 1; i+) int k = RightPartRulei.Length; if (RightPartRuleik - 1.ToString() = tempQ) Insert(LeftPartRulei0, tempa0, LastVtTable); for (int i = 0; i = VN.Count - 1; i+) strLast += LASTVT(

28、 + VNi.ToString() + )= ; for (int j = 0; j = VT.Count - 1; j+) if (LastVtTablei, j = true) strLast += VTj.ToString() + ; strLast += rn; return strLast; /計算LASTVT集合 public string RetFirstLastVt() return FirstVt() + rnrn + LastVt(); private void RetPreRelationTable() PreRelationTable = new charVT.Coun

29、t, VT.Count; foreach (string tempRule in RightPartRule) for (int i = 0; i = tempRule.Length - 2; i+) if (VT.Contains(tempRulei) & VT.Contains(tempRulei + 1) PreRelationTableVT.IndexOf(tempRulei), VT.IndexOf(tempRulei + 1) = =; if (i = tempRule.Length - 3 & VT.Contains(tempRulei) & !VT.Contains(tempRulei + 1) & VT.Contains(tempRulei + 2) PreRelationTableVT.IndexOf(tempRulei), VT.IndexOf(tempRulei + 2) = =; if (VT.Contains(tempRulei) & !VT.Contains(tempRulei + 1) for (int j = 0; j = VT.Cou