編譯基本知識教學(xué)規(guī)劃報告算符優(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é)生增進對編譯原理的認識，加強用程序設(shè)計語言實現(xiàn)編譯算法能 力。2、進一步培養(yǎng)學(xué)生編譯器設(shè)計的思想，加深對編譯原理和應(yīng)用程序的理 解，針對編譯過程的重點和難點內(nèi)容進行編程，獨立完成有一定工作量的程序設(shè)計任務(wù)，同時強調(diào)好的程序設(shè)計風(fēng)格，并綜合使用程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識，熟悉使用開發(fā)工具VC6.0 或 JAVA。2 .課程

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ù)或過程的功能說明; 運行結(jié)果分析：分析程序的運行結(jié)果是否正確以及出現(xiàn)的問題;總結(jié)：遇到的主要問題是如何解決的、對設(shè)計和編碼的

3、回顧討論和 分析、進一步改進設(shè)想、經(jīng)驗和體會等;附錄，包括源程序清單和運行結(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)度及考勤是否降等級：是（、否（:)評閱人:職稱：教授 2010 年 6 月 28、課設(shè)題目

4、、概要設(shè)計三、詳細設(shè)計457四、運行結(jié)果五、總結(jié)六、附錄、課設(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->TE 'E' ->+TE ' | £T->FT 'T' ->*FT ' | £F->(

5、E)|i二、概要設(shè)計用結(jié)構(gòu)體數(shù)組存儲多行正規(guī)式，用LIST控件顯示算法，用CDC類依據(jù)進行算法進行作圖。并實現(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-1<ak為止。3、由句柄ak.ai在文法的產(chǎn)生式中查找右部為ak.ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯，這時 可斷定輸入串不是該文法的句子。重復(fù)這

6、三步，直到歸約完輸入符號串，棧中只剩文法的開始 符號為止。求出該文法的優(yōu)先關(guān)系表，在程序中用2維數(shù)組表示，-1表示小于或者等于，大于為1，其它為0表示錯誤。在輸入一串字符串以后進行按照文法步的進行規(guī)約,若ABb則a LASTVT(B),a>b我所進行的是直接規(guī)約到文法的符號而不是規(guī)約到 數(shù)據(jù)結(jié)構(gòu)使用的是鏈表，用一個STRUCT來表示一個元素，其中 包含符號和下一個符號的指針。計算優(yōu)先符關(guān)系,1)'關(guān)系 直接看產(chǎn)生式的右部，若出現(xiàn)了A fab 或 A f aBb,則 a=b2)' < 關(guān)系求出每個非終結(jié)符B 的 FIRSTVT(B)若AfaB，則b FIRSTVT(B

7、),a<b3)' > '關(guān)系求出每個非終結(jié)符B 的 LASTVT(B)構(gòu)造分析表M 對每個產(chǎn)生式AT 1|I n執(zhí)行，.對FIRST(A)中每個終結(jié)符a,把A - i加入到MA,a,其中 為終結(jié)首符集中 含a的候選式i或唯一候選式.若£FIRST(A),則對任何屬于FOLLOW(A)的終結(jié)符b,將A加入 MA,b.把所有無定義的MA,a標記為出錯.三、詳細設(shè)計1、優(yōu)先關(guān)系矩陣的構(gòu)造過程:(1)=關(guān)系由產(chǎn)生式F->(E)知(=)'FIRSTVT 集FIRSTVT(E)= +,-,*,/,(,i FIRSTVT(F)= (,i FIRSTVT(T

8、)= *,/,(,i LASTVT(E)= +,-,*,/,),i LASTVT(F)= ),i LASTVT(T)= *,/,),i < 關(guān)系+T 貝U有：+ < FIRSTVT(T)-T 貝U有：-< FIRSTVT(T)*F則有：* < FIRSTVT(F)IF則有：I < FIRSTVT(F)(E則有：(< FIRSTVT(E)關(guān)系E+則有:LASTVT(E) > +E-則有：LASTVT(E) > -T*則有：LASTVT(T) > *TI則有：LASTVT(T) > IE)則有：LASTVT(E) > )終結(jié)符之間的

9、優(yōu)先關(guān)系是唯一的，該文法是算符優(yōu)先文法。2、程序的功能描述:程序由文件讀入字符串（以#結(jié)束），然后進行算符優(yōu)先分析，分 析過程中如有錯誤，則終止程序并報告錯誤位置，最終向屏幕輸 出移近規(guī)約過程。主程序流程圖:功能模塊:3、程序所調(diào)用的函數(shù)清單及其功能P rivate bool TestGrammar()/測試是否為算符優(yōu)先文法/構(gòu)造語法規(guī)則集合（去除“I”符號）p rivate void AddToGrammarRules(stri ng Left Part,stri ngRight Part)private void AddToVtV n(stri ngLeft Part, stri ng

10、Right Part)/構(gòu)造終結(jié)符與非終結(jié)符p ublic stri ng RetJudgeme nt()/返回對于輸入語法規(guī)則的判斷/是FirstVtO函數(shù)和LastVtO函數(shù)所調(diào)用的一個過程，作用是入P rivate void In sert(char Vn, char Vt, bool, TempArr) p rivate stri ng FirstVt() /計算FIRSTVT集合 p rivate stri ng LastVt() /計算LASTVT集合 public stri ng RetFirstLastVt() /返回FIRSTVT集合與LASTVT集合 p rivate vo

11、id RetP reRelati on Table()/計算優(yōu)先關(guān)系表 p ublic Stri ngCollectio n Draw PreRelati on Table()/返回優(yōu)先關(guān)系表 p rivate stri ng TraceBack(stri ng s, int m, int n)分析過程所調(diào)用的歸約函數(shù)p rivate bool An alysis Process(stn ng Inp utSe nten ce)/分析過程 p ublic Stri ngCollectio n RetA nalysis Process(stri ngInp utSe nten ce)/返回分析（

12、歸約移進）過程/*構(gòu)造函數(shù)，參數(shù)為規(guī)則數(shù)組，構(gòu)造函數(shù)將規(guī)則分為兩部分,分別存于 LeftPartRuleTemp和 RightPartRuleTemp中*/P ublic Grammar(Stri ng GrammarRules) foreach (Stri ng ruleTe mp in GrammarRules)if (!ruleTe mp .Co ntai ns("->") return;elseruleTem p.Re place("->",">"Stri ng te mp = ruleTe mp .S pl

13、it('>');Left PartRuleTe mp .Add(te mp 0);Right PartRuleTe mp .Add(te mp 1);/*測試是否為算符優(yōu)先文法,若是返回true，否則返回false*/P rivate bool TestGrammar() foreach (Stri ng temp Rule in Right PartRuleTe mp)for (i nt i = 0; i <= temp Rule.Le ngth - 2; i+)if (te mp Rulei >= 'A' && temp R

14、ulei <='Z')'Z' && temp Rulei + 1 >= 'A' && temp Rulei + 1 <=return false;return true;/*構(gòu)造語法規(guī)則集合（去除“I”符號）*/p rivate void AddToGrammarRules(stri ng Left Part,stri ngRight Part)Stri ng p artTe mp = Stri ng.E mpty;for(i nt i=0;i<=Right Part.Le ngth-1;i

15、+) char vt = Right Parti;if (vt != T)P artTe mp += vt.ToStri ng();elseRight PartRule.Add( partTem p);Left PartRule.Add(Left Part0.ToStri ng();p artTe mp = Stri ng.E mpty;if (i = (Right Part.Le ngth -1 )Right PartRule.Add( partTem p);Left PartRule.Add(Left Part0.ToStri ng();p artTe mp = Stri ng.E mpt

16、y;/*構(gòu)造終結(jié)符集合和非終結(jié)符集合,輸入的字符串應(yīng)不包含1符號*/private void AddToVtV n( stri ng LeftPart, stri ng Right Part)if (!VN.Co ntain s(Left PartO)VN.Add(Left Part0);foreach (char vt in Right Part) if (vt < 'A' II vt > 'Z') && !VT.Co ntain s(vt)&& vt != T)VT.Add(vt);/*返回對于輸入語法規(guī)則的判斷*

17、/ p ublic stri ng RetJudgeme nt() stri ng RetStri ng = strin g.E mpty;if (TestGrammarO) RetStri ng +=" 這是一個算符優(yōu)先文法！ rn"for (i nt i = 0; i <= LeftP artRuleTem p.Cou nt - 1; i+)AddToGrammarRules(Left PartRuleTe mp i.ToStri ng(),Right PartRuleTe mp i.ToStri ng();AddToVtV n(Left PartRuleTe m

18、p i.ToStri ng().Right PartRuleTe mp i.ToStri ng();RetStri ng +=" 非終結(jié)符為：rn"foreach (char vn in VN)RetStri ng += vn .ToStri ng();RetString += "rn終結(jié)符為：rn"foreach (char vt in VT)RetStri ng += vt.ToStri ng();elseRetStri ng +="這不是一個算符優(yōu)先算法！"return RetStri ng;四、運行結(jié)果執(zhí)行程序彈出算符優(yōu)先分析

19、表生成的界面:叵岡蘑輸人文法”FIESTVT 與LJtSIVT集合:輸入或者讀取文法諂輔人文法輸入文法FIESTVT 與LASTVr集合:算符憂先關(guān)粟恚:打開已源代碼l_Ujgrad&R6pcrt_Pilas 1 Backup我最近的空擋3黨面iTi4rAnily£&r J0 GrammarS 羽 Gt amm ar Analyzer.：-Gr amm 建AiiilyE&r回I £*iilencel_l 呂 StiitaiiceL_2 =lIpgraleLoe匸3簡我的電胞執(zhí)行，運行出FIRSTVT集和LASTVT集并得出算符優(yōu)先關(guān)系表B算符憂先分析

20、*生威模0®誼輸入文法F工RSTTI 與LASTVT集合:；ETTFT-Hir 15T-FTr -MFT IGF->CE)|i以下対nasm集合: fIK5mCE)= + *( i 1 FIRSTVT CT)訂 * ( i riR5m(p)=( I 1 riRsrvT m # 輸入女怯以下対LASTVT集合: U5TVTa)= + * ) i U5TVTC 口 * ) i Lr c) 1 #c< < <五、總結(jié)由于編譯原理課學(xué)的并不好，開始看見題目不知該如何下手, 后面把課本復(fù)習(xí)了一下，才開始算符優(yōu)先文法的設(shè)計。通過設(shè)計, 對算符優(yōu)先文法有了更深入的了解，原來

21、并不理解算符優(yōu)先文法 為什么會設(shè)計成那樣，后面經(jīng)過程序的逐步調(diào)試，也逐步理解算 符文法的設(shè)計原理。通過編寫語法分析這樣一個程序，讓我對于 算符優(yōu)先分析有了更加深刻和直觀的了解，對于整個過程也變得 非常清晰，去除了當(dāng)初學(xué)習(xí)過程中似是而非的理解。此次試驗最終能夠完成，程序能夠運行且能實現(xiàn)預(yù)計功能, 但有些地方還有待改進，比如輸出結(jié)果框應(yīng)改變一下顯示模式,以便能夠?qū)Τ绦蜻\行結(jié)果一目了然。通過此次課程設(shè)計實驗，我加深了對算符優(yōu)先文法的理解，鞏固了編程技術(shù)和對C#的使用。通過這次學(xué)課設(shè)，我發(fā)現(xiàn)有很多東西，很多細節(jié)沒注意，如經(jīng)常漏大小寫問題等很小的問題，真正自己動手做了才發(fā)現(xiàn)了自己 的理論知識是如此的不扎

22、實。有時候一個很小的問題卡一下就要 處理很久，細節(jié)方面會帶來很大的問題等等。我深刻體會到這給 我?guī)淼恼系K。不過也因為通過這次的課程設(shè)計鞏固了我的知識, 查漏補缺，鞏固我已有的知識，把那些遺忘掉的知識再重新學(xué)習(xí) 一遍，使我學(xué)到很多，得到很多。在算符優(yōu)先程序設(shè)計過程中，我覺得比較復(fù)雜，其中在優(yōu)先 關(guān)系矩陣的構(gòu)造時遇到了非常大的困難，由于最初對程序的總體 流程不是十分清晰，而且實驗中因本人馬虎將優(yōu)先關(guān)系矩陣輸入 錯誤，造成了設(shè)計與調(diào)試的困難。這個課程設(shè)計的思路我能掌握, 但要不參考任何資料完全靠自己編確有不小的難度。 在編程之前, 我參考了很多網(wǎng)上的一個程序和同學(xué)的程序，在吸收其精華的基 礎(chǔ)上，自

23、己做了些改進，最終將程序調(diào)出來了。但經(jīng)過自己的努 力，通過多次調(diào)試，最終構(gòu)造出優(yōu)先關(guān)系矩陣并調(diào)試成功。通過本次實驗一定程度上提高了軟件開發(fā)能力，對編譯原理 這一門課程也有了比較深刻的了解。最后，由于所學(xué)知識不夠全 面，實驗在很多方面還有待完善，在以后的學(xué)習(xí)過程中，會掌握 更多知識，力求做到更好。六、附錄參考文獻1程序設(shè)計語言編譯原理陳火旺等.國防工業(yè)出版社2編譯原理 張素琴呂映芝蔣維杜戴桂蘭.清華大學(xué)出版社3編譯原理及編譯程序構(gòu)造高仲儀.北京航天航空大學(xué)出版社部分代碼using System;using System.Collecti ons;using System.Collecti on

24、s.S pecialized;using System.Wi ndows.Forms;n ames pace GrammarA nalyzer class Grammar Stri ngCollection Left PartRuleTe mp = new Stri ngCollectio n();Strin gCollecti on Right PartRuleTe mp = new Stri ngCollectio n();Stri ngCollection LeftP artRule = new Stri ngCollectio n();Stri ngCollection Right P

25、artRule = new Strin gCollectio n();ArrayList VT = new ArrayList();ArrayList VN = new ArrayList();bool, FirstVtTable;bool, LastVtTable;char, Pr eRelati on Table;Stri ngCollecti on ProcessStr = new Strin gCollectio n();Stack stack = new Stack();p ublic Grammar(Str in g GrammarRules)/略p rivate bool Tes

26、tGrammar()/略p rivate void AddToGrammarRules(stri ng Left Part, stri ng Right Part)/略private void AddToVtV n(stri ng LeftP art, stri ng Right Part)/略p ublic stri ng RetJudgeme ntO/略p rivate void In sert(char Vn, char Vt, bool, TempArr) int VnNum = VN.I ndexOf(V n);int VtNum = VT.I ndexOf(Vt);if (!Tem

27、pArrV nNum, VtNum)TempArrV nNum, VtNum = true;stack. Push(V n. ToStri ngO + Vt.ToStri ng();private string FirstVt() / 計算FIRSTVT集合 string strFirst =" 以下為 FIRSTVT集合：rn"stack.Clear();FirstVtTable = new boolVN.Cou nt, VT.Cou nt;for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)if (VT.Co nt

28、a in s(Right PartRuleiO)>= 2 &&In sert(Left PartRulei0, Right PartRulei0, FirstVtTable);else if(Right PartRulei.Le ngthVT.Co ntai ns(Right PartRulei1)In sert(Left PartRulei0, Right PartRulei1, FirstVtTable);while (stack.Cou nt >= 1) stri ng tempQa = stack .Pop( ).ToStri ng();stri ng te

29、mpQ = temp Qa0.ToStri ng();stri ng tempa = temp Qa1.ToStri ngO;for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)if (Right PartRulei0.ToStr in g() = tempQ)In sert(Left PartRulei0, temp a0, FirstVtTable);for (i nt i = 0; i <= VN.Cou nt - 1; i+) strFirst += "FIRSTVT(" + VNi.ToStri ngO

30、 + ")="for (i nt j = 0; j <= VT.Cou nt - 1; j+) if (FirstVtTablei, j = true)strFirst += VTj.ToStri ngO + ""strFirst += "rn"return strFirst;p rivate stri ng LastVt()string strLast ="以下為 LASTVT 集合：rn"stack.ClearO;LastVtTable = new boolVN.Cou nt, VT.Cou nt;for

31、 (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)I nsert(Left PartRuleiO, temp a0, LastVtTable);j - 1)if (VT.Co ntai ns(Right PartRulei In sert(Left PartRulei0,Right PartRulei1,LastVtTable);else if(Right PartRulei.Le ngth>=&&VT.Co nta in s(Right PartRuleij - 2)In sert(Left PartRuleiO,Ri

32、ght PartRulei2,LastVtTable);while (stack.Cou nt >= 1) stri ng tempQa = stack .Pop( ).ToStri ng();stri ng tempQ = temp Qa0.ToStri ng();stri ng tempa = temp Qa1.ToStri ng();for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+) int k = Right PartRulei.Le ngth;if (Right PartRuleik - 1.ToStri ng() =

33、tempQ)for (i nt i = 0; i <= VN.Cou nt - 1; i+)strLast += "LASTVT(" + VNi.ToStri ng() + ")="for (i nt j = 0; j <= VT.Cou nt - 1; j+)H H. if (LastVtTablei, j = true)strLast += VT j.ToStri ng() +strLast += "rn"return strLast;/計算LASTVT集合public stri ng RetFirstLastVt()

34、 return FirstVt() + "rnrn" + LastVt();+ 1)P reRelatio nTableVT.I ndexOf(te mp Rulei),p rivate void RetPr eRelati on Table。P reRelatio nTable = new charVT.Cou nt, VT.Cou nt;foreach (stri ng temp Rule in Right PartRule) for (i nt i = 0; i <= temp Rule.Le ngth - 2; i+)if (VT.Contains(tempR

35、ulei)&& VT.Contains(tempRuleiVT.I ndexOf(te mp Rulei + 1)='='if (i<= temp Rule.Le ngth&&VT.Co ntain s(te mp Rulei)&&!VT.Co ntai ns(te mp Rulei1)&&VT.Co ntai ns(te mp Rulei + 2)P reRelatio nTableVT.I ndexOf(te mp Rulei),VT.I ndexOf(te mp Rulei + 2)='='if (VT.Co ntai ns(te mp Rulei) && !VT.Co ntai ns(te mp Rulei + 1)for (i nt j = 0; j <= VT.Cou nt - 1; j+)if (FirstVtTableVN.I ndexOf(te mp Rulei + 1), j=true)P reRelatio nTableVT.I ndexO