編譯器設(shè)計和實(shí)現(xiàn)課件

編譯器設(shè)計與實(shí)現(xiàn)——Lcc原理剖析華中科技大學(xué)計算機(jī)學(xué)院張德2023/8/7編譯器設(shè)計與實(shí)現(xiàn)——Lcc原理剖析華中科技大學(xué)計算機(jī)學(xué)院201一、概述1、編譯器各階段詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器錯誤處理器符號表管理器源程序目標(biāo)程序2023/8/7一、概述1、編譯器各階段詞法分析器語法分析器語義分析器中間代22、編譯器各階段的分組前端：依賴于語言并很大程度上獨(dú)立于目標(biāo)機(jī)器。一般包括語法分析、詞法分析、符號表的建立、語義分析、中間代碼生成以及相關(guān)錯誤處理。后端：依賴于目標(biāo)機(jī)器的階段或某些階段的某些部分。一般來說，后端完成的任務(wù)不依賴于源語言而只依賴于中間語言。主要包括代碼優(yōu)化、代碼生成以及相關(guān)的錯誤處理和符號表操作。2023/8/72、編譯器各階段的分組前端：依賴于語言并很大程度上獨(dú)立于目標(biāo)3二、符號表符號表是編譯器保存信息的中心庫，編譯器的各部分通過符號表進(jìn)行交互，并訪問符號表中的數(shù)據(jù)——符號。符號表把各種名字映射到符號集合。常量、標(biāo)識符和標(biāo)號都是名字，不同名字有不同的屬性。符號管理不僅要處理符號本身，還管理符號的作用域。2023/8/7二、符號表符號表是編譯器保存信息的中心庫，編譯器的各部分通過41、符號的表示structsymbol{ char *name; //名稱 int scope; //作用域 Coordinate src; //在源程序中位置 Symbol up; //連接符號表中上一個符號 List uses; //可保存一個Coordinate列表，表示使用情況 int sclass; //擴(kuò)展存儲類型 <symbolflag> //符號標(biāo)記 Type type; //如變量、函數(shù)、常量、結(jié)構(gòu)或聯(lián)合等信息 float ref; //被引用的粗略次數(shù) union{ //聯(lián)合u為標(biāo)號、結(jié)構(gòu)、聯(lián)合、枚舉、常量、全局 <appendentinfo> //和靜態(tài)變量提供附加信息 }u; // Xsymbol x; //由后端處理，如為變量分配寄存器 <debuggerextension>// 為調(diào)試器產(chǎn)生數(shù)據(jù)信息}2023/8/71、符號的表示structsymbol{2023/7/351、符號的表示scope域： enum{CONSTANTS=1,LABELS,GLOBAL,PARAM,LOCAL};

第k層中聲明的局部變量其scope域等于LOCAL+k。src域： typedefstructcoord{ char *file; unsigned

x,y; }

Coordinate; file指名包含該符號定義文件名，y和x表示出現(xiàn)的行號及行中位置。sclass域：符號擴(kuò)展類型

可以是AUTO、REGISTER、STATIC或EXTERN等首字母大寫的類型表示全小寫類型的指針，如Symbol。2023/8/71、符號的表示scope域：2023/7/3162、符號表的表示extern Table constants;extern Table externals;extern Table globals;extern Table identifiers;extern Table labels;extern Table types;struct

table{ int level; //同symbol中scope域 Table

previous; //符號表鏈表，指向level-1的表 struct

entry{ struct

symbol

sym; struct

entry

*link; }*buckets[256]; //這是一個哈希鏈數(shù)組，方便插入、查找 Symbol

all; //指向當(dāng)前及其外層所有符號列表的表頭};2023/8/72、符號表的表示extern Table constants73、符號表舉例int x,y;f(intx,inta){ intb; y=x+a*b; if(y<5){ inta; y=x+a*b; }}2023/8/73、符號表舉例int x,y;2023/7/3183045600000abxy2023/8/73456abxy2023/7/94、符號表的相關(guān)操作查找和建立標(biāo)識符Symbolinstall(constchar*name,Table*tpp,intlevel,intarena);Symbollookup(constchar*name,Tabletp);標(biāo)號:與標(biāo)識符相似，但不涉及作用域常量：這些符號保存在constants表中產(chǎn)生變量：用于產(chǎn)生靜態(tài)變量保存字符串等2023/8/74、符號表的相關(guān)操作查找和建立標(biāo)識符2023/7/3110三、代碼生成接口這一章內(nèi)容定義了與目標(biāo)機(jī)器無關(guān)的前端和與目標(biāo)機(jī)器相關(guān)的后端之間的接口。Lcc接口包括一些共享數(shù)據(jù)結(jié)構(gòu)、18個函數(shù)和包括36個操作符的語言。該語言用于將可執(zhí)行代碼從源程序生成dag（有向無環(huán)圖）。共享數(shù)據(jù)結(jié)構(gòu)可供前后端共享，但某些域?yàn)橐欢怂接?。symbol就是一個共享數(shù)據(jù)結(jié)構(gòu)。2023/8/7三、代碼生成接口這一章內(nèi)容定義了與目標(biāo)機(jī)器無關(guān)的前端和與目標(biāo)111、類型度量typedefstructmetrics{ unsignedcharsize,align,outofline;}Metrics;size:類型的大??；align：對齊字節(jié)數(shù)；outofline：控制相關(guān)類型的常量的放置。為1時，不出現(xiàn)在dag中，存于靜態(tài)變量中。Metrics

charmetric;Metrics

shortmetric;Metrics

intmetric;Metrics

floatmetric;Metrics

doublemetric;Metrics

structmetric;2023/8/71、類型度量typedefstructmetrics{122、接口記錄 typedefstructinterface{ <metrics> <interfaceflags> <interfacefunctions> Xinterface x; } Interface;lcc為每一種目標(biāo)機(jī)器形成一個獨(dú)有的接口實(shí)例。x域是對interface的擴(kuò)展，后段使用它存放與目標(biāo)及其相關(guān)的接口數(shù)據(jù)和函數(shù)，對后端私有。2023/8/72、接口記錄 typedefstructinte133、dag操作可執(zhí)行代碼用dag來描述。函數(shù)體是用dag組成的序列或森林。每個dag都可以同過gen函數(shù)傳給后端。dag節(jié)點(diǎn) struct

node{ short

op; short

count; Symbol

syms[3]; Node

kids[2]; Node

link; Xnode

x; };2023/8/73、dag操作可執(zhí)行代碼用dag來描述。函數(shù)體是用dag組成143、dag操作op域存放dag操作符。dag操作符后綴表示操作數(shù)類型：enum{ F=FLOAT, I=INT, U=UNSIGNED, P=POINTER, V=VOID, B=STRUCT};如CNST，有變體CNSTI、CNSTU、CNSTP等。 CNST

=

1<<4； CNSTC=CNST+F； CNSTI=CNST+I； ……2023/8/73、dag操作op域存放dag操作符。2023/7/31152023/8/72023/7/31162023/8/72023/7/31173、dag操作舉例：inti,*p;f(){i=*p++;}3CNSTI45ASGNP1ADDRGPp7INDIRI6ADDRGPi8ASGNI4ADDP2INDIRP2023/8/73、dag操作舉例：inti,*p;f(){i184、接口標(biāo)志 unsignedlittle_endian:1;目標(biāo)機(jī)器存儲是低位優(yōu)先還是高位優(yōu)先 unsignedmulops_calls:1;有硬件實(shí)現(xiàn)乘、除和求余，mulopes_calls應(yīng)等于0 unsignedwants_callb:1;通知前端產(chǎn)生CALLB節(jié)點(diǎn)以調(diào)用返回結(jié)構(gòu)的函數(shù) unsignedwants_argb:1;通知前端節(jié)點(diǎn)產(chǎn)生ARGB節(jié)點(diǎn)以產(chǎn)生結(jié)構(gòu)參數(shù) unsignedleft_to_right:1;告訴前端按照從左到右的順序計算和提交參數(shù)給后端 unsignedwants_dag:1;告訴前端傳遞dag給后端2023/8/74、接口標(biāo)志 unsignedlittle_endian:195、函數(shù)前端將函數(shù)編譯為私有數(shù)據(jù)結(jié)構(gòu)。將函數(shù)的任意部分傳遞給后端之前，前端必須先對每個函數(shù)進(jìn)行完整的分析。函數(shù)的處理：function函數(shù)包括前端過程gencode遍歷前端的私有數(shù)據(jù)結(jié)構(gòu)，將dag的每個森林傳給后端過程gen。gen選擇代碼，在dag上添加注釋并將返回一個dag指針。gencode還可以調(diào)用local宣告新的局不變量。前端過程emitcode再次遍歷，將gen返回的指針傳遞給emit函數(shù)發(fā)送代碼。2023/8/75、函數(shù)前端將函數(shù)編譯為私有數(shù)據(jù)結(jié)構(gòu)。將函數(shù)的任意部分傳遞給206、上行調(diào)用

前段調(diào)用后端以執(zhí)行代碼生成和發(fā)送。后端調(diào)用前端完成輸出、分配存儲空間、查詢類型等功能。上行調(diào)用即后端調(diào)用前端。allocate分配空間，保證對齊方式符合機(jī)器多

數(shù)類型newnode分配新的dag節(jié)點(diǎn)newconst符號表中創(chuàng)建新的常量newtemp符號表中創(chuàng)建新的變量……2023/8/76、上行調(diào)用 前段調(diào)用后端以執(zhí)行代碼生成和發(fā)送。后端調(diào)用前21四、詞法分析詞法分析器讀入源程序，產(chǎn)生語言的基本詞法單元。例：*prt＝56；單詞編碼附加值‘*’ID“prt”‘＝’ICON“56”2023/8/7四、詞法分析詞法分析器讀入源程序，產(chǎn)生語言的基本詞法單元。單221、輸入bufferbuffer+MAXLINEbuffer+MAXLINE＋MAXSIZE\ncplimit當(dāng)limit-cp小于某一個固定值時，調(diào)用fillbuf函數(shù)填充buffer2023/8/71、輸入bufferbuffer+MAXLINEbuffer232、單詞識別部分文法：token: keyword identifier constant operator punctuatorpunctuator: oneof[](){}*,:=;…定義：ID標(biāo)識符FCON 浮點(diǎn)常量ICON整型常量SCON…INCRDECRDEREF……2023/8/72、單詞識別部分文法：定義：2023/7/3124emun{#definexx(a,b,c,d,e,f,g)a=b,#defineyy(a,b,c,d,e,f,g)#include“token.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(VOID,8,0,0,0,CHAR,"void")xx(STRUCT,9,0,0,0,CHAR,"struct")……2023/8/7emun{2023/7/31253、關(guān)鍵字的識別可以通過查表完成，也可以通過硬編碼方式識別。例如，當(dāng)起始小寫字母為i時由gettok函數(shù)中switch語句的case‘i’處理。case'i':if(rcp[0]=='f'&&!(map[rcp[1]]&(DIGIT|LETTER))){ cp=rcp+1; returnIF;}if(rcp[0]=='n'&&rcp[1]=='t'&&!(map[rcp[2]]&(DIGIT|LETTER))){ cp=rcp+2; tsym=inttype->u.sym; returnINT;}gotoid;2023/8/73、關(guān)鍵字的識別可以通過查表完成，也可以通過硬編碼方式識別。264、標(biāo)識符識別 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':case'U':case'V':case'W':case'X': case'Y':case'Z': id: if(limit-rcp<MAXLINE){ cp=rcp-1; fillbuf(); rcp=++cp; } assert(cp==rcp); token=(char*)rcp-1; while(map[*rcp]&(DIGIT|LETTER)) rcp++; token=stringn(token,(char*)rcp-token); tsym=lookup(token,identifiers); cp=rcp; returnID;檢查是否需要填充buffer2023/8/74、標(biāo)識符識別 case'h':case'j':c275、其他另外還有：數(shù)字識別字符常量和字符串識別都是有g(shù)ettok函數(shù)實(shí)現(xiàn)，實(shí)現(xiàn)方法相似。

詞法分析器可以有象LEX這樣的工具實(shí)現(xiàn)。Lcc手工實(shí)現(xiàn)了詞法分析器，體積更小。2023/8/75、其他另外還有：2023/7/3128五、語法分析根據(jù)語言的文法分析，以確認(rèn)輸入是否符合語言規(guī)則，并建立輸入源程序的內(nèi)部表示。Lcc采用遞歸下降的語法分析。語法分析以形式語言理論為基礎(chǔ)，采取語法制導(dǎo)翻譯方法，處理程序中的錯誤。2023/8/7五、語法分析根據(jù)語言的文法分析，以確認(rèn)輸入是否符合語言規(guī)則，291、表達(dá)式表達(dá)式的表示：(a+b)+b*(a+b)ADD+IADDRG+PaMUL+IADD+IINDIR+IINDIR+IADD+IADDRG+PbADDRG+PbINDIR+IINDIR+IINDIR+IADDRG+PaADDRG+Pb2023/8/71、表達(dá)式表達(dá)式的表示：(a+b)+b*(a+b)ADD+30表達(dá)式的分析：c語言的小部分表達(dá)式語法: expr:term{+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();factor()}voidfactor(){if(t==ID)t=gettok();elseif(t==‘(’){t=gettok();expr();expect(‘)’);}}2023/8/7表達(dá)式的分析：voidfactor(){2023/7/3131c語言表達(dá)式分析賦值表達(dá)式：assignment-expression: conditional-expression unary-expressionassign-operatorassignment-expressionTreeexpr1(inttok){ staticcharstop[]={IF,ID,0}; Treep=expr2(); if(t=='=‘||(prec[t]>=6&&prec[t]<=8) ||(prec[t]>=11&&prec[t]<=13)){ intop=t; t=gettok(); if(oper[op]==ASGN) p=asgntree(ASGN,p,value(expr1(0))); else<augmentedassignment> returnp}2023/8/7c語言表達(dá)式分析2023/7/3132條件表達(dá)式：

conditonal-expression: binary-expression[?expression:conditional-expression]staticTreeexpr2(void){ Treep=expr3(4); if(t=='?'){ Treel,r; Coordinatepts[2]; if(Aflag>1&&isfunc(p->type)) warning("%susedinaconditionalexpression\n", funcname(p)); p=pointer(p); t=gettok(); pts[0]=src; l=pointer(expr(':')); pts[1]=src; r=pointer(expr2()); }<other> returnp;}2023/8/7條件表達(dá)式：2023/7/3133另有二元表達(dá)式、一元表達(dá)式、后綴表達(dá)式和基本表達(dá)式。表達(dá)式分析多是用遞歸和大量switch語句實(shí)現(xiàn)。在編譯領(lǐng)域用一個分析函數(shù)代替n個函數(shù)處理n級優(yōu)先是非常流行的。關(guān)于表達(dá)式的分析還包括表達(dá)式語義的分析，如類型檢查轉(zhuǎn)換、函數(shù)調(diào)用分析等各種操作。2023/8/7另有二元表達(dá)式、一元表達(dá)式、后綴表達(dá)式和基本表達(dá)式。2023342、語句分析代碼的表示：表達(dá)式首先被編譯為分析樹然后轉(zhuǎn)化為dag。每個函數(shù)的dag在代碼表中被串起來，代碼表表示了函數(shù)的代碼。 code結(jié)構(gòu)：structcode{ enum{Blockbeg,Blockend,Local,Address,Defpoint, Label,Start,Gen,Jump,Switch }kind; Codeprev,next; union{ <unions> }u;}2023/8/72、語句分析代碼的表示：表達(dá)式首先被編譯為分析樹然后轉(zhuǎn)化為d35語句的識別：voidstatement(intloop,Swtchswp,intlev){ floatref=refinc; if(Aflag>=2&&lev==15) warning("morethan15levelsofnestedstatements\n"); switch(t){ caseIF:ifstmt(genlabel(2),loop,swp,lev+1);break; caseWHILE:whilestmt(genlabel(3),swp,lev+1);break; caseDO:dostmt(genlabel(3),swp,lev+1);expect(';');break; …… } <check> refinc=ref;}expect(‘;’)break;2023/8/7語句的識別：2023/7/3136if語句的識別：

ifexpression==0gotoL

statement1 gotoL+1L: statement2L＋1： staticvoidifstmt(intlab,intloop,Swtchswp,intlev){ t=gettok(); expect(‘(’); //判斷if后的（ definept(NULL); walk(conditional(‘)’),0,lab);//包含listnode函數(shù)生成dag并加入 refinc/=2.0; //森林，把入口加入代碼表.同時根 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); }2023/8/7if語句的識別：2023/7/3137在循環(huán)、switch、goto語句中都用到了標(biāo)號和跳轉(zhuǎn)，標(biāo)號使通過definelab函數(shù)定義的，而跳轉(zhuǎn)通過branch函數(shù)生成。除語句識別外，還有聲明的識別。聲明的識別非常復(fù)雜，c語言中聲明的形式很多，處理時大量的相互遞歸調(diào)用。經(jīng)過前端的分析后，將源程序轉(zhuǎn)化為dag，并添加進(jìn)代碼表。3、小結(jié)2023/8/7在循環(huán)、switch、goto語句中都用到了標(biāo)號3、小結(jié)2038六、中間代碼生成編譯器的后端通過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á)式。2023/8/7六、中間代碼生成2023/7/31391、構(gòu)建節(jié)點(diǎn)Nodelistnodes(Treetp,inttlab,intflab){ Nodep=NULL,l,r; intop; if(tp==NULL) returnNULL; if(tp->node)//node標(biāo)識listnode訪問過的樹 returntp->node; if(isarray(tp->type)) op=tp->op+sizeop(voidptype->size); else op=tp->op+sizeop(tp->type->size); switch(generic(tp->op)){ <listnodescases> } tp－>node＝p; returnp;}2023/8/71、構(gòu)建節(jié)點(diǎn)Nodelistnodes(Treetp,402、控制流最簡單的一元和二元操作加入結(jié)點(diǎn)表，但是并不會出現(xiàn)在根中。賦值等操作可以用這種情況解決。要改變控制流需要跳轉(zhuǎn)。

caseJUMP:{ l=listnodes(tp->kids[0],0,0); list(newnode(JUMP+V,l,NULL,NULL)); reset(); }break;2023/8/72、控制流最簡單的一元和二元操作加入結(jié)點(diǎn)表，但是并不會出現(xiàn)在41staticvoidlist(Nodep){ if(p&&p->link==NULL){ if(forest){ p->link=forest->link; forest->link=p; }else p->link=p; forest=p; }}forest是一個循環(huán)鏈表，不為空則指向鏈表最后一個節(jié)點(diǎn)，為空則將其初始化，link域可以表示根結(jié)點(diǎn)。2023/8/7staticvoidlist(Nodep){fore42 caseLT:{//LT代表大于轉(zhuǎn)移，是接口dag標(biāo)識符 l=listnodes(tp->kids[0],0,0); r=listnodes(tp->kids[1],0,0); if(tlab) list(newnode(generic(tp->op)+opkind(l->op),l,r,findlabel(tlab))); elseif(flab){ switch(generic(tp->op)){ caseEQ:op=NE;break;caseNE:op=EQ;break; caseGT:op=LE;break;caseLT:op=GE;break; caseGE:op=LT;break;caseLE:op=GT;break; default:assert(0); } list(newnode(op+opkind(l->op),l,r,findlabel(flab))); } if(forest&&forest->syms[0]) forest->syms[0]->ref++;}break;2023/8/7 caseLT:{//LT代表大于轉(zhuǎn)移，是接口43a[i]&&a[i]+b[i]>0&&a[i]+b[i]<10的森林EQI2LEI2GEI2LABELV2INDIRICNSTI0ADDIADDPLSHIADDRGPaINDIRICNSTI2ADDRGPiINDIRIADDPADDRGPbCNSTI102023/8/7a[i]&&a[i]+b[i]>0&&a[i]+b[i]<144七、代碼生成器代碼生成器：為編譯前端提供接口函數(shù)，接口函數(shù)用與目標(biāo)機(jī)器相關(guān)的指令來實(shí)現(xiàn)無關(guān)的中間代碼。接口函數(shù)也為臨時變量指派寄存器、固定的函數(shù)單元或?？臻g。Lcc將大部分與機(jī)器無關(guān)的函數(shù)重組到一個大的與機(jī)器無關(guān)的程序中。2023/8/7七、代碼生成器代碼生成器：為編譯前端提供接口函數(shù)，接口函數(shù)用45例程名功能function產(chǎn)生函數(shù)的頭代碼和尾代碼，調(diào)用gencodegencode解釋代碼表，并將數(shù)傳遞給gengen處理代碼表中各個森林rewriteprelabel修改樹，以適應(yīng)寄存器變量和特殊的目標(biāo)機(jī)器_label用所有可能的實(shí)現(xiàn)標(biāo)記樹reduce選擇代價最小的實(shí)現(xiàn)prune從樹中提出某些自指令linearize輸出排序指令ralloc分配寄存器emitcode解釋代碼表，為每個森林調(diào)用emitemit追溯指令列表requate刪除寄存器到寄存器的復(fù)制moveself刪除寄存器復(fù)制到自身的指令emitasm解釋匯編模版，輸出大多數(shù)指令emit2輸出過復(fù)雜不適于模版的指令2023/8/7例程名功能function產(chǎn)生函數(shù)的頭代碼和尾代碼，調(diào)用ge461、選擇和發(fā)送指令Lcc的指令選擇器時由程序lburg根據(jù)緊縮規(guī)范自動生成的，lburg是代碼生成器的生成器。lburg接收緊縮規(guī)范并產(chǎn)生一個用c語言編寫的樹分析程序，該程序?yàn)槟繕?biāo)機(jī)器選擇指令。樹分析程序接受中間代碼的主題樹，并將它分割成與目標(biāo)機(jī)器相對應(yīng)的程序塊，成為數(shù)覆蓋。2023/8/71、選擇和發(fā)送指令Lcc的指令選擇器時由程序lburg根據(jù)緊47模式：ADDI(reg，con)表示如果ADDI的第一個子節(jié)點(diǎn)能遞歸的匹配reg，第二個子節(jié)點(diǎn)匹配con，那么該模式就在ADDI除匹配一棵樹。規(guī)則：addr：ADDI（reg，con）規(guī)定了非終結(jié)符addr與上述模式相匹配規(guī)則：stmt：ASGNI（addr，reg）規(guī)定了ASGNI節(jié)點(diǎn)的每子節(jié)點(diǎn)遞歸的與addr和reg匹配非終結(jié)符stmt就與該ASGNI匹配。例：ASGNI(ADDP(INDIRP(ADDRLP(p)),CNSTI(4)),CNSTI(5))的覆蓋ASGNIADDPINDIRPCNSTI4ADDRLPpCNSTI5addr：ADDP（addr，con）reg：INDIRP（addr）addr：ADDRLPcon：CNSTIreg：concon：CNSTIstmt：ASGNI（addr，reg）2023/8/7模式：ADDI(reg，con)表示如果ADDI的第一個子節(jié)482023/8/72023/7/31492023/8/72023/7/31502、發(fā)送器Lcc發(fā)送器（emitter）的作用是為目標(biāo)機(jī)器輸出代碼。發(fā)送器并不依賴于目標(biāo)機(jī)器，由兩個描述與機(jī)器相關(guān)的數(shù)據(jù)的數(shù)組驅(qū)動。Lburg為每個BURM生成一些c語言代碼，用來聲明并初始化這兩個數(shù)組。兩個數(shù)組都是通過規(guī)則號索引。規(guī)則生成模板數(shù)組：staticchar*_template[];標(biāo)記與指令對應(yīng)的模板，以區(qū)別子指令（如尋址指令）：staticchar*_isinstruction[];2023/8/72、發(fā)送器Lcc發(fā)送器（emitter）的作用是為目標(biāo)機(jī)器輸51 lburg從1開始為規(guī)則編號，并通過返回規(guī)則號來報告匹配情況，這樣當(dāng)需要的時候就可以找到響應(yīng)的模板。如果模板以一個換行符為結(jié)尾表示它是一條指令，否則就必然是某條指令的一部分，比如是一個操作數(shù)。 rc:reg"%0" rc:con"%0" reg:ADDI4(reg,mrc1)"?mov%c,%0\nadd%c,%1\n"1 reg:ADDP4(reg,mrc1)"?mov%c,%0\nadd%c,%1\n"12023/8/7 lburg從1開始為規(guī)則編號，并通過返回規(guī)則號來報告匹配52emitasm對規(guī)則結(jié)構(gòu)及匯編程序代碼模板進(jìn)行了解釋。emitasm遞歸調(diào)用自身，以處理地址計算之類的子指令。emitasm的遍歷從一個指令開始，當(dāng)遞歸到達(dá)為該指令提供值的指令時結(jié)束。emitasm由emit調(diào)用，emit確保emitasm以正確的順序來處理這些指令，這樣便可以處理指令間的順序。2023/8/7emitasm對規(guī)則結(jié)構(gòu)及匯編程序代碼模板進(jìn)行了解釋。20253例如：發(fā)送器解釋字符串“l(fā)wr%c,%1\n”

先生成“l(fā)wr”，然后是目標(biāo)寄存器的名字（通常是一個數(shù)字），接著是一個逗號。如果nts[1]中保存了表示非終結(jié)符addr的整數(shù)，那么遞歸生成p->kids[1]作為一個addr。最后emitasm生成一個換行符。2023/8/7例如：發(fā)送器解釋字符串“l(fā)wr%c,%1\n”2023/543、寄存器的分配從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代碼，但是匯編代碼中的寄存器是如何分配的？寄存器分配包括兩個內(nèi)容：分配：決定哪些值占用寄存器指派：為每個值指派特定的寄存器2023/8/73、寄存器的分配從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代55例程名作用linearize為輸出一棵指令樹排序ralloc為一條指令釋放和分配寄存器putreg釋放一個忙寄存器getreg發(fā)現(xiàn)和分配一個寄存器askreg發(fā)現(xiàn)和分配一個空寄存器askfixedreg嘗試分配一個制定的寄存器spillee標(biāo)記一個最遠(yuǎn)使用寄存器溢出spill溢出一個或多個寄存器spillr溢出一個寄存器genspill產(chǎn)生代碼溢出一個寄存器