本科畢業(yè)設(shè)計(jì)

1、<p><b>　　1 緒論</b></p><p>　　編譯技術(shù)是理論與實(shí)踐并重的課程，在大學(xué)本科計(jì)算機(jī)科學(xué)與技術(shù)系的學(xué)生的培養(yǎng)教育中有非常重要的地位。而其實(shí)驗(yàn)課程要綜合運(yùn)用一年級(jí)、二年級(jí)和三年級(jí)所學(xué)的多門(mén)課程的內(nèi)容和知識(shí)，用來(lái)完成一個(gè)小型編譯程序的設(shè)計(jì)和實(shí)現(xiàn)。從而鞏固和加強(qiáng)對(duì)詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成和報(bào)錯(cuò)處理等理論的認(rèn)識(shí)和理解；培養(yǎng)在校大學(xué)生對(duì)一個(gè)完整的編譯系統(tǒng)

2、的獨(dú)立分析和設(shè)計(jì)開(kāi)發(fā)的能力，進(jìn)一步的培養(yǎng)當(dāng)代大學(xué)生動(dòng)手實(shí)踐能力以及獨(dú)立自主的開(kāi)發(fā)設(shè)計(jì)能力。 </p><p>　　完整的編譯器設(shè)計(jì)開(kāi)發(fā)和實(shí)現(xiàn)是一個(gè)非常復(fù)雜的過(guò)程，為了簡(jiǎn)潔明了的說(shuō)明編譯器的基本原理，本程序采用了自定義一種類(lèi)高級(jí)語(yǔ)言的高級(jí)語(yǔ)言的方法，先定義了該類(lèi)高級(jí)語(yǔ)言的語(yǔ)法規(guī)則，然后再設(shè)計(jì)與實(shí)現(xiàn)了該語(yǔ)言的編譯器前端，并且分別從詞法分析，語(yǔ)法分析和語(yǔ)義分析等三個(gè)方面進(jìn)行了詳細(xì)的開(kāi)發(fā)和設(shè)計(jì)。希望可以讓學(xué)生可以更加清楚

3、直觀的認(rèn)識(shí)和理解編譯原理的各個(gè)方面的知識(shí)。</p><p>　　從以往的日常教學(xué)經(jīng)驗(yàn)來(lái)看，我們大學(xué)課程中接觸和學(xué)習(xí)的最多的就是C語(yǔ)言和C++語(yǔ)言。C語(yǔ)言是計(jì)算機(jī)科學(xué)與技術(shù)等信息類(lèi)專(zhuān)業(yè)的基礎(chǔ)必修課，大部分同學(xué)都掌握的比較扎實(shí)，所以，本程序所寫(xiě)的詞法分析器，語(yǔ)法分析器，語(yǔ)義分析器大部分所用的語(yǔ)言都是C語(yǔ)言，C語(yǔ)言是面向過(guò)程的結(jié)構(gòu)化語(yǔ)言，程序設(shè)計(jì)結(jié)構(gòu)清晰，邏輯嚴(yán)謹(jǐn)，能讓讓學(xué)生很好的理解和接受。C++語(yǔ)言也是計(jì)算機(jī)科學(xué)與

4、技術(shù)等專(zhuān)業(yè)的基礎(chǔ)課程，是C語(yǔ)言在面對(duì)對(duì)象思想方面的改進(jìn)版，它繼承了C語(yǔ)言的結(jié)構(gòu)化設(shè)計(jì)思路，邏輯層次感強(qiáng)，同時(shí)又具備了面向?qū)ο笤O(shè)計(jì)的能力，也是一門(mén)非常優(yōu)秀的語(yǔ)言，很多學(xué)生對(duì)這門(mén)語(yǔ)言很感興趣，所以本程序也設(shè)計(jì)了幾個(gè)用C++語(yǔ)言編寫(xiě)的詞法分析器，語(yǔ)法分析器，語(yǔ)義分析器，以備那些在C++語(yǔ)言方面熟練掌握的學(xué)生學(xué)習(xí)和借鑒。</p><p><b>　　1.1 選題背景</b></p>

5、<p>　　21世紀(jì)是飛速發(fā)展的高科技時(shí)代。在日常的生活和工作中各行各業(yè)都離不開(kāi)計(jì)算機(jī)技術(shù)的運(yùn)用。學(xué)好計(jì)算機(jī)技術(shù)可以讓你在以后的工作和生活中對(duì)電腦的使用得心應(yīng)手。所以計(jì)算機(jī)科學(xué)與技術(shù)成為了在大學(xué)里非常熱門(mén)的專(zhuān)業(yè)。但是大部分學(xué)生往往注重高級(jí)語(yǔ)言和軟件設(shè)計(jì)運(yùn)用方面的學(xué)習(xí)，對(duì)計(jì)算機(jī)的底層運(yùn)用卻不是特別在意，往往不求甚解，馬馬虎虎。其實(shí)這些都是不好的學(xué)習(xí)習(xí)慣，像計(jì)算機(jī)原理，操作系統(tǒng)和編譯原理都是非常重要的課程，學(xué)好并且掌握它們能讓你在

6、遇到計(jì)算機(jī)硬件方面的問(wèn)題的時(shí)候能夠輕松解決，了解計(jì)算機(jī)的底層運(yùn)行原理更可以幫助我們?cè)谠O(shè)計(jì)和開(kāi)發(fā)軟件的時(shí)候避免一些很棘手的問(wèn)題，使開(kāi)發(fā)出來(lái)的軟件更健壯，運(yùn)行效率更高。所以，為了增強(qiáng)大家對(duì)編譯原理課程的學(xué)習(xí)理解和動(dòng)手實(shí)踐能力，本課題整理和設(shè)計(jì)了一些和編譯器有關(guān)的程序，方便大家學(xué)習(xí)和參考。</p><p><b>　　1.2 選題意義</b></p><p>　　目前世界

7、上的發(fā)達(dá)國(guó)家普遍都非常重視發(fā)展以計(jì)算機(jī)科學(xué)和通信技術(shù)為核心的信息技術(shù)、信息產(chǎn)業(yè)和信息技術(shù)的應(yīng)用，大部分經(jīng)濟(jì)比較發(fā)達(dá)的國(guó)家的信息產(chǎn)業(yè)的發(fā)展都非常迅速。當(dāng)前，我國(guó)正處于國(guó)民經(jīng)濟(jì)的高速發(fā)展時(shí)期。與此相伴隨著的，必然有信息技術(shù)應(yīng)用方面的高速發(fā)展，各行各業(yè)都將面臨著信息技術(shù)研究與發(fā)展的大課題以及信息化技術(shù)改造的大任務(wù)與大工程。所以，很多高校都非常重視學(xué)生在計(jì)算機(jī)科學(xué)技術(shù)方面的學(xué)習(xí)。信息技術(shù)基礎(chǔ)更是成為了大部分學(xué)校的公共基礎(chǔ)課。</p>

8、<p>　　當(dāng)然，編譯原理作為一門(mén)比較復(fù)雜的計(jì)算機(jī)技術(shù)，對(duì)非計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生要求不是那么高，但是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的學(xué)生就應(yīng)該好好學(xué)習(xí)和掌握。要求學(xué)生不但要學(xué)習(xí)課堂上的理論知識(shí)，也要加強(qiáng)動(dòng)手實(shí)踐能力，所以，編譯原理的課程設(shè)計(jì)和實(shí)踐就顯得非常重要了，但是目前來(lái)說(shuō)，很多學(xué)生的動(dòng)手實(shí)踐能力很差，實(shí)驗(yàn)課上設(shè)計(jì)的程序往往會(huì)遇見(jiàn)各種各樣的問(wèn)題，比如程序的語(yǔ)法總是有問(wèn)題，或者邏輯不嚴(yán)謹(jǐn)，又或者經(jīng)常報(bào)錯(cuò)，結(jié)果不符合設(shè)計(jì)要求等等。<

9、/p><p>　　在這個(gè)教學(xué)實(shí)踐背景下，本課題決定整理和設(shè)計(jì)一些編譯原理實(shí)踐課程中常用的程序，方便學(xué)生更好的學(xué)習(xí)和理解編譯原理這門(mén)課程，同時(shí)提高他們的動(dòng)手實(shí)踐的能力，能讓他們?cè)谧约涸O(shè)計(jì)編譯程序的時(shí)候少犯錯(cuò)誤，少走彎路，更好的完成學(xué)校既定的教學(xué)任務(wù)和目標(biāo)。希望同學(xué)們能把本課題設(shè)計(jì)的程序當(dāng)做一個(gè)參考，更好的掌握編譯原理這門(mén)課的精髓，更好的提高自己。</p><p><b>　　1.3

10、資料來(lái)源</b></p><p>　　在設(shè)計(jì)過(guò)程之中曾多次對(duì)編譯原理的課程設(shè)計(jì)和編譯器的設(shè)計(jì)實(shí)現(xiàn)收集資料，在互聯(lián)網(wǎng)上和圖書(shū)館中查找編譯原理的相關(guān)信息，力求使本課題設(shè)計(jì)的程序能夠充分的貼近現(xiàn)實(shí)，滿(mǎn)足同學(xué)們的實(shí)踐需求。由于在收集資料的時(shí)候很多資料的內(nèi)容互相重復(fù)，有資料中的程序也有互相借鑒，所以該課題所編寫(xiě)的程序代碼可能有的也會(huì)互相類(lèi)似，但是這應(yīng)該不會(huì)影響整個(gè)程序的可讀性以及準(zhǔn)確性。整個(gè)程序設(shè)計(jì)中的很多東西

11、都有參考教科書(shū)，所以，教科書(shū)也是一個(gè)很重要的資料來(lái)源。 </p><p><b>　　1.4 程序特點(diǎn)</b></p><p>　　本課題做的這個(gè)套程序主要針對(duì)的是編譯原理的實(shí)踐教學(xué)和程序設(shè)計(jì)方面，所以各個(gè)程序之間相對(duì)比較獨(dú)立，功能比較單一，主要就是三個(gè)功能，詞法分析，語(yǔ)法分析以及語(yǔ)義分析。最后統(tǒng)一在VS2010下做了一個(gè)簡(jiǎn)單的界面，能把整個(gè)編譯過(guò)程演示一下。&l

12、t;/p><p>　　本程序的主要特點(diǎn)為：</p><p><b>　　a)界面簡(jiǎn)單</b></p><p>　　本程序在開(kāi)發(fā)的過(guò)程中，為了讓學(xué)生更直觀的學(xué)習(xí)和了解編譯原理內(nèi)部知識(shí)和編譯器的結(jié)構(gòu)，使操作界面簡(jiǎn)潔、統(tǒng)一，易學(xué)易用。采用人機(jī)對(duì)話(huà)方式，交互性強(qiáng)。</p><p><b>　　b)操作簡(jiǎn)單</b>

13、;</p><p>　　本系統(tǒng)盡量使用DOS操作界面，風(fēng)格一致，用戶(hù)只需熟悉DOS界面的基本操作，就能基本學(xué)會(huì)本程序的使用。在數(shù)據(jù)輸入過(guò)程中，本課題盡可能多地采用數(shù)據(jù)輸入確認(rèn)，減少數(shù)據(jù)輸入錯(cuò)誤,將鍵盤(pán)的錄入錯(cuò)誤量減至最少。最后統(tǒng)一的編譯器程序界面也非常簡(jiǎn)單，只有兩個(gè)按鈕，一個(gè)編譯一個(gè)運(yùn)行，簡(jiǎn)單實(shí)用。</p><p><b>　　c)注釋很詳細(xì)</b></p>

14、;<p>　　程序內(nèi)部源代碼的注釋非常詳細(xì)，可以讓學(xué)生簡(jiǎn)潔直觀的判斷每一行代碼的功能以及作用，方便教學(xué)。</p><p><b>　　2 開(kāi)發(fā)環(huán)境</b></p><p>　　2.1 C語(yǔ)言簡(jiǎn)介</p><p>　　C語(yǔ)言是由20世紀(jì)70年代中期UNIX操作系統(tǒng)的發(fā)明者Dennis Ritchie在1970年于B語(yǔ)言的基礎(chǔ)上設(shè)

15、計(jì)和發(fā)明的。在1972年年初，Thompson等人在早期簡(jiǎn)易的計(jì)算機(jī)PDP型計(jì)算機(jī)上運(yùn)用C語(yǔ)言重寫(xiě)了UNIX操作的系統(tǒng)內(nèi)部關(guān)鍵程序，可以這么說(shuō)，C語(yǔ)言是伴隨著UNIX操作系統(tǒng)的誕生而誕生的。</p><p>　　20世紀(jì)80年代中期，C語(yǔ)言被程序員廣泛使用，漸漸的演變成為個(gè)人計(jì)算機(jī)上非常流行和受歡迎的編程語(yǔ)言和工具。早在1983年7月，美國(guó)的國(guó)家標(biāo)準(zhǔn)委員會(huì)就對(duì)C語(yǔ)言進(jìn)行了標(biāo)準(zhǔn)化得管理，發(fā)布了第一個(gè)C語(yǔ)言的標(biāo)準(zhǔn)草案

16、，使得C語(yǔ)言廣發(fā)傳播。</p><p>　　為了更好地適應(yīng)大規(guī)模軟件的生產(chǎn)和開(kāi)發(fā)，在C語(yǔ)言的基礎(chǔ)上，貝爾實(shí)驗(yàn)室Biarne Stroustrup博士和她的同事們開(kāi)始對(duì)它進(jìn)行改進(jìn)和擴(kuò)充。將“類(lèi)”的概念引入到了C語(yǔ)言當(dāng)中。在1983年末構(gòu)成了最早期的C++語(yǔ)言。為了讓C++語(yǔ)言可以適應(yīng)軟件的大規(guī)模的開(kāi)發(fā)需求，計(jì)算機(jī)技術(shù)的先驅(qū)們又為C++語(yǔ)言引入了多重繼承的概念，運(yùn)算符的重載技術(shù)以及引用和虛函數(shù)方法等許多全新的特性。美

17、國(guó)國(guó)家標(biāo)準(zhǔn)委員會(huì)（ANSI）和國(guó)際標(biāo)準(zhǔn)化組織ISO一起進(jìn)行了標(biāo)準(zhǔn)化工作，并且于1998年正式頒布了C++語(yǔ)言的國(guó)際標(biāo)準(zhǔn)ISO/IEC：1998-14882，從此刻開(kāi)始，軟件開(kāi)發(fā)進(jìn)入到了一個(gè)快速發(fā)展的新階段。</p><p>　　20世界90年代，美國(guó)的微軟公司（Microsoft）為了減少和降低Windows的應(yīng)用程序開(kāi)發(fā)成本，提高應(yīng)用軟件在軟件市場(chǎng)當(dāng)中的地位和價(jià)值，在1992年發(fā)布了包含MFC2.0在內(nèi)的Vis

18、ual C++1.0。一個(gè)創(chuàng)時(shí)代的可視化C++集成的開(kāi)發(fā)環(huán)境面世了。我們常說(shuō)的MFC其實(shí)就是一個(gè)常用的軟件集合包（framework），就是利用面向?qū)ο蟮姆椒ò裌indows的應(yīng)用程序的接口封裝起來(lái)。提高了Windows的平臺(tái)上的軟件產(chǎn)品的開(kāi)發(fā)效率。1998年，美國(guó)的微軟公司（Microsoft）推出了目前最流行也是最受歡迎的Visual C++ 6.0 版本。2002年末，又推出了Visual C++ 7.0，即是嵌入在Visual

19、Studio.NET框架中的Visual C++.NET2002。到目前為止，最新的版本已經(jīng)更新到了VS2012了。</p><p>　　盡管軟件開(kāi)發(fā)的環(huán)境一直在不換的更新發(fā)展，但是對(duì)于初學(xué)者來(lái)說(shuō)，打好基礎(chǔ)，學(xué)好C語(yǔ)言是非常重要的第一步。</p><p>　　2.1.1 C語(yǔ)言是一門(mén)中級(jí)語(yǔ)言</p><p>　　C語(yǔ)言是一門(mén)非?；A(chǔ)的中級(jí)語(yǔ)言，也就是說(shuō)C語(yǔ)言具有“

20、低級(jí)語(yǔ)言”的一些固有特征：允許程序自由訪問(wèn)計(jì)算機(jī)物理地址，可以進(jìn)行位操作，能夠?qū)τ?jì)算機(jī)的硬件接口直接訪問(wèn)，生成的目標(biāo)代碼的質(zhì)量非常高，程序的執(zhí)行效率也很高，同時(shí)它也兼顧了“高級(jí)語(yǔ)言”的固有特點(diǎn)：語(yǔ)句簡(jiǎn)潔，緊湊，運(yùn)算符特別靈活，數(shù)據(jù)類(lèi)型豐富，具有結(jié)構(gòu)化的控制語(yǔ)句，邏輯嚴(yán)謹(jǐn)，可移植性也很好。</p><p>　　2.1.2 C語(yǔ)言是結(jié)構(gòu)式語(yǔ)言</p><p>　　C語(yǔ)言的一個(gè)特別突出的特點(diǎn)就

21、是C語(yǔ)言的代碼和數(shù)據(jù)是分隔開(kāi)的，它把各個(gè)子程序之間除去必要的信息交流之外的程序部分相互獨(dú)立。這樣的結(jié)構(gòu)化程序設(shè)計(jì)方式可以使得程序代碼的層次更加清晰，便于用戶(hù)使用、程序的后期維護(hù)維護(hù)以及代碼編寫(xiě)人員進(jìn)行調(diào)試。C 語(yǔ)言的很多方法是用函數(shù)的方式提供給用戶(hù)使用的，函數(shù)可以在C語(yǔ)言中非常方便的調(diào)用，并且C語(yǔ)言中具有多種循環(huán)控制結(jié)構(gòu)、條件判斷語(yǔ)句可以控制程序和數(shù)據(jù)信息的流向，從而使源代碼完全結(jié)構(gòu)化。</p><p>　　2.

22、1.3 C語(yǔ)言的獨(dú)有特點(diǎn)</p><p>　　a ） C語(yǔ)言是包含結(jié)構(gòu)化程序設(shè)計(jì)以及遞歸功能的面向過(guò)程的中級(jí)語(yǔ)言。</p><p>　　b ） C語(yǔ)言的傳遞參數(shù)均是以值傳遞（pass by value），也可以傳遞指針（a pointer passed by value）。</p><p>　　c ） 在C語(yǔ)言中不同的變量類(lèi)型能夠用結(jié)構(gòu)體（struct）組合在一

23、起。</p><p>　　d ） C語(yǔ)言只有32個(gè)保留字（reserved keywords），這樣變量、函數(shù)命名有更多的彈性。</p><p>　　e ） 在C語(yǔ)言中部份的變量類(lèi)型可以轉(zhuǎn)換，比如整型和字符型變量。</p><p>　　f ） 使用指針的方式，C語(yǔ)言可以很輕松的對(duì)計(jì)算機(jī)中的存儲(chǔ)器進(jìn)行比較底層的控制。</p><p>　　g )

24、 預(yù)編譯處理（preprocessor）讓整個(gè)C語(yǔ)言的編譯過(guò)程更具有彈性。 </p><p>　　2.2 C++簡(jiǎn)介</p><p>　　C++語(yǔ)言一門(mén)非常流行而且受歡迎的高級(jí)語(yǔ)言，C語(yǔ)言算是C++語(yǔ)言當(dāng)中的一個(gè)子集，C++語(yǔ)言基本囊括了了C語(yǔ)言當(dāng)中的的絕大多數(shù)思想以及內(nèi)容。C++的應(yīng)用非常廣泛。C++可以支持多種編程范式 －－面向?qū)ο缶幊?、泛型編程以及過(guò)程化編程。目前最新的正式標(biāo)準(zhǔn)C

25、++14將于2014年8月18日發(fā)布。 C++語(yǔ)言在程序設(shè)計(jì)的領(lǐng)域使用的非常廣泛，經(jīng)常將之運(yùn)用在各種系統(tǒng)開(kāi)發(fā)以及引擎開(kāi)發(fā)等眾多的實(shí)際應(yīng)用當(dāng)中，是當(dāng)前社會(huì)上一門(mén)最受人們喜愛(ài)，使用人數(shù)最多的一門(mén)面向過(guò)程開(kāi)發(fā)的程序設(shè)計(jì)語(yǔ)言之一。它可以支持類(lèi)、封裝、重載等各種開(kāi)發(fā)功能的實(shí)際應(yīng)用。</p><p>　　2.2.1 C++語(yǔ)言支持?jǐn)?shù)據(jù)封裝</p><p>　　支持?jǐn)?shù)據(jù)封裝可以說(shuō)就是支持?jǐn)?shù)據(jù)

26、抽象。在C++語(yǔ)言中，類(lèi)是支持?jǐn)?shù)據(jù)封裝的工具，對(duì)象是數(shù)據(jù)封裝的實(shí)現(xiàn)。面向?qū)ο蟮某绦蛟O(shè)計(jì)思想與面向過(guò)程的程序設(shè)計(jì)思想在運(yùn)用函數(shù)以及數(shù)據(jù)信息的關(guān)系和方法上是完全不一樣的。在我們常用的面向過(guò)程的程序開(kāi)發(fā)和設(shè)計(jì)的過(guò)程當(dāng)中，數(shù)據(jù)通常只是被當(dāng)做了一種靜態(tài)結(jié)構(gòu)，只能夠等待程序的調(diào)用函數(shù)來(lái)對(duì)它們進(jìn)行計(jì)算和處理等操作，但是在我們面對(duì)對(duì)象方式的程序開(kāi)發(fā)設(shè)計(jì)過(guò)程當(dāng)中，將要操作的數(shù)據(jù)以及可以對(duì)這個(gè)數(shù)據(jù)進(jìn)行操作的調(diào)用函數(shù)一起封裝，作為一個(gè)新生成的類(lèi)的定義。另外，

27、封裝還可以提供一種對(duì)數(shù)據(jù)訪問(wèn)的控制機(jī)制，保障程序的安全性。</p><p>　　2.2.2 C++語(yǔ)言允許函數(shù)名和運(yùn)算符重載</p><p>　　函數(shù)名的重載和運(yùn)算符的重載都是屬于高級(jí)語(yǔ)言的多態(tài)性表現(xiàn)。函數(shù)的多態(tài)性指的是完全一樣的語(yǔ)法結(jié)構(gòu)可以用來(lái)代表不相同的實(shí)體或者對(duì)不相同的實(shí)體類(lèi)型進(jìn)行一些操作。C++語(yǔ)言可以支持函數(shù)的多態(tài)性，C++語(yǔ)言允許一個(gè)相同的運(yùn)算符號(hào)或者一個(gè)完全一樣的函數(shù)名稱(chēng)代

28、表多個(gè)不相同的實(shí)現(xiàn)的函數(shù)，這個(gè)就被稱(chēng)之為運(yùn)算符或者說(shuō)是表示符的重載。當(dāng)然，使用者可以根據(jù)自己的需要定義各種各樣的函數(shù)重載或者運(yùn)算符重載。</p><p>　　2.2.3 C++語(yǔ)言支持動(dòng)態(tài)聯(lián)編</p><p>　　在C++語(yǔ)言當(dāng)中可以定義虛函數(shù)。C++語(yǔ)言通過(guò)定義虛函數(shù)的方法可以完全支持程序設(shè)計(jì)中的動(dòng)態(tài)聯(lián)編功能，動(dòng)態(tài)聯(lián)編可以說(shuō)是高級(jí)語(yǔ)言多態(tài)性表現(xiàn)出來(lái)的一個(gè)非常明顯的特點(diǎn)，多態(tài)性形成的由父

29、類(lèi)以及子類(lèi)來(lái)組成的一個(gè)簡(jiǎn)單的樹(shù)形結(jié)構(gòu)。在這個(gè)樹(shù)形結(jié)構(gòu)中的每一個(gè)子類(lèi)都可以接受一個(gè)或者數(shù)個(gè)具有相同名字的消息和信息。</p><p>　　2.3 編譯原理介紹</p><p>　　編譯程序算是計(jì)算機(jī)軟件系統(tǒng)的最基本的組成部分之一了，而且目前市場(chǎng)上流行的大多數(shù)計(jì)算機(jī)系統(tǒng)都配置了不止一種高級(jí)程序設(shè)計(jì)語(yǔ)言（例如JAVA和C++）的編譯程序，對(duì)一些使用率較高的高級(jí)語(yǔ)言甚至準(zhǔn)備了好幾個(gè)不同性能的編譯

30、程序。從功能上來(lái)說(shuō)，一個(gè)編譯程序就好比一個(gè)語(yǔ)言的翻譯器，它可以把一種語(yǔ)言書(shū)寫(xiě)的程序翻譯成用另外一種語(yǔ)言編寫(xiě)的等價(jià)的程序。例如，匯編程序就是一個(gè)翻譯程序。它可以把匯編語(yǔ)言程序翻譯成由機(jī)器語(yǔ)言編寫(xiě)的程序。如果這個(gè)程序的設(shè)計(jì)語(yǔ)言是像C語(yǔ)言或者C++語(yǔ)言這類(lèi)的高級(jí)程序設(shè)計(jì)語(yǔ)言，而且程序的目標(biāo)語(yǔ)言是像機(jī)器語(yǔ)言這樣的低級(jí)程序設(shè)計(jì)語(yǔ)言，那么這個(gè)翻譯過(guò)程的程序就可以稱(chēng)之為編譯程序，這種翻譯的原理則可以稱(chēng)之為編譯原理。</p><p&

31、gt;　　2.4 編譯器介紹</p><p>　　編譯是從源程序代碼（一般是高級(jí)語(yǔ)言）到可以直接被計(jì)算機(jī)或者虛擬機(jī)執(zhí)行的目標(biāo)程序代碼（一般為低級(jí)語(yǔ)言或機(jī)器語(yǔ)言）的翻譯過(guò)程。但是，目前市場(chǎng)上也由把較低級(jí)的編程語(yǔ)言通過(guò)復(fù)雜的翻譯過(guò)程翻譯成較高級(jí)的編程語(yǔ)言的編譯程序，在這一類(lèi)型的編譯器當(dāng)中，那部分用來(lái)把由高級(jí)編程語(yǔ)言生成的低級(jí)語(yǔ)言代碼重新翻譯成由高級(jí)編程語(yǔ)言代碼的程序被我們稱(chēng)為反編譯器。也存在著從一種高級(jí)編程語(yǔ)言翻譯

32、為另外一種不同的高級(jí)編程語(yǔ)言的編譯程序，或者是生成另一種還需要計(jì)算機(jī)進(jìn)一步處理的的中間代碼的編譯程序（又稱(chēng)之為級(jí)聯(lián)）。</p><p>　　3 程序設(shè)計(jì)前期分析</p><p><b>　　3.1 初步調(diào)查</b></p><p>　　在編譯原理的日常教學(xué)中，大部分學(xué)校的教學(xué)模式還是以課堂教學(xué)為主，學(xué)生主要通過(guò)在課堂上聽(tīng)老師講解編譯原理教科

33、書(shū)上的理論知識(shí)來(lái)學(xué)習(xí)編譯原理這門(mén)課。但是，課堂講解的教學(xué)方式比較枯燥乏味，導(dǎo)致很多學(xué)生的學(xué)習(xí)積極性不高，學(xué)習(xí)效率較低，不能好好理解編譯原理的關(guān)鍵內(nèi)容。同時(shí)，學(xué)生在自己獨(dú)立編寫(xiě)和設(shè)計(jì)編譯程序的時(shí)候往往無(wú)從下手，動(dòng)手實(shí)踐能力很差，有的學(xué)生甚至連編譯器的運(yùn)行環(huán)境和平臺(tái)都不了解，更不要說(shuō)自己獨(dú)立設(shè)計(jì)和實(shí)現(xiàn)一個(gè)完整地編譯器程序了。所以，開(kāi)展編譯原理的實(shí)踐教學(xué)課程勢(shì)在必行，在實(shí)踐課上，學(xué)生可以系統(tǒng)的學(xué)習(xí)編譯程序的開(kāi)發(fā)過(guò)程，從一開(kāi)始的需求分析，語(yǔ)法結(jié)

34、構(gòu)制定，詞法分析，語(yǔ)法分析，四元式到最后完整的編譯器。這些東西不自己動(dòng)手練習(xí)是很難掌握的，通過(guò)實(shí)驗(yàn)教學(xué)，會(huì)使學(xué)生熟練地掌握編譯程序設(shè)計(jì)和實(shí)現(xiàn)的各個(gè)步驟，而且還能激發(fā)學(xué)生探究編譯原理更深層次的東西，增強(qiáng)學(xué)生對(duì)編譯原理的學(xué)習(xí)興趣。所以，一些好的、嚴(yán)謹(jǐn)?shù)膶?shí)驗(yàn)程序范例就顯得十分重要了。</p><p>　　本課題的研究正是為了給編譯原理的日常教學(xué)提供一個(gè)更適合學(xué)生學(xué)習(xí)和成長(zhǎng)的方式，給學(xué)生在動(dòng)手實(shí)踐的過(guò)程中提供一個(gè)示范，使

35、越來(lái)越多的學(xué)生能對(duì)編譯原理產(chǎn)生興趣，希望繼續(xù)研究下去。這樣，老師們就再也不用擔(dān)心學(xué)生的成績(jī)啦。</p><p>　　3.2 可行性分析</p><p>　　通過(guò)對(duì)編譯原理課程實(shí)際教學(xué)的初步調(diào)查后，發(fā)現(xiàn)目前編譯原理課程的教學(xué)現(xiàn)狀非常需要一門(mén)實(shí)驗(yàn)實(shí)踐課程來(lái)輔助教學(xué)，并且現(xiàn)在掌握的資料和技術(shù)可以設(shè)計(jì)和編寫(xiě)一些實(shí)驗(yàn)實(shí)踐程序。在對(duì)現(xiàn)有的人力、物力、財(cái)力和技術(shù)條件進(jìn)行分析之后，確定開(kāi)發(fā)該類(lèi)高級(jí)語(yǔ)言編

36、譯系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)課題，在經(jīng)濟(jì)上、技術(shù)上、時(shí)間上，法律上都已具備可行性。</p><p>　　a）經(jīng)濟(jì)可行性：即實(shí)現(xiàn)這個(gè)程序設(shè)計(jì)有沒(méi)有什么經(jīng)濟(jì)效益。這個(gè)編譯器程序設(shè)計(jì)是作為個(gè)人畢業(yè)設(shè)計(jì)而設(shè)計(jì)開(kāi)發(fā)的，因?yàn)閭€(gè)人能力和設(shè)計(jì)水平不高，程序的結(jié)構(gòu)以及功能都不夠完整，正確性有待考究，內(nèi)容也許沒(méi)有太高的實(shí)際價(jià)值，該程序設(shè)計(jì)方案可能并沒(méi)有太高的經(jīng)濟(jì)效益，但是作為一個(gè)畢業(yè)設(shè)計(jì)，卻使得它具有了開(kāi)發(fā)的價(jià)值。</p>&l

37、t;p>　　b）技術(shù)可行性：即現(xiàn)有的技術(shù)能否開(kāi)發(fā)該程序，會(huì)有哪些困難。目前掌握的編譯原理和C語(yǔ)言知識(shí)還行，也有很多相關(guān)資料可以查閱，所以技術(shù)上應(yīng)該是可行的。</p><p>　　c）運(yùn)行可行性：即該平臺(tái)規(guī)定的運(yùn)行方式是否可行。本課題用的主要是VC++6.0，和學(xué)校機(jī)房的操作環(huán)境一致，所以肯定是可以再學(xué)校機(jī)房運(yùn)行的。</p><p>　　d）法律可行性：該程序的開(kāi)發(fā)和設(shè)計(jì)應(yīng)該不會(huì)觸犯法

38、律。因?yàn)樵摮绦蛑皇亲鳛楫厴I(yè)設(shè)計(jì)與商業(yè)無(wú)關(guān)，又因?yàn)槭亲灾鏖_(kāi)發(fā)設(shè)計(jì)，因此不會(huì)構(gòu)成侵權(quán)，在法律上是可行的。</p><p>　　通過(guò)以上的可行性分析，決定設(shè)計(jì)和實(shí)現(xiàn)這個(gè)編譯器程序。</p><p>　　在程序的設(shè)計(jì)和開(kāi)發(fā)過(guò)程中，還應(yīng)注意一下兩點(diǎn)：</p><p>　　a）要注意程序的準(zhǔn)確性和注釋的完整性，只有完整的準(zhǔn)確的注釋才能為學(xué)生提供一個(gè)正確的參考和借鑒。</p

39、><p>　　b）從全局出發(fā)注意程序設(shè)計(jì)的整體優(yōu)化，還要注意程序的可擴(kuò)展性和延伸性。</p><p><b>　　3.3 需求分析</b></p><p>　　我們?cè)谲浖_(kāi)發(fā)中經(jīng)常遇見(jiàn)關(guān)于需求分析的問(wèn)題。需求分析，就是指對(duì)程序開(kāi)發(fā)當(dāng)中需要解決的問(wèn)題和障礙進(jìn)行的分析處理，搞明白要開(kāi)發(fā)的程序軟件的實(shí)際需求，包括程序要輸入什么樣的類(lèi)型和種類(lèi)的數(shù)據(jù)，期望

40、得到怎樣的運(yùn)行結(jié)果，最終程序應(yīng)該輸出什么東西?？梢哉f(shuō)，在軟件工程當(dāng)中的“需求分析”就是確定程序要“做什么”。 </p><p>　　在程序設(shè)計(jì)開(kāi)發(fā)的過(guò)程中，我們所說(shuō)的需求分析指的是在建立一個(gè)全新的或改變一個(gè)已經(jīng)存在的程序或者軟件的時(shí)候描述新的程序的設(shè)計(jì)方法、范圍、目的、功能和定義時(shí)所要進(jìn)行的所有的工作的總稱(chēng)。需求分析是軟件工程中的一個(gè)關(guān)鍵過(guò)程。在需求分析的過(guò)程中，大部分的分析員以及高級(jí)軟件工程師都會(huì)明確顧客的實(shí)際

41、需要，只有在我們明確了顧客的這些實(shí)際需要以后，程序設(shè)計(jì)人員才能夠分析出新的系統(tǒng)的解決方案和方法。 </p><p>　　基于需求分析的重要作用，查閱了圖書(shū)館書(shū)籍，瀏覽了網(wǎng)上的相關(guān)資料，從程序設(shè)計(jì)的方法，功能的實(shí)現(xiàn)，技術(shù)的要求以及可行性等多方面進(jìn)行考慮完成了需求分析。</p><p>　　現(xiàn)在很多高校都急需開(kāi)展編譯原理課程的實(shí)驗(yàn)實(shí)踐課程，肯定需要一些和實(shí)驗(yàn)教學(xué)相關(guān)的參考程序，本課題設(shè)計(jì)的這些

42、程序可以很好地滿(mǎn)足他們的需求，所以本課題的這個(gè)設(shè)計(jì)還是很有市場(chǎng)的。</p><p><b>　　4 總體設(shè)計(jì)</b></p><p><b>　　4.1 設(shè)計(jì)思想</b></p><p>　　本程序采用分步設(shè)計(jì)方式設(shè)計(jì)，把整個(gè)編譯器分解成三個(gè)主要部分，分別是詞法分析程序，語(yǔ)法分析程序，語(yǔ)義分析程序。各個(gè)部分的設(shè)計(jì)和實(shí)現(xiàn)

43、相對(duì)獨(dú)立，等把各個(gè)部分的功能設(shè)計(jì)和實(shí)現(xiàn)以后，在根據(jù)編譯器的運(yùn)行原來(lái)來(lái)進(jìn)行組合，這樣，一個(gè)完整的，結(jié)構(gòu)層次清晰的編譯器就開(kāi)發(fā)完成了。</p><p>　　首先需要設(shè)計(jì)的程序是詞法分析器，</p><p>　　第二步要做的是設(shè)計(jì)語(yǔ)法分析器，</p><p>　　第三部要實(shí)現(xiàn)的部分是語(yǔ)義分析器。</p><p>　　最后設(shè)計(jì)一個(gè)簡(jiǎn)單地前端，把上面三

44、個(gè)功能組合一下，就實(shí)現(xiàn)了一個(gè)完整的編譯器程序了。</p><p><b>　　4.2 主要任務(wù)</b></p><p>　　由于本程序是用于給學(xué)校的實(shí)驗(yàn)課教學(xué)提供一個(gè)參考，所以，程序的準(zhǔn)確性和平臺(tái)適用性需要保障，要確定程序能夠在學(xué)校機(jī)房的操作環(huán)境正常運(yùn)行，同時(shí)要注意程序注釋部分的完整性，要使學(xué)生能夠清楚正確的理解程序的每個(gè)部分要實(shí)現(xiàn)的功能，要讓他們弄懂每一句代碼的含

45、義，由于編譯原理詞法分析，語(yǔ)法分析，語(yǔ)義分析的方法有很多，所以還要注意程序編譯分析方法的多樣性。由于每個(gè)學(xué)生擅長(zhǎng)的編程語(yǔ)言各不相同，所以本課題選擇了C語(yǔ)言和C++語(yǔ)言作為程序開(kāi)發(fā)的主要語(yǔ)言，因?yàn)镃語(yǔ)言和C++語(yǔ)言是計(jì)算機(jī)科學(xué)與技術(shù)系的專(zhuān)業(yè)必修課，每個(gè)學(xué)生都應(yīng)該掌握的很不錯(cuò)。同時(shí)，C語(yǔ)言和C++語(yǔ)言都很常用，二者代表了現(xiàn)如今最流行的兩種程序設(shè)計(jì)語(yǔ)言的類(lèi)型，分別體現(xiàn)了面向?qū)ο笠约懊嫦蜻^(guò)程兩種完全不同的編程思想，對(duì)學(xué)生的日常學(xué)習(xí)有非常多的幫助

46、。</p><p><b>　　4.3 模塊結(jié)構(gòu)</b></p><p>　　4.3.1 詞法分析</p><p>　　詞法分析的過(guò)程基本上是所有的編譯程序的第一個(gè)處理過(guò)程，編譯器一般可以使用兩種完全不相同的設(shè)計(jì)方法來(lái)構(gòu)造和設(shè)計(jì)開(kāi)發(fā)詞法分析子程序。其中第一種就是根據(jù)對(duì)類(lèi)高級(jí)程序設(shè)計(jì)語(yǔ)言中得各類(lèi)單詞和符號(hào)的某種描述以及定義，使用手工構(gòu)造的策略

47、（例如可以用C語(yǔ)言或者C++語(yǔ)言）來(lái)開(kāi)發(fā)詞法分析子程序。通常來(lái)說(shuō)，程序可以根據(jù)已經(jīng)定義好的文法規(guī)則或者已經(jīng)畫(huà)好的狀態(tài)轉(zhuǎn)換圖來(lái)設(shè)計(jì)和開(kāi)發(fā)相對(duì)應(yīng)的狀態(tài)矩陣，這個(gè)狀態(tài)矩陣所有的控制語(yǔ)句一起控制程序就可以組成一個(gè)簡(jiǎn)單的編譯程序的詞法分析程序；也可以根據(jù)定義好的文法規(guī)則或狀態(tài)轉(zhuǎn)換圖來(lái)直接設(shè)計(jì)和編寫(xiě)詞法分析程序。另外的一種構(gòu)造詞法分析程序的途徑就是所謂的詞法分析程序的自動(dòng)生成，即先使用正規(guī)式對(duì)類(lèi)高級(jí)語(yǔ)言中的各個(gè)種類(lèi)的單詞和符號(hào)進(jìn)行詞型描述，并且分別

48、指出在識(shí)別單詞的過(guò)程中詞法分析程序應(yīng)該進(jìn)行的語(yǔ)義處理工作，然后用一個(gè)所謂的詞法分析程序的構(gòu)造程序?qū)ι鲜龅男畔⑦M(jìn)行進(jìn)一步的加工。例如著名的美國(guó)BELL科學(xué)實(shí)驗(yàn)室研制和開(kāi)發(fā)的LEX程序就是一個(gè)詞法分析子程序的自動(dòng)化生成工具。</p><p>　　一般的情況下，當(dāng)需要開(kāi)發(fā)一種全新的編程語(yǔ)言的時(shí)候，因?yàn)樵摼幊陶Z(yǔ)言的單詞和運(yùn)算符號(hào)在不停地開(kāi)發(fā)和修改，所以利用LEX這一類(lèi)的工具生成的我們需要的詞法分析程序相對(duì)于手工編寫(xiě)的方式

49、來(lái)說(shuō)會(huì)比較易于修改和維護(hù)。當(dāng)然，如果一旦這種語(yǔ)言確定了，那么采用手工設(shè)計(jì)和編寫(xiě)詞法分析程序的效率會(huì)更高。</p><p>　　4.3.2 語(yǔ)法分析</p><p>　　語(yǔ)法分析的過(guò)程可以說(shuō)是編譯程序中最核心的部分了，語(yǔ)法分析的目的就是識(shí)別由詞法分析程序所給出的單詞或者符號(hào)序列是不是事先給定文法的正確程序語(yǔ)句，目前大學(xué)教科書(shū)當(dāng)中涉及的語(yǔ)法分析方法有自頂向下分析方法以及自底向上這兩大類(lèi)別，自

50、頂向下的分析方法又包括了確定分析和不確定分析兩個(gè)分支，自底向上分析方法則又包含了運(yùn)算符優(yōu)先分析方法以及LR分析方法，這些分析方法都有各自的優(yōu)缺點(diǎn)。然而除去自頂向下的不確定分析方法外，都是目前編譯程序構(gòu)造的實(shí)用方法，本課題將在下一章著重介紹它們的實(shí)現(xiàn)原理和實(shí)踐技術(shù)。</p><p>　　4.3.3 語(yǔ)義分析</p><p>　　語(yǔ)法制導(dǎo)翻譯的模式是在語(yǔ)法分析的基礎(chǔ)上，增加語(yǔ)義操作來(lái)實(shí)現(xiàn)的。

51、對(duì)于要求中給定文法當(dāng)中的每一個(gè)產(chǎn)生式，開(kāi)發(fā)和設(shè)計(jì)其相對(duì)應(yīng)的語(yǔ)義子程序。在程序的語(yǔ)法分析過(guò)程當(dāng)中，每當(dāng)程序使用一個(gè)產(chǎn)生式來(lái)進(jìn)行歸約或者是推導(dǎo)的時(shí)候，語(yǔ)法分析程序不但要執(zhí)行相對(duì)應(yīng)的語(yǔ)法分析動(dòng)作，還需要調(diào)用相對(duì)應(yīng)的語(yǔ)義子程序，以便程序可以順利的完成包括生成中間代碼、查找和填寫(xiě)相關(guān)的表格數(shù)據(jù)、檢查并且報(bào)告源程序中的錯(cuò)誤在內(nèi)所有工作。每一個(gè)語(yǔ)義子程序都要求能夠指明相對(duì)應(yīng)的產(chǎn)生當(dāng)中的每一個(gè)字符和符號(hào)的具體含義和內(nèi)容，而且需要規(guī)定使用這個(gè)產(chǎn)生式來(lái)分析

52、程序的時(shí)候所應(yīng)該進(jìn)行的語(yǔ)義動(dòng)作。</p><p><b>　　5 詳細(xì)設(shè)計(jì)</b></p><p>　　5.1 詞法分析器的設(shè)計(jì)和實(shí)現(xiàn)</p><p>　　本程序用手工編碼方式構(gòu)造識(shí)別類(lèi)高級(jí)語(yǔ)言的詞法分析程序。該類(lèi)語(yǔ)言中具有的單詞包括了五個(gè)有代表性的關(guān)鍵字begin、end、if、then、else；標(biāo)識(shí)符；整型常數(shù)；六種關(guān)系運(yùn)算符；一個(gè)賦

53、值符和四個(gè)算術(shù)運(yùn)算符。</p><p>　　第一步，我們需要做的是對(duì)單詞進(jìn)行簡(jiǎn)單的分類(lèi)：設(shè)計(jì)好上面所說(shuō)的類(lèi)高級(jí)語(yǔ)言中的每一類(lèi)單詞的符號(hào)以及分類(lèi)碼表。</p><p><b>　　如下表5.1所示：</b></p><p>　　表5.1 類(lèi)高級(jí)語(yǔ)言中的各類(lèi)單詞符號(hào)及其分類(lèi)碼表</p><p>　　然后就是關(guān)于本程序詞法分

54、析的詳細(xì)處理過(guò)程了，在一個(gè)高級(jí)程序設(shè)計(jì)語(yǔ)言中，通常都會(huì)包含很多種類(lèi)的單詞符號(hào)。所以，本程序采用先為每個(gè)種類(lèi)的單詞符號(hào)建立一張完整的狀態(tài)轉(zhuǎn)換圖，然后再把這些狀態(tài)轉(zhuǎn)換圖一起組合成一張統(tǒng)一的狀態(tài)圖，就可以得到一個(gè)有限的自動(dòng)機(jī)，再進(jìn)行一些必要的確定化以及狀態(tài)數(shù)的最小化處理過(guò)程，最后再根據(jù)這個(gè)程序的狀態(tài)圖來(lái)設(shè)計(jì)和編寫(xiě)詞法分析程序。在這里，為了使得本程序的詞法分析程序的設(shè)計(jì)結(jié)構(gòu)更加清晰，而且要盡量避免一些不必要問(wèn)題的煩惱，可以假設(shè)要編譯的類(lèi)高級(jí)語(yǔ)言

55、當(dāng)中，所有的關(guān)鍵字都算作是系統(tǒng)的保留字，開(kāi)發(fā)人員不得將它們作為源程序中的標(biāo)識(shí)符；在要分析的源程序的輸入文本當(dāng)中，標(biāo)識(shí)符、關(guān)鍵字以及整常數(shù)之間，如果沒(méi)有出現(xiàn)關(guān)系運(yùn)算符、算術(shù)運(yùn)算符以及賦值符號(hào)，那么程序至少需要使用一個(gè)空白的字符來(lái)加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標(biāo)識(shí)符的識(shí)別統(tǒng)一進(jìn)行處理。每當(dāng)程序開(kāi)始識(shí)別一個(gè)單詞的時(shí)候，如果掃視到的第一個(gè)字符是字母的話(huà)，就會(huì)把后續(xù)輸入的字母或者數(shù)字字符按順序進(jìn)行一一拼接，直到程序掃視到不是字母或者

56、數(shù)字字符為止，以期望可以得到一個(gè)盡可能長(zhǎng)的字母字符串或者數(shù)字字符串，然后程序再用這個(gè)字符串來(lái)查詢(xún)</p><p>　　第三步，將表5.1里面的單詞集中的整常數(shù)全部改為無(wú)符號(hào)常數(shù)，本程序把無(wú)符號(hào)常數(shù)的單詞分類(lèi)碼助記符記為UCON；其值為無(wú)符號(hào)常數(shù)的機(jī)內(nèi)二進(jìn)制表示。</p><p>　　描述無(wú)符號(hào)數(shù)的BNF定義和狀態(tài)轉(zhuǎn)換圖：</p><p>　　無(wú)符號(hào)數(shù)的文法G如下：&

57、lt;/p><p>　　〈無(wú)符號(hào)數(shù)〉→ d〈余留無(wú)符號(hào)數(shù)〉</p><p>　　〈無(wú)符號(hào)數(shù)〉→ ·〈小數(shù)部分〉</p><p><b>　　〈無(wú)符號(hào)數(shù)〉→ d</b></p><p>　　〈余留無(wú)符號(hào)數(shù)〉→ d〈余留無(wú)符號(hào)數(shù)〉</p><p>　　〈余留無(wú)符號(hào)數(shù)〉→ ·〈十進(jìn)小數(shù)〉

58、</p><p>　　〈余留無(wú)符號(hào)數(shù)〉→ E〈指數(shù)部分〉</p><p>　　〈余留無(wú)符號(hào)數(shù)〉→ d</p><p>　　〈余留無(wú)符號(hào)數(shù)〉→ ·</p><p>　　〈十進(jìn)小數(shù)〉→ E〈指數(shù)部分〉</p><p>　　〈十進(jìn)小數(shù)〉→ d〈十進(jìn)小數(shù)〉</p><p><b>　

59、　〈十進(jìn)小數(shù)〉→ d</b></p><p>　　〈小數(shù)部分〉→ d〈十進(jìn)小數(shù)〉</p><p><b>　　〈小數(shù)部分〉→ d</b></p><p>　　〈指數(shù)部分〉→ d〈余留整指數(shù)〉</p><p>　　〈指數(shù)部分〉→ +〈整指數(shù)〉</p><p>　　〈指數(shù)部分〉→ -〈整指

60、數(shù)〉</p><p><b>　　〈指數(shù)部分〉→ d</b></p><p>　　〈整指數(shù)〉→ d〈余留整指數(shù)〉</p><p><b>　　〈整指數(shù)〉→ d</b></p><p>　　〈余留整指數(shù)〉→ d〈余留整指數(shù)〉</p><p>　　〈余留整指數(shù)〉→ d</p

61、><p>　　圖5.1所表示的就是上述文法的狀態(tài)轉(zhuǎn)換圖，下圖當(dāng)中編號(hào)0、1、2、3、4、5、6 分別代表了非終結(jié)符號(hào)中的<無(wú)符號(hào)數(shù)>、 <余留無(wú)符號(hào)數(shù)>、 <十進(jìn)小數(shù)>、 <小數(shù)部分>、<指數(shù)部分> 、<整指數(shù)> 以及<余留整指數(shù)>。</p><p>　　圖5.1 文法G【<無(wú)符號(hào)數(shù)>】的狀態(tài)轉(zhuǎn)化

62、圖</p><p>　　本程序用來(lái)實(shí)現(xiàn)無(wú)符號(hào)數(shù)識(shí)別的方法：在計(jì)算機(jī)系統(tǒng)內(nèi)部實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的常用方法方法之一就是把狀態(tài)圖當(dāng)中的各個(gè)狀態(tài)作為行，把有可能輸入的每一個(gè)輸入符號(hào)做為列，組成了一個(gè)狀態(tài)矩陣。在這個(gè)狀態(tài)矩陣當(dāng)中，矩陣內(nèi)的元素用來(lái)表示下一個(gè)狀態(tài)以及掃描器需要完成的語(yǔ)義動(dòng)作（例如字符的拼接、數(shù)制之間的轉(zhuǎn)換、填充的符號(hào)表和程序輸出的單詞在計(jì)算機(jī)內(nèi)部的表示方法等）。下表5.2里面的第一列表示各狀態(tài)Si的編號(hào)，表中的第

63、二列則分別列出了在每一種狀態(tài)下程序有可能掃視到的輸入符號(hào)aj，表中的第三列指出了當(dāng)（Si,aj）出現(xiàn)的時(shí)候程序應(yīng)該執(zhí)行的語(yǔ)義動(dòng)作，最后一欄的內(nèi)容用來(lái)指明下一個(gè)狀態(tài)的編號(hào)（假如其后是NULL或者是“結(jié)束”則表示沒(méi)有后繼狀態(tài)）。</p><p>　　表5.2 包含語(yǔ)義處理過(guò)程的識(shí)別無(wú)符號(hào)數(shù)的狀態(tài)矩陣</p><p>　　圖5.2和詞法分析程序中所出現(xiàn)的語(yǔ)義變量及語(yǔ)義函數(shù)的含義和功能說(shuō)明如下。

64、</p><p>　　函數(shù)GETCHAR：程序每調(diào)用一次該函數(shù)，就會(huì)把掃描指示器當(dāng)中的現(xiàn)在所指示的源程序中的字符傳送給字符變量ch，接著程序會(huì)把掃描指示器的位置前推一個(gè)字符位置。</p><p>　　字符數(shù)組TOKEN：用來(lái)依次存放一個(gè)單詞詞文中的各個(gè)字符。</p><p>　　函數(shù)CAT：程序每調(diào)用一次該函數(shù)，就會(huì)把當(dāng)前ch中存儲(chǔ)的字符拼接到TOKEN中所存儲(chǔ)的字

65、符串的右邊。</p><p>　　函數(shù)LOOKUP：程序每調(diào)用一次該函數(shù)，就會(huì)用TOKEN中存儲(chǔ)的字符串來(lái)查詢(xún)保留字表，如果查到存在，該函數(shù)就會(huì)將相對(duì)應(yīng)關(guān)鍵字的類(lèi)別碼賦值傳給整型變量c；如果沒(méi)有查到就將c置為零。</p><p>　　函數(shù)RETRACT：程序每調(diào)用一次該函數(shù)，就會(huì)把掃描指示器立刻回退一個(gè)字符的位置（就是退掉剛才多讀的那個(gè)字符）。</p><p>　　

66、函數(shù)OUT：程序一般只有在進(jìn)入終態(tài)的時(shí)候才會(huì)調(diào)用到這個(gè)函數(shù)，調(diào)用的形式一般是OUT(c，VAL)。在這里面，實(shí)參c作為相對(duì)應(yīng)的單詞的類(lèi)別碼或者是它的助記符。</p><p><b>　　圖5.2如下所示：</b></p><p>　　圖5.2 識(shí)別圖5.1所列語(yǔ)言中的部分單詞的DFA及相關(guān)的語(yǔ)義過(guò)程</p><p>　　該詞法分析程序編譯運(yùn)行結(jié)

67、果如圖5.3所示：</p><p>　　圖5.3 詞法分析程序運(yùn)行界面圖</p><p>　　輸入字符串begin x:=10;if x>5 then x:=2*x+6/2; end #;</p><p>　　其運(yùn)行結(jié)果如下圖5.4所示:</p><p>　　圖5.4 詞法分析程序測(cè)試結(jié)果一</p><p>　　

68、輸入字符串hello end#;</p><p>　　其運(yùn)行結(jié)果如下圖5.5所示:</p><p>　　圖5.5 詞法分析程序測(cè)試結(jié)果一</p><p>　　輸入字符串if x>5 ;y:=3; end #;</p><p>　　其運(yùn)行結(jié)果如下圖5.6所示:</p><p>　　圖5.6 詞法分析程序測(cè)試結(jié)果三&

69、lt;/p><p><b>　　源程序如下所示：</b></p><p>　　#include<stdio.h></p><p>　　#include<string.h></p><p>　　char prog[80],token[6];</p><p><b>　　

70、char ch;</b></p><p>　　int syn,p,m,n,sum;</p><p>　　char * rwtab[6]={"begin","if","then","while","do","end"}; //定義關(guān)鍵詞</p>

71、<p><b>　　main()</b></p><p><b>　　{</b></p><p><b>　　p=0;</b></p><p>　　printf("\n please intput string:");</p><p><b

72、>　　do</b></p><p><b>　　{</b></p><p>　　ch=getchar();</p><p>　　prog[p++]=ch;</p><p>　　}while(ch!='#');</p><p><b>　　p=0;<

73、/b></p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　scaner();</b></p><p>　　switch(syn)</p><p><b>　　{</b>

74、;</p><p>　　case 11:printf("(%d,%d)\n",syn,sum);break;</p><p>　　case -1:printf("input error\n"); break;</p><p>　　default:printf("(%d,%s)\n",syn,token);

75、</p><p><b>　　}</b></p><p>　　}while(syn!=0);</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p>　　/*詞法掃描程序：*/</p>

76、<p><b>　　scaner()</b></p><p><b>　　{</b></p><p>　　for(n=0;n<8;n++)</p><p>　　token[n]=NULL;</p><p><b>　　m=0;</b></p>&l

77、t;p>　　ch=prog[p++];</p><p>　　while(ch==' ')ch=prog[p++];</p><p>　　if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A'))</p><

78、;p><b>　　{</b></p><p>　　while((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0'))</p>&l

79、t;p><b>　　{</b></p><p>　　token[m++]=ch;</p><p>　　ch=prog[p++];</p><p><b>　　}</b></p><p>　　token[m++]='\0';</p><p>　　ch=pr

80、og[--p];</p><p><b>　　syn=10;</b></p><p>　　for(n=0;n<6;n++)</p><p>　　if(strcmp(token,rwtab[n])==0)</p><p><b>　　{</b></p><p><b

81、>　　syn=n+1;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><

82、p>　　if((ch<='9'&&ch>='0'))</p><p><b>　　{</b></p><p><b>　　sum=0;</b></p><p>　　while((ch<='9'&&ch>='

83、0'))</p><p><b>　　{</b></p><p>　　sum=sum*10+ch-'0';</p><p>　　ch=prog[p++];</p><p><b>　　}</b></p><p>　　ch=prog[--p];</

84、p><p><b>　　syn=11;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　switch(ch)</p><p><b>　　{</b></p>

85、<p>　　case '<':m=0;token[m++]=ch;</p><p>　　ch=prog[p++];</p><p>　　if(ch=='>')</p><p><b>　　{</b></p><p><b>　　syn=21;</b&

86、gt;</p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(ch=='=')</p><p><b>　　{</b></p

87、><p><b>　　syn=22;</b></p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p&g

88、t;<p><b>　　syn=20;</b></p><p>　　ch=prog[--p];</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case '>':token[m++

89、]=ch;</p><p>　　ch=prog[p++];</p><p>　　if(ch=='=')</p><p><b>　　{</b></p><p><b>　　syn=24;</b></p><p>　　token[m++]=ch;</p&g

90、t;<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　syn=23;</b></p><p>　　ch=prog[--p];</p>

91、<p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case ':':token[m++]=ch;</p><p>　　ch=prog[p++];</p><p>　　if(ch=='=')</p&g

92、t;<p><b>　　{</b></p><p><b>　　syn=18;</b></p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p>

93、<p><b>　　{</b></p><p><b>　　syn=17;</b></p><p>　　ch=prog[--p];</p><p><b>　　}</b></p><p><b>　　break;</b></p>

94、<p>　　case '+':syn=13;token[0]=ch;break; //判斷符號(hào)“+”。</p><p>　　case '-':syn=14;token[0]=ch;break; //判斷符號(hào)“-”。</p><p>　　case '*':syn=15;token[0]=ch;break; //判斷

95、符號(hào)“*”。</p><p>　　case '/':syn=16;token[0]=ch;break; //判斷符號(hào)“/”。</p><p>　　case ':=':syn=18;token[0]=ch;break; //判斷符號(hào)“:=”。</p><p>　　case '<>':syn=21;t

96、oken[0]=ch;break; //判斷符號(hào)“<>”。</p><p>　　case '<=':syn=22;token[0]=ch;break; //判斷符號(hào)“<=”。</p><p>　　case '>=':syn=24;token[0]=ch;break; //判斷符號(hào)“>=”。</p>

97、<p>　　case '=':syn=25;token[0]=ch;break; //判斷符號(hào)“=”。</p><p>　　case ';':syn=26;token[0]=ch;break; //判斷符號(hào)“;”。</p><p>　　case '(':syn=27;token[0]=ch;break; //

98、判斷符號(hào)“(”。</p><p>　　case ')':syn=28;token[0]=ch;break; //判斷符號(hào)“)”。</p><p>　　case '#':syn=0;token[0]=ch;break; //判斷符號(hào)“#”。</p><p>　　default:syn=-1;</p>&l

99、t;p><b>　　}</b></p><p><b>　　}</b></p><p>　　5.2 語(yǔ)法分析器的設(shè)計(jì)和實(shí)現(xiàn)</p><p>　　通過(guò)設(shè)計(jì)和開(kāi)發(fā)一個(gè)典型的語(yǔ)法分析程序,使學(xué)生能夠?qū)崿F(xiàn)并且進(jìn)一步掌握日常教學(xué)中常常涉及的語(yǔ)法分析方法。本程序把下圖文法G1所定義的算術(shù)表達(dá)式的賦值語(yǔ)句作為分析對(duì)象，對(duì)輸入語(yǔ)

100、句的語(yǔ)法進(jìn)行分析。</p><p>　　G1[<賦值語(yǔ)句>]：</p><p>　　<賦值語(yǔ)句> → <變量>:=<算術(shù)表達(dá)式></p><p>　　<算術(shù)表達(dá)式> → <項(xiàng)> | <算術(shù)表達(dá)式>+<項(xiàng)> | <算術(shù)表達(dá)式>-<項(xiàng)></p&g

101、t;<p>　　<項(xiàng)> → <因式> | <項(xiàng)>*<因式> | <項(xiàng)>/<因式></p><p>　　<因式> → <變量> | <常數(shù)> | (<算術(shù)表達(dá)式>)</p><p>　　<變量> → <標(biāo)識(shí)符></p>&

102、lt;p>　　<標(biāo)識(shí)符> → <標(biāo)識(shí)符> <字母> | <標(biāo)識(shí)符> <數(shù)字> | <字母></p><p>　　<常數(shù)> → <整數(shù)> | <浮點(diǎn)數(shù)></p><p>　　<整數(shù)> → <數(shù)字> | <數(shù)字> <整數(shù)></p

103、><p>　　<浮點(diǎn)數(shù)> → ? <整數(shù)> | <整數(shù)> ? <整數(shù)></p><p>　　<字母> → A|B|C|…|X|Y|Z|a|b|c|…|x|y|z</p><p>　　<數(shù)字> → 0|1|2|…9</p><p>　　該語(yǔ)法分析程序編譯運(yùn)行結(jié)果如圖5.7所示：

104、</p><p>　　圖5.7 語(yǔ)法分析程序運(yùn)行結(jié)果界面</p><p>　　輸入字符串begin x:=3*y end #;</p><p>　　其運(yùn)行結(jié)果如下圖5.8所示:</p><p>　　圖5.8 語(yǔ)法分析程序測(cè)試結(jié)果一</p><p>　　輸入字符串x:=3*5 end #;</p><

105、p>　　其運(yùn)行結(jié)果如下圖5.9所示:</p><p>　　圖5.9 語(yǔ)法分析程序測(cè)試結(jié)果二</p><p>　　輸入字符串begin x:=2*3(3+4 end #;</p><p>　　其運(yùn)行結(jié)果如下圖5.10所示:</p><p>　　圖5.10 語(yǔ)法分析程序測(cè)試結(jié)果三</p><p><b>　

106、　源程序如下所示：</b></p><p>　　#include<iostream></p><p>　　using namespace std;</p><p>　　#include<stdio.h></p><p>　　#include<string.h></p><p&

107、gt;　　#define MAX 150 //詞法分析表的最大容量</p><p>　　#define MAXBUF 255 //緩沖區(qū)的最大緩沖量</p><p>　　void term();</p><p>　　void lrparser();</p><p>　　void statement();</p>

108、<p>　　void yucu();</p><p>　　void expression();</p><p>　　void factor();</p><p>　　char prog[MAXBUF],token[MAX];</p><p><b>　　char ch;</b></p><p

109、>　　int syn,p,m,n,sum,kk;</p><p>　　char * rwtab[6]={"begin","if","then","while","do","end"}; //定義關(guān)鍵詞</p><p>　　void scaner()

110、 //詞法掃描程序</p><p><b>　　{</b></p><p>　　for(m=0;m<MAX;m++)</p><p>　　token[m]=NULL;</p><p>　　m=0;sum=0;</p><p>　　

111、ch=prog[p++];</p><p>　　while(ch==' ')ch=prog[p++];</p><p>　　if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A'))</p><p><

112、;b>　　{</b></p><p>　　while((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0'))</p><p>&l

113、t;b>　　{</b></p><p>　　token[m++]=ch;</p><p>　　ch=prog[p++]; //讀取下一個(gè)字符</p><p><b>　　}</b></p><p>　　token[m++]='\0';</p&g

114、t;<p>　　ch=prog[--p];</p><p><b>　　syn=10;</b></p><p>　　for(n=0;n<6;n++)</p><p>　　if(strcmp(token,rwtab[n])==0)</p><p><b>　　{</b></p

115、><p>　　syn=n+1; //給出syn值</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　

116、else</b></p><p>　　if((ch<='9'&&ch>='0'))</p><p><b>　　{</b></p><p><b>　　sum=0;</b></p><p>　　while((ch<=

117、9;9'&&ch>='0'))</p><p><b>　　{</b></p><p>　　sum=sum*10+ch-'0';</p><p>　　ch=prog[p++];</p><p><b>　　}</b></p>

118、<p>　　ch=prog[--p];</p><p><b>　　syn=11;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　switch(ch)</p><p><

119、;b>　　{</b></p><p>　　case '<':m=0;token[m++]=ch;</p><p>　　ch=prog[p++];</p><p>　　if(ch=='>')</p><p><b>　　{</b></p><

120、p><b>　　syn=21;</b></p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(ch=='=')</p><p&g

121、t;<b>　　{</b></p><p><b>　　syn=22;</b></p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>

122、<b>　　{</b></p><p><b>　　syn=20;</b></p><p>　　ch=prog[--p];</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　

123、　case '>':token[m++]=ch;</p><p>　　ch=prog[p++];</p><p>　　if(ch=='=')</p><p><b>　　{</b></p><p><b>　　syn=24;</b></p><

124、;p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　syn=23;</b></p><p

125、>　　ch=prog[--p];</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case ':':token[m++]=ch;</p><p>　　ch=prog[p++];</p><p>

126、;　　if(ch=='=')</p><p><b>　　{</b></p><p><b>　　syn=18;</b></p><p>　　token[m++]=ch;</p><p><b>　　}</b></p><p><b

127、>　　else</b></p><p><b>　　{</b></p><p><b>　　syn=17;</b></p><p>　　ch=prog[--p];</p><p><b>　　}</b></p><p><b>

128、;　　break;</b></p><p>　　case '+':syn=13;token[0]=ch;break; //判斷符號(hào)“+”。</p><p>　　case '-':syn=14;token[0]=ch;break; //判斷符號(hào)“-”。</p><p>　　case '