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