編譯原理大作業(yè)設(shè)計(jì)

1、塔里木大學(xué)課程設(shè)計(jì)2017屆課程設(shè)計(jì)C語言編譯器的設(shè)計(jì)與實(shí)現(xiàn) 學(xué)生姓名: 庫爾班江.阿瓦克日 學(xué) 號: 5011212524 所屬學(xué)院: 信息工程學(xué)院 專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù) 班 級: 計(jì)算機(jī)17-1班 塔里木大學(xué)教務(wù)處制不要?jiǎng)h除行尾的分節(jié)符，此行不會(huì)被打印編譯原理大作業(yè)目錄第1章 編譯器概述21.1編譯器概述2第2章 編譯器設(shè)計(jì)42.1詞法分析設(shè)計(jì)42.1語法分析設(shè)計(jì)62.1中間代碼生成92.1語法翻譯實(shí)現(xiàn)方法11第3章 數(shù)據(jù)結(jié)構(gòu)說明123.1數(shù)據(jù)結(jié)構(gòu)說明12第4章 編譯程序運(yùn)行測試154.1編譯程序運(yùn)行測試15參考文獻(xiàn)18第1章 編譯器概述黃金分割的 哈工大回歸熱大 【】個(gè)阿訇 婦孺誒

2、航天拖后腿航天皇太后 1.1 編譯器概述編譯器的任務(wù)是：輸入 *.asm 源程序文件，輸出 *.obj 目標(biāo)代碼文件和 *.lst 列表文件對輸入的源程序進(jìn)行掃描，找出所有詞法和語法的錯(cuò)誤，然后生成有待重定位的目標(biāo)代碼（中間文件）和提供查看信息的列表文件。中間文件后綴名為obj，是連接器的輸入文件。一個(gè)編譯器的整個(gè)工作流程是劃分成一個(gè)一個(gè)階段進(jìn)行的，每個(gè)階段都將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個(gè)階段進(jìn)行的操作在邏輯上是緊密聯(lián)結(jié)在一起的。這幾個(gè)階段是：詞法分析、語法分析、語義分析、中間代碼生成。另外兩個(gè)重要的工作：符號表格的管理和出錯(cuò)處理貫穿以上的所有階段。編譯過程中源程序的各種信息

3、被保留在種種不同的表格里。編譯時(shí)自始至終涉及到表格的構(gòu)造、查找和更新。如果編譯過程中發(fā)現(xiàn)源程序有錯(cuò)誤，編譯程序應(yīng)報(bào)告錯(cuò)誤的性質(zhì)和錯(cuò)誤發(fā)生的地點(diǎn)，并且將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，有些地方編譯器還能自動(dòng)校正錯(cuò)誤，這些工作稱之為出錯(cuò)處理。詞法分析自左至右掃描源程序的字符串，并識別出一個(gè)個(gè)的單詞（也稱單詞符號）。這里所謂的單詞是指邏輯上緊密相連的按詞的組成規(guī)則結(jié)合起來的一組字符，它們具有一定的意義。把每個(gè)單詞的ASCII 碼序列替換成所謂的機(jī)內(nèi)表示Token 形式。這時(shí)還需要檢查詞法錯(cuò)誤。詞法分析階段不依靠語法關(guān)系。語法分析掃描對象可能是源程序的AS

4、CII 碼序列，也可能是詞法分析后的Token 序列。前者情形，詞法分析程序作為語法分析程序的子程序。語法分析的主要任務(wù)是檢查源程序的形式語法錯(cuò)誤。每當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)將輸出有關(guān)信息。很多編譯程序在進(jìn)行語法分析時(shí)同時(shí)完成其他工作，但要注意，如果語法有錯(cuò)誤，那么其他工作也就白做。語義分析掃描的對象通常是語法分析后的結(jié)果。這時(shí)候，源程序的Token 序列已經(jīng)變換成沒有錯(cuò)誤的符合語法的Token 生成樹。對于編譯器來說，它的任務(wù)是收集符號信息，登記在符號表格里，對偽指令的語義進(jìn)行解釋，完成相應(yīng)的動(dòng)作。偽指令的功能是改變編譯器的狀態(tài)并將一些必要的信息（如段定義，變量聲明）加入到目標(biāo)文件中去。另外，表達(dá)式的求

5、值，段的選擇，地址計(jì)數(shù)器的計(jì)數(shù)，指令長度的計(jì)算等都在這個(gè)階段中完成。語義分析階段同樣進(jìn)行著對錯(cuò)誤的處理。目標(biāo)代碼生成這時(shí)候的Token 流在形式上已經(jīng)比較一致，符號信息都已經(jīng)登記在各種表格里。這個(gè)階段的任務(wù)是根據(jù)助記符的各種尋址方式?jīng)Q定它的目標(biāo)代碼。這一部分的工作與目標(biāo)機(jī)的指令系統(tǒng)緊密相關(guān)。目標(biāo)代碼生成之后，還要根據(jù)obj 文件的格式把目標(biāo)代碼寫入文件。最后還要產(chǎn)生列表文件，為用戶提供源碼與目標(biāo)碼的對照。第2章 編譯器設(shè)計(jì)2.1 詞法分析設(shè)計(jì)由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯(cuò)誤的檢查，而將編譯程序的重點(diǎn)放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出

6、單詞符號。我們規(guī)定輸出的單詞符號格式為如下的二元式： (單詞種別，單詞自身的值)#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#d

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

8、區(qū)已被讀空，則再執(zhí)行readline( )從 in.txt 中讀取下一行至輸入緩沖區(qū)。2 掃描函數(shù) scan( ) 掃描函數(shù) scan( )的功能是濾除多余空格并對主要單詞進(jìn)行分析處理，將分析得到的二元式存入二元式結(jié)果緩沖區(qū)。3 變量處理 find( )變量處理中首先把以字母開頭的字母數(shù)字串存到 spelling 數(shù)組中，然后進(jìn)行識別。識別過程是先讓它與保留關(guān)鍵字表中的所有關(guān)鍵字進(jìn)行匹配，若獲得成功則說明它為保留關(guān)鍵字，即將其內(nèi)碼值寫入二元式結(jié)果緩沖區(qū)；否則說明其為變量，這時(shí)讓它與變量名表中的變量進(jìn)行匹配(變量匹配函數(shù)find( )，如果成功，則說明該變量已存在并在二元式結(jié)果緩沖區(qū)中標(biāo)記為此變

9、量(值填為該變量在變量名表中的位置)，否則將該變量登記到變量名表中，再將這個(gè)新變量存入二元式緩存數(shù)組中。4 數(shù)字識別 number( ) 數(shù)字識別將識別出的數(shù)字填入二元式結(jié)果緩存數(shù)組。5 顯示函數(shù) disp( )顯示函數(shù)的功能在屏幕上輸出詞法分析的結(jié)果（即二元式序列程序），同時(shí)給出二元式個(gè)數(shù)及源程序行數(shù)統(tǒng)計(jì)。2.2 語法分析設(shè)計(jì)語法分析器的核心是三張 SLR 分析表以及針對這三張 SLR 分析表進(jìn)行語義加工的語義動(dòng)作。編譯程序中語法分析處理及四元式生成部分主要是以二元式作為輸入，并通過 SLR 分析表對語法分析處理過程進(jìn)行控制，使四元式翻譯的工作有條不紊的進(jìn)行，同時(shí)識別語法分析中的語法錯(cuò)誤。在

10、處理 if 和 while 語句時(shí)，需要進(jìn)行真值或假值的拉鏈和返填工作，以便轉(zhuǎn)移目標(biāo)的正確填入。1. 控制語句的 SLR 分析表1 設(shè)計(jì)如下：將擴(kuò)展文法G0)Sà S1)S à if e S else S2)S à while e S3)S à L 4)S à a;5)L à S6)L à SLstatic int action2011=/* 0 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 1, -1,/* 1 */ -1, -1, -1, -1, -1, -1, -1, -1,ACC, -1, -

11、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, 12, -1,/* 8 */

12、-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,103, -1, -1,/* 14*/

13、 -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 個(gè)移進(jìn)狀態(tài)（ 即 Si）；-1表示出錯(cuò)；ACC 表示分析成功；而 100106 對應(yīng) 7 個(gè)歸約產(chǎn)生式：100 Sà S101 S à if e S else S102 S à while e S10

14、3 S à L 104 S à a;105 L à S106 L à SL2. 算術(shù)表達(dá)式的 LR 分析表 2 設(shè)計(jì)如下：0)S à E1)E à E+E2)E à E*E3)E à (E)4)E à i static int action1107=/* 0 */ 3, -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, -

15、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,103, -1,103,103, -1;3.布爾表達(dá)式的 SLR 分析表3 設(shè)計(jì)如下：0) Sà B1) B à i2) B à i rop i3) B à ( B )4) B à !

16、B5) A à B &&6) B à AB7) O à B |8) B à OBstatic 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,/* 4 */ 1, -1

17、, 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,107, -1,107,

18、 -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;2.3 中間代碼生成1. 布爾表達(dá)式 布爾表達(dá)式在

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

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

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

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

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

24、便在處理外層語句時(shí)再伺機(jī)回填。2.4 語法翻譯實(shí)現(xiàn)方法將上述語法翻譯付諸實(shí)現(xiàn)過程中，我們僅保留了算術(shù)表達(dá)式和布爾表達(dá)式翻譯的文法和語義動(dòng)作；面對程序語句的翻譯，由于改造后含有較多的非終結(jié)符且語義動(dòng)作又相對簡單，故仍恢復(fù)為改造之前的程序語句文法。由于總體上構(gòu)造一個(gè) SLR 分析表來實(shí)現(xiàn)語法分析及語義加工將使得所構(gòu)造的 SLR 分析表過大，所以將其分為下面三部分處理：(1) 對算術(shù)表達(dá)式單獨(dú)處理，即為算術(shù)表達(dá)式構(gòu)造一個(gè) SLR 分析表，并將賦值語句A=E 與算術(shù)表達(dá)式歸為一類處理，處理之后的賦值語句僅看作為程序語句文法中的一個(gè)終結(jié)符 a。(2) 對布爾表達(dá)式也單獨(dú)處理，并為其構(gòu)造一個(gè) SLR 分析

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

26、式地址（ 即無條件轉(zhuǎn)出此層 if 語句的四元式）。也即，對程序語句的翻譯來說：(1)在處理完布爾表達(dá)式 e 后，回填 if 或 while 語句的真值鏈；(2)在歸約完每一個(gè)語句 S 之后檢查符號棧，看在 S 之前的文法符號是否 if 或 while，若是則回填假值鏈（ 假值入口為語句 S 所對應(yīng)的四元式序列之后；對 if 語句，此時(shí)已在該序列之后加入了一條無條件轉(zhuǎn)移的四元式）；(3)在 if 語句中，else 前面要加入一個(gè)無條件轉(zhuǎn)移的四元式轉(zhuǎn)向 if 語句末尾；在 while語句尾要有一個(gè)無條件轉(zhuǎn)移四元式轉(zhuǎn)向 while 語句開頭。第3章 數(shù)據(jù)結(jié)構(gòu)說明3.1 數(shù)據(jù)結(jié)構(gòu)說明編譯程序中涉及到的

27、數(shù)據(jù)結(jié)構(gòu)說明如下：char ch='0' /*從字符緩沖區(qū)中讀取當(dāng)前字符*/int count=0; /*詞法分析結(jié)果緩沖區(qū)計(jì)數(shù)器*/static char spelling10=" " /*存放識別的字*/static char line81=" " /*一行字符緩沖區(qū)（ 最多 80 個(gè)字符）*/char *pline; /*字符緩沖區(qū)指針*/static char ntab110010; /*變量名表：共100項(xiàng)，每項(xiàng)長度為10*/struct ntab int tc; /*真值*/ int fc; /*假值*/ ntab2200;

28、/*在布爾表達(dá)式 ) 中保存有關(guān)布爾變量的真、假值*/int label=0; /*指向 ntab2 的指針*/struct rewords char sp10; int sy; ; /*匹配表的結(jié)構(gòu)，用來與輸入緩沖區(qū)中的單詞進(jìn)行匹配*/struct rewords rewords8= "if",syl_if, "else",syl_else, "while",syl_while, "",syl_begin, "",syl_end, "&&",op_and,

29、"|",op_or, "!",op_not; /*匹配表初始化，大小為8*/struct aa int syl; /*存放名字*/ int pos; /*存放名字所對應(yīng)的值*/ buf100, /*詞法分析結(jié)果緩沖區(qū)*/ n, /*讀取二元式的當(dāng)前字符*/ n1, /*當(dāng)前表達(dá)式中的字符*/ E, /*非終結(jié)符*/ sstack100, /*算術(shù)或布爾表達(dá)式加工處理使用的符號棧*/ ibuf100, /*算術(shù)或布爾表達(dá)式使用的緩沖區(qū)*/ stack1000; /*語法分析加工處理使用的符號棧*/struct aa oth; /*四元式中空白位置*/struct fourexp char op10; struct aa arg1; struct aa arg2; int result; fexp200; /*四元式的結(jié)構(gòu)定義*/int ssp=0; /*指向sstack棧指針*/struct aa *pbuf=buf; /*指向詞法分析緩沖區(qū)的指針*/int nlength=0; /*詞法分析中記錄單詞的長度*/int tt1=0; /*變量名表指針*/FILE *cfile; /*源程序文件，為結(jié)束符*