簡單的C語言編譯器.

1、中國好資料一個簡單的C語言編譯器一小組成員朱嘉?。?991102161） 計(jì)算機(jī)996王筱（3991102168） 計(jì)算機(jī)996朱杭（3991102162） 計(jì)算機(jī)996朱林（3991102094） 計(jì)算機(jī)994 二運(yùn)行方式 在DOS環(huán)境下運(yùn)行: Cminus.exe <filename> -h三概述 經(jīng)過一段時間的學(xué)習(xí)，我們在初步掌握了編譯器的基本原理以后，設(shè)計(jì)了一個具有基本編譯功能的編譯器。該編譯器接受類C語言語法的源代碼輸入，輸出結(jié)果是PC機(jī)的匯編源代碼。在捆綁了宏匯編編譯器Masm后，即可直接生成MSDOS下的二進(jìn)制可執(zhí)行文件。為方便起見，以下簡稱為C語言編譯器。 本編譯器

2、實(shí)現(xiàn)了基本高級語言所必須的語法要素，包括簡單變量聲明、函數(shù)的實(shí)現(xiàn)、整數(shù)和字符串運(yùn)算、條件判斷語句和循環(huán)語句及跳轉(zhuǎn)語句、基本代數(shù)運(yùn)算、賦值等，還支持匯編語言嵌入。本編譯器是利用編譯器生成器Parse Generator和VC6.0在Windows平臺上實(shí)現(xiàn)的，并開發(fā)了一個基于Windows平臺的32位編譯集成開發(fā)環(huán)境CompilerMan， 提供了關(guān)鍵字彩色提示、出錯同屏提示、出錯代碼跳轉(zhuǎn)等較為完善方便的功能。 由于編譯程序本身涉及到詞法分析、語法分析、代碼生成、錯誤恢復(fù)和優(yōu)化等諸多模塊，要在實(shí)驗(yàn)中做到面面俱到不太可能，所以本編譯器不可避免的會存在各種問題，但作為一個具有基本功能的、可擴(kuò)充的系統(tǒng)

3、，完全達(dá)到了鞏固編譯原理的理論知識，并將其運(yùn)用于實(shí)踐的目的。 四背景 編譯程序，就是一種具有編撰和翻譯功能的程序。人們要用計(jì)算機(jī)來解決問題，首先面臨的一個問題，就是要告訴計(jì)算機(jī)解決什么問題，或者告訴計(jì)算機(jī)如何解決這個問題。這就涉及到用什么樣的語言來描述的問題，人所習(xí)慣的自然語言和計(jì)算機(jī)認(rèn)識的機(jī)器語言有很大的差別，用機(jī)器語言來描述人想解決的問題十分不便，因而，計(jì)算機(jī)科學(xué)家設(shè)計(jì)一些人們比較習(xí)慣的語言來描述要解決的問題，稱之為高級語言。用語言來描述的問題，統(tǒng)稱為程序。然而，用高級語言寫的程序，不能被計(jì)算機(jī)所直接認(rèn)識和理解，必須經(jīng)過等價的轉(zhuǎn)換，變成機(jī)器能理解并執(zhí)行的機(jī)器語言的程序。進(jìn)行這種等價轉(zhuǎn)換工作

4、的工具，就是編譯程序。1編譯程序的結(jié)構(gòu)編譯程序是很復(fù)雜的，但它可被分為相對獨(dú)立的幾個部分，每個部分承擔(dān)專門的工作，各部分間互相共享傳送數(shù)據(jù)。把編譯程序分解成較小的部分，不僅便于開發(fā)、調(diào)試，而且便于編譯程序的移植。一個典型的編譯程序通常具有如圖1的結(jié)構(gòu)。出錯處理符號表管理目標(biāo)機(jī)器碼IRIR中間語言語法結(jié)構(gòu)單詞代碼生成器優(yōu)化器語義分析器語法分析器詞法分析器圖1 編譯器基本結(jié)構(gòu)1.1 詞法分析詞法分析負(fù)責(zé)對源程序的字符串進(jìn)行掃描和分解，根據(jù)構(gòu)詞法將字符流(Character Stream)轉(zhuǎn)化成單詞流(Token Stream)。例如對于C-語句： x = y + z m * 10;詞法分析的結(jié)果是

5、： ID ASSIGN ID ADD ID SUB ID MUL NUM SEMI 構(gòu)詞的規(guī)則就是詞法，例如標(biāo)識符(ID)可定義為以字母開頭，后面跟零個或任意個字母或數(shù)字的序列。詞法分析程序就根據(jù)詞法構(gòu)造有限自動機(jī)來識別每一個單詞，將產(chǎn)生的單詞交給語法分析程序。1.2 語法分析語法分析模塊的任務(wù)是根據(jù)文法規(guī)則把單詞序列分解成各類語法單位，識別出一個一個句子，例如對前面的語句進(jìn)行語法分析可得到如圖2的分析樹。 如果輸入單詞不能構(gòu)成語法樹，則說明有語法錯誤。常見的語法分析方法分為自頂向下分析和自底向上分析兩大類。在C-編譯器中采用了一種自底向上的方法，即LR方法。圖2 語法分析樹NUM項(xiàng)ID項(xiàng)*表

6、達(dá)式IDID-項(xiàng)表達(dá)式+項(xiàng)表達(dá)式=變量賦值語句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)由于中間語言對后面的代碼優(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)代碼生成是編譯最后一個階段，它把中間代碼

7、轉(zhuǎn)換成匯編指令或可重定位的目標(biāo)代碼。例如對于前面生成的中間代碼，可以產(chǎn)生IBM PC匯編指令為：mov ax, mmul ax, 10 mov bx, zsub bx,axadd bx,ymov x, bx匯編代碼經(jīng)過Masm匯編器(Assembler)和連接器(Linker)處理，就產(chǎn)生了可在IBM PC機(jī)器上運(yùn)行的二進(jìn)制代碼。2形式語言簡介2.1 文法和語言文法是產(chǎn)生語言的規(guī)則，它可定義為：對于一個四元式G=(VN，VT，S，P)，其中(1) VN是非終結(jié)符號的有限集合(2) VT是終結(jié)符號的有限集合，且VTVN(3) 開始符號S，SVN(4) 一組產(chǎn)生式P，P中的每一個產(chǎn)生式都具有如下形

8、式：uv，u(VNVT)+且至少要有一個非終結(jié)符號，v(VNVT)*則G表示一個文法。喬姆斯基(Noam Chmosky)把文法分成四類：0型文法又稱無約束文法，產(chǎn)生式的形式為ab，a、b是任意字符串。1型文法又稱上下有關(guān)文法，產(chǎn)生式形式為ab，且|a|b|。2型文法又稱上下文無關(guān)文法(Context-Free Grammar)，產(chǎn)生式形式為Aa，a(VNVT)*，AVN。3型文法又稱正規(guī)文法，它的產(chǎn)生式左部是一個非終結(jié)符號，右部最多只有一個非終結(jié)符號且在右部的最左端或最右端。通常程序設(shè)計(jì)語言的文法屬于2型文法，可被下推機(jī)(Pushdown Automaton)識別。語言定義為L(G)=w|S

9、=>*w,wVT*，可見，文法G中的VT相當(dāng)于產(chǎn)生語言的字母表，G中的一組產(chǎn)生式是產(chǎn)生語言的一組規(guī)則；語言L(G)中的每一個句子w，是由G的開始符號S經(jīng)推導(dǎo)得到的，完全由終結(jié)符號組成的字。非終結(jié)符號是引起推導(dǎo)繼續(xù)進(jìn)行的中間符號，在推導(dǎo)進(jìn)行到某一步時，如果再沒有非終結(jié)符號留在推導(dǎo)的結(jié)果中，則稱推導(dǎo)成功。在語言的設(shè)計(jì)和編譯器的編寫方面，文法都提供了極大的優(yōu)點(diǎn)：a) 文法給出了精確的，也易于理解的語言語法說明。b) 對于某些文法類，可以自動產(chǎn)生高效的分析器。額外的好處是，分析器的構(gòu)造過程可以揭露出語法的二義性和其它難于分析的結(jié)構(gòu)，這些問題在語言和它的編譯器的最初設(shè)計(jì)階很可能沒有發(fā)現(xiàn)。c) 設(shè)計(jì)

10、得漂亮的文法，把結(jié)構(gòu)加于程序設(shè)計(jì)語言，這些結(jié)構(gòu)對把源程序翻譯成為正確的目標(biāo)代碼和錯誤診斷都是有用的。把以文法為基礎(chǔ)的翻譯的描述轉(zhuǎn)變成程序的開發(fā)工具也是存在的。d) 語言也是逐漸完善的，需要補(bǔ)充新的結(jié)構(gòu)和完成附加的任務(wù)。如果存在以文法為基礎(chǔ)的語言的實(shí)現(xiàn)，這些新結(jié)構(gòu)的加入就更方便。 2.2 巴科斯范式 （BNF）巴科斯范式(Backus Normal Form,BNF)是描述語法規(guī)則的一種形式方法，在該方法中，使用如下符號：< > 非終結(jié)號:= 定義符| 或者 括號內(nèi)的成份可以重復(fù)出現(xiàn)多次，也可以不出現(xiàn) 括號內(nèi)的成份為任選項(xiàng)，可以出現(xiàn)一次或不出現(xiàn)例如C語言中IFTHEN語句可以表示成：

11、<IF語句> := IF <布爾表達(dá)式> THEN <語句> <ELSE語句>用巴科斯范式的形式表示文法的優(yōu)點(diǎn)是簡潔、清楚并容易被理解。3編譯程序的實(shí)現(xiàn)環(huán)境Parse Generator簡介及其使用編譯器生成工具-Parse Generator 基于 Windows平臺，它集成了詞法生成器ALEX和語法生成器AYACC，并提供了較為強(qiáng)大的類庫。其主要優(yōu)點(diǎn)體現(xiàn)在以下幾個方面：l 可以視一個編譯程序?yàn)橐粋€Project，集成Alex和Ayacc文件的環(huán)境有利于整體調(diào)試和開發(fā)。且編輯界面友好，利于初學(xué)者使用。l .l文件（lex文件）和.y文件（yac

12、c文件）可生成為標(biāo)準(zhǔn)的C原代碼，也可生成Visual C+和Borland C+格式的原代碼。這對習(xí)慣與BC或VC編程的程序員，無疑是極大的方便。l ALex和AYacc的表驅(qū)動代碼隱藏在聯(lián)接庫中。庫在程序LINK的時候連入系統(tǒng)中。這在程序編譯的效率和靈活性兩個方面都有較大貢獻(xiàn)。l ALex和AYacc的原代碼和和生成的目標(biāo)代碼（C或C+）可以建立語句的對應(yīng)，這對生成代碼的調(diào)試提供很大方便。 實(shí)驗(yàn)中的編譯程序采用將ALex和AYacc文件轉(zhuǎn)化為Visual C+格式的代碼?，F(xiàn)將程序中使用的聯(lián)接庫中主要類和函數(shù)作一介紹。l 類yylexer - 所有詞法分析器類的基類 yylexer類提供由Al

13、ex生成的C+詞法分析器的一切基本功能。 yylexer是一個抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yylex 和 yyaction。 C-編譯器程序中的詞法分析器類是其子類C_Lexer類。 l 類 yyparser - 所有語法分析器類的基類 yyparser類提供由AYacc生成的C+語法分析器的一切基本功能。yyparser是一個抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yywork 和 yyparseaction。 C-編譯器程序中的語法分析器類是其子類C_Parser類。五詳 細(xì) 設(shè) 計(jì)1功能說明輸入：類C語言純文本源程序。輸出：·目標(biāo)機(jī)為具有80

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

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

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

17、)、(U.V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U) L(V)、L(U)L(V)和(L(U)*。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)所表示的字集才是上的正規(guī)集。正規(guī)式可以有效地描述詞法，而確定的有限自動機(jī)(DFA)能準(zhǔn)確地識別正規(guī)集，執(zhí)行詞法分析的功能。22 利用有限自動機(jī)進(jìn)行詞法分析 詞法分析是整個編譯過程的第一階段，它將字符序列轉(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

18、為接收態(tài)，若對于一個字符序列有限自動機(jī)可以到達(dá)2狀態(tài)，則說明一個整數(shù)已被識別出來。詞法分析器構(gòu)造程序LEX正是根據(jù)這一原理工作的。構(gòu)造詞法分析器的主要任務(wù)是設(shè)計(jì)詞法的正規(guī)定義和相關(guān)的動作。上面例子的LEX程序段就是：1-9+0-9*return ICON;23 C-詞法分析器的實(shí)現(xiàn)·數(shù)據(jù)結(jié)構(gòu)1）關(guān)鍵字和系統(tǒng)標(biāo)識符表 Ktab 保存關(guān)鍵字和系統(tǒng)標(biāo)識符的信息，定義如下： typedef struct char *name; int val; KWORD;其中·name域保存關(guān)鍵字的名字，val域保存關(guān)鍵字的種類標(biāo)識。·val域就是詞法分析器傳遞給語法分析器的終結(jié)符信息

19、。2）C-中的關(guān)鍵字 以下為Ktab數(shù)組的定義：KWORD Ktab = "break",BREAK,"char",TYPE,"continue",CONTINUE,"do",DO,"else",ELSE,"for",FOR,"goto",GOTO,"if",IF,"int",TYPE,"main",MAIN,"print",PRINT,"while",WH

20、ILE; ·具體實(shí)現(xiàn)（參見源文件C-_lex.l）1） 對注釋的處理：支持/*.*/和/兩種注釋風(fēng)格，對于注釋內(nèi)容在匹配到/* 和 / 后，直接通過動作input跳過。處理了注釋符號遺漏的情況，并有出錯信息顯示。2） 常數(shù)的處理：詞法分析器可識別十進(jìn)制、八進(jìn)制和十六進(jìn)制無符號整數(shù)以及字符常數(shù)（形為a），并通過函數(shù)int stoi(char *string, int radix)轉(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_keyw

21、ord返回相應(yīng)的標(biāo)識（token）。返回值相同的，可以通過yytext區(qū)別。· 對于用戶自定義的標(biāo)識符，函數(shù)id_or_keyword返回NAME。為了提高查找關(guān)鍵字和系統(tǒng)標(biāo)識符表的效率，函數(shù)id_or_keyword采用二分查找法（bsearch函數(shù)）。5） 嵌入?yún)R編（_asm）的處理：在函數(shù)id_or_keyword（）中當(dāng)遇到y(tǒng)ytext=“_asm”時，則進(jìn)入嵌入?yún)R編處理代碼：先匹配字符，如果接下來的第一個字符不是，則打印出錯信息。如果匹配則將后續(xù)代碼原樣寫入?yún)R編代碼中，直至遇到字符結(jié)束；如果未遇到則打印出錯信息。由于要防止嵌入?yún)R編代碼中出現(xiàn)字符立即操作數(shù)或注釋語句中的，因此

22、要考慮這些情況。采用上述方法的好處是大大簡化了語法分析器的工作，不必設(shè)計(jì)大量的產(chǎn)生式來處理匯編格式。但是這樣就不能檢查嵌入?yún)R編的語法錯誤?？梢圆捎眠@樣的方法：用Masm編譯嵌入的代碼，重定向其輸出而判斷有無匯編語法錯誤。6）生成的C_Lexer 的類定義（參見源文件C-_lex.h）： class C_Lexer : public yyflexer public: 嵌入 C_Lexer (); protected: void yytables(); virtual int yyaction(int action); public: ; C_Lexer () 實(shí)現(xiàn)對詞法分析器對象的初始化，它調(diào)用

23、yytables()。 yyaction()則具體由定義的正則表達(dá)式實(shí)現(xiàn)歸約。3語法分析器（parser）31 上下文無關(guān)文法 上下文無關(guān)文法G可以用一個四元組表示G(V,T,P,S)其中：·V是文法的非終結(jié)符號集，每個非終結(jié)符號表示語言的一個語法變量；·T是終結(jié)符號集，每個終結(jié)符號表示語言的一個基本符號，即詞匯；·P是產(chǎn)生式集，文法用產(chǎn)生式定義每個非終結(jié)符號；·S是V中的一個非終結(jié)符號，稱開始符號。文法的每個產(chǎn)生式由左、右兩部分組成，左部是一個非終結(jié)符號；右部是由零個或若干個終結(jié)符、非終結(jié)符組成的符號串。32 LR分析方法LR分析方法是自底向上進(jìn)行語法

24、分析，它的功能很強(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)行識別。·LR分析法是具有一般性的無回溯移進(jìn)歸約分析法，并且能有效地被實(shí)現(xiàn)。·能用LR分析器分析的文法類包含能用LL(1)分析器分析的全部文法類。·LR分析器在自左向右掃描輸入時，可以盡可能地發(fā)現(xiàn)語法錯誤。圖 4 LR分析器圖4是LR分析器的結(jié)構(gòu)示意。其中分析棧存放狀態(tài)和移進(jìn)、歸約的文法符號： S0X1S1.Xm-1Sm-1S0其中，Si表示狀態(tài)，Xi

25、表示文法符號；在實(shí)現(xiàn)中，文法符號不必進(jìn)分析棧。動作表中的項(xiàng)目ACTIONSm,ai表示當(dāng)前輸入符號為ai、棧頂狀態(tài)為Sm時，分析算法應(yīng)執(zhí)行的動作；若ACTIONSm,aiSi，表示移進(jìn)，然后棧頂狀態(tài)為i;rj表示用產(chǎn)生式j(luò)歸約；acc表示接收輸入串，err表示語法錯誤。狀態(tài)轉(zhuǎn)換表中的項(xiàng)目GOTOSi,X表示歸約出非終結(jié)符號X之后，當(dāng)前棧頂狀態(tài)為Si時，分析棧應(yīng)轉(zhuǎn)換到的下一上狀態(tài)，即棧頂?shù)男聽顟B(tài)。LR分析算法為： 根據(jù)輸入符號ai、棧頂狀態(tài)Sm和動作表項(xiàng)actionSm,ai的值，決定當(dāng)前分析應(yīng)執(zhí)行的動作；移進(jìn)、歸約、接收或出錯；移進(jìn)或歸約之后要根據(jù)動作表或狀態(tài)轉(zhuǎn)換表設(shè)置分析棧的狀態(tài)。 可以把分

26、析棧中的串和等待輸入的終結(jié)答號串看成是兩個分量，這兩個分量構(gòu)成如下形式的二元組： (S0X1S1X2S2.XmSm , aiai+1.an#)這個二元組結(jié)構(gòu)表示右句型 X1X2.Xmaiai+1.an#假定當(dāng)前分析棧的棧頂為狀態(tài)Sm，下一個輸入符號為ai，分析器的下一個動作由動作表項(xiàng)actionSm,ai決定。 ·如果actionSm,ai移進(jìn)S，則分析器執(zhí)行移進(jìn)，二元組變成 (S0X1S1X2S2.XmSmaiS , ai+1.an#) 即分析器將輸入符號ai和狀態(tài)S移進(jìn)棧，于是，ai+1變成下一個輸入符號。 ·如果actionSm,ai歸約A則分析器執(zhí)行歸約，二元組變成

27、 (S0X1S1X2S2.Xm-rSm-rAS , ai+1.an#)其中，S由goto表確定：S = gotoSm-r,ai，r=|，是句柄號串的長度。歸約時，分析器先從棧中彈出2r個元素：r個狀態(tài)和r個文法符號；于是使?fàn)顟B(tài)Sm-r出現(xiàn)在棧頂；然后，再把歸約產(chǎn)生式左部的非終結(jié)符A和由gotoSm-r,A確定的狀態(tài)S壓入棧。在歸約過程中不改變輸入符號。對LR分析器來說，從棧中彈出的文法符號串Xm-r+1.Xm總是匹配歸約產(chǎn)生式的右部。 ·如果actionSm,aiacc，則接收輸入符號串，語法分析完成 ·如果actionSm,aierr，則發(fā)現(xiàn)語法錯誤，調(diào)用錯誤處理子程序。

28、33 C-系統(tǒng)中使用的主要產(chǎn)生式（參見源文件C-_par.h）program :MAIN LP RP compound_stmtcompound_stmt :LC local_defs stmt_list RClocal_defs :def_listdef_list :def_list def |/* epsilon */def:specifiers decl_listSEMIdecl_list :var_decl |decl_list COMMA var_declvar_decl :new_name|var_decl LB ICON RB|LP var_decl RPnew_name :NA

29、MEspecifiers :TYPEstmt_list :stmt_list statement |/* epsilon */statement :SEMI |compound_stmt|PRINT LP expr COMMA DIVOP ICON RP SEMI|expr SEMI|GOTO target SEMI|target COLONstatement|IF LP test RP statement|IF LP test RP statement ELSEstatement|WHILE LP test RPstatement|DOstatement WHILELP test RP SE

30、MI|FOR LP opt_expr SEMI test SEMI opt_expr RPstatement|BREAK SEMI|CONTINUE SEMItest :expr| /* epsilon */target :NAMEopt_expr :exprexpr :expr COMMAnon_comma_expr :non_comma_expr EQUAL non_comma_expr| non_comma_expr ASSIGNOP non_comma_expr|or_expror_expr :or_listor_list :or_list ORORand_expr| and_expr

31、and_expr :and_listand_list :and_list ANDANDbinary|binarybinary : binary RELOP binary|binary POWER binary| |unaryunary : LP expr RP|34 系統(tǒng)中符號表的實(shí)現(xiàn)1）符號表的組織要求 編譯程序用符號表跟蹤關(guān)于名稱的匯聚信息和作用域，當(dāng)詞法分析器識別出一個標(biāo)識符后，編譯程序就查找符號表，看它是否在符號表中，如果沒有，則把這個新標(biāo)識符填入符號表。在語義分析階段和代碼生成階段也要通過查找符號表來獲得標(biāo)識符的屬性信息。可見在編譯過程中符號表的查、填動作非常頻繁，因而提高符號表查填

32、效率是提高編譯程序運(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ù)雜度較高。對于名稱沖 突也要特別處理。在某些情況下，二叉樹

33、會退化成線性表，這個問題可以 通過采用AVL樹的結(jié)構(gòu)來解決，但這會進(jìn)一步提高實(shí)現(xiàn)的代價。 3）C-系統(tǒng)中符號表的組織（參見源文件Symbol.h） 本編譯程序中對符號表的管理和操作在CSymbol類中實(shí)現(xiàn)，采用的是哈希雜湊表的方式。 該類的聲明如下：class CSymbol public:CSymbol();symbol *NewSymbol(char *name, unsigned level);symbol *FindSymbol(char *name);bool DeleteNest(symbol *pHead);unsigned Hash(char *name);virtual CS

34、ymbol();private:Hash_Node *SymTableTABLE_LEN;類中所涉及到的結(jié)構(gòu)聲明如下：struct symbolchar nameNAME_MAX+1;/輸入變量名char rnameNAME_MAX+1;/實(shí)際變量名unsigned level;/當(dāng)前嵌套級type *pType;/變量類型symbol *next;/指向同層的下一個變量;struct Hash_NodeHash_Node *pre;/上一個沖突節(jié)點(diǎn)Hash_Node *next;/下一個沖突節(jié)點(diǎn)symbol *sym;/指向此節(jié)點(diǎn)上的變量; CSymbol采用哈希表來實(shí)現(xiàn)對變量的管理和查找。

35、變量表采用數(shù)組實(shí)現(xiàn)，對于每一個產(chǎn)生哈系沖突的變量節(jié)點(diǎn)，利用鏈表將其連接到已有的節(jié)點(diǎn)后。在本編譯程序中，采用了較復(fù)雜的計(jì)算哈系值的算法，其偽碼如下：unsigned CSymbol:Hash(char *name)hash_val = 0;for(對變量名中的每一個字符)hash_val = (hash_val << 2) + 變量字符值;if(i = hash_val & 0x3fff)hash_val = (hash_val (i >> 12) & 0x3fff;返回hash_val;CSymbol類中兩個主要的成員函數(shù)是：·symbol *

36、FindSymbol(char *name)，實(shí)現(xiàn)根據(jù)變量名，在變量表中查找該一項(xiàng)。·symbol*NewSymbol(char *name, unsigned level)，實(shí)現(xiàn)在變量表中加入一個symbol項(xiàng)。4) 其他主要結(jié)構(gòu)定義（參見源文件Structs.h）struct typeunsigned noun;/CHAR INTint num_ele;/number of elements if arrayint v_int;/Value if constant;struct valuechar nameNAME_MAX * 2;/Operand that accesses t

37、he valuetype *pType;/Variable's typesymbol *sym;/Original symbolbool lvalue;/TRUE = lvalue, FALSE = rvaluebool is_tmp;/TRUE = temp, FALSE = non-tempunsigned offset;/Abolute value of offset from base of temp /stack;35 系統(tǒng)中局部變量的處理雖然本編譯程序采用預(yù)分配棧來存放局部變量，這樣的做法浪費(fèi)空間且缺乏靈活性，但是它帶來的一個好處是局部變量可以回收，而不像很多編譯程序存在著

38、局部變量無法回收的缺憾。處理局部變量的主要函數(shù)有（參見源文件Functions.h及Functions.cpp）：void figure_local_offsets(symbol *s);void release_local(symbol *s);函數(shù)figure_local_offsets為一個層中的局部變量分配空間，而函數(shù)release_local則釋放在某一層執(zhí)行完時釋放其中的所有變量。這可以通過遍歷雜湊鏈表中的該層的變量鏈表（單向鏈表）得到所有變量的存儲總長度，然后把局部變量堆棧指針減掉這個長度就可以了。這樣該層的所有變量所占的空間都釋放掉了。下一次又可以使用這些釋放的空間。36 系統(tǒng)

39、中臨時變量的處理臨時變量是編譯系統(tǒng)中使用較多的部分，通過建立臨時變量來記錄每一次運(yùn)算的結(jié)果，使后續(xù)的運(yùn)算能方便地引用前次的值，是一個較通用的方法。所以，臨時變量的管理成為編譯程序中一個比較重要的部分。· 因?yàn)楸揪幾g程序的條件限制，系統(tǒng)中對臨時變量的處理采取棧式結(jié)構(gòu)存 放的方法。存放臨時變量的堆棧是系統(tǒng)全局的，通過在編譯程序初始化是建立，如下：fprintf(OutPut,"t%stdbt%d dup(?)nn", TMP_STACK, TMP_STACK_LEN);此語句將在匯編源代碼中生成如下的語句：t_stackdb1024 dup(?)·系統(tǒng)通過一

40、個布爾型數(shù)組對臨時變量棧進(jìn)行管理。bool Tmp_RegTMP_STACK_LEN;Tmp_Regoffset的值表示臨時變量棧中偏移量為offset的空間是否已被分配為臨時變量的存放。·系統(tǒng)使用以下4個函數(shù)完成對臨時變量的管理：int tmp_alloc(int size)；value *tmp_create(type *t)；void tmp_free(int offset, int size)；void tmp_freeall(void)；37 系統(tǒng)中代碼的生成 編譯程序中的翻譯的推導(dǎo)規(guī)則和每一個推導(dǎo)的相應(yīng)動作，生成匯編源代碼。（詳見程序清單）·主程序框架的生成通過函數(shù)void Init(void) 和void End(void)完成。 Init主要任務(wù)：·生成數(shù)據(jù)段、代碼段；·生成主程序的起始代碼；·返回地址入棧；·創(chuàng)建全局和系統(tǒng)堆棧；·初始化系統(tǒng)變量。End主要任務(wù)：·生成返回操作系統(tǒng)代碼；·結(jié)束代碼段；·結(jié)束