編譯原理課程設(shè)計-簡單計算器實(shí)現(xiàn).doc

課程設(shè)計報告課程：編譯原理學(xué)號：姓名：班級：11級嵌入式應(yīng)用技術(shù)班教師：時間：2014年6月計算機(jī)科學(xué)與技術(shù)系設(shè)計名稱：簡單計算器的實(shí)現(xiàn)設(shè)計內(nèi)容、目的與要求：設(shè)計內(nèi)容：計算器的功能要求如下：可以支持加（+）、減（-）、乘（*）、除（/）運(yùn)算，如3+4-5*2/2;支持括號運(yùn)算，如（4+5）*5/8。用戶輸入表達(dá)式后，轉(zhuǎn)化為逆波蘭式并執(zhí)行計算，最后輸出該表達(dá)式的結(jié)果。設(shè)計目的：1、對單詞的構(gòu)詞規(guī)則有明確的定義；2、編寫的分析程序能夠正確識別源程序中的語法符號；3、計算器源程序的以.c格式輸出；4、對于源程序中的語法錯誤，能夠做出簡單的錯誤處理，給出簡單的錯誤提示， 保證順利完成整個源程序的分析；5、計算器能夠?qū)崿F(xiàn)加，減，乘，除，混合運(yùn)算，多項(xiàng)式運(yùn)算設(shè)計要求：1、 將非后綴式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)式，并計算用逆波蘭式來表示的算術(shù)表達(dá)式的值。2、 掌握利用算符優(yōu)先分析法完成中綴表達(dá)式到逆波蘭式的轉(zhuǎn)化。計劃與進(jìn)度安排：5月20日5月21日：確定本次課程設(shè)計研究課題：實(shí)現(xiàn)簡單計算器。5月22日5月30日：進(jìn)行需求分析，分析該計算器具有哪些功能，并明確該課題的一些要求。5月31日6月 3日：查找相關(guān)資料和書籍，了解本課題涉及有關(guān)知識，如：編譯原理的一些基本概念，逆波蘭式的基本概念，以及逆波蘭式的轉(zhuǎn)化問題等。6月 4日6月 8日：概要設(shè)計，將程序的幾大模塊分開來設(shè)計，畫出程序的流程圖6月 8日6月10日：詳細(xì)設(shè)計，寫出代碼并進(jìn)行調(diào)試6月10日6月12日：運(yùn)行程序，如果能夠?qū)崿F(xiàn)本次課程設(shè)計則進(jìn)行優(yōu)化，如果不能滿足要求則繼續(xù)改進(jìn)。6月13日6月15日：對本次課程設(shè)計進(jìn)行分析總結(jié)。設(shè)計過程、步驟（可加頁）：一、需求分析1.1總述在日常的學(xué)習(xí)與工作過程中， 經(jīng)常遇到計算表達(dá)式數(shù)值的問題， 諸如34-（8+5*10）。如果人為地分步計算， 難免因疏漏了括號或字符而導(dǎo)致結(jié)果出錯。表達(dá)式計算器具有計算表達(dá)式結(jié)果的功能，大大方便了學(xué)習(xí)與工作。本次開發(fā)的表達(dá)式計算器能幫我們對數(shù)據(jù)進(jìn)行有效的運(yùn)算，如通過四則運(yùn)算能實(shí)現(xiàn)對輸入數(shù)據(jù)的加減乘除。本課程設(shè)計結(jié)合了編譯原理中的利用算符優(yōu)先分析法完成中綴表達(dá)式到逆波蘭式的轉(zhuǎn)化，并計算輸入表達(dá)式的結(jié)果。1.2編寫表達(dá)式計算器的意義我們每個人都使用過計算器, 專用的計算器都是一個現(xiàn)成的器件, 是由運(yùn)算芯片完成運(yùn)算功能的。而且只能進(jìn)行單純的加、減、乘、除運(yùn)算, 不能進(jìn)行表達(dá)式運(yùn)算。那么如何用計算機(jī)來實(shí)現(xiàn)一個基于表達(dá)式的計算器呢? 用計算機(jī)來實(shí)現(xiàn)一個基于表達(dá)式的計算器, 也就是用編寫程序( 即軟件) 的方法來實(shí)現(xiàn)。所謂的編譯程序是指這樣的一種程序, 它能夠把某一種語言程序( 稱為源語言程序) 轉(zhuǎn)換成另一種語言程序( 稱為目標(biāo)語言程序) , 而后者與前者在邏輯上是等價的。四則混合計算器的輸入是一個由字符組成的表達(dá)式( 源程序) , 如果這個表達(dá)式是合法的, 則輸出是這個表達(dá)式的計算結(jié)果( 目標(biāo)代碼) ; 否則輸出錯誤信息。因此四則混合計算器是一個典型的編譯程序。編譯原理是計算機(jī)軟件專業(yè)的一門重要的專業(yè)必修課。盡管編譯過程與外文書刊的翻譯工作過程比較類似, 但由于編譯程序所翻譯的畢竟不是自然語言, 必然有其自身特性, 因而學(xué)生普遍認(rèn)為這門課程是專業(yè)課中比較難于學(xué)習(xí)的。即使學(xué)習(xí)了編譯原理這門課, 大多數(shù)學(xué)生也不可能就開發(fā)出一個編譯程序。事實(shí)上, 許多從事計算機(jī)專業(yè)的人士也未能編寫出一個完整的編譯系統(tǒng)。而編制四則混合運(yùn)算的計算器, 就等價于編寫一個小的編譯系統(tǒng), 而且又具有可實(shí)現(xiàn)性, 因此, 把這個題目作為編譯原理學(xué)習(xí)的一個測驗(yàn)題目是非常適合的。現(xiàn)有的編譯程序通常有兩大類: 一類是翻譯, 另一類是解釋。所謂翻譯, 是指在計算機(jī)中放置一個能為計算機(jī)直接執(zhí)行的翻譯程序, 它以某一種程序設(shè)計語言( 源語言) 所編寫的程序( 源程序) 作為翻譯或加工的對象, 當(dāng)計算機(jī)執(zhí)行翻譯程序時, 就將它翻譯為與之等價的另一種語言目標(biāo)語言的程序( 目標(biāo)程序) 。如 C 編譯程序就是一種翻譯程序, 它的源語言和目標(biāo)語言分別是相應(yīng)的 C 語言和機(jī)器語言。解釋程序也是以源程序作為它的輸入, 它與編譯的主要區(qū)別是在解釋程序的執(zhí)行過程中不產(chǎn)生目標(biāo)程序, 而是邊解釋邊執(zhí)行源程序本身。1.3功能要求要求：實(shí)現(xiàn)具有加、減、乘、除、括號等運(yùn)算的簡單計算器，輸入表達(dá)式，轉(zhuǎn)換為逆波蘭式，輸出該表達(dá)式的值。二、概要設(shè)計2.1 開發(fā)環(huán)境操作系統(tǒng): Windows 7開發(fā)平臺： VC+6.0開發(fā)語言：C2.2 總體設(shè)計程序在VC+6.0中使用面向?qū)ο蟮募夹g(shù)實(shí)現(xiàn)了計算器。程序主要結(jié)構(gòu)如下：1.定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。2.初始化：設(shè)立算符優(yōu)先分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）； 3.控制部分：從鍵盤輸入一個表達(dá)式符號串；4.利用算符優(yōu)先分析算法進(jìn)行表達(dá)式處理：根據(jù)算符優(yōu)先分析表對表達(dá)式符號串進(jìn)行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。5.對生成的逆波蘭式進(jìn)行計算。2.2.1逆波蘭式定義將運(yùn)算對象寫在前面，而把運(yùn)算符號寫在后面。用這種表示法表示的表達(dá)式也稱做后綴式。逆波蘭式的特點(diǎn)在于運(yùn)算對象順序不變，運(yùn)算符號位置反映運(yùn)算順序。采用逆波蘭式可以很好的表示簡單算術(shù)表達(dá)式，其優(yōu)點(diǎn)在于易于計算機(jī)處理表達(dá)式。2.2.2逆波蘭表達(dá)式的運(yùn)算法則利用一個棧單純地從左至右掃描逆波蘭式中各個字符，就能計算出他們的值。戰(zhàn)中保存的是未被使用的全部的運(yùn)算對象它們或者是已經(jīng)掃描過的，或者是某種運(yùn)算所產(chǎn)生的結(jié)果。運(yùn)算規(guī)則如下：如果掃描的字符是操作符，則其值進(jìn)棧，并掃描下一個字符如果掃描的字符是一個二目運(yùn)算符，則對棧頂?shù)膬蓚€操作數(shù)執(zhí)行該運(yùn)算，并用運(yùn)算的結(jié)果代替這兩個元素。如果掃描的字符是一個一目運(yùn)算符，則對棧頂?shù)牟僮鲾?shù)執(zhí)行該運(yùn)算，并用運(yùn)算的結(jié)果代替該運(yùn)算對象。2.2.3逆波蘭式生成的設(shè)計思想及算法（1） 首先構(gòu)造一個運(yùn)算符棧，此運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。（2） 讀入一個用中綴表示的簡單算術(shù)表達(dá)式，表達(dá)式以“/0”結(jié)束。（3） 從左至右掃描該算術(shù)表達(dá)式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。（4）如果不是數(shù)字，該字符則是運(yùn)算符，此時需比較優(yōu)先關(guān)系。做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。倘若不是的話，則將此運(yùn)算符棧頂?shù)倪\(yùn)算從棧中彈出，將該字符入棧。（4） 重復(fù)上述操作直至掃描完整個簡單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達(dá)式。圖一 生成逆波蘭式流程圖2.2.4表達(dá)式計算的設(shè)計思想及算法(1)構(gòu)造一個棧，存放運(yùn)算對象。(2)讀入一個用逆波蘭式表示的簡單算術(shù)表達(dá)式。 (3)自左至右掃描該簡單算術(shù)表達(dá)式并判斷該字符，如果該字符是運(yùn)算對象，則將該字符入棧。若是運(yùn)算符，如果此運(yùn)算符是二目運(yùn)算符，則將對棧頂部的兩個運(yùn)算對象進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果入棧，并且將執(zhí)行該運(yùn)算的兩個運(yùn)算對象從棧頂彈出。如果該字符是一目運(yùn)算符，則對棧頂部的元素實(shí)施該運(yùn)算，將該棧頂部的元素彈出，將運(yùn)算結(jié)果入棧。 (4)重復(fù)上述操作直至掃描完整個簡單算術(shù)表達(dá)式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術(shù)表達(dá)式的值。圖二 表達(dá)式結(jié)果計算流程圖結(jié)果與分析（可以加頁）： 圖三 實(shí)現(xiàn)計算器加法功能圖四 實(shí)現(xiàn)計算器減法功能圖五 實(shí)現(xiàn)計算器乘法功能圖六 實(shí)現(xiàn)計算器除法功能圖七 實(shí)驗(yàn)計算器混合運(yùn)算功能設(shè)計體會與建議： 在期末的課程設(shè)計中，我們小組討論選擇一個比較熟悉的課題簡單計算器的實(shí)現(xiàn)。本課題的設(shè)計要求是實(shí)現(xiàn)具有加、減、乘、除、括號等運(yùn)算的簡單計算器，輸入表達(dá)式，輸出該表達(dá)式的值。從大一學(xué)習(xí)C語言，到大三學(xué)習(xí)JAVA，我們都接觸過實(shí)現(xiàn)計算器的實(shí)驗(yàn)，對于本次的課程設(shè)計，我們還是有點(diǎn)基礎(chǔ)。而這次的課程設(shè)計我們選擇是用C語言編寫的。設(shè)計的主要原理是用后綴表達(dá)式和堆棧實(shí)現(xiàn)對表達(dá)式的分析后進(jìn)行計算。 在編程的過程中，有些C語言的知識已經(jīng)忘記，我重新找出C語言的書，一邊重溫之前學(xué)習(xí)的知識，一邊編寫代碼。在此，我運(yùn)用到編譯原理中間代碼生成的一種形式逆波蘭式。逆波蘭式生成的要點(diǎn)是運(yùn)算對象順序不變，運(yùn)算符緊跟運(yùn)算對象之后。掌握了這個要點(diǎn)，理解起來還是很容易的。在這次的課程設(shè)計中，通過我們小組的積極配合，共同努力，我們很順利的完成這次任務(wù)。但是我感覺有兩點(diǎn)不足，就是我們不能實(shí)現(xiàn)小數(shù)的計算，再者就是運(yùn)行的界面不夠美觀。這兩點(diǎn)需要提升?？偟膩碚f，對于這次課程設(shè)計我很滿意。 這學(xué)期學(xué)習(xí)編譯原理這門課程，一開始我認(rèn)為學(xué)習(xí)編譯原理就是了解一些原理，理論的知識，是不需要編寫代碼的，但是在第一堂課經(jīng)過老師的介紹之后，我了解到，雖然本課程是編譯原理，書本上講到的都是一些理論知識，但是無論是哪一門課程都是需要有實(shí)踐作為基礎(chǔ)才能夠?qū)⑵鋵W(xué)習(xí)的更好。在第一次課上，老師就聲明這門課比較難，要認(rèn)真學(xué)，所以我很認(rèn)真的對待這門課程。本次課程設(shè)計是實(shí)現(xiàn)一個簡易的計算器，經(jīng)過大一以到大三的學(xué)習(xí)，再重新運(yùn)用C語言編程感覺還挺上手的，這也可以讓我重新復(fù)習(xí)一下C語言的知識。這次課程設(shè)計采用逆波蘭式的知識，這可以很好的表示簡單算術(shù)表達(dá)式，其優(yōu)點(diǎn)在于易于計算機(jī)處理表達(dá)式。本次設(shè)計使我進(jìn)一步端正了我的學(xué)習(xí)態(tài)度，學(xué)會了實(shí)事求是，對自己要嚴(yán)格要求。我覺得動手做設(shè)計之前，頭腦里必須清楚該怎么做，這一點(diǎn)是很重要的。就目前來說，我的動手能力雖然差一點(diǎn)，但我想，通過我的不懈努力，在這方面，我總會得到提高。在此次的課程設(shè)計中我最大的體會就是進(jìn)一步認(rèn)識到了理論聯(lián)系實(shí)踐的重要性?？偠灾?，此次課程設(shè)計讓我學(xué)到了好多平時在課堂上學(xué)不到的東西，增加了我的知識運(yùn)用能力，增強(qiáng)我的實(shí)際操作能力。我相信經(jīng)過實(shí)踐后的學(xué)習(xí)我可以將編譯原理這門課程掌握的更好。編譯原理是一門比較難懂但是又非常核心的計算機(jī)課程，在學(xué)習(xí)的過程中對什么是編譯程序，編譯程序工作的基本過程及其各階段的基本任務(wù)，熟悉了編譯程序總流程框圖，了解了編譯程序的生成過程、構(gòu)造工具及其相關(guān)的技術(shù)有了大致的了解。但是要想真正理解，那就需要實(shí)踐。本次課程設(shè)計就是一個將課本上的知識運(yùn)用于實(shí)踐的過程。本次課程設(shè)計是實(shí)現(xiàn)一個簡單的計算器，該計算器可以支持加（+）、減（-）、乘（*）、除（/）運(yùn)算，如3+4-5*2/2。支持括號運(yùn)算，如（4+5）*5/8。用戶輸入表達(dá)式后，轉(zhuǎn)化為逆波蘭式并執(zhí)行計算，最后輸出結(jié)果。通過本次的課程設(shè)計,加深了對于編譯原理中算符優(yōu)先分析算法的理解,通過自己編寫一個程序去實(shí)現(xiàn)這個算法,增強(qiáng)了對于編譯原理的理解和應(yīng)用能力,從另一個方面,提高了理論與實(shí)踐相結(jié)合的能力,鍛煉了使用VC6等編程環(huán)境將課上所學(xué)習(xí)的各種理論知識轉(zhuǎn)換為可執(zhí)行的應(yīng)用程序并使用其解決問題的能力,為進(jìn)一步深入學(xué)習(xí)編譯原理打下了良好的基礎(chǔ),加深了動手能力的鍛煉。通過課程設(shè)計,與其他兩名同組的同學(xué)一起,以編譯原理課上所學(xué)知識為基礎(chǔ),通過編程實(shí)現(xiàn)一個能夠?qū)崿F(xiàn)簡單計算器的程序。在此過程中遇到了許許多多的問題,我們相互協(xié)同合作，充分利用了網(wǎng)絡(luò)搜索引擎的強(qiáng)大功能和學(xué)校圖書館的大量相關(guān)書籍,最終解決了所遇到的各種各樣的問題,完成了預(yù)定的任務(wù)。雖然實(shí)現(xiàn)了該簡單計算器，但我們深知，本次課程設(shè)計還存在一些不足。比如：我們還可以將算法進(jìn)行優(yōu)化；計算器的功能不夠強(qiáng)大，可以加以改進(jìn)成為一個科學(xué)計算器；沒有制作界面，不夠美觀實(shí)用等。由于時間有限，這些不足我們只能在接下來的時間里繼續(xù)研究探討。源代碼：#include#include#define MaxSize 99void translate(char str,char exp) struct char dataMaxSize; int top; op; char ch; int i = 0,t = 0; op.top = -1; ch = stri; i+; while(ch != 0) switch(ch) case (: op.top+;op.dataop.top=ch; break; case ): while(op.dataop.top != () expt=op.dataop.top; op.top-; t+; op.top-; break; case +: case -: while(op.top != -1&op.dataop.top != () expt = op.dataop.top; op.top-; t+; op.top+; op.dataop.top = ch; break; case *: case /: while(op.dataop.top = /|op.dataop.top = *) expt = op.dataop.top; op.top-; t+; op.top+; op.dataop.top = ch; break; case : break; default: while(ch = 0&ch = 0&ch = 9) d = 10*d+ch-0; ch = expt; t+; st.top+; st.datast.top = d; ch = expt; t+; return st.datast.top;int m