簡(jiǎn)單的C語(yǔ)言編譯器

1、中國(guó)好資料一個(gè)簡(jiǎn)單的C語(yǔ)言編譯器一小組成員朱嘉?。?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 -h三概述 經(jīng)過(guò)一段時(shí)間的學(xué)習(xí)，我們?cè)诔醪秸莆樟司幾g器的基本原理以后，設(shè)計(jì)了一個(gè)具有基本編譯功能的編譯器。該編譯器接受類C語(yǔ)言語(yǔ)法的源代碼輸入，輸出結(jié)果是PC機(jī)的匯編源代碼。在捆綁了宏匯編編譯器Masm后，即可直接生成MSDOS下的二進(jìn)制可執(zhí)行文件。為方便起見(jiàn)，以下簡(jiǎn)稱為C語(yǔ)言編譯器。 本編譯器實(shí)現(xiàn)了基本高級(jí)語(yǔ)言所必須的語(yǔ)法要素

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

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

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

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

6、變量賦值語(yǔ)句1.3 語(yǔ)義分析 這一階段部分是根據(jù)前一階段產(chǎn)生的語(yǔ)法樹(shù)，按語(yǔ)言的語(yǔ)義進(jìn)行翻譯，產(chǎn)生四元式或三元式等中間語(yǔ)言。中間語(yǔ)言可以很方便地轉(zhuǎn)換成目標(biāo)代碼。前面的語(yǔ)法樹(shù)可能產(chǎn)生的四元式序列為： (*,_t0,10,m)(-,_t1,z,_t0)(+,_t0,y,_t1)(=,x,_t0)由于中間語(yǔ)言對(duì)后面的代碼優(yōu)化和目標(biāo)代碼生成有密切關(guān)系，又和目標(biāo)機(jī)器的體系結(jié)構(gòu)有關(guān)，所以中間語(yǔ)言的選擇對(duì)于編譯器的效率和質(zhì)量有很大的影響。1.4 代碼優(yōu)化 代碼優(yōu)化是把中間代碼進(jìn)行變換，以產(chǎn)生更加高效的目標(biāo)代碼。1.5 目標(biāo)代碼生成 目標(biāo)代碼生成是編譯最后一個(gè)階段，它把中間代碼轉(zhuǎn)換成匯編指令或可重定位的目標(biāo)代碼

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

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

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

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

11、潔、清楚并容易被理解。3編譯程序的實(shí)現(xiàn)環(huán)境Parse Generator簡(jiǎn)介及其使用編譯器生成工具-Parse Generator 基于 Windows平臺(tái)，它集成了詞法生成器ALEX和語(yǔ)法生成器AYACC，并提供了較為強(qiáng)大的類庫(kù)。其主要優(yōu)點(diǎn)體現(xiàn)在以下幾個(gè)方面：l 可以視一個(gè)編譯程序?yàn)橐粋€(gè)Project，集成Alex和Ayacc文件的環(huán)境有利于整體調(diào)試和開(kāi)發(fā)。且編輯界面友好，利于初學(xué)者使用。l .l文件（lex文件）和.y文件（yacc文件）可生成為標(biāo)準(zhǔn)的C原代碼，也可生成Visual C+和Borland C+格式的原代碼。這對(duì)習(xí)慣與BC或VC編程的程序員，無(wú)疑是極大的方便。l ALex和A

12、Yacc的表驅(qū)動(dòng)代碼隱藏在聯(lián)接庫(kù)中。庫(kù)在程序LINK的時(shí)候連入系統(tǒng)中。這在程序編譯的效率和靈活性兩個(gè)方面都有較大貢獻(xiàn)。l ALex和AYacc的原代碼和和生成的目標(biāo)代碼（C或C+）可以建立語(yǔ)句的對(duì)應(yīng)，這對(duì)生成代碼的調(diào)試提供很大方便。 實(shí)驗(yàn)中的編譯程序采用將ALex和AYacc文件轉(zhuǎn)化為Visual C+格式的代碼?，F(xiàn)將程序中使用的聯(lián)接庫(kù)中主要類和函數(shù)作一介紹。l 類yylexer - 所有詞法分析器類的基類 yylexer類提供由Alex生成的C+詞法分析器的一切基本功能。 yylexer是一個(gè)抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yylex 和 yyaction。 C-編譯器程

13、序中的詞法分析器類是其子類C_Lexer類。 l 類 yyparser - 所有語(yǔ)法分析器類的基類 yyparser類提供由AYacc生成的C+語(yǔ)法分析器的一切基本功能。yyparser是一個(gè)抽象類，要使用它，必須繼承出自己的類，并實(shí)現(xiàn)抽象函數(shù)yywork 和 yyparseaction。 C-編譯器程序中的語(yǔ)法分析器類是其子類C_Parser類。五詳 細(xì) 設(shè) 計(jì)1功能說(shuō)明輸入：類C語(yǔ)言純文本源程序。輸出：目標(biāo)機(jī)為具有8086+處理器的MSDOS系統(tǒng)下的二進(jìn)制可執(zhí)行代 碼。PC Assembly Language匯編語(yǔ)言源代碼以供分析使用。本編譯程序?qū)崿F(xiàn)的主要功能如下表所示：功能備注支持以下數(shù)

14、據(jù)類型：int 整型char 字符型char 字符數(shù)組int 整型數(shù)組整型為有符號(hào)16位數(shù)。字符型為8位數(shù)。數(shù)組的下標(biāo)允許為任何合法的表達(dá)式。經(jīng)過(guò)簡(jiǎn)單擴(kuò)充后，即可實(shí)現(xiàn)長(zhǎng)整型，無(wú)符號(hào)整型。支持以下數(shù)據(jù)操作：+ 加法- 減法* 乘法/ 除法% 取余+ 自加1- 自減1* 乘方&, | 位與，位或 異或 位非&,| 邏輯與，邏輯或！ 邏輯非,= 關(guān)系比較運(yùn)算=，！= 關(guān)系比較運(yùn)算 算術(shù)移位+-*/%=，*=， 多達(dá)12種賦值=，&=， 語(yǔ)句|=，=，=支持以關(guān)鍵字_asm前導(dǎo)的形式為_(kāi)asm 的嵌入?yún)R編代碼(EMBEDED ASSEMBLY)。對(duì)嵌入?yún)R編的支持大大提高的語(yǔ)言的可用性，一定程度彌補(bǔ)了系

15、統(tǒng)函數(shù)較少的缺憾。提供系統(tǒng)級(jí)庫(kù)函數(shù)：void print(/*表達(dá)式*/,% t)；支持字符串，字符，整型三種類型的變量輸出，包括任何合法表達(dá)式的值。支持循環(huán)，轉(zhuǎn)移，判斷分支的程序設(shè)計(jì)，支持if, if.else,if.else if.forwhile, do.whilegoto .語(yǔ)句。支持Label，允許在任何語(yǔ)句前定義Label作為控制轉(zhuǎn)移目的地。for和while語(yǔ)句支持break, continue流程控制。支持函數(shù)概念。系統(tǒng)以main函數(shù)為入口函數(shù)。支持源程序注釋。注釋以”/” 或 ”/*” ,”*/”標(biāo)示。支持出錯(cuò)提示。對(duì)于嵌入?yún)R編代碼的出錯(cuò)提示可以通過(guò)重定向匯編代碼編譯器的出錯(cuò)

16、信息實(shí)現(xiàn)。2詞法分析器（lexer）21 正規(guī)式和DFA和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)(U)和L(V)， 那么，(U|V)、(U.V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U) L(V)、L(U)L(V)和(L(U)*。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)所表示的字集才是上的正規(guī)集。正規(guī)式可以有效地描述詞法，而確定的有限自動(dòng)機(jī)(DFA)能準(zhǔn)確地識(shí)別正規(guī)集，執(zhí)行詞法分析的功能。22 利用有限自動(dòng)機(jī)進(jìn)行詞法分析 詞法分析是整個(gè)編譯過(guò)程的第

17、一階段，它將字符序列轉(zhuǎn)化為單詞序列。識(shí)別單詞的基本方法是根據(jù)詞法定義構(gòu)造有限自動(dòng)機(jī)即描述語(yǔ)言結(jié)構(gòu)特征的狀態(tài)轉(zhuǎn)換圖。例如對(duì)于十進(jìn)制整數(shù)正規(guī)定義： 1-9+0-9*可以構(gòu)造如圖3所示的有限自動(dòng)機(jī)。圖 3 識(shí)別十進(jìn)制整數(shù)的有限自動(dòng)機(jī)其中狀態(tài)2為接收態(tài)，若對(duì)于一個(gè)字符序列有限自動(dòng)機(jī)可以到達(dá)2狀態(tài)，則說(shuō)明一個(gè)整數(shù)已被識(shí)別出來(lái)。詞法分析器構(gòu)造程序LEX正是根據(jù)這一原理工作的。構(gòu)造詞法分析器的主要任務(wù)是設(shè)計(jì)詞法的正規(guī)定義和相關(guān)的動(dòng)作。上面例子的LEX程序段就是：1-9+0-9*return ICON;23 C-詞法分析器的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)1）關(guān)鍵字和系統(tǒng)標(biāo)識(shí)符表 Ktab 保存關(guān)鍵字和系統(tǒng)標(biāo)識(shí)符的信息，定義如下

18、： typedef struct char *name; int val; KWORD;其中name域保存關(guān)鍵字的名字，val域保存關(guān)鍵字的種類標(biāo)識(shí)。val域就是詞法分析器傳遞給語(yǔ)法分析器的終結(jié)符信息。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,WHILE; 具體實(shí)現(xiàn)（參見(jiàn)源文件C-_lex.l）1） 對(duì)注釋的處理：支持/*.*/和/兩

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

20、or_keyword返回NAME。為了提高查找關(guān)鍵字和系統(tǒng)標(biāo)識(shí)符表的效率，函數(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編處理代碼：先匹配字符，如果接下來(lái)的第一個(gè)字符不是，則打印出錯(cuò)信息。如果匹配則將后續(xù)代碼原樣寫入?yún)R編代碼中，直至遇到字符結(jié)束；如果未遇到則打印出錯(cuò)信息。由于要防止嵌入?yún)R編代碼中出現(xiàn)字符立即操作數(shù)或注釋語(yǔ)句中的，因此要考慮這些情況。采用上述方法的好處是大大簡(jiǎn)化了語(yǔ)法分析器的工作，不必設(shè)計(jì)大量的產(chǎn)生式來(lái)處理匯編格式。但是這樣就不能檢查嵌入?yún)R

21、編的語(yǔ)法錯(cuò)誤。可以采用這樣的方法：用Masm編譯嵌入的代碼，重定向其輸出而判斷有無(wú)匯編語(yǔ)法錯(cuò)誤。6）生成的C_Lexer 的類定義（參見(jiàn)源文件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)對(duì)詞法分析器對(duì)象的初始化，它調(diào)用yytables()。 yyaction()則具體由定義的正則表達(dá)式實(shí)現(xiàn)歸約。3語(yǔ)法分析器（parser）31 上下文無(wú)關(guān)文

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

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

24、j歸約；acc表示接收輸入串，err表示語(yǔ)法錯(cuò)誤。狀態(tài)轉(zhuǎn)換表中的項(xiàng)目GOTOSi,X表示歸約出非終結(jié)符號(hào)X之后，當(dāng)前棧頂狀態(tài)為Si時(shí)，分析棧應(yīng)轉(zhuǎn)換到的下一上狀態(tài)，即棧頂?shù)男聽(tīng)顟B(tài)。LR分析算法為： 根據(jù)輸入符號(hào)ai、棧頂狀態(tài)Sm和動(dòng)作表項(xiàng)actionSm,ai的值，決定當(dāng)前分析應(yīng)執(zhí)行的動(dòng)作；移進(jìn)、歸約、接收或出錯(cuò)；移進(jìn)或歸約之后要根據(jù)動(dòng)作表或狀態(tài)轉(zhuǎn)換表設(shè)置分析棧的狀態(tài)。 可以把分析棧中的串和等待輸入的終結(jié)答號(hào)串看成是兩個(gè)分量，這兩個(gè)分量構(gòu)成如下形式的二元組： (S0X1S1X2S2.XmSm , aiai+1.an#)這個(gè)二元組結(jié)構(gòu)表示右句型 X1X2.Xmaiai+1.an#假定當(dāng)前分析棧的棧

25、頂為狀態(tài)Sm，下一個(gè)輸入符號(hào)為ai，分析器的下一個(gè)動(dòng)作由動(dòng)作表項(xiàng)actionSm,ai決定。 如果actionSm,ai移進(jìn)S，則分析器執(zhí)行移進(jìn)，二元組變成 (S0X1S1X2S2.XmSmaiS , ai+1.an#) 即分析器將輸入符號(hào)ai和狀態(tài)S移進(jìn)棧，于是，ai+1變成下一個(gè)輸入符號(hào)。 如果actionSm,ai歸約A則分析器執(zhí)行歸約，二元組變成 (S0X1S1X2S2.Xm-rSm-rAS , ai+1.an#)其中，S由goto表確定：S = gotoSm-r,ai，r=|，是句柄號(hào)串的長(zhǎng)度。歸約時(shí)，分析器先從棧中彈出2r個(gè)元素：r個(gè)狀態(tài)和r個(gè)文法符號(hào)；于是使?fàn)顟B(tài)Sm-r出現(xiàn)在棧頂

26、；然后，再把歸約產(chǎn)生式左部的非終結(jié)符A和由gotoSm-r,A確定的狀態(tài)S壓入棧。在歸約過(guò)程中不改變輸入符號(hào)。對(duì)LR分析器來(lái)說(shuō)，從棧中彈出的文法符號(hào)串Xm-r+1.Xm總是匹配歸約產(chǎn)生式的右部。 如果actionSm,aiacc，則接收輸入符號(hào)串，語(yǔ)法分析完成 如果actionSm,aierr，則發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤處理子程序。33 C-系統(tǒng)中使用的主要產(chǎn)生式（參見(jiàn)源文件C-_par.h）program :MAIN LP RP compound_stmtcompound_stmt :LC local_defs stmt_list RClocal_defs :def_listdef_list

27、: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 :NAMEspecifiers :TYPEstmt_list :stmt_list statement |/* epsilon */statement :SEMI |compound_stmt|PRINT LP expr COMMA DIVOP ICON RP SEMI|e

28、xpr 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 SEMI|FOR LP opt_expr SEMI test SEMI opt_expr RPstatement|BREAK SEMI|CONTINUE SEMItest :expr| /* epsilon */target :NAMEopt_expr :exprexpr

29、 :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_exprand_expr :and_listand_list :and_list ANDANDbinary|binarybinary : binary RELOP binary|binary POWER binary| |unaryunary : LP expr RP|34

30、系統(tǒng)中符號(hào)表的實(shí)現(xiàn)1）符號(hào)表的組織要求 編譯程序用符號(hào)表跟蹤關(guān)于名稱的匯聚信息和作用域，當(dāng)詞法分析器識(shí)別出一個(gè)標(biāo)識(shí)符后，編譯程序就查找符號(hào)表，看它是否在符號(hào)表中，如果沒(méi)有，則把這個(gè)新標(biāo)識(shí)符填入符號(hào)表。在語(yǔ)義分析階段和代碼生成階段也要通過(guò)查找符號(hào)表來(lái)獲得標(biāo)識(shí)符的屬性信息?？梢?jiàn)在編譯過(guò)程中符號(hào)表的查、填動(dòng)作非常頻繁，因而提高符號(hào)表查填效率是提高編譯程序運(yùn)行效率的關(guān)鍵因素，也是對(duì)符號(hào)表設(shè)計(jì)的根本要求。 2）符號(hào)表的幾種組織方式線性表 符表項(xiàng)按順序排列，這種組織方式最簡(jiǎn)單并且實(shí)現(xiàn)也很容易。線性表的缺 點(diǎn)是插入和查找的效率較低，雖然可以采用反序查找、表項(xiàng)排序、動(dòng)態(tài)調(diào) 整表項(xiàng)來(lái)提高效率，但其性能的改善是很

31、有限的。哈希表 通過(guò)計(jì)算符號(hào)的哈希值來(lái)確定其在表格中的位置。哈希表結(jié)構(gòu)簡(jiǎn)單、實(shí)現(xiàn) 較容易，而且其插入和查找效率很高。采用哈希表要解決“沖突”的問(wèn)題， 而解決沖突將會(huì)提高哈希表的復(fù)雜度。 二叉樹(shù) 二叉樹(shù)的組織方式平均查填效率最高，但實(shí)現(xiàn)的復(fù)雜度較高。對(duì)于名稱沖 突也要特別處理。在某些情況下，二叉樹(shù)會(huì)退化成線性表，這個(gè)問(wèn)題可以 通過(guò)采用AVL樹(shù)的結(jié)構(gòu)來(lái)解決，但這會(huì)進(jìn)一步提高實(shí)現(xiàn)的代價(jià)。 3）C-系統(tǒng)中符號(hào)表的組織（參見(jiàn)源文件Symbol.h） 本編譯程序中對(duì)符號(hào)表的管理和操作在CSymbol類中實(shí)現(xiàn)，采用的是哈希雜湊表的方式。 該類的聲明如下：class CSymbol public:CSymbo

32、l();symbol *NewSymbol(char *name, unsigned level);symbol *FindSymbol(char *name);bool DeleteNest(symbol *pHead);unsigned Hash(char *name);virtual CSymbol();private:Hash_Node *SymTableTABLE_LEN;類中所涉及到的結(jié)構(gòu)聲明如下：struct symbolchar nameNAME_MAX+1;/輸入變量名char rnameNAME_MAX+1;/實(shí)際變量名unsigned level;/當(dāng)前嵌套級(jí)type *

33、pType;/變量類型symbol *next;/指向同層的下一個(gè)變量;struct Hash_NodeHash_Node *pre;/上一個(gè)沖突節(jié)點(diǎn)Hash_Node *next;/下一個(gè)沖突節(jié)點(diǎn)symbol *sym;/指向此節(jié)點(diǎn)上的變量; CSymbol采用哈希表來(lái)實(shí)現(xiàn)對(duì)變量的管理和查找。變量表采用數(shù)組實(shí)現(xiàn)，對(duì)于每一個(gè)產(chǎn)生哈系沖突的變量節(jié)點(diǎn)，利用鏈表將其連接到已有的節(jié)點(diǎn)后。在本編譯程序中，采用了較復(fù)雜的計(jì)算哈系值的算法，其偽碼如下：unsigned CSymbol:Hash(char *name)hash_val = 0;for(對(duì)變量名中的每一個(gè)字符)hash_val = (hash_

34、val 12) & 0x3fff;返回hash_val;CSymbol類中兩個(gè)主要的成員函數(shù)是：symbol *FindSymbol(char *name)，實(shí)現(xiàn)根據(jù)變量名，在變量表中查找該一項(xiàng)。symbol*NewSymbol(char *name, unsigned level)，實(shí)現(xiàn)在變量表中加入一個(gè)symbol項(xiàng)。4) 其他主要結(jié)構(gòu)定義（參見(jiàn)源文件Structs.h）struct typeunsigned noun;/CHAR INTint num_ele;/number of elements if arrayint v_int;/Value if constant;struct v

35、aluechar nameNAME_MAX * 2;/Operand that accesses the valuetype *pType;/Variables 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ù)分配棧來(lái)存放局部變量，這樣的

36、做法浪費(fèi)空間且缺乏靈活性，但是它帶來(lái)的一個(gè)好處是局部變量可以回收，而不像很多編譯程序存在著局部變量無(wú)法回收的缺憾。處理局部變量的主要函數(shù)有（參見(jiàn)源文件Functions.h及Functions.cpp）：void figure_local_offsets(symbol *s);void release_local(symbol *s);函數(shù)figure_local_offsets為一個(gè)層中的局部變量分配空間，而函數(shù)release_local則釋放在某一層執(zhí)行完時(shí)釋放其中的所有變量。這可以通過(guò)遍歷雜湊鏈表中的該層的變量鏈表（單向鏈表）得到所有變量的存儲(chǔ)總長(zhǎng)度，然后把局部變量堆棧指針減掉這個(gè)長(zhǎng)度就

37、可以了。這樣該層的所有變量所占的空間都釋放掉了。下一次又可以使用這些釋放的空間。36 系統(tǒng)中臨時(shí)變量的處理臨時(shí)變量是編譯系統(tǒng)中使用較多的部分，通過(guò)建立臨時(shí)變量來(lái)記錄每一次運(yùn)算的結(jié)果，使后續(xù)的運(yùn)算能方便地引用前次的值，是一個(gè)較通用的方法。所以，臨時(shí)變量的管理成為編譯程序中一個(gè)比較重要的部分。 因?yàn)楸揪幾g程序的條件限制，系統(tǒng)中對(duì)臨時(shí)變量的處理采取棧式結(jié)構(gòu)存 放的方法。存放臨時(shí)變量的堆棧是系統(tǒng)全局的，通過(guò)在編譯程序初始化是建立，如下：fprintf(OutPut,t%stdbt%d dup(?)nn, TMP_STACK, TMP_STACK_LEN);此語(yǔ)句將在匯編源代碼中生成如下的語(yǔ)句：t_st

38、ackdb1024 dup(?)系統(tǒng)通過(guò)一個(gè)布爾型數(shù)組對(duì)臨時(shí)變量棧進(jìn)行管理。bool Tmp_RegTMP_STACK_LEN;Tmp_Regoffset的值表示臨時(shí)變量棧中偏移量為offset的空間是否已被分配為臨時(shí)變量的存放。系統(tǒng)使用以下4個(gè)函數(shù)完成對(duì)臨時(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ī)則和每一個(gè)推導(dǎo)的相應(yīng)動(dòng)作，生成匯編源代碼。（詳見(jiàn)程序清單）主程序框架的生成通過(guò)函數(shù)void Init(void) 和void End(void)完成。 Init主要任務(wù)：生成數(shù)據(jù)段、代碼段；生成主程序的起始代碼；返回地址入棧；創(chuàng)建全局和系