【正文】 C語言編譯器設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)論文目　　錄摘　要 iAbstract ii第一章 緒論 1 開發(fā)背景 1 開發(fā)目標(biāo)和意義 1 當(dāng)前編譯器國內(nèi)外的發(fā)展情況 2第二章 理論基礎(chǔ) 4 編譯系統(tǒng)概述 4 什么是編譯器 4 編譯器的產(chǎn)生 4 編譯器的結(jié)構(gòu) 4 編譯器的組織 6 編譯的分遍 6 分遍的設(shè)計(jì) 6 編譯器中的主要數(shù)據(jù)結(jié)構(gòu) 7 編譯程序的開發(fā) 7 歷史與發(fā)展 7 開發(fā)注意事項(xiàng) 7 編譯技術(shù)和軟件工具 7第三章 C編譯器可行性分析及總體設(shè)計(jì) 9 可行性分析 9 經(jīng)濟(jì)可行性 9 技術(shù)可行性 9 運(yùn)行可行性 9 時(shí)間可行性 10 法律可行性 10 C語言的基本描述 10 C編譯器的功能 10 C編譯器的程序結(jié)構(gòu) 11 C編譯器的設(shè)計(jì)模式 11 C編譯器的文件組成 12 C編譯器中的主要數(shù)據(jù)結(jié)構(gòu) 12第四章 C編譯器的實(shí)現(xiàn) 14 詞法分析階段 14 概述 14 C詞法分析程序的實(shí)現(xiàn) 14 關(guān)鍵字與標(biāo)識(shí)符的識(shí)別 16 詞法識(shí)別具體實(shí)現(xiàn) 16 語法分析階段 18 概述 18 C語言抽象出來的文法規(guī)則 19 C語法分析程序的實(shí)現(xiàn) 22 語義分析階段 27 概述 27 C語言的語義 27 C的符號(hào)表 27 C語義分析程序的實(shí)現(xiàn) 28 中間代碼生成階段 33 概述 33 C編譯器的使用方法及測(cè)試 33 使用方法 33 測(cè)試源文件 34 測(cè)試詞法分析 34 測(cè)試語義分析及中間代碼生成 35 測(cè)試分析表文件的構(gòu)造 36參考文獻(xiàn) 38致謝 39 第一章 緒論 開發(fā)背景隨著計(jì)算機(jī)科學(xué)技術(shù)的飛速發(fā)展，計(jì)算機(jī)技術(shù)被應(yīng)用在了越來越廣泛的領(lǐng)域，實(shí)現(xiàn)各種各樣功能的計(jì)算機(jī)程序被大量地開發(fā)出來，應(yīng)用在我們的生活、學(xué)習(xí)和工作當(dāng)中。相應(yīng)地，也產(chǎn)生了許多用以編寫這些計(jì)算機(jī)程序的高級(jí)程序設(shè)計(jì)語言。程序編制者通過特定語言的編譯器將自己編寫的源程序翻譯為特定機(jī)器上的目標(biāo)程序，從而能夠最終達(dá)到程序執(zhí)行的目的。從20世紀(jì)60年代以來，編譯器設(shè)計(jì)就一直是計(jì)算機(jī)研究發(fā)展和開發(fā)領(lǐng)域中的一個(gè)活躍主題。雖然編譯器設(shè)計(jì)已有很長的歷史，并且也是一門相對(duì)成熟的計(jì)算機(jī)技術(shù)，但編譯器畢竟是一種實(shí)現(xiàn)由高級(jí)語言源程序至機(jī)器或匯編指令的高效映射工具，隨著計(jì)算機(jī)軟、硬件水平的飛速發(fā)展，使得計(jì)算機(jī)應(yīng)用日新月異，程序語言的設(shè)計(jì)在不斷地變化，目標(biāo)機(jī)體系結(jié)構(gòu)也在不斷地改進(jìn)，軟件越來越復(fù)雜，其規(guī)模也越來越大。盡管編譯器設(shè)計(jì)問題在高級(jí)層次上沒有變化（或變化很?。?dāng)我們深入其內(nèi)部研究時(shí)就會(huì)發(fā)現(xiàn)，編譯器的內(nèi)部構(gòu)造其實(shí)也一直在變化。此外，由于我們能夠提供給編譯器本身使用的計(jì)算資源也在不斷增加。因此，現(xiàn)代編譯器可以采用比以前更耗費(fèi)時(shí)間和空間的算法。當(dāng)然，編譯技術(shù)研究人員也在繼續(xù)努力開發(fā)新的、更好的技術(shù)來解決傳統(tǒng)編譯器的一些設(shè)計(jì)性問題[1]。另一方面，很多編譯“前端”技術(shù)，如文法、正則表達(dá)式、語法分析器以及語法制導(dǎo)翻譯器等，仍然被廣泛使用。 開發(fā)目標(biāo)和意義編譯器是一種相當(dāng)復(fù)雜的系統(tǒng)程序，其代碼的長度可從幾千行到幾百萬行不等，所以編寫甚至讀懂這樣的一個(gè)程序都不是一件容易的事。絕大多數(shù)的計(jì)算機(jī)專業(yè)人員從來沒有編寫過一個(gè)完整的編譯器，但是，幾乎所有形式的計(jì)算均要用到編譯器，而且任何一個(gè)與計(jì)算機(jī)打交道的專業(yè)人員都應(yīng)該掌握編譯器的基本結(jié)構(gòu)和操作。除此之外，計(jì)算機(jī)應(yīng)用程序中經(jīng)常遇到的一個(gè)任務(wù)就是有關(guān)命令解釋程序和界面程序的開發(fā)，這比編譯器的開發(fā)規(guī)模要小，但使用的卻是很類似的技術(shù)。因此，掌握編譯器的開發(fā)技術(shù)具有非常重大的實(shí)際意義。編譯器的設(shè)計(jì)的原理和技術(shù)還可以用于編譯器設(shè)計(jì)之外的眾多領(lǐng)域。因此，這些原理和技術(shù)通常會(huì)在一個(gè)計(jì)算機(jī)科學(xué)家的職業(yè)生涯中多次被用到。研究編譯器的編寫講設(shè)計(jì)程序設(shè)計(jì)語言、計(jì)算機(jī)體系結(jié)構(gòu)、形式語言理論、算法和軟件工程。編譯器的設(shè)計(jì)從本質(zhì)上來說是一種工程活動(dòng)，它所使用的方法必須很好地解決現(xiàn)實(shí)中出現(xiàn)的各種翻譯問題（即用真實(shí)的語言編制且在真實(shí)的機(jī)器上能夠執(zhí)行的真實(shí)的程序）。大多數(shù)情況下，開發(fā)編譯器的人必須接受他們面對(duì)的語言和機(jī)器，很少能夠去影響或改善這兩者的設(shè)計(jì)。在開發(fā)過程中做什么樣的分析和轉(zhuǎn)換，以及什么時(shí)候去做，這些都是工程上的選擇，但正是這些選擇決定了一個(gè)編譯器的性能高低。本實(shí)驗(yàn)就建立在一個(gè)自主開發(fā)的名為C的微型編譯器基礎(chǔ)之上，該編譯器雖然功能弱于像Turbo C或Borland Pascal這樣的經(jīng)典編譯器，但也已經(jīng)完全具備了一個(gè)編譯器應(yīng)有的所有特征。雖然本實(shí)驗(yàn)只是一個(gè)規(guī)模很小的微型編譯器的開發(fā)，但所謂“麻雀雖小，五臟俱全”，作為一次較為完整的編譯開發(fā)實(shí)踐，它已經(jīng)足夠讓我透徹地了解一個(gè)編譯器開發(fā)過程了，同時(shí)能更深刻地理解和運(yùn)用編譯開發(fā)過程中的眾多技術(shù)和方法，并能在此基礎(chǔ)上針對(duì)編譯器的優(yōu)化展開深入的討論，這些對(duì)于自己以后的研究和發(fā)展方向?qū)⑵鸬椒浅４蟮耐苿?dòng)作用。C編譯器以C++語言作為開發(fā)語言，以Microsoft Visual Studio2012作為開發(fā)工具，C編譯器的各個(gè)階段以類的形式表示，最后以項(xiàng)目文件為單位來編譯生成C編譯器的可執(zhí)行文件。本實(shí)驗(yàn)以Microsoft Visual Studio2012作為開發(fā)工具，用標(biāo)準(zhǔn)C++進(jìn)行開發(fā)，因此可以很好的的移植到其他平臺(tái)（比如：linux，用g++編譯生成可執(zhí)行文件）。 當(dāng)前編譯器國內(nèi)外的發(fā)展情況在編譯器技術(shù)的發(fā)展過程中，如何提高編譯的效率一直是核心研究目標(biāo)之一，編譯效率主要是根據(jù)該編譯器所生成的目標(biāo)代碼在執(zhí)行過程中的時(shí)間指標(biāo)和空間指標(biāo)來衡量的，所以編譯優(yōu)化也必定圍繞時(shí)間和空間這兩個(gè)方面來實(shí)施。在編譯過程中針對(duì)代碼優(yōu)化的技術(shù)有很多，它們通常是通過搜集源代碼或中間代碼的特定信息，然后利用這些信息對(duì)代碼中的數(shù)據(jù)結(jié)構(gòu)或算法操作實(shí)施等價(jià)的改進(jìn)變換，從而力求在時(shí)間效率和空間效率上達(dá)到一個(gè)最佳平衡點(diǎn)。編譯器的開發(fā)者們總是希望能夠?qū)⒏鞣N代碼優(yōu)化技術(shù)充分地運(yùn)用在自己的編譯器設(shè)計(jì)中，但往往事與愿違，畢竟優(yōu)化操作本身也是需要付出開銷的。在C編譯器的開發(fā)過程中，雖然沒有運(yùn)用到太復(fù)雜的代碼優(yōu)化技術(shù)，但通過本實(shí)驗(yàn)的研究，在現(xiàn)有開發(fā)的C編譯器基礎(chǔ)之上，能夠在后續(xù)相關(guān)項(xiàng)目的開發(fā)中有效地提高程序代碼的編譯質(zhì)量，對(duì)于自己以后的研究和發(fā)展方向?qū)⑵鸬椒浅４蟮耐苿?dòng)作用。這正是本實(shí)驗(yàn)的研究意義所在。本實(shí)驗(yàn)是以C微型編譯器的項(xiàng)目開發(fā)為基礎(chǔ)，該項(xiàng)目的開發(fā)目標(biāo)是自定義一種C高級(jí)語言，然后編碼實(shí)現(xiàn)出C語言的編譯器（稱為C編譯器），完成將C語言源程序翻譯為基于MM機(jī)（Mini Machine）的目標(biāo)代碼的任務(wù)，這是本實(shí)驗(yàn)的實(shí)際應(yīng)用背景。編譯器的開發(fā)具有極高的實(shí)用價(jià)值和意義，高級(jí)語言編譯器的性能決定了基于該語言平臺(tái)所開發(fā)出的軟件的質(zhì)量。所以國內(nèi)外很多大學(xué)的科研和技術(shù)人員也在積極地開展這方面的技術(shù)探索和項(xiàng)目實(shí)踐。他們大多是以特定的軟件項(xiàng)目為背景來進(jìn)行一些與編譯器開發(fā)相關(guān)或類似的研究分析，他們的研究目標(biāo)大多是基于某種實(shí)驗(yàn)型高級(jí)語言的編譯器開發(fā)和優(yōu)化改進(jìn)，然后把有價(jià)值的研究成果移植或運(yùn)用到產(chǎn)品級(jí)的編譯器開發(fā)中（）。最近十年以來，國外關(guān)于編譯器設(shè)計(jì)的發(fā)展動(dòng)態(tài)主要體現(xiàn)在：首先，編譯器采用了大量的更加復(fù)雜的算法，主要用于推斷或簡(jiǎn)化程序中的信息，這又與更為復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一起，其中典型的有用于函數(shù)語言編譯的HindleyMilner類型檢查的統(tǒng)一算法[2]。其次，編譯器已越來越成為基于窗口的可視化交互開發(fā)環(huán)境（Interactive Development Environment，IDE）的一部分，該環(huán)境還包括了智能編輯器、連接程序、調(diào)試程序以及項(xiàng)目管理程序等，已經(jīng)成為了事實(shí)上的編譯器行業(yè)標(biāo)準(zhǔn)。另一方面，盡管國內(nèi)外的專家學(xué)者們近年來在編譯原理領(lǐng)域進(jìn)行了大量的研究，但是基本的編譯器設(shè)計(jì)原理在近20年中都沒有多大的改變，它現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心環(huán)節(jié)之一。在九十年代，作為GNU項(xiàng)目或其它開放源代碼項(xiàng)目的一部分，許多免費(fèi)的編譯器或編譯器構(gòu)造工具被開發(fā)出來。這些工具可用來編譯數(shù)種程序設(shè)計(jì)語言的源程序（典型的就是GCC）。它們中的一些項(xiàng)目被認(rèn)為是高質(zhì)量的，而且對(duì)現(xiàn)代編譯理論感興趣的人都可以較容易地得到它們的免費(fèi)源代碼。典型的是在1999年，SGI公布了他們的一個(gè)工業(yè)化的并行優(yōu)化編譯器Pro64的源代碼，隨后被全世界多個(gè)編譯器研究小組用做研究平臺(tái)，并命名為Open64。Open64的設(shè)計(jì)結(jié)構(gòu)好，分析優(yōu)化全面，是編譯器高級(jí)研究的理想平臺(tái)。反觀國內(nèi)，現(xiàn)階段對(duì)于編譯技術(shù)的相關(guān)研究，基本上都是著眼于特定編譯器的特定部分來展開的，而本實(shí)驗(yàn)將研究和分析的重點(diǎn)主要集中于一個(gè)完整的微型編譯器的構(gòu)造的討論。44 北京郵電大學(xué)畢業(yè)設(shè)計(jì)第二章 理論基礎(chǔ) 編譯系統(tǒng)概述 什么是編譯器編譯器，是將便于人類編寫、閱讀、維護(hù)的計(jì)算機(jī)高級(jí)語言程序翻譯為機(jī)器能夠識(shí)別、運(yùn)行的計(jì)算機(jī)低級(jí)語言程序的一種系統(tǒng)軟件。編譯器將源程序（Source Program）作為輸入，翻譯產(chǎn)生使用目標(biāo)語言的等價(jià)目標(biāo)程序（（Target Program）。其中，源程序一般為高級(jí)語言（Highlevel language），如Pascal，C++等，而目標(biāo)語言則是匯編語言或目標(biāo)機(jī)器的機(jī)器語言[3]。編譯器的這一作用如圖21所示：圖21 編譯器的作用 編譯器的產(chǎn)生本世紀(jì)四十年代，由于馮諾依曼在存儲(chǔ)程序計(jì)算機(jī)方面的先鋒作用，使得編寫一串代碼或程序已成為可能和必要，這樣計(jì)算機(jī)就可以執(zhí)行所需的計(jì)算。在初期，這些程序都是用機(jī)器語言編寫，編寫或維護(hù)這樣的代碼是非?？菰锓ξ肚倚实拖碌?，所以機(jī)器語言很快就被匯編語言代替了。匯編語言大大提高了程序編寫速度和準(zhǔn)確度，但它也有許多缺點(diǎn)。于是發(fā)展編程技術(shù)的下一個(gè)重要革新就是以一個(gè)更加類似于數(shù)學(xué)定義或自然語言的簡(jiǎn)潔形式來編寫程序的功能操作，它應(yīng)與任何機(jī)器都無關(guān)，而且也可由一個(gè)程序翻譯為可執(zhí)行的代碼。隨著對(duì)形式語言和自動(dòng)機(jī)理論的研究，人們對(duì)高級(jí)程序設(shè)計(jì)語言的認(rèn)識(shí)越來越深，對(duì)編譯器結(jié)構(gòu)的設(shè)計(jì)也越來越清晰。人們通過對(duì)形式語言文法規(guī)則的研究，相當(dāng)完善地解決了分析問題。當(dāng)分析問題變得相對(duì)成熟時(shí)，設(shè)計(jì)者們又花費(fèi)了很多的精力來研究這一部分的編譯器的自動(dòng)構(gòu)造，這就是分析程序生成器（parser generator）最初的雛形。類似地，對(duì)有窮自動(dòng)機(jī)的研究也促進(jìn)了一種稱為掃描程序生成器（scanner generator）工具的發(fā)展。接著，人們又深化了生成有效目標(biāo)代碼的方法，這些就構(gòu)成了傳統(tǒng)的編譯器，在這個(gè)過程中運(yùn)用到的技術(shù)被一直使用至今。 編譯器的結(jié)構(gòu)嚴(yán)格地說，編譯器是一個(gè)將高級(jí)語言源程序轉(zhuǎn)換成能在一臺(tái)計(jì)算機(jī)上執(zhí)行的等價(jià)目標(biāo)代碼或機(jī)器語言程序的軟件系統(tǒng)。這個(gè)定義可擴(kuò)展到包含將一個(gè)高級(jí)語言程序轉(zhuǎn)換成匯編語言程序的系統(tǒng)，將一個(gè)高級(jí)語言程序轉(zhuǎn)換成另一種高級(jí)語言程序的系統(tǒng)，從一個(gè)機(jī)器語言程序轉(zhuǎn)換成另一種機(jī)器語言程序的系統(tǒng)，從一種高級(jí)語言程序轉(zhuǎn)換成一種中間語言程序的系統(tǒng)，等等。在通常情況下，一個(gè)編譯器應(yīng)由一系列的階段組成，這些階段從要編譯的源程序的字符序列開始，依次對(duì)一個(gè)給定形式的程序進(jìn)行分析，并得到一種新的表示形式，在大多數(shù)情況下最終產(chǎn)生一個(gè)可以與其他目標(biāo)代碼鏈接，并裝入一臺(tái)機(jī)器的存儲(chǔ)器中執(zhí)行的可重定位目標(biāo)模塊。這一編譯過程一般由如下6個(gè)階段構(gòu)成，它們執(zhí)行不同的邏輯操作如圖22所示[4]： （1） 掃描程序（scanner）在這個(gè)階段，編譯器閱讀源程序（通常以字符流的形式表示，），由掃描程序執(zhí)行詞法分析（lexical analysis）：它將字符序列收集到稱為記號(hào)（token）的單元中，也就是說，將其識(shí)別為一個(gè)個(gè)符合編程語言詞法規(guī)范的單詞符號(hào)。實(shí)際上，一個(gè)掃描程序所做的工作與自然語言中對(duì)英文單詞的拼寫是十分類似的。掃描程序還可完成與識(shí)別記號(hào)一起執(zhí)行的其他操作，例如，可將相應(yīng)的記號(hào)輸入到對(duì)應(yīng)的符號(hào)表中。（2） 語法分析程序（parser）語法分析程序從掃描程序中獲取記號(hào)形式的代碼，并完成定義程序結(jié)構(gòu)的語法分析（syntax analysis），根據(jù)語言的語法規(guī)則將上階段產(chǎn)生的單詞串分解成各類語法單位（如表達(dá)式、語句、子過程等），這與自然語言中關(guān)于某篇文章的句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將語法分析的結(jié)果表示為分析樹或語法樹。（3） 語義分析程序（semantic analyzer）程序的語義就是它的“意思”，程序如何運(yùn)行以及運(yùn)行結(jié)果都由它的語義來決定。大多數(shù)程序設(shè)計(jì)語言具有在執(zhí)行之前被確定語義的特征，這些特征不容易用語法結(jié)構(gòu)表示，更無法用詞法分析程序進(jìn)行分析，這些特征被稱為靜態(tài)語義。語義分析程序的職責(zé)就是分析這樣的語義，為代碼生成階段搜集相關(guān)的語義信息。一般程序設(shè)計(jì)語言的典型靜態(tài)語義有聲明和類型檢查。而在程序執(zhí)行階段才能確定的程序特性稱為動(dòng)態(tài)語義，語義分析程序無法對(duì)這類特性做出分析。語義分析程序還要計(jì)算被稱為屬性（attribute）的程序固有信息，如數(shù)據(jù)類型、值等。語義分析程序通常將計(jì)算后的屬性值添加到語法樹中（也可將屬性添加到符號(hào)表中）。（4） 源代碼優(yōu)化程序（source code optimizer）完善的編譯器通常包括許多代碼改進(jìn)和優(yōu)化步驟。這些優(yōu)化和改進(jìn)一般是在語義分析之后完成的。在語法分析和語義分析的基礎(chǔ)之上，將源程序變換為等價(jià)的中間代碼。所謂中間代碼，是指一種結(jié)構(gòu)簡(jiǎn)單、含義明確、形式多樣化的記號(hào)系統(tǒng)，它比較容易能轉(zhuǎn)換為目標(biāo)代碼。優(yōu)化程序?qū)⒃创a以中間代碼（intermediate code）的形式輸出，進(jìn)而完成對(duì)源代碼的相應(yīng)優(yōu)化處理，目的是使將來生成的目標(biāo)代碼更為高效（即省時(shí)間、省空間）。（5） 代碼生成器（code generator）這是編譯的最后必備階段，它將中間代碼（或經(jīng)優(yōu)化后的中間代碼）轉(zhuǎn)換成特定機(jī)器上的絕對(duì)指令代碼或可重新定位的指令代碼或匯編指令代碼。由于該階段的工作與硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義有關(guān)，涉及到硬件系統(tǒng)功能部