1、編譯器設(shè)計(jì)與實(shí)現(xiàn),Lcc原理剖析,華中科技大學(xué)計(jì)算機(jī)學(xué)院 張 德,2020/10/9,一、概述,1、編譯器各階段,2020/10/9,2、編譯器各階段的分組,前端：依賴于語言并很大程度上獨(dú)立于目標(biāo)機(jī)器。一般包括語法分析、詞法分析、符號(hào)表的建立、語義分析、中間代碼生成以及相關(guān)錯(cuò)誤處理。 后端：依賴于目標(biāo)機(jī)器的階段或某些階段的某些部分。一般來說，后端完成的任務(wù)不依賴于源語言而只依賴于中間語言。主要包括代碼優(yōu)化、代碼生成以及相關(guān)的錯(cuò)誤處理和符號(hào)表操作。,2020/10/9,二、符號(hào)表,符號(hào)表是編譯器保存信息的中心庫，編譯器的各部分通過符號(hào)表進(jìn)行交互，并訪問符號(hào)表中的數(shù)據(jù)符號(hào)。 符號(hào)表把各種名字映射到

2、符號(hào)集合。常量、標(biāo)識(shí)符和標(biāo)號(hào)都是名字，不同名字有不同的屬性。 符號(hào)管理不僅要處理符號(hào)本身，還管理符號(hào)的作用域。,2020/10/9,1、符號(hào)的表示,struct symbol char *name; /名稱 int scope;/作用域 Coordinate src;/在源程序中位置 Symbol up;/連接符號(hào)表中上一個(gè)符號(hào) List uses;/可保存一個(gè)Coordinate列表，表示使用情況 int sclass;/擴(kuò)展存儲(chǔ)類型 /符號(hào)標(biāo)記 Type type;/如變量、函數(shù)、常量、結(jié)構(gòu)或聯(lián)合等信息 floatref;/被引用的粗略次數(shù) union /聯(lián)合u為標(biāo)號(hào)、結(jié)構(gòu)、聯(lián)合、枚舉、常

3、量、全局 /和靜態(tài)變量提供附加信息 u;/ Xsymbol x;/由后端處理，如為變量分配寄存器 /為調(diào)試器產(chǎn)生數(shù)據(jù)信息 ,2020/10/9,1、符號(hào)的表示,scope域： enum CONSTANTS=1, LABELS, GLOBAL, PARAM, LOCAL ; 第k層中聲明的局部變量其scope域等于LOCAL+k。 src域： typedef struct coord char *file; unsigned x, y; Coordinate; file指名包含該符號(hào)定義文件名，y和x表示出現(xiàn)的行號(hào)及行中位置。 sclass域：符號(hào)擴(kuò)展類型 可以是AUTO、REGISTER、ST

4、ATIC或EXTERN等 首字母大寫的類型表示全小寫類型的指針，如Symbol。,2020/10/9,2、符號(hào)表的表示,externTableconstants; externTableexternals; externTableglobals; externTableidentifiers; externTablelabels; externTabletypes; struct table intlevel; /同symbol中scope域 Table previous;/符號(hào)表鏈表，指向level-1的表 struct entry struct symbol sym; struct ent

5、ry *link; *buckets256;/這是一個(gè)哈希鏈數(shù)組，方便插入、查找 Symbol all;/指向當(dāng)前及其外層所有符號(hào)列表的表頭 ;,2020/10/9,3、符號(hào)表舉例,int x, y; f(int x, int a) int b; y = x + a*b; if (y 5) int a; y = x + a*b; ,2020/10/9,2020/10/9,4、符號(hào)表的相關(guān)操作,查找和建立標(biāo)識(shí)符 Symbol install(const char * name, Table * tpp, int level, int arena); Symbol lookup(const cha

6、r *name, Table tp); 標(biāo)號(hào):與標(biāo)識(shí)符相似，但不涉及作用域 常量：這些符號(hào)保存在constants表中 產(chǎn)生變量：用于產(chǎn)生靜態(tài)變量保存字符串等,2020/10/9,三、代碼生成接口,這一章內(nèi)容定義了與目標(biāo)機(jī)器無關(guān)的前端和與目標(biāo)機(jī)器相關(guān)的后端之間的接口。 Lcc接口包括一些共享數(shù)據(jù)結(jié)構(gòu)、18個(gè)函數(shù)和包括36個(gè)操作符的語言。該語言用于將可執(zhí)行代碼從源程序生成dag（有向無環(huán)圖）。 共享數(shù)據(jù)結(jié)構(gòu)可供前后端共享，但某些域?yàn)橐欢怂接?。symbol就是一個(gè)共享數(shù)據(jù)結(jié)構(gòu)。,2020/10/9,1、類型度量,typedef struct metrics unsigned char size,

7、align, outofline; Metrics; size:類型的大??； align：對齊字節(jié)數(shù)； outofline：控制相關(guān)類型的常量的放置。為1時(shí)，不出現(xiàn)在dag中，存于靜態(tài)變量中。 Metrics charmetric; Metrics shortmetric; Metrics intmetric; Metrics floatmetric; Metrics doublemetric; Metrics structmetric;,2020/10/9,2、接口記錄,typedef struct interface Xinterfacex; Interface; lcc為每一種目標(biāo)機(jī)器形

8、成一個(gè)獨(dú)有的接口實(shí)例。x域是對interface的擴(kuò)展，后段使用它存放與目標(biāo)及其相關(guān)的接口數(shù)據(jù)和函數(shù)，對后端私有。,2020/10/9,3、dag操作,可執(zhí)行代碼用dag來描述。函數(shù)體是用dag組成的序列或森林。每個(gè)dag都可以同過gen函數(shù)傳給后端。 dag節(jié)點(diǎn) struct node short op; short count; Symbol syms3; Node kids2; Node link; Xnode x; ;,2020/10/9,3、dag操作,op域存放dag操作符。 dag操作符后綴表示操作數(shù)類型： enum F=FLOAT, I=INT, U=UNSIGNED, P=P

9、OINTER, V=VOID, B=STRUCT ; 如CNST，有變體CNSTI、CNSTU、CNSTP等。 CNST = 14； CNSTC=CNST+F； CNSTI=CNST+I； ,2020/10/9,2020/10/9,2020/10/9,3、dag操作,舉例： int i, *p; f() i = *p+;,2020/10/9,4、接口標(biāo)志,unsigned little_endian:1; 目標(biāo)機(jī)器存儲(chǔ)是低位優(yōu)先還是高位優(yōu)先 unsigned mulops_calls:1; 有硬件實(shí)現(xiàn)乘、除和求余，mulopes_calls應(yīng)等于0 unsigned wants_callb:1

10、; 通知前端產(chǎn)生CALLB節(jié)點(diǎn)以調(diào)用返回結(jié)構(gòu)的函數(shù) unsigned wants_argb:1; 通知前端節(jié)點(diǎn)產(chǎn)生ARGB節(jié)點(diǎn)以產(chǎn)生結(jié)構(gòu)參數(shù) unsigned left_to_right:1; 告訴前端按照從左到右的順序計(jì)算和提交參數(shù)給后端 unsigned wants_dag:1; 告訴前端傳遞dag給后端,2020/10/9,5、函數(shù),前端將函數(shù)編譯為私有數(shù)據(jù)結(jié)構(gòu)。將函數(shù)的任意部分傳遞給后端之前，前端必須先對每個(gè)函數(shù)進(jìn)行完整的分析。 函數(shù)的處理：function函數(shù)包括前端過程gencode遍歷前端的私有數(shù)據(jù)結(jié)構(gòu)，將dag的每個(gè)森林傳給后端過程gen。gen選擇代碼，在dag上添加注釋并將

11、返回一個(gè)dag指針。gencode還可以調(diào)用local宣告新的局不變量。前端過程emitcode再次遍歷，將gen返回的指針傳遞給emit函數(shù)發(fā)送代碼。,2020/10/9,6、上行調(diào)用,前段調(diào)用后端以執(zhí)行代碼生成和發(fā)送。后端調(diào)用前端完成輸出、分配存儲(chǔ)空間、查詢類型等功能。上行調(diào)用即后端調(diào)用前端。 allocate分配空間，保證對齊方式符合機(jī)器多 數(shù)類型 newnode分配新的dag節(jié)點(diǎn) newconst符號(hào)表中創(chuàng)建新的常量 newtemp符號(hào)表中創(chuàng)建新的變量 ,2020/10/9,四、詞法分析,詞法分析器讀入源程序，產(chǎn)生語言的基本詞法單元。 例：*prt 56；,2020/10/9,1、輸入

12、,2020/10/9,n,cp,limit,當(dāng)limit-cp小于某一個(gè)固定值時(shí)，調(diào)用fillbuf函數(shù)填充buffer,2、單詞識(shí)別,部分文法： token: keyword identifier constant operator punctuator punctuator: one of ( ) * , : = ; ,2020/10/9,定義： ID 標(biāo)識(shí)符 FCON 浮點(diǎn)常量 ICON 整型常量 SCON INCR DECR DEREF ,emun #define xx(a,b,c,d,e,f,g) a=b, #define yy(a,b,c,d,e,f,g) #include “to

13、ken.h” LAST token.h文件： yy(0, 0, 0, 0, 0, 0, 0) xx(FLOAT, 1, 0, 0, 0, CHAR, float) xx(DOUBLE, 2, 0, 0, 0, CHAR, double) xx(CHAR, 3, 0, 0, 0, CHAR, char) xx(SHORT, 4, 0, 0, 0, CHAR, short) xx(INT, 5, 0, 0, 0, CHAR, int) xx(UNSIGNED, 6, 0, 0, 0, CHAR, unsigned) xx(POINTER, 7, 0, 0, 0, 0, pointer) xx(VO

14、ID, 8, 0, 0, 0, CHAR, void) xx(STRUCT, 9, 0, 0, 0, CHAR, struct) ,2020/10/9,3、關(guān)鍵字的識(shí)別,可以通過查表完成，也可以通過硬編碼方式識(shí)別。 例如，當(dāng)起始小寫字母為i時(shí)由gettok函數(shù)中switch語句的case i處理。,2020/10/9,case i: if (rcp0 = f,4、標(biāo)識(shí)符識(shí)別,case h: case j: case k: case m: case n: case o: case p: case q: case x: case y: case z: case A: case B: case C:

15、 case D: case E: case F: case G: case H: case I: case J: case K: case M: case N: case O: case P: case Q: case R: case S: case T: case U: case V: case W: case X: case Y: case Z: id: if (limit - rcp MAXLINE) cp = rcp - 1; fillbuf(); rcp = +cp; ,2020/10/9,assert(cp = rcp); token = (char *)rcp - 1; whil

16、e (map*rcp,檢查是否需要填充buffer,5、其他,另外還有： 數(shù)字識(shí)別 字符常量和字符串識(shí)別 都是有g(shù)ettok函數(shù)實(shí)現(xiàn)，實(shí)現(xiàn)方法相似。 詞法分析器可以有象LEX這樣的工具實(shí)現(xiàn)。Lcc手工實(shí)現(xiàn)了詞法分析器，體積更小。,2020/10/9,五、語法分析,根據(jù)語言的文法分析，以確認(rèn)輸入是否符合語言規(guī)則，并建立輸入源程序的內(nèi)部表示。 Lcc采用遞歸下降的語法分析。 語法分析以形式語言理論為基礎(chǔ)，采取語法制導(dǎo)翻譯方法，處理程序中的錯(cuò)誤。,2020/10/9,1、表達(dá)式,表達(dá)式的表示： (a+b)+b*(a+b),2020/10/9,表達(dá)式的分析： c語言的小部分表達(dá)式語法: expr: t

17、erm+term term: factor *factor factor: ID| ( expr ) T(expr) T(term+term) T(term)T(+term) term();T(+term) term();while(t = +) T(+term) term();while(t = +) T(+)T(term) term();while(t = +) t = gettok();T(term) term();while(t = +) t = gettok(); term() 同理得分析函數(shù)term是：factor();while(t = *) t = gettok(); fact

18、or(),2020/10/9,void factor() if(t=ID) t=gettok(); else if (t = () t=gettok(); expr(); expect() ; ,c語言表達(dá)式分析 賦值表達(dá)式： assignment-expression: conditional-expression unary-expression assign-operator assignment-expression Tree expr1(int tok) static char stop = IF, ID, 0 ; Tree p = expr2(); if (t = = | (pre

19、ct = 6 else return p ,2020/10/9,條件表達(dá)式： conditonal-expression: binary-expression? expression : conditional-expression static Tree expr2(void) Tree p = expr3(4); if (t = ?) Tree l, r; Coordinate pts2; if (Aflag 1 ,2020/10/9,另有二元表達(dá)式、一元表達(dá)式、后綴表達(dá)式和基本表達(dá)式。 表達(dá)式分析多是用遞歸和大量switch語句實(shí)現(xiàn)。 在編譯領(lǐng)域用一個(gè)分析函數(shù)代替n個(gè)函數(shù)處理n級(jí)優(yōu)先是非

20、常流行的。 關(guān)于表達(dá)式的分析還包括表達(dá)式語義的分析，如類型檢查轉(zhuǎn)換、函數(shù)調(diào)用分析等各種操作。,2020/10/9,2、語句分析,代碼的表示：表達(dá)式首先被編譯為分析樹然后轉(zhuǎn)化為dag。每個(gè)函數(shù)的dag在代碼表中被串起來，代碼表表示了函數(shù)的代碼。 code結(jié)構(gòu)： struct code enum Blockbeg, Blockend, Local, Address, Defpoint, Label, Start, Gen, Jump, Switch kind; Code prev, next; union u; ,2020/10/9,語句的識(shí)別： void statement(int loop,

21、Swtch swp, int lev) float ref = refinc; if (Aflag = 2 ,2020/10/9,if語句的識(shí)別： if expression = 0 goto L statement1 goto L+1 L:statement2 L1： static void ifstmt(int lab, int loop, Swtch swp, int lev) t = gettok(); expect();/判斷if后的（ definept(NULL); walk(conditional(), 0, lab); /包含listnode函數(shù)生成dag并加入 refinc

22、/= 2.0; /森林，把入口加入代碼表.同時(shí)根 statement(loop, swp, lev);/據(jù)接過設(shè)置flab，tlab if (t = ELSE) branch(lab + 1); t = gettok(); definelab(lab); statement(loop, swp, lev); if (findlabel(lab + 1)-ref) definelab(lab + 1); else definelab(lab); ,2020/10/9,在循環(huán)、switch、goto語句中都用到了標(biāo)號(hào) 和跳轉(zhuǎn)，標(biāo)號(hào)使通過definelab函數(shù)定義的， 而跳轉(zhuǎn)通過branch函數(shù)生成

23、。 除語句識(shí)別外，還有聲明的識(shí)別。聲明的識(shí)別非常復(fù)雜，c語言中聲明的形式很多，處理時(shí)大量的相互遞歸調(diào)用。 經(jīng)過前端的分析后，將源程序轉(zhuǎn)化為dag，并添加進(jìn)代碼表。,2020/10/9,3、小結(jié),六、中間代碼生成,編譯器的后端通過function接口函數(shù)調(diào)用gencode和emitcode來遍歷代碼表。 walk和listnodes函數(shù)操作處理dag森林。 newnode函數(shù)為節(jié)點(diǎn)分配內(nèi)存并用它的參數(shù)只來初始化節(jié)點(diǎn)的域。 listnode還負(fù)責(zé)刪除公共子表達(dá)式。,2020/10/9,1、構(gòu)建節(jié)點(diǎn),Node listnodes(Tree tp, int tlab, int flab) Node p

24、 = NULL, l, r; int op; if (tp = NULL) return NULL; if (tp-node) /node標(biāo)識(shí)listnode訪問過的樹 return tp-node; if (isarray(tp-type) op = tp-op + sizeop(voidptype-size); else op = tp-op + sizeop(tp-type-size); switch (generic(tp-op) tpnode p; return p; ,2020/10/9,2、控制流,最簡單的一元和二元操作加入結(jié)點(diǎn)表，但是并不會(huì)出現(xiàn)在根中。賦值等操作可以用這種情況解

25、決。 要改變控制流需要跳轉(zhuǎn)。 case JUMP: l = listnodes(tp-kids0, 0, 0); list(newnode(JUMP+V, l, NULL, NULL); reset(); break;,2020/10/9,static void list(Node p) if (p ,2020/10/9,forest是一個(gè)循環(huán)鏈表，不為空則指向鏈表最后一個(gè)節(jié)點(diǎn)，為空則將其初始化，link域可以表示根結(jié)點(diǎn)。,case LT: /LT代表大于轉(zhuǎn)移，是接口dag標(biāo)識(shí)符 l = listnodes(tp-kids0, 0, 0); r = listnodes(tp-kids1, 0,

26、 0); if (tlab) list(newnode(generic(tp-op) + opkind(l-op), l, r, findlabel(tlab); else if (flab) switch (generic(tp-op) case EQ: op = NE; break;case NE: op = EQ; break; case GT: op = LE; break; case LT: op = GE; break; case GE: op = LT; break; case LE: op = GT; break; default: assert(0); list(newnod

27、e(op + opkind(l-op), l, r, findlabel(flab); if (forest ,2020/10/9,2020/10/9,ai 標(biāo)記與指令對應(yīng)的模板，以區(qū)別子指令（如尋址指令）： static char *_isinstruction;,2020/10/9,lburg從1開始為規(guī)則編號(hào)，并通過返回規(guī)則號(hào)來報(bào)告匹配情況，這樣當(dāng)需要的時(shí)候就可以找到響應(yīng)的模板。如果模板以一個(gè)換行符為結(jié)尾表示它是一條指令，否則就必然是某條指令的一部分，比如是一個(gè)操作數(shù)。 rc: reg %0 rc: con %0 reg: ADDI4(reg,mrc1) ?mov %c,%0nadd %

28、c,%1n 1 reg: ADDP4(reg,mrc1) ?mov %c,%0nadd %c,%1n 1,2020/10/9,emitasm對規(guī)則結(jié)構(gòu)及匯編程序代碼模板進(jìn)行了解釋。 emitasm遞歸調(diào)用自身，以處理地址計(jì)算之類的子指令。 emitasm的遍歷從一個(gè)指令開始，當(dāng)遞歸到達(dá)為該指令提供值的指令時(shí)結(jié)束。 emitasm由emit調(diào)用，emit確保emitasm以正確的順序來處理這些指令，這樣便可以處理指令間的順序。,2020/10/9,例如：發(fā)送器解釋字符串“l(fā)w r%c,%1n” 先生成“l(fā)w r”，然后是目標(biāo)寄存器的名字（通常是一個(gè)數(shù)字），接著是一個(gè)逗號(hào)。如果nts1中保存了表示

29、非終結(jié)符addr的整數(shù)，那么遞歸生成p-kids1作為一個(gè)addr。最后emitasm生成一個(gè)換行符。,2020/10/9,3、寄存器的分配,從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代碼，但是匯編代碼中的寄存器是如何分配的？ 寄存器分配包括兩個(gè)內(nèi)容： 分配：決定哪些值占用寄存器 指派：為每個(gè)值指派特定的寄存器,2020/10/9,2020/10/9,在后端選擇指令并將子指令從樹中分離出來，linearize采用前序遍歷分離的樹，并按照最后執(zhí)行的順序鏈接指令。gen再將每條指令傳遞給ralloc函數(shù)，ralloc一般首先調(diào)用putreg來釋放不再被其子節(jié)點(diǎn)使用的寄存器，然后調(diào)用getreg函數(shù)為自身分配一個(gè)寄存器。對于臨時(shí)變量，ralloc在首次賦值的時(shí)候?yàn)樗峙湟粋€(gè)寄存器，在最后一次使用的時(shí)候釋放該機(jī)存器。,2020/10/9,寄存器狀態(tài)的跟蹤 unsigned freemask2; unsigned usedmask2; 用掩碼表示寄存器的狀態(tài) 對于寄存器r： int n = r-set; r-m