C語言編譯器設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)論文設(shè)計(jì)

北京郵電大學(xué)畢業(yè)設(shè)計(jì)（論文）任務(wù)書第1頁畢業(yè)設(shè)計(jì)（論文）題目：C語言編譯器設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)（論文）要求及原始數(shù)據(jù)（資料）：1．C語言簡介和國內(nèi)外編譯器技術(shù)研究現(xiàn)狀；2．深入了解編譯器前端,包括詞法分析,語法分析,語義分析；3．熟練掌握C語言語法及語法特點(diǎn)；4．深入分析編譯器編寫語言（C++）；5．設(shè)計(jì)并實(shí)現(xiàn)編譯過程中各個(gè)子過程，詞法分析，語法分析，語義分析；6．訓(xùn)練檢索文獻(xiàn)資料和利用文獻(xiàn)資料的能力；7．訓(xùn)練撰寫技術(shù)文檔與學(xué)位論文的能力。第2頁畢業(yè)設(shè)計(jì)（論文）主要內(nèi)容：1．C語言簡介和國內(nèi)外編譯器技術(shù)研究現(xiàn)狀；2．深入了解編譯器前端,包括詞法分析,語法分析,語義分析；3．熟練掌握C語言語法及語法特點(diǎn)；4．深入分析編譯器編寫語言（C++）；5．設(shè)計(jì)并實(shí)現(xiàn)編譯過程中各個(gè)子過程，詞法分析，語法分析，語義分析；6．訓(xùn)練檢索文獻(xiàn)資料和利用文獻(xiàn)資料的能力；7．訓(xùn)練撰寫技術(shù)文檔與學(xué)位論文的能力。學(xué)生應(yīng)交出的設(shè)計(jì)文件（論文）：1．內(nèi)容完整、層次清晰、敘述流暢、排版規(guī)范的畢業(yè)設(shè)計(jì)論文；2．包括畢業(yè)設(shè)計(jì)論文、源程序等內(nèi)容在內(nèi)的畢業(yè)設(shè)計(jì)電子文檔及其它相關(guān)材料。第3頁主要參考文獻(xiàn)（資料）：KennethA．Reek.C和指針.人民郵電出版社,2008BrianW.Kernighan,DennisM.Richie.TheCProgramLanguage.,2004RichardStevens.UNIX環(huán)境高級編程.人民郵電出版社,2006布萊恩特，奧哈拉倫.深入理解計(jì)算機(jī)系統(tǒng).機(jī)械工業(yè)出版社，2011StanleyB.Lippman等.C++Primer.人民郵電出版社,2008AlfredV.Aho等.編譯原理技術(shù)和工具.機(jī)械工業(yè)出版社，2003AndrewW.Appel等.現(xiàn)代編譯原理-C語義描述.人民郵電出版社.2006StevenS.Muchnick.高級編譯器設(shè)計(jì)與實(shí)現(xiàn).機(jī)械工業(yè)出版社.2005嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).2012高一凡.面向?qū)ο蟮腃++數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社.2011ThomasH.Cormen,IntroductiontoAlgorithmsm.2012Portland.Lex&yaccTutorial.2013ChrisFrase,DavidHansonARetargetable.CCompiler:DesignandImplementation.2005專業(yè)班級軟件1008班學(xué)生郝靖宇要求設(shè)計(jì)（論文）工作起止日期2014年3月17日~2014年6月27日指導(dǎo)教師簽字日期2014年3月17日教研室主任審查簽字日期系主任批準(zhǔn)簽字日期C語言編譯器設(shè)計(jì)與實(shí)現(xiàn)摘要隨著計(jì)算機(jī)的廣泛應(yīng)用，計(jì)算機(jī)程序設(shè)計(jì)語言也從初期的機(jī)器語言發(fā)展為匯編語言，以及現(xiàn)在的各種高級程序設(shè)計(jì)語言。而編譯技術(shù)是計(jì)算機(jī)語言發(fā)展的支柱，也是計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)分支，他集中體現(xiàn)了計(jì)算機(jī)發(fā)展的成果與精華。其核心思想就是把同樣的邏輯結(jié)構(gòu)和思想從一種語言表示的程序轉(zhuǎn)換為另外一種語言表示的程序。從高級語言，甚至運(yùn)行與虛擬平臺的高級語言，到機(jī)器語言，最終到硬件執(zhí)行的物理信號，這一層層的轉(zhuǎn)化，都涉及編譯技術(shù)的應(yīng)用。本系統(tǒng)采用C++為編程語言。論文主要介紹了本課題的開發(fā)背景，所要完成的功能和開發(fā)的過程。重點(diǎn)的說明了系統(tǒng)設(shè)計(jì)的重點(diǎn)、設(shè)計(jì)思想、難點(diǎn)技術(shù)和解決方案。關(guān)鍵詞：編譯技術(shù)，編程程序，高級語言ClanguagecompilerdesignandImplementationAbstractWiththewideapplicationofthecomputer,computerprogramminglanguages??aredevelopedfromtheearlymachinelanguageintoassemblylanguage,andnowavarietyofhigh-levelprogramminglanguage.Thecompilertechnologyisthebackboneofcomputerlanguagedevelopment,butalsothefastestgrowingincomputerscience,abranchofthemostmature,heepitomizestheessenceofthecomputerandthefruitsofdevelopment.Thecoreideaisthesamelogicalstructureoftheprogramandideasexpressedintheconversionfromonelanguagetoanotherlanguageprogramrepresented.Fromthehigh-levellanguage,andevenrunningwithhigh-levellanguagevirtualplatformtomachinelanguage,andultimatelytothehardwareimplementationofthephysicalsignal,thelayersoftransformationinvolvesapplicationofcompilertechnology.SystemusesC++astheprogramminglanguage.Paperintroducesthedevelopmentbackgroundofthetopic,thedevelopmentandfunctiontocompletetheprocess.Notethefocusofsystemsdesign,designideas,technologiesandsolutionsdifficult.KeyWords:Compilertechnology，Programmingprocedures，High-levelprogramminglanguage目錄TOC\o"1-3"\h\u7355摘要 i2720Abstract ii1951第一章緒論 1151161.1開發(fā)背景 1261691.2開發(fā)目標(biāo)和意義 116071.2當(dāng)前編譯器國內(nèi)外的發(fā)展情況 211150第二章理論基礎(chǔ) 4114752.1編譯系統(tǒng)概述 444502.1.1什么是編譯器 4142182.1.2編譯器的產(chǎn)生 4252852.2編譯器的結(jié)構(gòu) 4318522.3編譯器的組織 6164122.3.1編譯的分遍 6233092.3.2分遍的設(shè)計(jì) 6205872.4編譯器中的主要數(shù)據(jù)結(jié)構(gòu) 7300022.5編譯程序的開發(fā) 7127742.5.1歷史與發(fā)展 734912.5.2開發(fā)注意事項(xiàng) 7194752.5.3編譯技術(shù)和軟件工具 717979第三章C編譯器可行性分析及總體設(shè)計(jì) 9307313.1可行性分析 9326943.1.1經(jīng)濟(jì)可行性 9224163.1.2技術(shù)可行性 9288923.1.3運(yùn)行可行性 9148753.1.4時(shí)間可行性 10306983.1.5法律可行性 1099953.2C語言的基本描述 101113.3C編譯器的功能 1078353.4C編譯器的程序結(jié)構(gòu) 11268773.4.1C編譯器的設(shè)計(jì)模式 11284993.4.2C編譯器的文件組成 12112603.5C編譯器中的主要數(shù)據(jù)結(jié)構(gòu) 127922第四章C編譯器的實(shí)現(xiàn) 14282754.1詞法分析階段 14238614.1.1概述 14137704.1.2C詞法分析程序的實(shí)現(xiàn) 14182864.1.3關(guān)鍵字與標(biāo)識符的識別 16252264.1.4詞法識別具體實(shí)現(xiàn) 16313744.2語法分析階段 18107904.2.1概述 18228824.2.2C語言抽象出來的文法規(guī)則 19253034.2.3C語法分析程序的實(shí)現(xiàn) 22198214.3語義分析階段 27213664.3.1概述 2781704.3.2C語言的語義 27202444.3.3C的符號表 27131754.3.4C語義分析程序的實(shí)現(xiàn) 28251794.4中間代碼生成階段 33277654.4.1概述 33186934.5C編譯器的使用方法及測試 33177084.5.1使用方法 33214764.5.2測試源文件 34133514.5.3測試詞法分析 34277284.5.4測試語義分析及中間代碼生成 35323644.5.5測試分析表文件的構(gòu)造 362049參考文獻(xiàn) 387291致謝 39第一章緒論1.1開發(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ì)語言。程序編制者通過特定語言的編譯器將自己編寫的源程序翻譯為特定機(jī)器上的目標(biāo)程序，從而能夠最終達(dá)到程序執(zhí)行的目的。從20世紀(jì)60年代以來，編譯器設(shè)計(jì)就一直是計(jì)算機(jī)研究發(fā)展和開發(fā)領(lǐng)域中的一個(gè)活躍主題。雖然編譯器設(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ī)模也越來越大。盡管編譯器設(shè)計(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)翻譯器等，仍然被廣泛使用。1.2開發(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ā)編譯器的人必須接受他們面對的語言和機(jī)器，很少能夠去影響或改善這兩者的設(shè)計(jì)。在開發(fā)過程中做什么樣的分析和轉(zhuǎn)換，以及什么時(shí)候去做，這些都是工程上的選擇，但正是這些選擇決定了一個(gè)編譯器的性能高低。本實(shí)驗(yàn)就建立在一個(gè)自主開發(fā)的名為C的微型編譯器基礎(chǔ)之上，該編譯器雖然功能弱于像TurboC或BorlandPascal這樣的經(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ǔ)上針對編譯器的優(yōu)化展開深入的討論，這些對于自己以后的研究和發(fā)展方向?qū)⑵鸬椒浅４蟮耐苿?dòng)作用。C編譯器以C++語言作為開發(fā)語言，以MicrosoftVisualStudio2012作為開發(fā)工具，C編譯器的各個(gè)階段以類的形式表示，最后以項(xiàng)目文件為單位來編譯生成C編譯器的可執(zhí)行文件。本實(shí)驗(yàn)以MicrosoftVisualStudio2012作為開發(fā)工具，用標(biāo)準(zhǔn)C++進(jìn)行開發(fā)，因此可以很好的的移植到其他平臺（比如：linux，用g++編譯生成可執(zhí)行文件）。1.2當(dāng)前編譯器國內(nèi)外的發(fā)展情況在編譯器技術(shù)的發(fā)展過程中，如何提高編譯的效率一直是核心研究目標(biāo)之一，編譯效率主要是根據(jù)該編譯器所生成的目標(biāo)代碼在執(zhí)行過程中的時(shí)間指標(biāo)和空間指標(biāo)來衡量的，所以編譯優(yōu)化也必定圍繞時(shí)間和空間這兩個(gè)方面來實(shí)施。在編譯過程中針對代碼優(yōu)化的技術(shù)有很多，它們通常是通過搜集源代碼或中間代碼的特定信息，然后利用這些信息對代碼中的數(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ì)量，對于自己以后的研究和發(fā)展方向?qū)⑵鸬椒浅４蟮耐苿?dòng)作用。這正是本實(shí)驗(yàn)的研究意義所在。本實(shí)驗(yàn)是以C微型編譯器的項(xiàng)目開發(fā)為基礎(chǔ)，該項(xiàng)目的開發(fā)目標(biāo)是自定義一種C高級語言，然后編碼實(shí)現(xiàn)出C語言的編譯器（稱為C編譯器），完成將C語言源程序翻譯為基于MM機(jī)（MiniMachine）的目標(biāo)代碼的任務(wù)，這是本實(shí)驗(yàn)的實(shí)際應(yīng)用背景。編譯器的開發(fā)具有極高的實(shí)用價(jià)值和意義，高級語言編譯器的性能決定了基于該語言平臺所開發(fā)出的軟件的質(zhì)量。所以國內(nèi)外很多大學(xué)的科研和技術(shù)人員也在積極地開展這方面的技術(shù)探索和項(xiàng)目實(shí)踐。他們大多是以特定的軟件項(xiàng)目為背景來進(jìn)行一些與編譯器開發(fā)相關(guān)或類似的研究分析，他們的研究目標(biāo)大多是基于某種實(shí)驗(yàn)型高級語言的編譯器開發(fā)和優(yōu)化改進(jìn)，然后把有價(jià)值的研究成果移植或運(yùn)用到產(chǎn)品級的編譯器開發(fā)中（比如.NET平臺編譯器）。最近十年以來，國外關(guān)于編譯器設(shè)計(jì)的發(fā)展動(dòng)態(tài)主要體現(xiàn)在：首先，編譯器采用了大量的更加復(fù)雜的算法，主要用于推斷或簡化程序中的信息，這又與更為復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一起，其中典型的有用于函數(shù)語言編譯的Hindley-Milner類型檢查的統(tǒng)一算法[2]。其次，編譯器已越來越成為基于窗口的可視化交互開發(fā)環(huán)境（InteractiveDevelopmentEnvironment，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ì)量的，而且對現(xiàn)代編譯理論感興趣的人都可以較容易地得到它們的免費(fèi)源代碼。典型的是在1999年，SGI公布了他們的一個(gè)工業(yè)化的并行優(yōu)化編譯器Pro64的源代碼，隨后被全世界多個(gè)編譯器研究小組用做研究平臺，并命名為Open64。Open64的設(shè)計(jì)結(jié)構(gòu)好，分析優(yōu)化全面，是編譯器高級研究的理想平臺。反觀國內(nèi)，現(xiàn)階段對于編譯技術(shù)的相關(guān)研究，基本上都是著眼于特定編譯器的特定部分來展開的，而本實(shí)驗(yàn)將研究和分析的重點(diǎn)主要集中于一個(gè)完整的微型編譯器的構(gòu)造的討論。第二章理論基礎(chǔ)2.1編譯系統(tǒng)概述2.1.1什么是編譯器編譯器，是將便于人類編寫、閱讀、維護(hù)的計(jì)算機(jī)高級語言程序翻譯為機(jī)器能夠識別、運(yùn)行的計(jì)算機(jī)低級語言程序的一種系統(tǒng)軟件。編譯器將源程序（SourceProgram）作為輸入，翻譯產(chǎn)生使用目標(biāo)語言的等價(jià)目標(biāo)程序（（TargetProgram）。其中，源程序一般為高級語言（High-levellanguage），如Pascal，C++等，而目標(biāo)語言則是匯編語言或目標(biāo)機(jī)器的機(jī)器語言[3]。編譯器的這一作用如圖2-1所示：圖2-1編譯器的作用2.1.2編譯器的產(chǎn)生本世紀(jì)四十年代，由于馮·諾依曼在存儲(chǔ)程序計(jì)算機(jī)方面的先鋒作用，使得編寫一串代碼或程序已成為可能和必要，這樣計(jì)算機(jī)就可以執(zhí)行所需的計(jì)算。在初期，這些程序都是用機(jī)器語言編寫，編寫或維護(hù)這樣的代碼是非常枯燥乏味且效率低下的，所以機(jī)器語言很快就被匯編語言代替了。匯編語言大大提高了程序編寫速度和準(zhǔn)確度，但它也有許多缺點(diǎn)。于是發(fā)展編程技術(shù)的下一個(gè)重要革新就是以一個(gè)更加類似于數(shù)學(xué)定義或自然語言的簡潔形式來編寫程序的功能操作，它應(yīng)與任何機(jī)器都無關(guān)，而且也可由一個(gè)程序翻譯為可執(zhí)行的代碼。隨著對形式語言和自動(dòng)機(jī)理論的研究，人們對高級程序設(shè)計(jì)語言的認(rèn)識越來越深，對編譯器結(jié)構(gòu)的設(shè)計(jì)也越來越清晰。人們通過對形式語言文法規(guī)則的研究，相當(dāng)完善地解決了分析問題。當(dāng)分析問題變得相對成熟時(shí)，設(shè)計(jì)者們又花費(fèi)了很多的精力來研究這一部分的編譯器的自動(dòng)構(gòu)造，這就是分析程序生成器（parsergenerator）最初的雛形。類似地，對有窮自動(dòng)機(jī)的研究也促進(jìn)了一種稱為掃描程序生成器（scannergenerator）工具的發(fā)展。接著，人們又深化了生成有效目標(biāo)代碼的方法，這些就構(gòu)成了傳統(tǒng)的編譯器，在這個(gè)過程中運(yùn)用到的技術(shù)被一直使用至今。2.2編譯器的結(jié)構(gòu)嚴(yán)格地說，編譯器是一個(gè)將高級語言源程序轉(zhuǎn)換成能在一臺計(jì)算機(jī)上執(zhí)行的等價(jià)目標(biāo)代碼或機(jī)器語言程序的軟件系統(tǒng)。這個(gè)定義可擴(kuò)展到包含將一個(gè)高級語言程序轉(zhuǎn)換成匯編語言程序的系統(tǒng)，將一個(gè)高級語言程序轉(zhuǎn)換成另一種高級語言程序的系統(tǒng)，從一個(gè)機(jī)器語言程序轉(zhuǎn)換成另一種機(jī)器語言程序的系統(tǒng)，從一種高級語言程序轉(zhuǎn)換成一種中間語言程序的系統(tǒng)，等等。在通常情況下，一個(gè)編譯器應(yīng)由一系列的階段組成，這些階段從要編譯的源程序的字符序列開始，依次對一個(gè)給定形式的程序進(jìn)行分析，并得到一種新的表示形式，在大多數(shù)情況下最終產(chǎn)生一個(gè)可以與其他目標(biāo)代碼鏈接，并裝入一臺機(jī)器的存儲(chǔ)器中執(zhí)行的可重定位目標(biāo)模塊。這一編譯過程一般由如下6個(gè)階段構(gòu)成，它們執(zhí)行不同的邏輯操作如圖2-2所示[4]：（1）掃描程序（scanner）在這個(gè)階段，編譯器閱讀源程序（通常以字符流的形式表示，比如本實(shí)驗(yàn)設(shè)計(jì)的C語言的源程序.c），由掃描程序執(zhí)行詞法分析（lexicalanalysis）：它將字符序列收集到稱為記號（token）的單元中，也就是說，將其識別為一個(gè)個(gè)符合編程語言詞法規(guī)范的單詞符號。實(shí)際上，一個(gè)掃描程序所做的工作與自然語言中對英文單詞的拼寫是十分類似的。掃描程序還可完成與識別記號一起執(zhí)行的其他操作，例如，可將相應(yīng)的記號輸入到對應(yīng)的符號表中。（2）語法分析程序（parser）語法分析程序從掃描程序中獲取記號形式的代碼，并完成定義程序結(jié)構(gòu)的語法分析（syntaxanalysis），根據(jù)語言的語法規(guī)則將上階段產(chǎn)生的單詞串分解成各類語法單位（如表達(dá)式、語句、子過程等），這與自然語言中關(guān)于某篇文章的句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將語法分析的結(jié)果表示為分析樹或語法樹。（3）語義分析程序（semanticanalyzer）程序的語義就是它的“意思”，程序如何運(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)語義，語義分析程序無法對這類特性做出分析。語義分析程序還要計(jì)算被稱為屬性（attribute）的程序固有信息，如數(shù)據(jù)類型、值等。語義分析程序通常將計(jì)算后的屬性值添加到語法樹中（也可將屬性添加到符號表中）。（4）源代碼優(yōu)化程序（sourcecodeoptimizer）完善的編譯器通常包括許多代碼改進(jìn)和優(yōu)化步驟。這些優(yōu)化和改進(jìn)一般是在語義分析之后完成的。在語法分析和語義分析的基礎(chǔ)之上，將源程序變換為等價(jià)的中間代碼。所謂中間代碼，是指一種結(jié)構(gòu)簡單、含義明確、形式多樣化的記號系統(tǒng)，它比較容易能轉(zhuǎn)換為目標(biāo)代碼。優(yōu)化程序?qū)⒃创a以中間代碼（intermediatecode）的形式輸出，進(jìn)而完成對源代碼的相應(yīng)優(yōu)化處理，目的是使將來生成的目標(biāo)代碼更為高效（即省時(shí)間、省空間）。（5）代碼生成器（codegenerator）這是編譯的最后必備階段，它將中間代碼（或經(jīng)優(yōu)化后的中間代碼）轉(zhuǎn)換成特定機(jī)器上的絕對指令代碼或可重新定位的指令代碼或匯編指令代碼。由于該階段的工作與硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義有關(guān)，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)的存儲(chǔ)空間分配以及寄存器調(diào)度等，也就是說目標(biāo)機(jī)器的特性成為了主要因素，所以這個(gè)階段的工作相當(dāng)復(fù)雜。正是出于這點(diǎn)考慮，本實(shí)驗(yàn)設(shè)計(jì)選擇了與機(jī)器指令無關(guān)的三地址碼的四元式表示形式。（6）目標(biāo)代碼優(yōu)化程序（targetcodeoptimizer）在這個(gè)階段中，編譯器嘗試著改進(jìn)由代碼生成器生成的目標(biāo)代碼。這種改進(jìn)包括對編址模式的選擇、提高性能、將速度慢的指令更換成速度快的以及刪除多余的操作等。除了這6個(gè)階段，編譯器通常還包含一張符號表和訪問該表的若干例程，以及針對編譯過程中發(fā)現(xiàn)的各種錯(cuò)誤進(jìn)行檢查和處理的錯(cuò)誤處理程序，它們在編譯過程的所有階段都會(huì)使用到。上述編譯過程的階段劃分只是一個(gè)典型模式，事實(shí)上并非所有的編譯程序都分成這6個(gè)階段，有些編譯程序并不生成中間代碼，有些編譯程序并不進(jìn)行優(yōu)化，有些最簡單的編譯程序甚至在語法分析的同時(shí)產(chǎn)生目標(biāo)代碼。編譯器生成的目標(biāo)代碼可以是可重定位目標(biāo)代碼或匯編代碼，如果是匯編代碼則需要再用匯編器來生成可重定位目標(biāo)代碼，本實(shí)驗(yàn)設(shè)計(jì)的C編譯器生成的目標(biāo)代碼是三地址碼的四元式表示形式。2.3編譯器的組織2.3.1編譯的分遍在2.2節(jié)中我們討論了一個(gè)編譯器的典型結(jié)構(gòu)，簡要介紹了編譯器的6個(gè)階段各自應(yīng)完成的基本工作，并通過圖2-2指出了它們之間的相互關(guān)系，但需要注意的是，這些關(guān)系僅代表它們之間的邏輯關(guān)系，并不一定就是執(zhí)行時(shí)間上的先后順序。事實(shí)上，可按不同的執(zhí)行流程來組織上述各階段的工作，這在很大程度上依賴于編譯過程中對源程序掃描的遍數(shù)，以及如何劃分各遍掃描所進(jìn)行的工作。這里所說的“遍”，是指對源程序或其內(nèi)部表示從頭到尾掃視一次，并進(jìn)行有關(guān)的加工處理工作，每一遍的工作都是從獲取上一遍的工作結(jié)果開始，經(jīng)過本遍的加工后，將結(jié)果保存起來以便交給下一遍[5]。例如，對于要求經(jīng)一遍掃描就能完成從源代碼到目標(biāo)代碼翻譯的編譯程序，我們可以語法分析程序?yàn)橹行膩斫M織它的工作流程，這樣就不必產(chǎn)生中間代碼，顯然，這種做法所得到的目標(biāo)代碼的質(zhì)量是不能保證的，總體來說弊大于利。對于絕大部分語言（例如Pascal或C），實(shí)現(xiàn)一遍掃描的編譯程序是非常困難的，所以宜于采用多遍掃描的編譯程序結(jié)構(gòu)。具體的做法是將整個(gè)編譯程序劃分為若干個(gè)相繼執(zhí)行的模塊，每一模塊都對它前一模塊的輸出掃描一遍，并在掃描過程中完成前述6個(gè)階段中的一個(gè)或幾個(gè)，然后將工作結(jié)果保存下來供下一模塊加工。顯然，第一個(gè)模塊所掃描的是字符序列形式的源程序，最后一個(gè)模塊所輸出的是目標(biāo)代碼，而每一個(gè)中間模塊輸出的是與源程序等價(jià)的內(nèi)部表示或中間代碼。2.3.2分遍的設(shè)計(jì)在設(shè)計(jì)一個(gè)編譯程序時(shí)，如何確定掃描遍數(shù)，如何組織各遍中的工作，主要取決于源語言的具體情況及編譯程序運(yùn)行的具體環(huán)境，如語言的結(jié)構(gòu)、計(jì)算機(jī)軟硬件的配置，以及對編譯程序本身運(yùn)行效率的要求等等。一般而言，多遍掃描源程序具有如下優(yōu)點(diǎn)：（1）由于采用了模塊結(jié)構(gòu)，各遍掃描的功能相對獨(dú)立，整個(gè)編譯程序的結(jié)構(gòu)比較清晰。（2）由于對源程序及其內(nèi)部表示進(jìn)行多次掃視和加工，有利于進(jìn)行比較細(xì)致和充分的代碼優(yōu)化處理。（3）由于可將編譯程序按模塊依次調(diào)入內(nèi)存，有利于采用覆蓋技術(shù)，以減少執(zhí)行編譯程序時(shí)所占的內(nèi)存空間。由于分遍問題對具體語言及編譯程序的運(yùn)行環(huán)境有很強(qiáng)的依賴性，經(jīng)過權(quán)衡，本實(shí)驗(yàn)設(shè)計(jì)的編譯器采用了簡單的1遍掃描策略。2.4編譯器中的主要數(shù)據(jù)結(jié)構(gòu)當(dāng)然，編譯器的各個(gè)階段使用的算法與支持這些階段的數(shù)據(jù)結(jié)構(gòu)之間的交互是非常密切的。編譯器的編寫者在實(shí)施這些算法的同時(shí)應(yīng)盡可能地保證它們不過于復(fù)雜，最理想的情況是：該編譯器在編譯時(shí)所耗費(fèi)的時(shí)間與程序大小成線形比例，即時(shí)間復(fù)雜度為O(n)。能否達(dá)到這樣的理想情況，很大程度上取決于所采用的數(shù)據(jù)結(jié)構(gòu)，它們是各個(gè)階段都需要使用到的，并用來在各階段之間交流信息。通常編譯器中的主要數(shù)據(jù)結(jié)構(gòu)包括：記號、語法樹、符號表、常數(shù)表、中間代碼、臨時(shí)文件等。2.5編譯程序的開發(fā)2.5.1歷史與發(fā)展在編譯器開發(fā)的原始階段，人們主要用機(jī)器語言或匯編語言來構(gòu)造編譯程序，難度極大且效率很低?，F(xiàn)在的大部分編譯器是用某種高級語言開發(fā)的，這樣更節(jié)約時(shí)間，而且易讀、易改、易移植，同時(shí)也便于進(jìn)行編譯器的優(yōu)化設(shè)計(jì)。相信在不久的將來，編譯器的開發(fā)將主要借助于成熟的自動(dòng)化生成編譯程序技術(shù)。2.5.2開發(fā)注意事項(xiàng)（1）源語言：對被編譯的源語言，要深刻理解其結(jié)構(gòu)和含義。在定義C語言的過程中，是通過嚴(yán)格制定其詞法規(guī)則、語法規(guī)則和語義規(guī)則來達(dá)到的。（2）目標(biāo)語言：C編譯器的目標(biāo)語言選擇為三地址的四元表達(dá)式。（3）編譯技術(shù)：詞法分析、語法分析、語義分析、代碼優(yōu)化及代碼生成的相關(guān)技術(shù)有很多，必須根據(jù)所開發(fā)的編譯器的需求和特點(diǎn)來選擇最合適的編譯技術(shù)和方法。關(guān)于C編譯器中使用到的編譯技術(shù)可詳細(xì)參考論文第四章。（4）各種具體因素：例如系統(tǒng)功能要求、硬件開發(fā)環(huán)境、軟件開發(fā)工具等。2.5.3編譯技術(shù)和軟件工具為了提高軟件開發(fā)的效率和保證開發(fā)質(zhì)量，人們除了要遵循軟件工程中對軟件開發(fā)過程的規(guī)范化或標(biāo)準(zhǔn)化之外，還應(yīng)盡量使用先進(jìn)的軟件開發(fā)技術(shù)和相應(yīng)的軟件工具，而大部分軟件工具的開發(fā)，常常要用到編譯技術(shù)和方法。實(shí)際上編譯程序本身也是一種軟件開發(fā)工具。為了提高編程效率，縮短調(diào)試時(shí)間，軟件工作人員研制了不少對源程序處理的工具，這些工具的開發(fā)不同程度地用到編譯程序各個(gè)部分的技術(shù)和方法，典型的有下面幾種[7]：（1）語言的結(jié)構(gòu)化編輯器：結(jié)構(gòu)化編輯器是引導(dǎo)用戶在語言的語法制導(dǎo)下編制程序，能自動(dòng)地提供關(guān)鍵字和與其匹配的關(guān)鍵字，這樣可以減少語法上的錯(cuò)誤，加快對源程序的輸入和調(diào)試，提高效率和質(zhì)量?，F(xiàn)在的可視化開發(fā)工具基本都具備了這個(gè)功能。（2）語言程序的調(diào)試工具：調(diào)試是軟件開發(fā)過程中一個(gè)重要環(huán)節(jié)，凡是對算法的實(shí)現(xiàn)錯(cuò)誤或程序沒能反映算法的功能等錯(cuò)誤就需用調(diào)試器來協(xié)助解決。調(diào)試器的功能越強(qiáng)則實(shí)現(xiàn)越復(fù)雜，它必須與語法分析、語義處理有緊密聯(lián)系。（3）語言程序測試工具：對源程序進(jìn)行語法分析并制定相應(yīng)表格，檢查變量定值與引用的關(guān)系；也可在源程序的適當(dāng)位置插入某些信息，并用測試用例記錄程序運(yùn)行時(shí)的實(shí)際路徑，將運(yùn)行結(jié)果與期望的結(jié)果進(jìn)行比較分析，幫助編程人員快速查找問題所在。（4）高級語言之間的轉(zhuǎn)換工具：為了減少重新編制程序所耗費(fèi)的人力和時(shí)間，就要解決如何把一種高級語言轉(zhuǎn)換成另一種高級語言，乃至匯編語言轉(zhuǎn)換成高級語言的問題，這種異種程序設(shè)計(jì)語言之間的翻譯轉(zhuǎn)換工作要對被轉(zhuǎn)換的語言進(jìn)行詞法和語法分析，只不過生成的目標(biāo)語言是另一種高級語言而已，這與實(shí)現(xiàn)一個(gè)完整的編譯程序相比工作量要少些。（5）并行編譯技術(shù)：隨著并行機(jī)及多處理機(jī)的發(fā)展，對軟件的并行處理提出了新的要求，特別是并行編譯技術(shù)發(fā)展很快。運(yùn)用重構(gòu)技術(shù)把已有的串行語言編寫的程序經(jīng)過分析分解成可并行的成分，然后分配到多處理機(jī)上運(yùn)行。如果編程人員能按程序設(shè)計(jì)情況寫出并行語言程序，那么兩者結(jié)合將產(chǎn)生更高的效率。第三章C編譯器可行性分析及總體設(shè)計(jì)3.1可行性分析3.1.1經(jīng)濟(jì)可行性經(jīng)濟(jì)可行性研究是對組織的經(jīng)濟(jì)現(xiàn)狀和投資能力進(jìn)行分析，對系統(tǒng)建設(shè)運(yùn)行和維護(hù)費(fèi)用進(jìn)行估算，對系統(tǒng)建成后可能取得的社會(huì)和經(jīng)濟(jì)效益進(jìn)行估計(jì)。由于本系統(tǒng)是作為畢業(yè)設(shè)計(jì)由我們自己開發(fā)的，在經(jīng)濟(jì)上的投入甚微，系統(tǒng)建成之后將為今后C源程序的編譯提供很大的方便，估算新系統(tǒng)的開發(fā)費(fèi)用和今后的運(yùn)行、維護(hù)費(fèi)用，估計(jì)新系統(tǒng)將獲得的效益，并將費(fèi)用與效益進(jìn)行比較，看是否有利。開發(fā)、運(yùn)行和維護(hù)費(fèi)用主要包括：購買和安裝設(shè)備的費(fèi)用：無。軟件開發(fā)費(fèi)用：若由實(shí)習(xí)單位的技術(shù)人員開發(fā)，則該項(xiàng)費(fèi)用可以計(jì)入下面的人員費(fèi)用一項(xiàng)；人員費(fèi)用：系統(tǒng)開發(fā)人員、操作人員和維護(hù)人員的工資、培訓(xùn)費(fèi)用等；消耗品費(fèi)用：系統(tǒng)開發(fā)所用材料、系統(tǒng)正常運(yùn)行所用消耗品，例如水、電費(fèi)，打印紙、軟盤、色帶等開支。所有開支都不大，所以經(jīng)濟(jì)上是可行的。3.1.2技術(shù)可行性技術(shù)可行性要考慮現(xiàn)有的技術(shù)條件是否能夠順利完成開發(fā)工作，軟硬件配置是否滿足開發(fā)的需求等。C編譯系統(tǒng)用的是標(biāo)準(zhǔn)C++開發(fā)語言，調(diào)試相對簡單，當(dāng)前的計(jì)算機(jī)硬件配置也完全能滿足開發(fā)的需求，因此在技術(shù)上是絕對可行的。軟件方面：由于目前BS模式軟件相對發(fā)展成熟，故軟件的開發(fā)平臺成熟可行,它們速度快、容量大、可靠性能高、價(jià)格低，完全能滿足系統(tǒng)的需求。3.1.3運(yùn)行可行性對新系統(tǒng)運(yùn)行后給現(xiàn)行系統(tǒng)帶來的影響（包括組織機(jī)構(gòu)、管理方式、工作環(huán)境等）和后果進(jìn)行估計(jì)和評價(jià)。同時(shí)還應(yīng)考慮現(xiàn)有管理人員的培訓(xùn)、補(bǔ)充，分析在給定時(shí)間里能否完成預(yù)定的系統(tǒng)開發(fā)任務(wù)等。運(yùn)行可行性是對組織結(jié)構(gòu)的影響，現(xiàn)有人員和機(jī)構(gòu)和環(huán)境對系統(tǒng)的適應(yīng)性及人員培訓(xùn)補(bǔ)充計(jì)劃的可行性。當(dāng)前我國信息化技術(shù)已經(jīng)相當(dāng)普及，各類操作人員水平都有相當(dāng)?shù)母叨?，所以在運(yùn)行上是可行性的。本系統(tǒng)的開發(fā)，是用典型的VS2012或者其他c++編譯工具開發(fā)，主要是對算法的處理，包括詞法分析和分析表的構(gòu)造，及目標(biāo)代碼的輸出。已無技術(shù)上的問題。3.1.4時(shí)間可行性從時(shí)間上看，在兩個(gè)月的時(shí)間里學(xué)習(xí)相關(guān)知識，并開發(fā)C編譯器系統(tǒng)，時(shí)間上是有點(diǎn)緊，但是不是不可能實(shí)現(xiàn)，通過兩個(gè)多月的努力功能應(yīng)該基本實(shí)現(xiàn)。3.1.5法律可行性①所有技術(shù)資料都為合法。②開發(fā)過程中不存在知識產(chǎn)權(quán)問題。③未抄襲任何已存在的會(huì)員信息管理系統(tǒng)，不存在侵犯版權(quán)問題。④開發(fā)過程中未涉及任何法律責(zé)任。綜上所述，本系統(tǒng)的開發(fā)從技術(shù)上、從經(jīng)濟(jì)上、從法律上都是完全可靠的。3.2C語言的基本描述C語言是本實(shí)驗(yàn)設(shè)計(jì)要實(shí)現(xiàn)的一種微型語言的名稱，該語言的源程序?yàn)槲谋拘问降腁SCII字符序列。考慮到針對現(xiàn)有的處理器來說，如果使用真正的機(jī)器代碼作為C編譯器的目標(biāo)語言會(huì)太過于復(fù)雜，所以C語言將目標(biāo)程序簡化為三地址碼的四元式表示形式?？稍谌我庖环N文本編輯器中編輯C語言的源程序并保存為擴(kuò)展名為.c的文件，然后用命令行的形式調(diào)用C編譯器（C.EXE）對該源程序進(jìn)行編譯，經(jīng)過詞法分析、語法分析并在此基礎(chǔ)上展開語義處理，如果源程序中沒有錯(cuò)誤，則最終生成目標(biāo)代碼即三地址碼的四元式表示形式。這種四元式表達(dá)式更接近于中間語言形式，由于這種形式的中間語言便于優(yōu)化處理，因此是一種比較普遍采用的中間代碼形式。C語言的程序結(jié)構(gòu)很簡單，它的語法與C相似但規(guī)模小于C語言。C源程序是一個(gè)由分號分隔開的語句序列。C只有兩個(gè)控制語句：if語句和while語句，這兩個(gè)控制語句本身也可包含語句序列。if語句有一個(gè)可選的else部分。除此之外，還有數(shù)據(jù)的輸入和輸出（輸入語句一次只讀入一個(gè)變量，而輸出語句一次只輸出一個(gè)表達(dá)式）。C的表達(dá)式也局限于布爾表達(dá)式和整型算術(shù)表達(dá)式。布爾表達(dá)式由對兩個(gè)算術(shù)表達(dá)式的比較組成，所有比較使用<和=比較運(yùn)算符。算術(shù)表達(dá)式可以包括整型常數(shù)、變量、參數(shù)以及4個(gè)整型算符+、-、*、/，它們具備和通用語言相似的數(shù)學(xué)屬性。布爾表達(dá)式通常只作為測試條件出現(xiàn)在控制語句中。雖然缺少實(shí)用程序設(shè)計(jì)語言（如C、Pascal）所需要的許多特征——比如數(shù)組和指針等，但作為一次完整的編譯開發(fā)實(shí)踐，它已經(jīng)足夠體現(xiàn)出一個(gè)編譯器的開發(fā)過程了。3.3C編譯器的功能C編譯器的主要任務(wù)是分析基于C語言規(guī)范的字符組成的C源程序，把它們識別為一個(gè)個(gè)具有獨(dú)立意義的單詞符號（Token），并識別其有關(guān)屬性再轉(zhuǎn)換成長度統(tǒng)一的屬性字，以供后續(xù)語義部分分析使用。簡單的說，C編譯器的功能就是掃描C源程序，識別單詞，轉(zhuǎn)換成屬性字，再經(jīng)過語義處理和代碼生成，最終得到目標(biāo)代碼文件即三地址四元表達(dá)式。一般的說，C編譯器實(shí)現(xiàn)了下列幾項(xiàng)功能：（1）從C源程序中逐一取出單詞。（2）生成LR（1）分析表。（3）識別單詞的屬性并填入構(gòu)造好的符號表中。（4）將單詞轉(zhuǎn)換成屬性字，并輸出二元組屬性字流。（5）將符號表提供給語義分析程序加工處理。（6）生成目標(biāo)代碼。（7）提供基本出錯(cuò)處理。3.4C編譯器的程序結(jié)構(gòu)3.4.1C編譯器的設(shè)計(jì)模式C編譯器用C++實(shí)現(xiàn)，下面是主要類的類圖：TTokenReadCfgSReadCfgScannerLrLrGrammer圖3-1C++實(shí)現(xiàn)C語言編譯器的類圖主控模塊main.cpp：C編譯器的主程序。文法類ReadCfg：文法規(guī)則類，定義C語言文法的規(guī)則。（3）詞法掃描類Scanner：關(guān)鍵字、算符與界符將直接形成Token字；標(biāo)識符將插入符號表后形成Token字，數(shù)字將插入常數(shù)表后形成Token字。（4）詞法掃描類Scanner：將源程序的字符序列收集到稱作記號(token)的有意義單元中，即完成與語言單詞拼寫相類似的任務(wù)。（5）LR（1）分析表的構(gòu)造類Grammer：根據(jù)C語言文法的特點(diǎn)，夠造出相應(yīng)的分析表（包括ACTION表和GOTO表）。（6）語法分析類Lr：將語言結(jié)構(gòu)的語義以屬性(attribute)的形式賦予代表此結(jié)構(gòu)的文法符號，而屬性的計(jì)算以語義規(guī)則(semanticrules)的形式賦予由文法符號組成的產(chǎn)生式；在語法分析推導(dǎo)或歸約的每一步驟中，通過語義規(guī)則實(shí)現(xiàn)對屬性的計(jì)算，以達(dá)到對語義的處理。3.4.2C編譯器的文件組成.h頭文件.cpp源文件模塊功能說明Cfg.hCfg.cpp文法的定義Token.hToken.cppToken字Scanner.hScanner.cpp詞法分析Grammer.hGrammer.cpp語法分析表的構(gòu)造Lr.hLr.cpp語法和語義分析表3-1C編譯器的文件組成基類Token，它包括了編譯器中各種數(shù)據(jù)類型的定義和整個(gè)編譯器均可能使用到的全局變量的定義。ReadCfg類從文件讀取C語言文法，并保存在文法結(jié)點(diǎn)Cfg_node中。C語言文法總結(jié)出有57個(gè)產(chǎn)生式，終結(jié)符（terminal）31和存放在set<int> terminal中，非終結(jié)符26個(gè)，存放在set<int> nonterminal中。Scanner類是詞法分析的類，成員函數(shù)scan（）每次返回一個(gè)Token字。Grammer類主要負(fù)責(zé)大量數(shù)據(jù)結(jié)構(gòu)的保存和LR（1）分析表的構(gòu)造，最終分析表存放在action_goto_table.txt中。Lr類的包含語法分析的總控程序，用成員函數(shù)analyse（）實(shí)現(xiàn)對語法的分析，在語法分析推導(dǎo)或歸約的每一步驟中，通過語義規(guī)則實(shí)現(xiàn)對屬性的計(jì)算，以達(dá)到對語義的處理。main.c文件是C編譯器的主程序，它負(fù)責(zé)整個(gè)程序的掌控。3.5C編譯器中的主要數(shù)據(jù)結(jié)構(gòu)下面列舉出在C編譯器中使用到的主要數(shù)據(jù)結(jié)構(gòu)，它們通常在編譯的多個(gè)階段都需要使用到，并用來在各階段中共享一些特定數(shù)據(jù)[8]。（1）記號（token）當(dāng)掃描程序?qū)⑷舾蓚€(gè)字符收集到一個(gè)記號中時(shí)，它通常是以符號表示這個(gè)記號的，也就是說，用一個(gè)枚舉數(shù)據(jù)類型的值來表示源程序的記號集。有時(shí)還必須保留字符串本身或由此派生出的其他信息（例如：與標(biāo)識符記號相關(guān)的名字或數(shù)字記號值）。在C編譯器中，掃描程序一次只需要生成一個(gè)記號（這稱為單符號先行），考慮到這種情況，可以用全程變來量放置記號信息。（2）符號表（symboltable）符號表中的信息與標(biāo)識符（函數(shù)、變量、常量以及數(shù)據(jù)類型等）有關(guān)。它幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語義分析程序?qū)⒃黾訑?shù)據(jù)類型和其它語義信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息生成正確而恰當(dāng)?shù)拇a。因?yàn)樵诰幾g的全程中對符號表的訪問非常頻繁，所以插入、刪除和訪問等符號表操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是能達(dá)到這一要求的最理想的數(shù)據(jù)結(jié)構(gòu)。（3）項(xiàng)目（item）在文法G中，某個(gè)產(chǎn)生式的右部標(biāo)上“點(diǎn)號”的產(chǎn)生式，再放置一個(gè)向前所搜符號a，成為LR（1）項(xiàng)目。每個(gè)LR（1）項(xiàng)目集簇由若干狀態(tài)組成，每個(gè)狀態(tài)由若干項(xiàng)目組成。因此，對于構(gòu)建項(xiàng)目集簇，項(xiàng)目的操作相當(dāng)頻繁，如何表示和處理項(xiàng)目成為構(gòu)造分析表的重點(diǎn)。（4）中間代碼（intermediatecode）根據(jù)中間代碼的類型（例如三元式代碼和P-代碼）和優(yōu)化的類型，該代碼可以是字符串?dāng)?shù)組（指針數(shù)組）、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡單重組的中間代碼表示。

第四章C編譯器的實(shí)現(xiàn)C編譯器從整體上被劃分為4個(gè)階段：詞法分析、語法分析、語義分析、代碼生成，這4個(gè)階段分別用不同的程序模塊來實(shí)現(xiàn)（如表3-1）。一個(gè)C源程序經(jīng)過C編譯器的編譯之后，生成三地址的四元表達(dá)式目標(biāo)代碼，在整個(gè)編譯過程中，這4個(gè)階段分別承擔(dān)了相應(yīng)的翻譯任務(wù)。4.1詞法分析階段4.1.1概述編譯器的詞法分析階段可將源程序讀作有序字符文件并將其掃描分解為若干個(gè)記號（token）。記號與自然語言中的單詞類似：每一個(gè)記號都是表示源程序中信息單元的字符序列。典型的有：關(guān)鍵字(keyword)，例如if和while，它們是字母的固定串，在該語言中具有特定的含義；標(biāo)識符(identifier)是由用戶定義的串，它們通常由字母和數(shù)字組成并由一個(gè)字母開頭，例如變量名函數(shù)名等；算符符（operationsymbol）在語言中是作為語法上的運(yùn)算符號使用的。例如，+，-，*，/，（，），和++，--，<=；界符在語言中作為語法上的分界；數(shù)字，廣義上就是源程序中的字面值。如前所述，詞法分析程序的輸入是源程序字符串，輸出是與源程序等價(jià)的符號序列。作為詞法分析程序的符號可以有各種不同的內(nèi)部表現(xiàn)形式，原則是不同的符號能彼此區(qū)別開且有唯一的表示。為了便于編譯程序的進(jìn)一步加工（語法分析），內(nèi)部表示的符號都按屬性字形式，因此，詞法分析程序的輸出即是屬性字序列，采用二元式來表示一個(gè)單詞符號的內(nèi)部形式。符號類別符號值表4-1詞法Token字這五類單詞將用不同的方法處理。關(guān)鍵字、算符與界符將直接形成Token字；標(biāo)識符將插入符號表后形成Token字，數(shù)字將插入常數(shù)表后形成Token字。在實(shí)際做詞法分析時(shí)，考慮了所有的C語言現(xiàn)象，使得每一個(gè)C語言程序都可以被此法分析切割為單詞并且賦值上屬性。一般情況下，可以通過兩種途徑來設(shè)計(jì)詞法分析程序。一種是用手工方式構(gòu)造，另一種是所謂詞法分析程序的自動(dòng)生成。為了實(shí)現(xiàn)簡單，本實(shí)驗(yàn)采取手工構(gòu)造方式。4.1.2C詞法分析程序的實(shí)現(xiàn)C語言的記號分為5種類型：標(biāo)示符，關(guān)鍵字，數(shù)字，算符和界限符。關(guān)鍵字一共有8個(gè)，它們的含義類似于標(biāo)準(zhǔn)C語言中的相應(yīng)關(guān)鍵字。特殊符號共有12種：分別是4種基本的整數(shù)運(yùn)算符號，5種比較符號（等號、小于號、小于等于、大于、大于等于），以及左括號、右括號、分號、賦值符號。其中，除了比較等號、小于等于符號和大于等于是兩個(gè)字符的長度之外，其余均為單個(gè)字符?！捌渌庇浱柧褪菙?shù)和標(biāo)識符了，數(shù)是一個(gè)或多個(gè)數(shù)字的序列，而標(biāo)識符又是一個(gè)或多個(gè)字母的序列。所有這些記號歸納如下表4-2：關(guān)鍵字（8個(gè)）Int、if、while、double、return、void、continue、break界限符（12個(gè)）+、-、*、/、==、=、<、<=、>、>=、(、)、;其它數(shù)(1個(gè)或更多的數(shù)字序列)標(biāo)識符(1個(gè)或更多的字母序列)表4-2C語言的記號除了上表的記號之外，C語言的源程序還要遵循以下的詞法規(guī)則：代碼應(yīng)是自由書寫格式；空白符由空格、制表位和新行組成。根據(jù)對語言中各類單詞某種描述的定義，用手工方式構(gòu)造詞法分析程序。詞法分析程序的主要任務(wù)就是掃描程序、識別單詞、轉(zhuǎn)換并輸出屬性字。下面給出單獨(dú)成趟詞法分析控制流程圖。開始開始輸入C源文件輸入C源文件是否是否文件結(jié)尾巴尾YYNN進(jìn)入主控模塊進(jìn)入主控模塊選擇選擇識別的單詞形成Token形成Token字YY停止停止圖4-1單獨(dú)成趟的詞法分析控制流程圖詞法分析主要包含在Scanner.h和Scanner.cpp文件中，其核心函數(shù)是scan()，它每次從第一個(gè)非空格或換行符開始識別，直到遇到空格或者換行符，遇到單行注釋就跳過本行從“//”開始的以后字符識別，遇到多行注釋就跳過直到遇到“*/”為止（不支持注釋嵌套）。每次返回一個(gè)識別的單詞，遇到不識別的單詞就報(bào)錯(cuò)，輸出不識別的單詞和該單詞的行數(shù)。掃描程序在識別出每個(gè)記號的同時(shí)，還會(huì)計(jì)算出該記號的特性（比如串值）這五類單詞將用不同的方法處理。關(guān)鍵字、算符與界符將直接形成Token字；標(biāo)識符將插入符號表后形成Token字，數(shù)字將插入常數(shù)表后形成Token字。Token是本實(shí)驗(yàn)的所有類的基類，有2個(gè)成員變量：Tag，Value。Value是文法中非終結(jié)符，而Tag是Value對應(yīng)的唯一標(biāo)記。4.1.3關(guān)鍵字與標(biāo)識符的識別C對于關(guān)鍵字的識別，是通過先將它們看作是標(biāo)識符，然后再調(diào)用Token類的get_int()方法，根據(jù)返回值Tag是否22（標(biāo)示符的標(biāo)志）為來判斷是標(biāo)示符還是關(guān)鍵字。4.1.4詞法識別具體實(shí)現(xiàn)//分析一個(gè)單詞，并返回單詞的Token字TokenScanner::scan(){ inti=0; strings; staticcharprev_c=0; charline[Token::NAME_SIZE]={0}; prev_c=c; while(true) { if(fin.get(c)==NULL) //到文件結(jié)尾 return(Token()); if(c=='\n') //遇到換行符 linenum++; //行數(shù)+1 elseif(c==''||c=='\t') //遇到空格或者制表符 continue; //跳過，繼續(xù)讀 else //遇到普通字符，跳出循環(huán) break; } //遇到注釋的情況 while(c=='/'&&(fin.peek()=='/'||fin.peek()=='*')) { //處理注釋 }//endwhile if(isalpha(c)) //字母 return(alpha_process()); elseif(isdigit(c)) //數(shù)字 return(digit_process()); else //其他 { switch(c) //對字符進(jìn)行分析 { case'+': {...} case'-': {...} case'*': {...} case'/': {...} case'=': {...} case'<': {...} case'>': {...} case'!': {...} case'&': {...} case'|': {...} case'~': {...} case'(': return(Token(get_int("("),"(")); case')': return(Token(get_int(")"),")")); case'[': return(Token(get_int("["),"[")); case']': return(Token(get_int("]"),"]")); case'{': return(Token(get_int("{"),"{")); case'}': return(Token(get_int("}"),"}")); case'"': return(string_process()); case';': return(Token(get_int(";"),";")); case',': return(Token(get_int(","),",")); case'.': return(Token(get_int("."),".")); case':': return(Token(get_int(":"),":")); case'\'': {...} case'#': {...} default: std::cout<<"Error,line"<<linenum <<":\tillegalcharacter\'"<<c<<"\'\n"; line[0]=c; line[1]='\0'; return(Token(get_int("ILLEGAL"),s.assign(line))); } } returnToken();}4.2語法分析階段4.2.1概述語法分析是編譯過程的核心，分析的任務(wù)是根據(jù)語法規(guī)則分析源程序的語法結(jié)構(gòu)，并在分析過程中，對源程序進(jìn)行語法檢查，如果語法沒有錯(cuò)誤，則給出正確的語法結(jié)構(gòu)，為語義分析和代碼生成做準(zhǔn)備。目前語法分析方法有多種多樣，大致分為自頂而下和自底而上兩大類。自頂而下又分為LL（1）分析方法和遞歸下降分析方法。自底而上又分為簡單優(yōu)先文法、算符優(yōu)先文法、LR（K）分析方法。下面主要介紹自底而上的LR（K）分析方法。自底向上分析法，也稱移進(jìn)-歸約分析法。它的實(shí)現(xiàn)思想是對輸入符號串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號串形成某個(gè)句型的句柄時(shí)，(該句柄對應(yīng)某產(chǎn)生式的右部)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為移步歸約。重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。否則，分析失敗，表示輸入符號串不是文法的一個(gè)句子，其中必定存在語法錯(cuò)誤。LR（K）分析方法是1965年由D.Knuth先生提出的一種自底而上的語法分析方法。自底而上的分析方法就是移進(jìn)-規(guī)約的過程。LR（K）分析法能根據(jù)分析棧的當(dāng)前內(nèi)容以及向前看輸入串的K個(gè)字符來決定分析動(dòng)作移進(jìn)還是規(guī)約。LR（K）分析方法適用范圍較廣，分析速度較快，并且能準(zhǔn)確及時(shí)地發(fā)現(xiàn)語法錯(cuò)誤。由于LR（K）分析方法對文法限制很少，因而大多數(shù)能用上下文無關(guān)文法描述的程序設(shè)計(jì)語言都可用LR分析法進(jìn)行有效分析，而且LR分析效率不亞于自頂向下分析法好、算法優(yōu)先分析法，及其他“移進(jìn)-規(guī)約”分析法。因此，LR分析法是當(dāng)前最一般的語法分析方法。對于一般使用的程序設(shè)計(jì)語言的文法而言，若手工構(gòu)造分析程序，則工作量太大，而且K越大，構(gòu)造越復(fù)雜，實(shí)現(xiàn)越困難。因此，綜合考慮，本實(shí)驗(yàn)采用LR（1）分析方法進(jìn)行語法分析。4.2.2C語言抽象出來的文法規(guī)則文法是為了深入研究語言的內(nèi)在性質(zhì)，而構(gòu)造語言的方法。換句話說，給定一個(gè)文法，就能從結(jié)構(gòu)上唯一的確定語言（形式語言理論可以證明此結(jié)論為真）。一個(gè)文法必須由4部分組成：字母表，表中的字符成為終結(jié)符。因?yàn)橥ㄟ^文法規(guī)則，最終得到的句子只能含有這些字符，這種字母稱為終結(jié)符集合，記為termanal。一個(gè)中間字母集，稱為非終結(jié)符，記為nontermanal，一般出現(xiàn)在規(guī)則左部的符號都是非終結(jié)符。文法規(guī)則集合。規(guī)則形如type_specifier->void。讀作“導(dǎo)出”、“產(chǎn)生”、“生成”或者“定義為”。文法的開始符號S0。S0為特殊的非終結(jié)符。下面是總結(jié)出來的c語言的文法，總共有57條規(guī)則：1S0->translation_unit2translation_unit->external_declaration3external_declaration->function_definition4external_declaration->declaration5declaration->type_specifierid;6type_specifier->void7type_specifier->int8type_specifier->double9function_definition->type_specifierfunction_nameparametercompound_statement10function_name->id11parameter->()12compound_statement->{decalration_list}13compound_statement->{statement_list}14compound_statement->{decalration_liststatement_list}15decalration_list->declaration16decalration_list->decalration_listdeclaration17statement_list->statement18statement_list->statement_liststatement19statement->compound_statement20statement->expression_statement21statement->selection_statementM22statement->iteration_statementM23statement->jump_statement24expression_statement->;25expression_statement->expression;26expression->assignment_expression27assignment_expression->primary_expression=assignment_expression28assignment_expression->logical_or_expression29logical_or_expression->logical_or_expression||Mlogical_and_expression30logical_or_expression->logical_and_expression31logical_and_expression->logical_and_expression&&Mequality_expression32logical_and_expression->equality_expression33equality_expression->equality_expression==relational_expression34equality_expression->relational_expression35relational_expression->relational_expression<additive_expression36relational_expression->relational_expression>additive_expression37relational_expression->relational_expression<=additive_expression38relational_expression->relational_expression>=additive_expression39relational_expression->additive_expression40additive_expression->additive_expression-multiplicative_expression41additive_expression->additive_expression+multiplicative_expression42additive_expression->multiplicative_expression43multiplicative_expression->multiplicative_expression*primary_expression44multiplicative_expression->multiplicative_expression/primary_expression45multiplicative_expression->multiplicative_expression%primary_expression46multiplicative_expression->primary_expression47primary_expression->id48primary_expression->double_num49primary_expression->int_num50primary_expression->(expression)51selection_statement->if(expression)Mstatement52iteration_statement->while(Mexpression)Mstatement53jump_statement->continue;54jump_statement->break;55jump_statement->return;56jump_statement->returnexpression;57M->e因?yàn)榉墙K結(jié)符肯定會(huì)在產(chǎn)生是的左邊出現(xiàn)，終結(jié)符卻不會(huì)在產(chǎn)生式的左邊出現(xiàn)，故首先找出在產(chǎn)生式右邊出現(xiàn)但是沒在產(chǎn)生式左邊出現(xiàn)的即是終結(jié)符，所有的符號減去終結(jié)符則是非終結(jié)符。這些編碼都是由程序自動(dòng)算出，如表4-3所示。終結(jié)符非終結(jié)符符號編號符號編號"$"1"M"32"%"2"S0"33"&&"3"additive_expression"34"("4"assignment_expression"35")"5"compound_statement"36"*"6"decalration_list"37"+"7"declaration"38"-"8"equality_expression"39"/"9"expression"40";"10"expression_statement"41"<"11"external_declaration"42"<="12"function_definition"43"="13"function_name"44"=="14"iteration_statement"45">"15"jump_statement"46">="16"logical_or_expression"47"break"17"logical_and_expression"48"continue"18"multiplicative_expression"49"double"19"parameter"50"double_num"20"primary_expression"51"e"21"relational_expression"52"id"22"selection_statement"53"if"23"statement"54"int"24"statement_list"55"int_num"25"translation_unit"56"return"26"type_specifier"57"void"27"while"28"{"29"||"30"}"31表4-3C的終結(jié)符和非終結(jié)符我們可以從表4-2中閱讀出本實(shí)驗(yàn)C的語法規(guī)則：C程序只是一個(gè)語句序列，它共有5種語句：if語句、while語句、賦值語句。另外還可以看出：C的表達(dá)式有兩類：布爾表達(dá)式和算術(shù)表達(dá)式。布爾表達(dá)式使用比較運(yùn)算符“=”和“<”，通常用在if語句和while語句中作為測試條件；算術(shù)表達(dá)式使用整型運(yùn)算符“+”、“-”、“*”、“/”，它們具有左結(jié)合和常規(guī)的優(yōu)先關(guān)系。與此不同，比較運(yùn)算是非結(jié)合的（每個(gè)沒有括號的表達(dá)式只允許一種比較運(yùn)算）。比較運(yùn)算符的優(yōu)先權(quán)都低于算術(shù)運(yùn)算符。另外，我們也可以把C的表達(dá)式看作三類：算符表達(dá)式、常量表達(dá)式和標(biāo)識符表達(dá)式。C中的標(biāo)識符指的是簡單整型變量，它沒有類似數(shù)組或記錄等類型的變量。C中也無需顯式的變量聲明：任何一個(gè)變量只是通過出現(xiàn)在賦值語句左邊或者read關(guān)鍵字的右邊來隱式地聲明。另外，變量只有全局作用域。C的語句序列是指用N個(gè)分號分隔開來的N條語句。4.2.3C語法分析程序的實(shí)現(xiàn)在實(shí)現(xiàn)C的語法分析器時(shí)，采用的核心算法是自底而上的LR（1）分析方法。LR（1）分析方法，最終要的是生產(chǎn)LR（1）分析表，分析表由分析動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換表（GOTO）組成。分析表由來Grammer類來表示。Grammer類繼承自ReadCfg類。Grammer類的構(gòu)造函數(shù)用來初始化ReadCfg類的成員變量，成員變量定義為protected型，方便Grammer類直接取到。具體成員如下：protected: vector<cfg_node>cfg; //文法結(jié)點(diǎn)數(shù)組 vector<int>table_head; //值符號集 vector<string>string_table_head; //string符號集 set<int> terminal; //存放終結(jié)符數(shù)值形式的集合 set<int> nonterminal; //存放非終結(jié)符數(shù)值形式的集合文法結(jié)點(diǎn)結(jié)構(gòu)體：struct cfg_node{ string left; //文法規(guī)則左部 intleft_int; //左部多對應(yīng)的鍵值 vector<string> right; //文法規(guī)則的右部，對于每一個(gè)左部， //可能產(chǎn)生多個(gè)右部，放入vector中 vector<int>