編譯器設計與實現(xiàn)

1、編譯器設計與實現(xiàn)lcc原理剖析華中科技大學計算機學院張 德2021/10/12一、概述1、編譯器各階段2021/10/12詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器錯誤處理器符號表管理器源程序目標程序2、編譯器各階段的分組前端：依賴于語言并很大程度上獨立于目標機器。一般包括語法分析、詞法分析、符號表的建立、語義分析、中間代碼生成以及相關錯誤處理。后端：依賴于目標機器的階段或某些階段的某些部分。一般來說，后端完成的任務不依賴于源語言而只依賴于中間語言。主要包括代碼優(yōu)化、代碼生成以及相關的錯誤處理和符號表操作。2021/10/12二、符號表符號表是編譯器保存信息的中心庫，編譯

2、器的各部分通過符號表進行交互，并訪問符號表中的數據符號。符號表把各種名字映射到符號集合。常量、標識符和標號都是名字，不同名字有不同的屬性。符號管理不僅要處理符號本身，還管理符號的作用域。2021/10/121、符號的表示struct symbol char *name; /名稱int scope;/作用域coordinate src;/在源程序中位置symbol up;/連接符號表中上一個符號list uses;/可保存一個coordinate列表，表示使用情況int sclass;/擴展存儲類型/符號標記type type;/如變量、函數、常量、結構或聯(lián)合等信息floatref;/被引用的粗

3、略次數union /聯(lián)合u為標號、結構、聯(lián)合、枚舉、常量、全局/和靜態(tài)變量提供附加信息 u;/xsymbol x;/由后端處理，如為變量分配寄存器/為調試器產生數據信息2021/10/121、符號的表示scope域：enum constants=1, labels, global, param, local ;第k層中聲明的局部變量其scope域等于local+k。src域：typedef struct coord char *file;unsigned x, y; coordinate;file指名包含該符號定義文件名，y和x表示出現(xiàn)的行號及行中位置。sclass域：符號擴展類型可以是aut

4、o、register、static或extern等首字母大寫的類型表示全小寫類型的指針，如symbol。2021/10/122、符號表的表示externtableconstants;externtableexternals;externtableglobals;externtableidentifiers;externtablelabels;externtabletypes;struct table intlevel; /同symbol中scope域table previous;/符號表鏈表，指向level-1的表struct entry struct symbol sym;struct en

5、try *link; *buckets256;/這是一個哈希鏈數組，方便插入、查找symbol all;/指向當前及其外層所有符號列表的表頭;2021/10/123、符號表舉例、符號表舉例int x, y;f(int x, int a)int b;y = x + a*b;if (y 5)int a;y = x + a*b;2021/10/122021/10/123045600000a b x y4、符號表的相關操作查找和建立標識符symbol install(const char * name, table * tpp, int level, int arena); symbol lookup

6、(const char *name, table tp);標號:與標識符相似，但不涉及作用域常量：這些符號保存在constants表中產生變量：用于產生靜態(tài)變量保存字符串等2021/10/12三、代碼生成接口這一章內容定義了與目標機器無關的前端和與目標機器相關的后端之間的接口。lcc接口包括一些共享數據結構、18個函數和包括36個操作符的語言。該語言用于將可執(zhí)行代碼從源程序生成dag（有向無環(huán)圖）。共享數據結構可供前后端共享，但某些域為一端私有。symbol就是一個共享數據結構。2021/10/121、類型度量typedef struct metrics unsigned char size,

7、 align, outofline; metrics;size:類型的大小；align：對齊字節(jié)數；outofline：控制相關類型的常量的放置。為1時，不出現(xiàn)在dag中，存于靜態(tài)變量中。metrics charmetric;metrics shortmetric;metrics intmetric;metrics floatmetric;metrics doublemetric;metrics structmetric;2021/10/122、接口記錄typedef struct interface xinterfacex;interface;lcc為每一種目標機器形成一個獨有的接口實例。x

8、域是對interface的擴展，后段使用它存放與目標及其相關的接口數據和函數，對后端私有。2021/10/123、dag操作可執(zhí)行代碼用dag來描述。函數體是用dag組成的序列或森林。每個dag都可以同過gen函數傳給后端。dag節(jié)點struct node short op;short count; symbol syms3;node kids2;node link;xnode x;2021/10/123、dag操作op域存放dag操作符。dag操作符后綴表示操作數類型：enum f=float,i=int,u=unsigned,p=pointer,v=void,b=struct;如cnst，

9、有變體cnsti、cnstu、cnstp等。cnst = 1u.sym;return int; goto id;4、標識符識別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: 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: ca

10、se u: case v: case w: case x:case y: case z:id:if (limit - rcp = 6 & prect = 11 & prect = 13) int op = t;t = gettok();if (operop = asgn)p = asgntree(asgn, p, value(expr1(0);else return p2021/10/12條件表達式：conditonal-expression:binary-expression? expression : conditional-expressionstatic tree expr2(void

11、) tree p = expr3(4);if (t = ?) tree l, r;coordinate pts2;if (aflag 1 & isfunc(p-type)warning(%s used in a conditional expressionn,funcname(p);p = pointer(p);t = gettok();pts0 = src;l = pointer(expr(:);pts1 = src;r = pointer(expr2(); return p;2021/10/12另有二元表達式、一元表達式、后綴表達式和基本表達式。表達式分析多是用遞歸和大量switch語句實

12、現(xiàn)。在編譯領域用一個分析函數代替n個函數處理n級優(yōu)先是非常流行的。關于表達式的分析還包括表達式語義的分析，如類型檢查轉換、函數調用分析等各種操作。2021/10/122、語句分析代碼的表示：表達式首先被編譯為分析樹然后轉化為dag。每個函數的dag在代碼表中被串起來，代碼表表示了函數的代碼。code結構：struct code enum blockbeg, blockend, local, address, defpoint, label, start, gen, jump, switch kind;code prev, next;union u;2021/10/12語句的識別：void st

13、atement(int loop, swtch swp, int lev) float ref = refinc;if (aflag = 2 & lev = 15)warning(more than 15 levels of nested statementsn);switch (t) case if: ifstmt(genlabel(2), loop, swp, lev + 1); break;case while: whilestmt(genlabel(3), swp, lev + 1); break;case do: dostmt(genlabel(3), swp, lev + 1);

14、expect(;); break; refinc = ref;expect(;)break;2021/10/12if語句的識別：if expression = 0 goto lstatement1 goto l+1l:statement2l1：static void ifstmt(int lab, int loop, swtch swp, int lev) t = gettok();expect();/判斷if后的（definept(null);walk(conditional(), 0, lab); /包含listnode函數生成dag并加入refinc /= 2.0; /森林，把入口加入代

15、碼表.同時根statement(loop, swp, lev); /據接過設置flab，tlabif (t = else) branch(lab + 1);t = gettok();definelab(lab);statement(loop, swp, lev);if (findlabel(lab + 1)-ref)definelab(lab + 1); elsedefinelab(lab);2021/10/12在循環(huán)、switch、goto語句中都用到了標號和跳轉，標號使通過definelab函數定義的，而跳轉通過branch函數生成。除語句識別外，還有聲明的識別。聲明的識別非常復雜，c語言

16、中聲明的形式很多，處理時大量的相互遞歸調用。經過前端的分析后，將源程序轉化為dag，并添加進代碼表。2021/10/123、小結六、中間代碼生成編譯器的后端通過function接口函數調用gencode和emitcode來遍歷代碼表。walk和listnodes函數操作處理dag森林。newnode函數為節(jié)點分配內存并用它的參數只來初始化節(jié)點的域。listnode還負責刪除公共子表達式。2021/10/121、構建節(jié)點node listnodes(tree tp, int tlab, int flab) node p = null, l, r;int op;if (tp = null)retu

17、rn null;if (tp-node) /node標識listnode訪問過的樹return tp-node;if (isarray(tp-type)op = tp-op + sizeop(voidptype-size);elseop = tp-op + sizeop(tp-type-size);switch (generic(tp-op) tpnode p;return p;2021/10/122、控制流最簡單的一元和二元操作加入結點表，但是并不會出現(xiàn)在根中。賦值等操作可以用這種情況解決。 要改變控制流需要跳轉。case jump: l = listnodes(tp-kids0, 0, 0

18、); list(newnode(jump+v, l, null, null); reset(); break;2021/10/12static void list(node p) if (p & p-link = null) if (forest) p-link = forest-link;forest-link = p; elsep-link = p;forest = p;2021/10/12forest是一個循環(huán)鏈表，不為空則指向鏈表最后一個節(jié)點，為空則將其初始化，link域可以表示根結點。case lt: /lt代表大于轉移，是接口dag標識符 l = listnodes(tp-kids

19、0, 0, 0); r = listnodes(tp-kids1, 0, 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; br

20、eak; default: assert(0); list(newnode(op + opkind(l-op), l, r, findlabel(flab); if (forest & forest-syms0) forest-syms0-ref+; break;2021/10/122021/10/12ai&ai+bi0&ai+bikids1作為一個addr。最后emitasm生成一個換行符。2021/10/123、寄存器的分配從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代碼，但是匯編代碼中的寄存器是如何分配的？寄存器分配包括兩個內容：分配：決定哪些值占用寄存器指派：為每個值指派特定的寄存器20

21、21/10/122021/10/12例程名例程名作用作用 linearize為輸出一棵指令樹排序 ralloc為一條指令釋放和分配寄存器 putreg釋放一個忙寄存器 getreg發(fā)現(xiàn)和分配一個寄存器 askreg發(fā)現(xiàn)和分配一個空寄存器 askfixedreg嘗試分配一個制定的寄存器 spillee標記一個最遠使用寄存器溢出 spill溢出一個或多個寄存器 spillr溢出一個寄存器 genspill產生代碼溢出一個寄存器 genreload產生代碼重載一個被溢出的寄存器 reprune當genreload更新x.kids后，更新kids在后端選擇指令并將子指令從樹中分離出來，lineariz

22、e采用前序遍歷分離的樹，并按照最后執(zhí)行的順序鏈接指令。gen再將每條指令傳遞給ralloc函數，ralloc一般首先調用putreg來釋放不再被其子節(jié)點使用的寄存器，然后調用getreg函數為自身分配一個寄存器。對于臨時變量，ralloc在首次賦值的時候為它分配一個寄存器，在最后一次使用的時候釋放該機存器。2021/10/12寄存器狀態(tài)的跟蹤unsigned freemask2;unsigned usedmask2;用掩碼表示寄存器的狀態(tài)對于寄存器r：int n = r-set;r-mask & freemaskn 為0表示寄存器忙2021/10/12寄存器分配：寄存器分配器對森林進行三遍掃描:第一遍對所有使用臨時變量的節(jié)點建立一個表。該列表指名了臨時變量節(jié)點的最后一次使用。第二遍對森林的掃描刪去一些用于寄存器復制的指令，把計算源寄存器的表達式重定向，使用目的寄存器。最后一遍掃描為每個節(jié)點分配寄存器。2021/10/12寄存器的溢出：寄存器溢出是指寄存器分配器用完寄存器時需