編譯基本知識教學(xué)規(guī)劃報(bào)告算符優(yōu)先分析表

_課程設(shè)計(jì)(論文)任務(wù)書軟件學(xué)院 學(xué)院 軟件工程 專業(yè) 07-1 班一、課程設(shè)計(jì)(論文)題目 算符優(yōu)先分析表生成模擬二、課程設(shè)計(jì)(論文)工作自2010年6月20日起至2010年6月25感謝閱讀日止。三、課程設(shè)計(jì)(論文)地點(diǎn):四、課程設(shè)計(jì)(論文)內(nèi)容要求：1．本課程設(shè)計(jì)的目的1、使學(xué)生增進(jìn)對編譯原理的認(rèn)識，加強(qiáng)用程序設(shè)計(jì)語言實(shí)現(xiàn)編譯算法能精品文檔放心下載力。2、進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計(jì)的思想，加深對編譯原理和應(yīng)用程序的理精品文檔放心下載解，針對編譯過程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的謝謝閱讀程序設(shè)計(jì)任務(wù)，同時(shí)強(qiáng)調(diào)好的程序設(shè)計(jì)風(fēng)格，并綜合使用程序設(shè)計(jì)語言、精品文檔放心下載數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識，熟悉使用開發(fā)工具VC6.0或JAVA。感謝閱讀2．課程設(shè)計(jì)的任務(wù)及要求1）基本要求：_動態(tài)模擬算法的基本功能是：（1）輸入一個(gè)給定文法，及FIRSTVT和LASTVT集；謝謝閱讀（2）輸出算符優(yōu)先分析表生成算法；（3）輸出算法優(yōu)先分析表構(gòu)造過程的過程。2）課程設(shè)計(jì)論文編寫要求1）要按照書稿的規(guī)格打印謄寫課設(shè)報(bào)告；2）報(bào)告分為封面、課程設(shè)計(jì)任務(wù)書（本文檔）分析、總結(jié)和附錄；謝謝閱讀3）報(bào)告正文包括以下部分：①問題描述：題目要解決的問題是什么；②分析、設(shè)計(jì)、實(shí)現(xiàn)：解決問題的基本方法說明，包括主要算法思想，感謝閱讀算法的流程圖，程序中主要函數(shù)或過程的功能說明；④運(yùn)行結(jié)果分析：分析程序的運(yùn)行結(jié)果是否正確以及出現(xiàn)的問題；謝謝閱讀⑤總結(jié)：遇到的主要問題是如何解決的、對設(shè)計(jì)和編碼的回顧討論和精品文檔放心下載分析、進(jìn)一步改進(jìn)設(shè)想、經(jīng)驗(yàn)和體會等；⑥附錄，包括源程序清單和運(yùn)行結(jié)果。學(xué)生簽名：2009年6月25_日課程設(shè)計(jì)(論文)評審意見（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è)計(jì)報(bào)告（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性、設(shè)計(jì)態(tài)度及考勤是否降等級：是（）、否（）評閱人：

職稱：教授2010年6月28日_目錄一、課設(shè)題目……………………4感謝閱讀二、概要設(shè)計(jì)……………………5感謝閱讀三、詳細(xì)設(shè)計(jì)……………………7精品文檔放心下載_四、運(yùn)行結(jié)果……………………精品文檔放心下載五、總結(jié)…………感謝閱讀六、附錄…………謝謝閱讀_一、課設(shè)題目1、問題描述設(shè)計(jì)一個(gè)給定文法和對應(yīng)FIRSTVT和LASTVT集，能依據(jù)精品文檔放心下載依據(jù)文法和FIRSTVT和LASTVT生成算符優(yōu)先分析表。(算法參謝謝閱讀見教材)2、基本要求動態(tài)模擬算法的基本功能是：（1）輸入一個(gè)給定文法，及FIRSTVT和LASTVT集；謝謝閱讀（2）輸出算符優(yōu)先分析表生成算法；_（3）輸出算法優(yōu)先分析表構(gòu)造過程的過程；3、測試數(shù)據(jù)輸入文法：E->TE’E’->+TE’|εT->FT’T’->*FT’|εF->(E)|i_二、概要設(shè)計(jì)用結(jié)構(gòu)體數(shù)組存儲多行正規(guī)式，用LIST控件顯示算法，用CDC類依據(jù)進(jìn)行算法進(jìn)行作圖。并實(shí)現(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#依次逐個(gè)存入符號棧S中，直到遇到棧頂符號ai的優(yōu)先性>下一個(gè)待輸入符號aj時(shí)為止。精品文檔放心下載2、棧頂當(dāng)前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1<ak為止。精品文檔放心下載3、由句柄ak...ai在文法的產(chǎn)生式中查找右部為ak...ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯，這時(shí)可斷定輸入串不是該文法的句子。精品文檔放心下載重復(fù)這三步，直到歸約完輸入符號串，棧中只剩文法的開始符號為止。精品文檔放心下載_求出該文法的優(yōu)先關(guān)系表，在程序中用2維數(shù)組表示，-1表示小于或者等于，大于為1，其它為0表示錯誤。謝謝閱讀在輸入一串字符串以后進(jìn)行按照文法一步一步的進(jìn)行規(guī)約，我所進(jìn)行的是直接規(guī)約到文法的符號而不是規(guī)約到N。精品文檔放心下載數(shù)據(jù)結(jié)構(gòu)使用的是鏈表，用一個(gè)STRUCT來表示一個(gè)元素，其中包含符號和下一個(gè)符號的指針。精品文檔放心下載計(jì)算優(yōu)先符關(guān)系，‘=‘關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了→…ab…或A→…aBb,則a=b2)’<‘關(guān)系求出每個(gè)非終結(jié)符B的FIRSTVT(B)A→…aB…,則b∈FIRSTVT(B),a<b3)’>’關(guān)系謝謝閱讀求出每個(gè)非終結(jié)符B的LASTVT(B)A→…Bb…,則a∈LASTVT(B),a>b_構(gòu)造分析表M①對每個(gè)產(chǎn)生式A→1|…|n執(zhí)行②,③.②對FIRST(A)中每個(gè)終結(jié)符a,把A→i加入到M[A,a],其中為終結(jié)首符集中精品文檔放心下載a的候選式i或唯一候選式.③若ε∈FIRST(A),則對任何屬于FOLLOW(A)的終結(jié)符b,將A→ε加入M[A,b].④把所有無定義的M[A,a]標(biāo)記為出錯._三、詳細(xì)設(shè)計(jì)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}<關(guān)系+T 則有：+<FIRSTVT(T)-T 則有：-<FIRSTVT(T)_*F 則有：*<FIRSTVT(F)/F 則有：/<FIRSTVT(F)(E 則有：(<FIRSTVT(E)(3)>關(guān)系E+ 則有：LASTVT(E)>+E- 則有：LASTVT(E)>-T* 則有：LASTVT(T)>*T/ 則有：LASTVT(T)>/則有：LASTVT(E)>)終結(jié)符之間的優(yōu)先關(guān)系是唯一的，該文法是算符優(yōu)先文法。感謝閱讀2、程序的功能描述：程序由文件讀入字符串（以#結(jié)束），然后進(jìn)行算符優(yōu)先分析，分析過程中如有錯誤，則終止程序并報(bào)告錯誤位置，最終向屏幕輸出移近規(guī)約過程。謝謝閱讀主程序流程圖：__功能模塊：3、程序所調(diào)用的函數(shù)清單及其功能privateboolTestGrammar()感謝閱讀//測試是否為算符優(yōu)先文法//構(gòu)造語法規(guī)則集合（去除“|”符號）privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)感謝閱讀privatevoidAddToVtVn(stringLeftPart,stringRightPart)//構(gòu)造終結(jié)符與非終結(jié)符謝謝閱讀_publicstringRetJudgement()精品文檔放心下載//返回對于輸入語法規(guī)則的判斷//是FirstVt()函數(shù)和LastVt()函數(shù)所調(diào)用的一個(gè)過程，作用是入感謝閱讀棧privatevoidInsert(charVn,charVt,bool[,]TempArr)精品文檔放心下載privatestringFirstVt()//計(jì)算FIRSTVT集合privatestringLastVt()//計(jì)算LASTVT集合publicstringRetFirstLastVt()精品文檔放心下載//返回FIRSTVT集合與LASTVT集合謝謝閱讀privatevoidRetPreRelationTable()感謝閱讀//計(jì)算優(yōu)先關(guān)系表publicStringCollectionDrawPreRelationTable()謝謝閱讀//返回優(yōu)先關(guān)系表privatestringTraceBack(strings,intm,intn)//分析過程所調(diào)用的歸約函數(shù)精品文檔放心下載_privateboolAnalysisProcess(stringInputSentence)謝謝閱讀//分析過程publicStringCollectionRetAnalysisProcess(string謝謝閱讀InputSentence)//返回分析（歸約移進(jìn)）過程/****構(gòu)造函數(shù)，參數(shù)為規(guī)則數(shù)組，構(gòu)造函數(shù)將規(guī)則分為兩部分，精品文檔放心下載分別存于LeftPartRuleTemp和RightPartRuleTemp中謝謝閱讀****/publicGrammar(String[]GrammarRules)感謝閱讀{ foreach(StringruleTempinGrammarRules)謝謝閱讀{ if(!ruleTemp.Contains("->"))return;謝謝閱讀elseruleTemp.Replace("->",">");謝謝閱讀String[]temp=ruleTemp.Split('>');謝謝閱讀LeftPartRuleTemp.Add(temp[0]);謝謝閱讀RightPartRuleTemp.Add(temp[1]);精品文檔放心下載}_}/****測試是否為算符優(yōu)先文法，若是返回true，否則返回false****/privateboolTestGrammar()感謝閱讀{ foreach(StringtempRuleinRightPartRuleTemp)謝謝閱讀{ for(inti=0;i<=tempRule.Length-2;i++)感謝閱讀{if(tempRule[i]>='A'&&tempRule[i]<='Z'&&tempRule[i+1]>='A'&&tempRule[i+1]<='Z')感謝閱讀returnfalse;}}returntrue;}/****構(gòu)造語法規(guī)則集合（去除“|”符號）****/精品文檔放心下載privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)謝謝閱讀{ StringpartTemp=String.Empty;for(inti=0;i<=RightPart.Length-1;i++)謝謝閱讀_{ charvt=RightPart[i];if(vt!='|')partTemp+=vt.ToString();感謝閱讀else{ RightPartRule.Add(partTemp);謝謝閱讀LeftPartRule.Add(LeftPart[0].ToString());partTemp=String.Empty;謝謝閱讀}if(i==(RightPart.Length-1))精品文檔放心下載{ RightPartRule.Add(partTemp);精品文檔放心下載LeftPartRule.Add(LeftPart[0].ToString());partTemp=String.Empty;感謝閱讀}}}/****構(gòu)造終結(jié)符集合和非終結(jié)符集合，輸入的字符串應(yīng)不包含‘|’符號****/_privatevoidAddToVtVn(stringLeftPart,stringRightPart)感謝閱讀{ if(!VN.Contains(LeftPart[0]))謝謝閱讀VN.Add(LeftPart[0]);foreach(charvtinRightPart)感謝閱讀{ if((vt<'A'||vt>'Z')&&!VT.Contains(vt)謝謝閱讀&&vt!='|')VT.Add(vt);}}/****返回對于輸入語法規(guī)則的判斷****/publicstringRetJudgement()感謝閱讀{ stringRetString=string.Empty;謝謝閱讀if(TestGrammar()){RetString+="這是一個(gè)算符優(yōu)先文法！\r\n";for(inti=0;i<=LeftPartRuleTemp.Count-1;i++)謝謝閱讀{AddToGrammarRules(LeftPartRuleTemp[i].ToString(),RightPartRuleTemp[i].ToString());謝謝閱讀_AddToVtVn(LeftPartRuleTemp[i].ToString(),謝謝閱讀RightPartRuleTemp[i].ToString());謝謝閱讀}RetString+="非終結(jié)符為：\r\n";foreach(charvninVN)謝謝閱讀RetString+=vn.ToString();謝謝閱讀RetString+="\r\n終結(jié)符為：\r\n";謝謝閱讀foreach(charvtinVT)RetString+=vt.ToString();精品文檔放心下載}elseRetString+="這不是一個(gè)算符優(yōu)先算法！";returnRetString;謝謝閱讀}_四、運(yùn)行結(jié)果執(zhí)行程序彈出算符優(yōu)先分析表生成的界面：__輸入或者讀取文法_執(zhí)行，運(yùn)行出FIRSTVT集和LASTVT集并得出算符優(yōu)先關(guān)系表感謝閱讀_五、總結(jié)由于編譯原理課學(xué)的并不好，開始看見題目不知該如何下手，后面把課本復(fù)習(xí)了一下，才開始算符優(yōu)先文法的設(shè)計(jì)。通過設(shè)計(jì)，對算符優(yōu)先文法有了更深入的了解，原來并不理解算符優(yōu)先文法為什么會設(shè)計(jì)成那樣，后面經(jīng)過程序的逐步調(diào)試，也逐步理解算符文法的設(shè)計(jì)原理。通過編寫語法分析這樣一個(gè)程序，讓我對于算符優(yōu)先分析有了更加深刻和直觀的了解，對于整個(gè)過程也變得非常清晰，去除了當(dāng)初學(xué)習(xí)過程中似是而非的理解。感謝閱讀此次試驗(yàn)最終能夠完成，程序能夠運(yùn)行且能實(shí)現(xiàn)預(yù)計(jì)功能，但有些地方還有待改進(jìn)，比如輸出結(jié)果框應(yīng)改變一下顯示模式，以便能夠?qū)Τ绦蜻\(yùn)行結(jié)果一目了然。通過此次課程設(shè)計(jì)實(shí)驗(yàn)，我加深了對算符優(yōu)先文法的理解，鞏固了編程技術(shù)和對C#的使用。精品文檔放心下載通過這次學(xué)課設(shè)，我發(fā)現(xiàn)有很多東西，很多細(xì)節(jié)沒注意，如經(jīng)感謝閱讀_常漏大小寫問題等很小的問題，真正自己動手做了才發(fā)現(xiàn)了自己的理論知識是如此的不扎實(shí)。有時(shí)候一個(gè)很小的問題卡一下就要處理很久，細(xì)節(jié)方面會帶來很大的問題等等。我深刻體會到這給我?guī)淼恼系K。不過也因?yàn)橥ㄟ^這次的課程設(shè)計(jì)鞏固了我的知識，查漏補(bǔ)缺，鞏固我已有的知識，把那些遺忘掉的知識再重新學(xué)習(xí)一遍，使我學(xué)到很多，得到很多。感謝閱讀在算符優(yōu)先程序設(shè)計(jì)過程中，我覺得比較復(fù)雜，其中在優(yōu)先關(guān)系矩陣的構(gòu)造時(shí)遇到了非常大的困難，由于最初對程序的總體流程不是十分清晰，而且實(shí)驗(yàn)中因本人馬虎將優(yōu)先關(guān)系矩陣輸入錯誤，造成了設(shè)計(jì)與調(diào)試的困難。這個(gè)課程設(shè)計(jì)的思路我能掌握，但要不參考任何資料完全靠自己編確有不小的難度。在編程之前，我參考了很多網(wǎng)上的一個(gè)程序和同學(xué)的程序，在吸收其精華的基礎(chǔ)上，自己做了些改進(jìn)，最終將程序調(diào)出來了。但經(jīng)過自己的努力，通過多次調(diào)試，最終構(gòu)造出優(yōu)先關(guān)系矩陣并調(diào)試成功。精品文檔放心下載通過本次實(shí)驗(yàn)一定程度上提高了軟件開發(fā)能力，對編譯原理這一門課程也有了比較深刻的了解。最后，由于所學(xué)知識不夠全面，實(shí)驗(yàn)在很多方面還有待完善，在以后的學(xué)習(xí)過程中，會掌握更多知識，力求做到更好。謝謝閱讀_六、附錄1、參考文獻(xiàn)[1]《程序設(shè)計(jì)語言編譯原理》陳火旺等.國防工業(yè)出版社謝謝閱讀[2]《編譯原理》張素琴呂映芝蔣維杜戴桂蘭.清華大學(xué)出版社謝謝閱讀[3]《編譯原理及編譯程序構(gòu)造》高仲儀.北京航天航空大學(xué)出版社謝謝閱讀2、部分代碼usingSystem;usingSystem.Collections;usingSystem.Collections.Specialized;精品文檔放心下載usingSystem.Windows.Forms;精品文檔放心下載namespaceGrammarAnalyzer{ classGrammar{StringCollectionLeftPartRuleTemp=newStringCollection();感謝閱讀StringCollectionRightPartRuleTemp=newStringCollection();精品文檔放心下載_StringCollectionLeftPartRule=newStringCollection();謝謝閱讀StringCollectionRightPartRule=newStringCollection();感謝閱讀ArrayListVT=newArrayList();謝謝閱讀ArrayListVN=newArrayList();謝謝閱讀bool[,]FirstVtTable;bool[,]LastVtTable;char[,]PreRelationTable;StringCollectionProcessStr=newStringCollection();精品文檔放心下載Stackstack=newStack();精品文檔放心下載publicGrammar(String[]GrammarRules)精品文檔放心下載//略privateboolTestGrammar()感謝閱讀//略privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)精品文檔放心下載//略_privatevoidAddToVtVn(stringLeftPart,stringRightPart)精品文檔放心下載//略publicstringRetJudgement()謝謝閱讀//略privatevoidInsert(charVn,charVt,bool[,]TempArr)感謝閱讀{intVnNum=VN.IndexOf(Vn);謝謝閱讀intVtNum=VT.IndexOf(Vt);精品文檔放心下載if(!TempArr[VnNum,VtNum])感謝閱讀{TempArr[VnNum,VtNum]=true;stack.Push(Vn.ToString()+Vt.ToString());精品文檔放心下載}}privatestringFirstVt() //計(jì)算FIRSTVT集合感謝閱讀{stringstrFirst="以下為FIRSTVT集合：\r\n";stack.Clear();感謝閱讀_FirstVtTable=newbool[VN.Count,VT.Count];精品文檔放心下載for(inti=0;i<=LeftPartRule.Count-1;i++)精品文檔放心下載{ if(VT.Contains(RightPartRule[i][0]))感謝閱讀{Insert(LeftPartRule[i][0],RightPartRule[i][0],FirstVtTable);謝謝閱讀}else if (RightPartRule[i].Length >= 2 &&精品文檔放心下載VT.Contains(RightPartRule[i][1]))謝謝閱讀{Insert(LeftPartRule[i][0],RightPartRule[i][1],FirstVtTable);感謝閱讀}}while(stack.Count>=1){ stringtempQa=stack.Pop().ToString();謝謝閱讀stringtempQ=tempQa[0].ToString();謝謝閱讀stringtempa=tempQa[1].ToString();謝謝閱讀for(inti=0;i<=LeftPartRule.Count-1;i++)感謝閱讀{ if(RightPartRule[i][0].ToString()==tempQ)精品文檔放心下載{Insert(LeftPartRule[i][0],tempa[0],FirstVtTable);感謝閱讀}_}}for(inti=0;i<=VN.Count-1;i++)感謝閱讀{ strFirst+="FIRSTVT("+VN[i].ToString()+")={";精品文檔放心下載for(intj=0;j<=VT.Count-1;j++)感謝閱讀{ if(FirstVtTable[i,j]==true)感謝閱讀strFirst+=VT[j].ToString()+"";精品文檔放心下載}strFirst+="}\r\n";}returnstrFirst;}privatestringLastVt(){ stringstrLast="以下為LASTVT集合：\r\n";感謝閱讀stack.Clear();LastVtTable=newbool[VN.Count,VT.Count];謝謝閱讀for(inti=0;i<=LeftPartRule.Count-1;i++)精品文檔放心下載_{intj=RightPartRule[i].Length;if(VT.Contains(RightPartRule[i][j-1])){Insert(LeftPartRule[i][0],RightPartRule[i][j-1],LastVtTable);}elseif(RightPartRule[i].Length>=2&&VT.Contains(RightPartRule[i][j-2])){Insert(LeftPartRule[i][0],RightPartRule[i][j-2],LastVtTable);}}while(stack.Count>=1){ stringtempQa=stack.Pop().ToString();謝謝閱讀stringtempQ=tempQa[0].ToString();感謝閱讀stringtempa=tempQa[1].ToString();精品文檔放心下載for(inti=0;i<=LeftPartRule.Count-1;i++)感謝閱讀{ intk=RightPartRule[i].Length;感謝閱讀if(RightPartRule[i][k-1].ToString()==tempQ)謝謝閱讀_{Insert(LeftPartRule[i][0],tempa[0],LastVtTable);精品文檔放心下載}}}for(inti=0;i<=VN.Count-1;i++)精品文檔放心下載{strLast+="LASTVT("+VN[i].ToString()+")={";感謝閱讀for(intj=0;j<=VT.Count-1;j++)謝謝閱讀{ if(LastVtTable[i,j]==true)謝謝閱讀strLast+=VT[j].ToString()+"";感謝閱讀}strLast+="}\r\n";}returnstrLast;} //計(jì)算LASTVT集合publicstringRetFirstLastVt()謝謝閱讀{ returnFirstVt()+"\r\n\r\n"+LastVt();謝謝閱讀_}privatevoidRetPreRelationTable()精品文檔放心下載{ PreRelationTable=newchar[VT.Count,VT.Count];謝謝閱讀foreach(stringtempRuleinRightPartRule)謝謝閱讀{ for(inti=0;i<=tempRule.Length-2;i++)感謝閱讀{if(VT.Contains(tempRule[i])&&VT.Contains(tempRule[i謝謝閱讀+1])){ PreRelationTable[VT.IndexOf(tempRule[i]),精品文檔放心下載VT.IndexOf(tempRule[i+1])]='=';謝謝閱讀}if (i <= tempRule.Length - 3 &&感謝閱讀VT.Contains(tempRule[i]) && !VT.Contains(tempRule[i + 1]) &&謝謝閱讀VT.Contains((tempRule[i+2])))感謝閱讀{PreRelationTable[VT.IndexOf(tempRule[i]),精品文檔放心下載VT.IndexOf(tempRule[i+2])]='=';精品文檔放心下載}if(VT.Contains(tempRule[i])&&!VT.Contains(tempRule[i+1]))謝謝閱讀{ for(intj=0;j<=VT.Count-1;j++)精品文檔放心下載_{ if(FirstVtTable[VN.IndexOf(tempRule[i+1]),j]感