一個(gè)簡單的C語言編譯器

1、一個(gè)簡單的C語言編譯器.小組成員嘉筱杭林朱王朱朱（）（）（）計(jì)算機(jī)996計(jì)算機(jī)996計(jì)算機(jī)996計(jì)算機(jī)994在DO*境下運(yùn)行：Cminus.exe<filename>-h三.概述經(jīng)過一段時(shí)間的學(xué)習(xí)，我們在初步掌握了編譯器的基本原理以后，設(shè)計(jì)了一個(gè)具有基本編譯功能的編譯器。該編譯器接受類C語言語法的源代碼輸入，輸出結(jié)果是PC機(jī)的匯編源代碼。在捆綁了宏匯編編譯器Masmt,即可直接生成MSDOS的二進(jìn)制可執(zhí)行文件。為方便起見，以下簡稱為C語言編譯器。本編譯器實(shí)現(xiàn)了基本高級語言所必須的語法要素，包括簡單變量聲明、函數(shù)的實(shí)現(xiàn)、整數(shù)和字符串運(yùn)算、條件判斷語句和循環(huán)語句及跳轉(zhuǎn)語句、基本代數(shù)運(yùn)算

2、、賦值等，還支持匯編語言嵌入。本編譯器是利用編譯器生成器ParseGenerator和VC6.0在Windows平臺上實(shí)現(xiàn)的，并開發(fā)了一個(gè)基于Windows平臺的32位編譯集成開發(fā)環(huán)境CompilerMan,提供了關(guān)鍵字彩色提示、出錯(cuò)同屏提示、出錯(cuò)代碼跳轉(zhuǎn)等較為完善方便的功能。由于編譯程序本身涉及到詞法分析、語法分析、代碼生成、錯(cuò)誤恢復(fù)和優(yōu)化等諸多模塊，要在實(shí)驗(yàn)中做到面面俱到不太可能，所以本編譯器不可避免的會存在各種問題，但作為一個(gè)具有基本功能的、可擴(kuò)充的系統(tǒng)，完全達(dá)到了鞏固編譯原理的理論知識，并將其運(yùn)用于實(shí)踐的目的。四.背景編譯程序，就是一種具有編撰和翻譯功能的程序。人們要用計(jì)算機(jī)來解決問題

3、，首先面臨的一個(gè)問題，就是要告訴計(jì)算機(jī)解決什么問題，或者告訴計(jì)算機(jī)如何解決這個(gè)問題。這就涉及到用什么樣的語言來描述的問題，人所習(xí)慣的自然語言和計(jì)算機(jī)認(rèn)識的機(jī)器語言有很大的差別，用機(jī)器語言來描述人想解決的問題十分不便，因而，計(jì)算機(jī)科學(xué)家設(shè)計(jì)一些人們比較習(xí)慣的語言來描述要解決的問題，稱之為B級語言。用語言來描述的問題，統(tǒng)稱為程序。然而，用高級語言寫的程序，不能被計(jì)算機(jī)所直接認(rèn)識和理解，必須經(jīng)過等價(jià)的轉(zhuǎn)換，變成機(jī)器能理解并執(zhí)行的機(jī)器語言的程序。進(jìn)行這種等價(jià)轉(zhuǎn)換工作的工具，就是編譯程序。1 .編譯程序的結(jié)構(gòu)編譯程序是很復(fù)雜的，但它可被分為相對獨(dú)立的幾個(gè)部分，每個(gè)部分承擔(dān)專門的工作，各部分間互相共享傳送

4、數(shù)據(jù)。把編譯程序分解成較小的部分，不僅便于開發(fā)、調(diào)試，而且便于編譯程序的移植。一個(gè)典型的編譯程序通常具有如圖1的結(jié)構(gòu)目標(biāo)機(jī)器碼圖1編譯器基本結(jié)構(gòu)1.1 詞法分析詞法分析負(fù)責(zé)對源程序的字符串進(jìn)行掃描和分解，根據(jù)構(gòu)詞法將字符流(CharacterStream,?；蓡卧~流(TokenStream)。例如對于C-語句：x=y+z-m*10;詞法分析的結(jié)果是：IDASSIGNIDADDIDSUBIDMULNUMSEMI構(gòu)詞的規(guī)則就是詞法，例如標(biāo)識符（ID）可定義為以字母開頭，后面跟零個(gè)或任意個(gè)字母或數(shù)字的序列。詞法分析程序就根據(jù)詞法構(gòu)造有限自動機(jī)來識別每一個(gè)單詞，將產(chǎn)生的單詞交給語法分析程序。1.2

5、語法分析語法分析模塊的任務(wù)是根據(jù)文法規(guī)則把單詞序列分解成各類語法單位，識別出一個(gè)一個(gè)句子，例如對前面的語句進(jìn)行語法分析可得到如圖2的分析樹。如果輸入單詞不能構(gòu)成語法樹，則說明有語法錯(cuò)誤。常見的語法分析方法分為自頂向下分析和自底向上分析兩大類。在C-編譯器中采用了一種自底向上的方法,即LR方法。圖2語法分析樹1.3 語義分析這一階段部分是根據(jù)前一階段產(chǎn)生的語法樹，按語言的語義進(jìn)行翻譯，產(chǎn)生四元式或三元式等中間語言。中間語言可以很方便地轉(zhuǎn)換成目標(biāo)代碼。前面的語法樹可能產(chǎn)生的四元式序列為：(*,_t0,10,m)(-,_t1,z,_t0)(+,_t0,y,_t1)(二,x,_t0)由于中間語言對后面

6、的代碼優(yōu)化和目標(biāo)代碼生成有密切關(guān)系，又和目標(biāo)機(jī)器的體系結(jié)構(gòu)有關(guān)，所以中間語言的選擇對于編譯器的效率和質(zhì)量有很大的影響。1.4 代碼優(yōu)化代碼優(yōu)化是把中間代碼進(jìn)行變換，以產(chǎn)生更加高效的目標(biāo)代碼。1.5 目標(biāo)代碼生成目標(biāo)代碼生成是編譯最后一個(gè)階段，它把中間代碼轉(zhuǎn)換成匯編指令或可重定位的目標(biāo)代碼。例如對于前面生成的中間代碼，可以產(chǎn)生舊MPC匯編指令為：movax,mmulax,10movbx,zsubbx,axaddbx,ymovx,bx匯編代碼經(jīng)過Masm匯編器(Assembler)和連接器(Linker)處理，就產(chǎn)生了可在IBMPC機(jī)器上運(yùn)行的二進(jìn)制代碼。2 .形式語言簡介2.1 文法和語言文法是

7、產(chǎn)生語言的規(guī)則，它可定義為：對于一個(gè)四元式G=(Vn,Vt,S,P),其中(1) Vn是非終結(jié)符號的有限集合(2) Vt是終結(jié)符號的有限集合，且VtAVn二(3)開始符號S,SCVn(4) 一組產(chǎn)生式P,P中的每一個(gè)產(chǎn)生式都具有如下形式：uv,u(VnUVt)+且至少要有一個(gè)非終結(jié)符號，vC(VnUVt)*則G表示一個(gè)文法。喬姆斯基(NoamChmosky)把文法分成四類：0型文法又稱無約束文法，產(chǎn)生式的形式為a-b,a、b是任意字符串。1型文法又稱上下有關(guān)文法，產(chǎn)生式形式為a-b,且|aR|b|02型文法又稱上下文無關(guān)文法(Context-FreeGrammar),產(chǎn)生式形式為A-a,a(V

8、nUVt)*,ACVn。3型文法又稱正規(guī)文法，它的產(chǎn)生式左部是一個(gè)非終結(jié)符號，右部最多只有一個(gè)非終結(jié)符號且在右部的最左端或最右端。通常程序設(shè)計(jì)語言的文法屬于2型文法，可被下推機(jī)(PushdownAutomaton以別。語言定義為L(G尸wS=*w,wVt*,可見，文法G中的Vt相當(dāng)于產(chǎn)生語言的字母表，G中的一組產(chǎn)生式是產(chǎn)生語言的一組規(guī)則；語言L(G)中的每一個(gè)句子w,是由G的開始符號S經(jīng)推導(dǎo)得到的，完全由終結(jié)符號組成的字。非終結(jié)符號是引起推導(dǎo)繼續(xù)進(jìn)行的中間符號，在推導(dǎo)進(jìn)行到某一步時(shí)，如果再沒有非終結(jié)符號留在推導(dǎo)的結(jié)果中，則稱推導(dǎo)成功。在語言的設(shè)計(jì)和編譯器的編寫方面，文法都提供了極大的優(yōu)點(diǎn)：a)

9、文法給出了精確的，也易于理解的語言語法說明。b)對于某些文法類，可以自動產(chǎn)生高效的分析器。額外的好處是，分析器的構(gòu)造過程可以揭露出語法的二義性和其它難于分析的結(jié)構(gòu)，這些問題在語言和它的編譯器的最初設(shè)計(jì)階很可能沒有發(fā)現(xiàn)。c)設(shè)計(jì)得漂亮的文法，把結(jié)構(gòu)加于程序設(shè)計(jì)語言，這些結(jié)構(gòu)對把源程序翻譯成為正確的目標(biāo)代碼和錯(cuò)誤診斷都是有用的。把以文法為基礎(chǔ)的翻譯的描述轉(zhuǎn)變成程序的開發(fā)工具也是存在的。d)語言也是逐漸完善的，需要補(bǔ)充新的結(jié)構(gòu)和完成附加的任務(wù)。如果存在以文法為基礎(chǔ)的語言的實(shí)現(xiàn)，這些新結(jié)構(gòu)的加入就更方便。2.2 巴科斯范式(BNF)巴科斯范式(BackusNormalForm,BNF)是描述語法規(guī)則的

10、一種形式方法，在該方法中，使用如下符號：非終結(jié)號:=定義符|或者括號內(nèi)的成份可以重復(fù)出現(xiàn)多次，也可以不出現(xiàn)括號內(nèi)的成份為任選項(xiàng)，可以出現(xiàn)一次或不出現(xiàn)例如C語言中IF-THEN語句可以表示成：IF語句:=IF布爾表達(dá)式THEN語句卜ELSE語句習(xí)用巴科斯范式的形式表示文法的優(yōu)點(diǎn)是簡潔、清楚并容易被理解。3 .編譯程序的實(shí)現(xiàn)環(huán)境ParseGenerato徜介及其使用編譯器生成工具-ParseGenerator基于Windows平臺，它集成了詞法生成器ALEX和語法生成器AYACC,并提供了較為強(qiáng)大的類庫。其主要優(yōu)點(diǎn)體現(xiàn)在以下幾個(gè)方面：可以視一個(gè)編譯程序?yàn)橐粋€(gè)Project,集成Alex和Ayacc

11、文件的環(huán)境有利于整體調(diào)試和開發(fā)。且編輯界面友好，利于初學(xué)者使用。.l文件（lex文件）和.y文件（yacc文件）可生成為標(biāo)準(zhǔn)的C原代碼，也可生成VisualC+和BorlandC+格式的原代碼。這對習(xí)慣與BC或VC編程的程序員，無疑是極大的方便。ALex和AYacc的表驅(qū)動代碼隱藏在聯(lián)接庫中。庫在程序LINK的時(shí)候連入系統(tǒng)中。這在程序編譯的效率和靈活性兩個(gè)方面都有較大貢獻(xiàn)。ALex和AYacc的原代碼和和生成的目標(biāo)代碼（C或C+）可以建立語句的對應(yīng)，這對生成代碼的調(diào)試提供很大方便。實(shí)驗(yàn)中的編譯程序采用將ALex和AYacc文件轉(zhuǎn)化為VisualC+格式的代碼。現(xiàn)將程序中使用的聯(lián)接庫中主要類和函

12、數(shù)作一介紹。類yylexer-所有詞法分析器類的基類yylexer類提供由Alex生成的C+詞法分析器的一切基本功能。yylexer是一個(gè)抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yylex和yyaction。C-編譯器程序中的詞法分析器類是其子類C_Lexer類。類yyparser-所有語法分析器類的基類yyparser類提供由AYacc生成的C+語法分析器的一切基本功能。yyparser是一個(gè)抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yywork和yyparseaction=C-編譯器程序中的語法分析器類是其子類C_Parser類。五.詳細(xì)設(shè)計(jì)1.功能說明輸入：類C語言

13、純文本源程序。輸出：目標(biāo)機(jī)為具有8086+處理器的MSDOS系統(tǒng)下的二進(jìn)制可執(zhí)行代碼。PCAssemblyLanguage編語言源代碼以供分析使用。本編譯程序?qū)崿F(xiàn)的主要功能如下表所示:功能備注支持以下數(shù)據(jù)類型：int整型char字符型char口字符數(shù)組int口整型數(shù)組整型為有符號16位數(shù)。字符型為8位數(shù)。數(shù)組的下標(biāo)允許為任何合法的表達(dá)式。經(jīng)過簡單引、充后，即可實(shí)現(xiàn)長整型，無符號整型。支持以下數(shù)據(jù)操作：+加法-減法*乘法/除法%取余+自力口1-自減1*乘力&,|位與，位或A異或位非&&,|邏輯與，邏輯或!邏輯非<,>,<=,>=關(guān)系比較運(yùn)算=,!=

14、關(guān)系比較運(yùn)算<<,>>算術(shù)移位+-*/%=,*=,多達(dá)12種賦值<<=,>>=,&=,語句尸，A=,=支持以關(guān)鍵子_asm前導(dǎo)的形式為_asm的嵌入?yún)R編代碼(EMBEDEDASSEMBLY)對嵌入?yún)R編的支持大大提高的諦言的可用性，一定程度彌補(bǔ)了系統(tǒng)函數(shù)較少的缺憾。提供系統(tǒng)級庫函數(shù)：voidprint(/*表達(dá)式*/,%t);支持字符串，字符，整型三種類型的變量輸出，包括任何合法表達(dá)式的值。支持循環(huán)，轉(zhuǎn)移，判斷分支的程序設(shè)計(jì)，支持if,if.else,if.elseif.forwhile,do.whilegoto.語句。支持Label,允許

15、在任何語句前定義Label作為控制轉(zhuǎn)移目的地。for和while語句支持break,continue流程控制。支持函數(shù)概念。系統(tǒng)以main函數(shù)為入口函數(shù)。支持源程序注釋。注釋以“/或"/*"，標(biāo)型支持出錯(cuò)提示。對于嵌入?yún)R編代碼的出錯(cuò)提示可以通過重定向匯編代碼編譯器的出錯(cuò)信息實(shí)現(xiàn)。2.詞法分析器(lexer)2. 1正規(guī)式和DFA e和小都是2上的正規(guī)式，它們所表示的正規(guī)集分別為e和小 任何aCE,a是2上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a 假定U和V都是2上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V),那么，(U|V)、(U.V)和(U)*也都是正規(guī)式，它們所表示

16、的正規(guī)集分別為L(U)UL(V)、L(U)L(V)和(L(U)*。僅由有限次使用上述三步驟而定義的表達(dá)式才是2上的正規(guī)式，僅由這些正規(guī)所表示的字集才是2上的正規(guī)集。正規(guī)式可以有效地描述詞法，而確定的有限自動機(jī)(DFA)能準(zhǔn)確地識別正規(guī)集，執(zhí)行詞法分析的功能。2.2利用有限自動機(jī)進(jìn)行詞法分析詞法分析是整個(gè)編譯過程的第一階段，它將字符序列轉(zhuǎn)化為單詞序列。識別單詞的基本方法是根據(jù)詞法定義構(gòu)造有限自動機(jī)即描述語言結(jié)構(gòu)特征的狀態(tài)轉(zhuǎn)換圖。例如對于十進(jìn)制整數(shù)正規(guī)定義：1-9+0-9*可以構(gòu)造如圖3所示的有限自動機(jī)。圖3識別十進(jìn)制整數(shù)的有限自動機(jī)其中狀態(tài)2為接收態(tài)，若對于一個(gè)字符序列有限自動機(jī)可以到達(dá)2狀態(tài)，

17、則說明一個(gè)整數(shù)已被識別出來。詞法分析器構(gòu)造程序LEX正是根據(jù)這一原理工作的。構(gòu)造詞法分析器的主要任務(wù)是設(shè)計(jì)詞法的正規(guī)定義和相關(guān)的動作。上面例子的LEX程序段就是：1-9+0-9*returnICON;2. 3C-詞法分析器的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)1）關(guān)鍵字和系統(tǒng)標(biāo)識符表Ktab保存關(guān)鍵字和系統(tǒng)標(biāo)識符的信息，定義如下：typedefstructchar*name;intval;KWORD;其中name域保存關(guān)鍵字的名字，val域保存關(guān)鍵字的種類標(biāo)識。val域就是詞法分析器傳遞給語法分析器的終結(jié)符信息。2） C-中的關(guān)鍵字以下為Ktab數(shù)組的定義:KWORDKtab="break",BR

18、EAK"char",TYPE"continue",CONTINUE,"do",DO,"else",ELSE,"for",FOR,"goto",GOTO,"if",IF,"int",TYPE,"main",MAIN,"print",PRINT,"while",WHILE;具體實(shí)現(xiàn)（參見源文件C-_lex.l）1）對注釋的處理：支持/*.*/和/兩種注釋風(fēng)格，對于注釋內(nèi)容在匹配到/

19、*和/后，直接通過動作input跳過。處理了注釋符號遺漏的情況，并有出錯(cuò)信息顯示。2）常數(shù)的處理：詞法分析器可識別十進(jìn)制、八進(jìn)制和十六進(jìn)制無符號整數(shù)以及字符常數(shù)（形為a；并通過函數(shù)intstoi（char*string,intradix）轉(zhuǎn)化成數(shù)值形式。3）標(biāo)點(diǎn)符號的處理：直接返回其相應(yīng)的標(biāo)識。4）標(biāo)識符的處理：識別標(biāo)識符后，調(diào)用函數(shù)id_or_keyword查找其屬性值并返回。對于系統(tǒng)保留字和關(guān)鍵字，函數(shù)id_or_keyword返回相應(yīng)的標(biāo)識（token）返回值相同的，可以通過yytext區(qū)別。對于用戶自定義的標(biāo)識符，函數(shù)id_or_keyword返回NAME。為了提高查找關(guān)鍵字和系統(tǒng)標(biāo)識

20、符表的效率，函數(shù)id_or_keyword采用二分查找法(bsearch函數(shù))。5)嵌入?yún)R編(_asm)的處理：在函數(shù)id_or_keyword()中當(dāng)遇到y(tǒng)ytext="_asm”時(shí)，則進(jìn)入嵌入?yún)R編處理代碼：史匹而字符'',如果接下來的第一不字符不是',則打印出錯(cuò)信息。如果匹配則將后續(xù)代碼原樣寫入?yún)R編代碼中，直至遇到字符結(jié)束；如果未遇到則打印出錯(cuò)信息。由于要防止嵌入?yún)R編代碼中出現(xiàn)字符立即操作數(shù)'或注釋語句中的',因此要考慮這些情況。采用上述方法的好處是大大簡化了語法分析器的工作，不必設(shè)計(jì)大量的產(chǎn)生式來處理匯編格式。但是這樣就不能檢查嵌入?yún)R編的

21、語法錯(cuò)誤?？梢圆捎眠@樣的方法：用Masm編譯嵌入的代碼，重定向其輸出而判斷有無匯編語法錯(cuò)誤。6)生成的C_Lexer的類定義(參見源文件C-_lex.h):classC_Lexer:publicyyflexerpublic:嵌入C_Lexer();protected:voidyytables();virtualintyyaction(intaction);public:;C_Lexer()實(shí)現(xiàn)對詞法分析器對象的初始化，它調(diào)用yytables()。yyaction()則具體由定義的正則表達(dá)式實(shí)現(xiàn)歸約。3.語法分析器(parser)3.1上下文無關(guān)文法上下文無關(guān)文法G可以用一個(gè)四元組表示G=(V,

22、T,P,S)其中： V是文法的非終結(jié)符號集，每個(gè)非終結(jié)符號表示語言的一個(gè)語法變量； T是終結(jié)符號集，每個(gè)終結(jié)符號表示語言的一個(gè)基本符號，即詞匯； P是產(chǎn)生式集，文法用產(chǎn)生式定義每個(gè)非終結(jié)符號； S是V中的一個(gè)非終結(jié)符號，稱開始符號。文法的每個(gè)產(chǎn)生式由左、右兩部分組成，左部是一個(gè)非終結(jié)符號；右部是由零個(gè)或若干個(gè)終結(jié)符、非終結(jié)符組成的符號用。3. 2LR分析方法LR分析方法是自底向上進(jìn)行語法分析，它的功能很強(qiáng)，適用于多種上下文無關(guān)方法。L是指從左向右掃描輸入申，R指的是按照最右推導(dǎo)的的逆過程進(jìn)行歸約。LR分析法具有一些優(yōu)點(diǎn)： 能用上下文無關(guān)文法描述的程序設(shè)計(jì)語言結(jié)構(gòu)，都可以構(gòu)造其LR分析器進(jìn)行識別

23、。 LR分析法是具有一般性的無回溯移進(jìn)歸約分析法，并且能有效地被實(shí)現(xiàn)。 能用LR分析器分析的文法類包含能用LL(1)分析器分析的全部文法類。 LR分析器在自左向右掃描輸入時(shí)，可以盡可能地發(fā)現(xiàn)語法錯(cuò)誤。輸入圖4LR分析器圖4是LR分析器的結(jié)構(gòu)示意。其中分析棧存放狀態(tài)和移進(jìn)、歸約的文法符號：S0XlSl.Xm-lSm-lS0其中，Si表示狀態(tài)，Xi表示文法符號；在實(shí)現(xiàn)中，文法符號不必進(jìn)分析棧。動作表中的項(xiàng)目ACTIONSm,ai表示當(dāng)前輸入符號為a、棧頂狀態(tài)為Sm時(shí)，分析算法應(yīng)執(zhí)行的動作；若ACTIONSm,a=S,表示移進(jìn)，然后棧頂狀態(tài)為i;rj表示用產(chǎn)生式j(luò)歸約；acc表示接收輸入申，err表

24、示語法錯(cuò)誤。狀態(tài)轉(zhuǎn)換表中的項(xiàng)目GOTOSi,X表示歸約出非終結(jié)符號X之后，當(dāng)前棧頂狀態(tài)為Si時(shí)，分析棧應(yīng)轉(zhuǎn)換到的下一上狀態(tài)，即棧頂?shù)男聽顟B(tài)。LR分析算法為：根據(jù)輸入符號a、棧頂狀態(tài)Sm和動作表項(xiàng)actionSm,a的值，決定當(dāng)前分析應(yīng)執(zhí)行的動作；移進(jìn)、歸約、接收或出錯(cuò)；移進(jìn)或歸約之后要根據(jù)動作表或狀態(tài)轉(zhuǎn)換表設(shè)置分析棧的狀態(tài)?？梢园逊治鰲Ｖ械挠煤偷却斎氲慕K結(jié)答號用看成是兩個(gè)分量，這兩個(gè)分量構(gòu)成如下形式的二元組：(S0X1S1X2S2.XmSm,siai+1.an#)這個(gè)二元組結(jié)構(gòu)表示右句型X1X2.Xmaa+1.an#假定當(dāng)前分析棧的棧頂為狀態(tài)Sm,下一個(gè)輸入符號為ai,分析器的下一個(gè)動作由動

25、作表項(xiàng)actionSm,a決定。,如果actionSm,a=移進(jìn)S,則分析器執(zhí)行移進(jìn)，二元組變成(S0XlSlX2S2.XmSmaiS,ai+1.an#)即分析器將輸入符號ai和狀態(tài)S移進(jìn)棧，于是，a+1變成下一個(gè)輸入符號。 如果actionSm,a=歸約A-0則分析器執(zhí)行歸約，二元組變成(S0XlSlX2S2.Xm-rSm-rAS,ci+1.an#)其中，S由goto表確定：S=gotoSm-r,a,r=|0|,是句柄號用的長度。歸約時(shí)，分析器先從棧中彈出2r個(gè)元素：r個(gè)狀態(tài)和r個(gè)文法符號；于是使?fàn)顟B(tài)Sm-r出現(xiàn)在棧頂；然后，再把歸約產(chǎn)生式左部的非終結(jié)符A和由gotoSm-r,A確定的狀態(tài)S

26、壓入棧。在歸約過程中不改變輸入符號。對LR分析器來說，從棧中彈出的文法符號用Xm-r+1.Xm總是匹配歸約產(chǎn)生式的右部B。 如果actionSm,a=acc,則接收輸入符號用，語法分析完成 如果actionSm,a=err,則發(fā)現(xiàn)語法錯(cuò)誤，調(diào)用錯(cuò)誤處理子程序。3.3C-系統(tǒng)中使用的主要產(chǎn)生式(參見源文件C-_par.h)programMAINLPRPcompound_stmtcompound_stmtLClocal_defsstmt_listRClocal_defsdef_listdef_listdef_listdef|/*epsilon*/defspecifiersdecl_listSEMI

27、decl_listvar_decl|decl_listCOMMAvar_declvar_declnew_name|var_declLBICONRB|LPvar_declRPnew_nameNAMEspecifiersTYPEstmt_liststmt_liststatement|/*epsilon*/statementSEMI|compound_stmt|PRINTLPexprCOMMADIVOPICONRPSEMI|exprSEMI|GOTOtargetSEMI|targetCOLONstatement|IFLPtestRPstatement|IFLPtestRPstatementELSEs

28、tatement|WHILELPtestRPstatement|DOstatementWHILELPtestRPSEMI|FORLPopt_exprSEMItestSEMIopt_exprRPstatement|BREAKSEMI|CONTINUESEMItestexpr|/*epsilon*/targetNAMEopt_exprexprexprexprCOMMAnon_comma_exprnon_comma_exprEQUALnon_comma_expr|non_comma_exprASSIGNOPnon_comma_expr|or_expror_expr:or_listor_list:or

29、_listORORand_expr|and_exprand_expr:and_listand_list:and_listANDANDbinary|binarybinary:binaryRELOPbinary|binaryPOWERbinary|unaryunary:LPexprRP|3. 4系統(tǒng)中符號表的實(shí)現(xiàn)1)符號表的組織要求編譯程序用符號表跟蹤關(guān)于名稱的匯聚信息和作用域，當(dāng)詞法分析器識別出一個(gè)標(biāo)識符后，編譯程序就查找符號表，看它是否在符號表中，如果沒有，則把這個(gè)新標(biāo)識符填入符號表。在語義分析階段和代碼生成階段也要通過查找符號表來獲得標(biāo)識符的屬性信息?？梢娫诰幾g過程中符號表的查、填動作非常頻

30、繁，因而提高符號表查填效率是提高編譯程序運(yùn)行效率的關(guān)鍵因素，也是對符號表設(shè)計(jì)的根本要求。2)符號表的幾種組織方式線性表符表項(xiàng)按順序排列，這種組織方式最簡單并且實(shí)現(xiàn)也很容易。線性表的缺點(diǎn)是插入和查找的效率較低，雖然可以采用反序查找、表項(xiàng)排序、動態(tài)調(diào)整表項(xiàng)來提高效率，但其性能的改善是很有限的。,哈希表通過計(jì)算符號的哈希值來確定其在表格中的位置。哈希表結(jié)構(gòu)簡單、實(shí)現(xiàn)較容易，而且其插入和查找效率很高。采用哈希表要解決“沖突”的問題，而解決沖突將會提高哈希表的復(fù)雜度。二叉樹二叉樹的組織方式平均查填效率最高，但實(shí)現(xiàn)的復(fù)雜度較高。對于名稱沖突也要特別處理。在某些情況下，二叉樹會退化成線性表，這個(gè)問題可以通過

31、采用AVL樹的結(jié)構(gòu)來解決，但這會進(jìn)一步提高實(shí)現(xiàn)的代價(jià)。3)C-系統(tǒng)中符號表的組織(參見源文件Symbol.h)本編譯程序中對符號表的管理和操作在CSymbol類中實(shí)現(xiàn)，采用的是哈希雜湊表的方式。該類的聲明如下：classCSymbolpublic:CSymbol();symbol*NewSymbol(char*name,unsignedlevel);symbol*FindSymbol(char*name);boolDeleteNest(symbol*pHead);unsignedHash(char*name);virtual-CSymbol();private:Hash_Node*SymTab

32、leTABLE_LEN;類中所涉及到的結(jié)構(gòu)聲明如下:structsymbol/輸入變量名/實(shí)際變量名/當(dāng)前嵌套級/變量類型/指向同層的下一個(gè)變量charnameNAME_MAX+1;charrnameNAME_MAX+1;unsignedlevel;type*pType;symbol*next;structHash_NodeHash_Node*pre;Hash_Node*next;symbol*sym;/上一個(gè)沖突節(jié)點(diǎn)/下一個(gè)沖突節(jié)點(diǎn)/指向此節(jié)點(diǎn)上的變量CSymbol采用哈希表來實(shí)現(xiàn)對變量的管理和查找。變量表采用數(shù)組實(shí)現(xiàn)，對于每一個(gè)產(chǎn)生哈系沖突的變量節(jié)點(diǎn)，利用鏈表將其連接到已有的節(jié)點(diǎn)后。在本編

33、譯程序中，采用了較復(fù)雜的計(jì)算哈系值的算法，其偽碼如下：unsignedCSymbol:Hash(char*name)hash_val=0;for(制變量名中的每一個(gè)字符)hash_val=(hash_val<<2)+變量字符值;if(i=hash_val&0x3fff)hash_val=(hash_valA(i>>12)&0x3fff;返回hash_val;CSymbol類中兩個(gè)主要的成員函數(shù)是：symbol*FindSymbol(char*name),實(shí)現(xiàn)根據(jù)變量名，在變量表中查找該一項(xiàng)。-symbol*NewSymbol(char*name,unsi

34、gnedlevel),實(shí)現(xiàn)在變量表中力入個(gè)symbol項(xiàng)。4)其他主要結(jié)構(gòu)定義(參見源文件structtypeunsignednoun;intnum_ele;intv_int;一Structs.h)/CHARINTnumberofelementsifarrayValueifconstantstructvaluecharnameNAME_MAX*2;type*pType;symbol*sym;boollvalue;boolis_tmp;unsignedoffset;/Operandthataccessesthevalue/Variable'stype/Originalsymbol/TRU

35、E=lvalue,FALSE=rvalue/TRUE=temp,FALSE=non-temp/Abolutevalueofoffsetfrombaseoftemp/stack;3. 5系統(tǒng)中局部變量的處理雖然本編譯程序采用預(yù)分配棧來存放局部變量，這樣的做法浪費(fèi)空間且缺乏靈活性，但是它帶來的一個(gè)好處是局部變量可以回收，而不像很多編譯程序存在著局部變量無法回收的缺憾。處理局部變量的主要函數(shù)有(參見源文件Functions.h及Functions.cpp):voidfigure_local_offsets(symbol*s);voidrelease_local(symbol*s);函數(shù)巾gure_l

36、ocal_offsets為一個(gè)層中的局部變量分配空間，而函數(shù)release_local則釋放在某一層灰行疝寸釋放其中的所有變量。這可以通過遍歷雜湊鏈表中的該層一的變量鏈表(單向鏈表)得到所有變量的存儲總長度，然后把局部變量堆棧指針減掉這個(gè)長度就可以了。這樣該層的所有變量所占的空間都釋放掉了。下一次又可以使用這些釋放的空間。4. 6系統(tǒng)中臨時(shí)變量的處理臨時(shí)變量是編譯系統(tǒng)中使用較多的部分，通過建立臨時(shí)變量來記錄每一次運(yùn)算的結(jié)果，使后續(xù)的運(yùn)算能方便地引用前次的值，是一個(gè)較通用的方法。所以，臨時(shí)變量的管理成為編譯程序中一個(gè)比較重要的部分。因?yàn)楸揪幾g程序的條件限制，系統(tǒng)中對臨時(shí)變量的處理采取棧式結(jié)構(gòu)存放

37、的方法。存放臨時(shí)變量的堆棧是系統(tǒng)全局的，通過在編譯程序初始化是建立，如下：fprintf(OutPut,"t%stdbt%ddup(?)nn",TMP_STACK,TMP_STACK_LEN);此語句將在匯編源代碼中生成如下的語句：t_stackdb1024dup(?)系統(tǒng)通過一個(gè)布爾型數(shù)組對臨時(shí)變量棧進(jìn)行管理。boolTmp_RegTMP_STACK_LEN;Tmp_Regoffset的值表示臨時(shí)變量棧中偏移量為offset的空間是否已被分配為臨時(shí)變量的存放。系統(tǒng)使用以下4個(gè)函數(shù)完成對臨時(shí)變量的管理:inttmp_a110c(intsize)；value*tmp_create(type*t)；voidtmp_free(intoffset,intsize)；voidtmp_freeall(void)；3.7系統(tǒng)中代碼的生成編譯程序中的翻譯的推導(dǎo)規(guī)則和每一個(gè)推導(dǎo)的相應(yīng)動作，生成匯編源代碼。(詳見程序清單)主程序框架的生成通過函數(shù)voidInit(void)和voidEnd(void)完成。Init主要任務(wù)： 生成數(shù)據(jù)段、代碼段； 生成主程序的起始代碼； 返回地址入棧； 創(chuàng)建全局和系統(tǒng)堆棧； 初始化系統(tǒng)變量。End主要任務(wù)： 生成返回操作系