C語言編譯器的設計與實現

1、C語言編譯器的設計與實現 01計算機4班 18號任春妍 2號陳俊我們設計的編譯程序涉及到編譯五個階段中的三個，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析過程顯示及四元式序列程序，整個編譯程序分為三部分：(1) 詞法分析部分(2) 語法分析處理及四元式生成部分 (3) 輸出顯示部分一詞法分析器設計 由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式： (單詞種別，單詞自身的值)#

2、define ACC -2#define syl_if 0#define syl_else 1#define syl_while 2#define syl_begin 3#define syl_end 4#define a 5#define semicolon 6#define e 7#define jinghao 8#define s 9#define L 10#define tempsy 11#define EA 12#define EO 13#define plus 14#define times 15#define becomes 16#define op_and 17#define

3、op_or 18#define op_not 19#define rop 20#define lparent 21#define rparent 22#define ident 23#define intconst 24函數說明 1 讀取函數 readline( )、readch( )詞法分析包含從源文件讀取字符的操作，但頻繁的讀文件操作會影響程序執(zhí)行效率，故實際上是從源程序文件” source.dat ”中讀取一行到輸入緩沖區(qū)，而詞法分析過程中每次讀取一個字符時則是通過執(zhí)行 readch( )從輸入緩沖區(qū)獲得的；若緩沖區(qū)已被讀空，則再執(zhí)行readline( )從 source.dat 中讀取

4、下一行至輸入緩沖區(qū)。2 掃描函數 scan( ) 掃描函數 scan( )的功能是濾除多余空格并對主要單詞進行分析處理，將分析得到的二元式存入二元式結果緩沖區(qū)。3 變量處理 find（ ）變量處理中首先把以字母開頭的字母數字串存到 spelling 數組中，然后進行識別。識別過程是先讓它與保留關鍵字表中的所有關鍵字進行匹配，若獲得成功則說明它為保留關鍵字，即將其內碼值寫入二元式結果緩沖區(qū)；否則說明其為變量，這時讓它與變量名表中的變量進行匹配（ 變量匹配函數 find（ ） ），如果成功，則說明該變量已存在并在二元式結果緩沖區(qū)中標記為此變量（ 值填為該變量在變量名表中的位置），否則將該變量登記到

5、變量名表中，再將這個新變量存入二元式緩存數組中。4 數字識別 number( ) 數字識別將識別出的數字填入二元式結果緩存數組。5 顯示函數 顯示函數的功能在屏幕上輸出詞法分析的結果（ 即二元式序列程序），同時給出二元式個數及源程序行數統計。二語法分析器設計 語法分析器的核心是三張 SLR 分析表以及針對這三張 SLR 分析表進行語義加工的語義動作。編譯程序中語法分析處理及四元式生成部分主要是以二元式作為輸入，并通過 SLR 分析表對語法分析處理過程進行控制，使四元式翻譯的工作有條不紊的進行，同時識別語法分析中的語法錯誤。在處理 if 和 while 語句時，需要進行真值或假值的拉鏈和返填工作

6、，以便轉移目標的正確填入。1. 控制語句的 SLR 分析表1 設計過程如下： 將擴展文法G0） Sà S1）S à if e S else S2）S à while e S3）S à L 4）S à a;5）L à S6）L à SL用_CLOSURE方法構造LR(0)項目規(guī)范簇為：I0： Sà ·SS à ·if e S else SS à ·while e S S à · L S à · a ;I1: Sà S&

7、#183;I2: S à if·e S else SI3: S à while ·e SI4: S à ·L L à ·S L à ·SL S à ·if e S else SS à ·while e S S à · L S à · a ; I5: S à a· I6: S à if e ·S else S S à ·if e S else SS à

8、; ·while e S S à · L S à · a ; I7: Sà while e ·S S à ·if e S else SS à ·while e S S à · L S à · a ; I8: S à L· I9: L à S· L à S·L L à ·SL L à ·S S à ·if e S else SS

9、à ·while e S S à · L S à · a ; I10: S à a ; · I11: S à if e S ·else SI12: S à while e S· I13: S à L · I14: S à SL · I15: S à if e S else S S à ·if e S else SS à ·while e S S à · L S 

10、24; · a ; I16: S à if e S else S ·構造文法G中非終結符的FOLLOW集如下：1） FOLLOW(S) = # 2） S à if e S else S得FOLLOW(S) = else S à L 得FOLLOW(L) = 3) S à S 得FOLLOW(S) = else , # L à S 因為FIRST(S) = ，所以FOLLOW(S) = else , #, 在（）項目規(guī)范簇中，只有9有“移進歸約”沖突，L à S·L à S·L因為FOL

11、LOW(L) FIRST(L) = 所以可以用方法解決以上沖突，最后我們得到的分析表如下：ACTIONGOTO ifElsewhilea;e#SL0S2S3S4S511ACC2S63S74S2S3S4S5985S106S2S3S4S5117S2S3S4S5128S139S2S3S4R5S591410R4R4R4111512R2R2R213R3R3R314R615S2S3S4S51616R1R1R1static int action2011=/* 0 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 1, -1,/* 1 */ -1, -1, -1, -1, -1, -1,

12、-1, -1,ACC, -1, -1,/* 2 */ -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1,/* 3 */ -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, -1,/* 4 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 9, 8,/* 5 */ -1, -1, -1, -1, -1, -1, 10, -1, -1, -1, -1,/* 6 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 11, -1,/* 7 */ 2, -1, 3, 4, -1, 5, -1, -1, -1

13、, 12, -1,/* 8 */ -1, -1, -1, -1, 13, -1, -1, -1, -1, -1, -1,/* 9 */ 2, -1, 3, 4,105, 5, -1, -1, -1, 9, 14,/* 10*/ -1,104, -1, -1,104, -1, -1, -1,104, -1, -1,/* 11*/ -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 12*/ -1,102, -1, -1,102, -1, -1, -1,102, -1, -1,/* 13*/ -1,103, -1, -1,103, -1, -1, -1,10

14、3, -1, -1,/* 14*/ -1, -1, -1, -1,106, -1, -1, -1, -1, -1, -1,/* 15*/ 2, -1, 3, 4, -1, 5, -1, -1, -1, 16, -1,/* 16*/ -1,101, -1, -1,101, -1, -1, -1,101, -1, -1;其中，前 9 列為 action 值，后 2 列為 goto 值；016 表示 17 個移進狀態(tài)（ 即 Si）；-1表示出錯；ACC 表示分析成功；而 100106 對應 7 個歸約產生式：100 Sà S101 S à if e S else S102 S &

15、#224; while e S103 S à L 104 S à a;105 L à S106 L à SL2. 算術表達式的 LR 分析表 2 設計如下：0) S à E1) E à E+E2) E à E*E3) E à (E)4) E à i （過程略）ACTIONGOTOI+*()#E0S3S211S4S5ACC2S3S263R4R4R4R44S3S275S3S286S4S5S97R1R5R1R18R2R2R2R29R3R3R3R3static int action1107=/* 0 */ 3,

16、-1, -1, 2, -1, -1, 1,/* 1 */ -1, 4, 5, -1, -1,ACC, -1,/* 2 */ 3, -1, -1, 2, -1, -1, 6,/* 3 */ -1,104,104, -1,104,104, -1,/* 4 */ 3, -1, -1, 2, -1, -1, 7,/* 5 */ 3, -1, -1, 2, -1, -1, 8,/* 6 */ -1, 4, 5, -1, 9, -1, -1,/* 7 */ -1,101, 5, -1,101,101, -1,/* 8 */ -1,102,102, -1,102,102, -1,/* 9 */ -1,103

17、,103, -1,103,103, -1;3.布爾表達式的 SLR 分析表3 設計如下：（過程略）1) Sà B2) B à i3) B à i rop i4) B à ( B )5) B à ! B6) A à B &&7) B à AB8) O à B |9) B à OBACTIONGOTOiRop()!&&|#BAO0S1S4S513781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S51478

18、8S1S4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615R8S9S10R8static int action21611=/* 0 */ 1, -1, 4, -1, 5, -1, -1, -1, 13, 7, 8,/* 1 */ 1, 2, -1,101, -1,101,101,101, -1, -1, -1,/* 2 */ 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 3 */ -1, -1, -1,102, -1,102,102,102, -1, -1, -1,/*

19、4 */ 1, -1, 4, -1, 5, -1, -1, -1, 11, 7, 8,/* 5 */ 1, -1, 4, -1, 5, -1, -1, -1, 6, 7, 8,/* 6 */ -1, -1, -1,104, -1, 9, 10,104, -1, -1, -1,/* 7 */ 1, -1, 4, -1, 5, -1, -1, -1, 14, 7, 8,/* 8 */ 1, -1, 4, -1, 5, -1, -1, -1, 15, 7, 8,/* 9 */ 105, -1,105, -1,105, -1, -1, -1, -1, -1, -1,/*10 */ 107, -1,10

20、7, -1,107, -1, -1, -1, -1, -1, -1,/*11 */ -1, -1, -1, 12, -1, 9, 10, -1, -1, -1, -1,/*12 */ -1, -1, -1,103, -1,103,103,103, -1, -1, -1,/*13 */ -1, -1, -1, -1, -1, 9, 10,ACC, -1, -1, -1,/*14 */ -1, -1, -1,106, -1, 9, 10,106, -1, -1, -1,/*15 */ -1, -1, -1,108, -1, 9, 10,108, -1, -1, -1;LR 分析表控制語義加工的實現

21、：當掃描 LR 分析表的當前狀態(tài)為歸約狀態(tài)時，則在調用與該狀態(tài)對應的產生式進行歸約的同時，調用相應的語義子程序進行有關的翻譯工作?，F在對 LR 分析器的分析棧加以擴充，使得每個文法符號之后都跟著它的語義值。為了清晰起見，我們把這個棧的每一項看成由三部分組成：狀態(tài) state ，文法符號 syl 和語義值 val。編譯程序實現算術表達式、布爾表達式及程序語句的語義加工時，都是按這種狀態(tài)棧加工方式進行的。例如：( 5 + 3 ) * 6的分析過程序號STATEValsylinput10-#( 5 + 3 ) * 6 #202-#(5 + 3 ) * 6 #3023-#(5+ 3 ) * 6 #40

22、26-5#(E+ 3 ) * 6 #50264-5-#(E+3 ) * 6 #602643-5-#(E+3 ) * 6 #702647-5-3#(E+E) * 6 #8026-8#(E) * 6 #90269-8-#(E)* 6 #1001-8#E* 6 #11015-8-#E* 6 #120153-8-#E*6#130158-8-6#E*E#1401-48#E#15ACC在分析過程中，第（3）步操作后的狀態(tài)棧為 023，根據棧頂狀態(tài)“ 3”和現行輸入符號“ +”（ input 欄字符串的第一個字符）查分析表 ACTION3，+=R4，即按第（4）個產生式 En 來進行歸約；由于產生式右部僅含

23、一項，故去掉狀態(tài)棧棧頂“3”；此時 2 變?yōu)樾碌臈ｍ敔顟B(tài)，再查（ 2，E）的下一狀態(tài) s：GOTO2,E=6，即將狀態(tài) 6 和文法符號 E 壓棧，最后得到第（ 4）步的狀態(tài)。第（ 7）步操作后也是如此，當前狀態(tài)棧為 02647，根據棧頂狀態(tài) 7 和現行輸入符號“ ）”查分析表 ACTION7，）=R1，即按第（1）個產生式 EE1+E2進行歸約；由于產生式右部有三項，故去掉狀態(tài)棧棧頂的 647 三項；此時 2 變?yōu)樾碌臈ｍ敔顟B(tài)，再查（ 2，E）的下一狀態(tài) s：GOTO2，E=6,即將狀態(tài) 6 和文法符號 E 壓棧，最后得到第（8）步的狀態(tài)。三中間代碼生成器設計：布爾表達式 布爾表達式在程序語言

24、中有兩個基本作用：一是用作控制語句（ 如 if -else 或 while語句）的條件式；二是用于邏輯演算，計算邏輯值。布爾表達式是由布爾算符（ &&、| 、?。┳饔糜诓紶栕兞浚?或常數）或關系表達式而形成的。關系表達式的形式是 E1 rop E2，其中 rop 是關系符（ 如<、=、>或），E1和 E2是算術式。在這里，我們只考慮前面給定文法所產生的布爾表達式：BB &&B | B | B | ! B | (B) | i rop i | i遵照我們的約定，布爾算符的優(yōu)先順序（ 從高到低）為：!、&&、|，并假定&&和

25、|都服從左結合規(guī)則。所有關系符的優(yōu)先級都是相同的，而且高于任何布爾算符，低于任何算術算符，關系算符不得結合。表達式的真、假出口的確定：考慮表達式 B1 | B2 ，若 B1為真，則立即知道 B 也為真；因此，B1的真出口也就是整個 B 的真出口。若 B1?為假，則 B2必須被計值，B2的第一個四元式就是 B1的假出口。當然，B2的真、假出口也就是整個 B的真、假出口。類似的考慮適用于對 B1 && B2的翻譯，我們將 B1 | B2和 B1 && B2 的翻譯用下圖表示，在自下而上的分析過程中，一個布爾式的真假出口往往不能在產生四元式的同時就填上。我們只好把這種

26、未完成的四元式的地址（ 編號）作為 B 的語義值暫存起來，待到整個表達式的四元式產生完畢之后再來回填這個未填入的轉移目標。條件語句對條件語句 if e S1 else S2 中的布爾表達式 e，其作用僅在于控制對 S1和 S2的選擇。因此，作為轉移條件的布爾式e，我們可以賦予它兩種“ 出口”：一是“ 真”出T口，出向 S1；一是“ 假”出口，出向 S2。于是，e的代碼F條件語句可以翻譯成如圖的一般形式。非終結符 e 具有兩項語義值 e _TC 和e_FC，它們分別指出了尚待回填真、S2的代碼假出口的四元式串。e 的“ 真”出口只有在往回掃描到if時才能知道，而它圖 3-2 條件語句的代碼結構

27、的“ 假”出口則需到處理過 S1并且到達 else 才能明確。這就是說，必須把 e_FC 的值傳下去，以便到達相應的 else時才進行回填。另外，當 S1語句執(zhí)行完時意味著整個 if-else 語句也已執(zhí)行完畢；因此，在 S1的編碼之后應產生一條無條件轉移指令。這條轉移指令將導致程序控制離開整個 if-else 語句。但是，在完成 S2的翻譯之前，這條無條件轉移指令的轉移目標是不知道的。甚至，在翻譯完 S2之后，這條轉移指令的轉移目標仍無法確定。這種情形是由于語句的嵌套性所引起的。例如下面的語句：if e1 if e2 S1 else S2 else S3 在 S1的代碼之后的那條無條件轉移指

28、令不僅應跨越 S2而且應跨越 S3。這也就是說，轉移目標的確定和語句所處的環(huán)境密切相關。條件循環(huán)語句條件循環(huán)語句 while e S 通常被翻譯成圖的代碼結構。布爾式 e 的“ 真”出口出向 S 代碼段的第一個四元式。緊接 S 代碼段之后應產生一條轉向測試 e 的無條件轉移指令。e 的“ 假”出口將導致程序控制離開整個 while 語句。e 的“ 假”出口目標即使在整個 while 語句翻譯完之后也未必明確。例如： if e1 while e2 S1 else S2這種情況仍是由于語句的嵌套性引起的。所以，我們只好把它作為語句的語義值 S·CHAIN 暫留下來，以便在處理外層語句時再

29、伺機回填。語法翻譯實現方法 將上述語法翻譯付諸實現過程中，我們僅保留了算術表達式和布爾表達式翻譯的文法和語義動作；面對程序語句的翻譯，由于改造后含有較多的非終結符且語義動作又相對簡單，故仍恢復為改造之前的程序語句文法。由于總體上構造一個 SLR 分析表來實現語法分析及語義加工將使得所構造的 SLR 分析表過大，所以將其分為下面三部分處理：(1) 對算術表達式單獨處理，即為算術表達式構造一個 SLR 分析表，并將賦值語句A=E 與算術表達式歸為一類處理，處理之后的賦值語句僅看作為程序語句文法中的一個終結符 a。(2) 對布爾表達式也單獨處理，并為其構造一個 SLR 分析表，經 SLR 分析表處理

30、后的布爾表達式看作為程序語句文法中的一個終結符 e。(3) 程序語句文法此時變?yōu)椋篠 à if e S else S | while e S | L | a;L à SL | S此時為程序語句構造相應的 SLR 分析表就簡單多了。前面的程序語句文法中所添加的非終結符是為了能及時回填有關四元式轉移目標而引入的，在取消了這些非終結符后又如何解決及時回填轉移目標的問題呢？我們采取的解決方法是增加兩個數組 labelmark 和 labeltemp 來分別記錄語句嵌套中每一層布爾表達式（ 如果有的話）e 的首地址以及每一層else（ 如果有的話）之前的四元式地址（ 即無條件轉出此層

31、 if 語句的四元式）。也即，對程序語句的翻譯來說： 在處理完布爾表達式 e 后，回填 if 或 while 語句的真值鏈； 在歸約完每一個語句 S 之后檢查符號棧，看在 S 之前的文法符號是否 if 或 while，若是則回填假值鏈（ 假值入口為語句 S 所對應的四元式序列之后；對 if 語句，此時已在該序列之后加入了一條無條件轉移的四元式）； 在 if 語句中，else 前面要加入一個無條件轉移的四元式轉向 if 語句末尾；在 while語句尾要有一個無條件轉移四元式轉向 while 語句開頭。四數據結構說明 編譯程序中涉及到的數據結構說明如下：char ch='0' /*

32、從字符緩沖區(qū)中讀取當前字符*/int count=0; /*詞法分析結果緩沖區(qū)計數器*/static char spelling10=" " /*存放識別的字*/static char line81=" " /*一行字符緩沖區(qū)（ 最多 80 個字符）*/char *pline; /*字符緩沖區(qū)指針*/static char ntab110010; /*變量名表：共100項，每項長度為10*/struct ntab int tc; /*真值*/ int fc; /*假值*/ ntab2200; /*在布爾表達式 ) 中保存有關布爾變量的真、假值*/int

33、label=0; /*指向 ntab2 的指針*/struct rewords char sp10; int sy; ; /*匹配表的結構，用來與輸入緩沖區(qū)中的單詞進行匹配*/struct rewords rewords8= "if",syl_if, "else",syl_else, "while",syl_while, "",syl_begin, "",syl_end, "&&",op_and, "|",op_or, "!",op_not; /*匹配表初始化，大小為8*/struct aa int syl; /*存放名字*/ int pos; /*存放名字所對應的值*/ buf100, /*詞法分析結果緩沖區(qū)*/ n, /*讀取二元式的當前字符*/ n1,