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

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