編譯器設(shè)計(jì)和實(shí)現(xiàn)--Lcc原理剖析課件

編譯器設(shè)計(jì)與實(shí)現(xiàn)——原理剖析華中科技大學(xué)計(jì)算機(jī)學(xué)院張德2023/7/26一、概述1、編譯器各階段詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器錯(cuò)誤處理器符號(hào)表管理器源程序目標(biāo)程序2023/7/262、編譯器各階段的分組前端：依賴于語言并很大程度上獨(dú)立于目標(biāo)機(jī)器。一般包括語法分析、詞法分析、符號(hào)表的建立、語義分析、中間代碼生成以及相關(guān)錯(cuò)誤處理。后端：依賴于目標(biāo)機(jī)器的階段或某些階段的某些部分。一般來說，后端完成的任務(wù)不依賴于源語言而只依賴于中間語言。主要包括代碼優(yōu)化、代碼生成以及相關(guān)的錯(cuò)誤處理和符號(hào)表操作。2023/7/26二、符號(hào)表符號(hào)表是編譯器保存信息的中心庫，編譯器的各部分通過符號(hào)表進(jìn)行交互，并訪問符號(hào)表中的數(shù)據(jù)——符號(hào)。符號(hào)表把各種名字映射到符號(hào)集合。常量、標(biāo)識(shí)符和標(biāo)號(hào)都是名字，不同名字有不同的屬性。符號(hào)管理不僅要處理符號(hào)本身，還管理符號(hào)的作用域。2023/7/261、符號(hào)的表示{ *; 名稱 ; 作用域 ; 在源程序中位置 ; 連接符號(hào)表中上一個(gè)符號(hào) ; 可保存一個(gè)列表，表示使用情況 ; 擴(kuò)展存儲(chǔ)類型 <> 符號(hào)標(biāo)記 ; 如變量、函數(shù)、常量、結(jié)構(gòu)或聯(lián)合等信息 ; 被引用的粗略次數(shù) { 聯(lián)合u為標(biāo)號(hào)、結(jié)構(gòu)、聯(lián)合、枚舉、常量、全局 <> 和靜態(tài)變量提供附加信息 }u; x; 由后端處理，如為變量分配寄存器 <> 為調(diào)試器產(chǎn)生數(shù)據(jù)信息}2023/7/261、符號(hào)的表示域： {1,,,,}; 第k層中聲明的局部變量其域等于。域： { *; x,y; }; 指名包含該符號(hào)定義文件名，y和x表示出現(xiàn)的行號(hào)及行中位置。域：符號(hào)擴(kuò)展類型 可以是、、或等首字母大寫的類型表示全小寫類型的指針，如。2023/7/262、符號(hào)表的表示 ; ; ; ; ; ;{ ; 同中域 ; 符號(hào)表鏈表，指向1的表 { ; *; }*[256]; 這是一個(gè)哈希鏈數(shù)組，方便插入、查找 ; 指向當(dāng)前及其外層所有符號(hào)列表的表頭};2023/7/263、符號(hào)表舉例 x,y;f(x,a){ b; y=x+a*b; (y<5){ a; y=x+a*b; }}2023/7/263045600000abxy2023/7/264、符號(hào)表的相關(guān)操作查找和建立標(biāo)識(shí)符(*,*,,);(*,);標(biāo)號(hào):與標(biāo)識(shí)符相似，但不涉及作用域常量：這些符號(hào)保存在表中產(chǎn)生變量：用于產(chǎn)生靜態(tài)變量保存字符串等2023/7/26三、代碼生成接口這一章內(nèi)容定義了與目標(biāo)機(jī)器無關(guān)的前端和與目標(biāo)機(jī)器相關(guān)的后端之間的接口。接口包括一些共享數(shù)據(jù)結(jié)構(gòu)、18個(gè)函數(shù)和包括36個(gè)操作符的語言。該語言用于將可執(zhí)行代碼從源程序生成（有向無環(huán)圖）。共享數(shù)據(jù)結(jié)構(gòu)可供前后端共享，但某些域?yàn)橐欢怂接?。就是一個(gè)共享數(shù)據(jù)結(jié)構(gòu)。2023/7/261、類型度量{ ,,;};:類型的大小；：對(duì)齊字節(jié)數(shù)；：控制相關(guān)類型的常量的放置。為1時(shí)，不出現(xiàn)在中，存于靜態(tài)變量中。;;;;;;2023/7/262、接口記錄 { <> <> <> x; } ;為每一種目標(biāo)機(jī)器形成一個(gè)獨(dú)有的接口實(shí)例。x域是對(duì)的擴(kuò)展，后段使用它存放與目標(biāo)及其相關(guān)的接口數(shù)據(jù)和函數(shù)，對(duì)后端私有。2023/7/263、操作可執(zhí)行代碼用來描述。函數(shù)體是用組成的序列或森林。每個(gè)都可以同過函數(shù)傳給后端。節(jié)點(diǎn) { ; ; [3]; [2]; ; x; };2023/7/263、操作域存放操作符。操作符后綴表示操作數(shù)類型：{ , , , , ,

};如，有變體、、等。 =1<<4； ； ； ……2023/7/262023/7/262023/7/263、操作舉例：i,*p;f(){i=*;}3CNSTI45ASGNP1ADDRGPp7INDIRI6ADDRGPi8ASGNI4ADDP2INDIRP2023/7/264、接口標(biāo)志 :1;目標(biāo)機(jī)器存儲(chǔ)是低位優(yōu)先還是高位優(yōu)先 :1;有硬件實(shí)現(xiàn)乘、除和求余，應(yīng)等于0 :1;通知前端產(chǎn)生節(jié)點(diǎn)以調(diào)用返回結(jié)構(gòu)的函數(shù) :1;通知前端節(jié)點(diǎn)產(chǎn)生節(jié)點(diǎn)以產(chǎn)生結(jié)構(gòu)參數(shù) :1;告訴前端按照從左到右的順序計(jì)算和提交參數(shù)給后端 :1;告訴前端傳遞給后端2023/7/265、函數(shù)前端將函數(shù)編譯為私有數(shù)據(jù)結(jié)構(gòu)。將函數(shù)的任意部分傳遞給后端之前，前端必須先對(duì)每個(gè)函數(shù)進(jìn)行完整的分析。函數(shù)的處理：函數(shù)包括前端過程遍歷前端的私有數(shù)據(jù)結(jié)構(gòu)，將的每個(gè)森林傳給后端過程。選擇代碼，在上添加注釋并將返回一個(gè)指針。還可以調(diào)用宣告新的局不變量。前端過程再次遍歷，將返回的指針傳遞給函數(shù)發(fā)送代碼。2023/7/266、上行調(diào)用 前段調(diào)用后端以執(zhí)行代碼生成和發(fā)送。后端調(diào)用前端完成輸出、分配存儲(chǔ)空間、查詢類型等功能。上行調(diào)用即后端調(diào)用前端。分配空間，保證對(duì)齊方式符合機(jī)器多 數(shù)類型分配新的節(jié)點(diǎn)符號(hào)表中創(chuàng)建新的常量符號(hào)表中創(chuàng)建新的變量……2023/7/26四、詞法分析詞法分析器讀入源程序，產(chǎn)生語言的基本詞法單元。例：*＝56；單詞編碼附加值‘*’“”‘＝’“56”2023/7/261、輸入bufferbuffer+MAXLINEbuffer+MAXLINE＋MAXSIZE\n當(dāng)小于某一個(gè)固定值時(shí)，調(diào)用函數(shù)填充2023/7/262、單詞識(shí)別部分文法：:

: [](){}*,:=;…定義：標(biāo)識(shí)符 浮點(diǎn)常量整型常量………2023/7/26{(),()“”}文件：(0,0,0,0,0,0,0)(,1,0,0,0,,"")(,2,0,0,0,,"")(,3,0,0,0,,"")(,4,0,0,0,,"")(,5,0,0,0,,"")(,6,0,0,0,,"")(,7,0,0,0,0,"")(,8,0,0,0,,"")(,9,0,0,0,,"")……2023/7/263、關(guān)鍵字的識(shí)別可以通過查表完成，也可以通過硬編碼方式識(shí)別。例如，當(dāng)起始小寫字母為i時(shí)由函數(shù)中語句的‘i’處理。'i':([0]'f'!([[1]]&())){ =+1; ;}([0]'n'[1]'t'!([[2]]&())){ =+2; =>; ;};2023/7/264、標(biāo)識(shí)符識(shí)別 'h':'j':'k':'m':'n':'o': 'p':'q':'x':'y':'z': 'A':'B':'C':'D':'E':'F': 'G':'H':'I':'J':'K': 'M':'N':'O':'P':'Q':'R': 'S':'T':'U':'V':'W':'X': 'Y':'Z': : (-<){ =-1; (); =; } (); =(*)-1; ([*]&()) ; =(,(*)-); =(,); =; ;檢查是否需要填充2023/7/265、其他另外還有：數(shù)字識(shí)別字符常量和字符串識(shí)別都是有函數(shù)實(shí)現(xiàn)，實(shí)現(xiàn)方法相似。 詞法分析器可以有象這樣的工具實(shí)現(xiàn)。手工實(shí)現(xiàn)了詞法分析器，體積更小。2023/7/26五、語法分析根據(jù)語言的文法分析，以確認(rèn)輸入是否符合語言規(guī)則，并建立輸入源程序的內(nèi)部表示。采用遞歸下降的語法分析。語法分析以形式語言理論為基礎(chǔ)，采取語法制導(dǎo)翻譯方法，處理程序中的錯(cuò)誤。2023/7/261、表達(dá)式表達(dá)式的表示：()*()ADD+IADDRG+PaMUL+IADD+IINDIR+IINDIR+IADD+IADDRG+PbADDRG+PbINDIR+IINDIR+IINDIR+IADDRG+PaADDRG+Pb2023/7/26表達(dá)式的分析：c語言的小部分表達(dá)式語法: :{} :{*} :‘(’‘)’T()T({})T()T({})()({})()(t‘+’){T()}()(t‘+’){T(+)T()}()(t‘+’){t=()()}()(t‘+’){t=();()}同理得分析函數(shù)是：()(t‘*’){t=();()}(){()();(t‘(’){();();(‘)’);}}2023/7/26c語言表達(dá)式分析賦值表達(dá)式：:

1(){ []={,,0}; p=2(); (t'=‘([t]>=6[t]<=8) ([t]>=11[t]<=13)){ =t; t=(); ([]) p=(,p,(1(0)));

<> p}2023/7/26條件表達(dá)式： : [?:]2(){ p=3(4); (t'?'){ l,r; [2]; (>1(>)) ("a\n", (p)); p=(p); t=(); [0]=; l=((':')); [1]=; r=(2()); }<> p;}2023/7/26另有二元表達(dá)式、一元表達(dá)式、后綴表達(dá)式和基本表達(dá)式。表達(dá)式分析多是用遞歸和大量語句實(shí)現(xiàn)。在編譯領(lǐng)域用一個(gè)分析函數(shù)代替n個(gè)函數(shù)處理n級(jí)優(yōu)先是非常流行的。關(guān)于表達(dá)式的分析還包括表達(dá)式語義的分析，如類型檢查轉(zhuǎn)換、函數(shù)調(diào)用分析等各種操作。2023/7/262、語句分析代碼的表示：表達(dá)式首先被編譯為分析樹然后轉(zhuǎn)化為。每個(gè)函數(shù)的在代碼表中被串起來，代碼表表示了函數(shù)的代碼。 結(jié)構(gòu)：{ {,,,,, ,,,, }; ,; { <> }u;}2023/7/26語句的識(shí)別：(,,){ =; (>=215) ("15\n"); (t){ :((2),,,+1);; :((3),,+1);; :((3),,+1);(';');; …… } <> =;}(‘;’);2023/7/26語句的識(shí)別： 0L 1 1L: 2L＋1： (,,,){ t=(); (‘(’); 判斷后的（ (); ((‘)’),0,);包含函數(shù)生成并加入 2.0; 森林，把入口加入代碼表.同時(shí)根 (,,); 據(jù)接過設(shè)置， (t){ (+1); t=(); (); (,,); ((+1)->) (+1); } (); }2023/7/26在循環(huán)、、語句中都用到了標(biāo)號(hào)和跳轉(zhuǎn)，標(biāo)號(hào)使通過函數(shù)定義的，而跳轉(zhuǎn)通過函數(shù)生成。除語句識(shí)別外，還有聲明的識(shí)別。聲明的識(shí)別非常復(fù)雜，c語言中聲明的形式很多，處理時(shí)大量的相互遞歸調(diào)用。經(jīng)過前端的分析后，將源程序轉(zhuǎn)化為，并添加進(jìn)代碼表。3、小結(jié)2023/7/26六、中間代碼生成編譯器的后端通過接口函數(shù)調(diào)用和來遍歷代碼表。和函數(shù)操作處理森林。函數(shù)為節(jié)點(diǎn)分配內(nèi)存并用它的參數(shù)只來初始化節(jié)點(diǎn)的域。還負(fù)責(zé)刪除公共子表達(dá)式。2023/7/261、構(gòu)建節(jié)點(diǎn)(,,){ p=,l,r; ; () ; (>)標(biāo)識(shí)訪問過的樹 >; ((>)) =>+(>);

=>+(>>); ((>)){ <> } －>＝p; p;}2023/7/262、控制流最簡(jiǎn)單的一元和二元操作加入結(jié)點(diǎn)表，但是并不會(huì)出現(xiàn)在根中。賦值等操作可以用這種情況解決。要改變控制流需要跳轉(zhuǎn)。 :{ l=(>[0],0,0); ((,l,,)); (); };2023/7/26(p){ (p>){ (){ >=>; >=p; } >=p; =p; }}是一個(gè)循環(huán)鏈表，不為空則指向鏈表最后一個(gè)節(jié)點(diǎn)，為空則將其初始化，域可以表示根結(jié)點(diǎn)。2023/7/26 :{代表大于轉(zhuǎn)移，是接口標(biāo)識(shí)符 l=(>[0],0,0); r=(>[1],0,0); () (((>)+(>),l,r,())); (){ ((>)){ :=;:=;; :=;;:=;; :=;;:=;; :(0); } ((+(>),l,r,())); } (>[0]) >[0]->;};2023/7/26a[i][i][i]>0[i][i]<10的森林EQI2LEI2GEI2LABELV2INDIRICNSTI0ADDIADDPLSHIADDRGPaINDIRICNSTI2ADDRGPiINDIRIADDPADDRGPbCNSTI102023/7/26七、代碼生成器代碼生成器：為編譯前端提供接口函數(shù)，接口函數(shù)用與目標(biāo)機(jī)器相關(guān)的指令來實(shí)現(xiàn)無關(guān)的中間代碼。接口函數(shù)也為臨時(shí)變量指派寄存器、固定的函數(shù)單元或?？臻g。將大部分與機(jī)器無關(guān)的函數(shù)重組到一個(gè)大的與機(jī)器無關(guān)的程序中。2023/7/26例程名功能產(chǎn)生函數(shù)的頭代碼和尾代碼，調(diào)用

解釋代碼表，并將數(shù)傳遞給

處理代碼表中各個(gè)森林

修改樹，以適應(yīng)寄存器變量和特殊的目標(biāo)機(jī)器

用所有可能的實(shí)現(xiàn)標(biāo)記樹

選擇代價(jià)最小的實(shí)現(xiàn)

從樹中提出某些自指令

輸出排序指令

分配寄存器解釋代碼表，為每個(gè)森林調(diào)用

追溯指令列表

刪除寄存器到寄存器的復(fù)制

刪除寄存器復(fù)制到自身的指令

解釋匯編模版，輸出大多數(shù)指令2輸出過復(fù)雜不適于模版的指令2023/7/261、選擇和發(fā)送指令的指令選擇器時(shí)由程序根據(jù)緊縮規(guī)范自動(dòng)生成的，是代碼生成器的生成器。接收緊縮規(guī)范并產(chǎn)生一個(gè)用c語言編寫的樹分析程序，該程序?yàn)槟繕?biāo)機(jī)器選擇指令。樹分析程序接受中間代碼的主題樹，并將它分割成與目標(biāo)機(jī)器相對(duì)應(yīng)的程序塊，成為數(shù)覆蓋。2023/7/26模式：(，)表示如果的第一個(gè)子節(jié)點(diǎn)能遞歸的匹配，第二個(gè)子節(jié)點(diǎn)匹配，那么該模式就在除匹配一棵樹。規(guī)則：：（，）規(guī)定了非終結(jié)符與上述模式相匹配規(guī)則：：（，）規(guī)定了節(jié)點(diǎn)的每子節(jié)點(diǎn)遞歸的與和匹配非終結(jié)符就與該匹配。例：((((p))(4))(5))的覆蓋ASGNIADDPINDIRPCNSTI4ADDRLPpCNSTI5addr：ADDP（addr，con）reg：INDIRP（addr）addr：ADDRLPcon：CNSTIreg：concon：CNSTIstmt：ASGNI（addr，reg）2023/7/262023/7/262023/7/262、發(fā)送器發(fā)送器（）的作用是為目標(biāo)機(jī)器輸出代碼。發(fā)送器并不依賴于目標(biāo)機(jī)器，由兩個(gè)描述與機(jī)器相關(guān)的數(shù)據(jù)的數(shù)組驅(qū)動(dòng)。為每個(gè)生成一些c語言代碼，用來聲明并初始化這兩個(gè)數(shù)組。兩個(gè)數(shù)組都是通過規(guī)則號(hào)索引。規(guī)則生成模板數(shù)組：*[];標(biāo)記與指令對(duì)應(yīng)的模板，以區(qū)別子指令（如尋址指令）：*[];2023/7/26 從1開始為規(guī)則編號(hào)，并通過返回規(guī)則號(hào)來報(bào)告匹配情況，這樣當(dāng)需要的時(shí)候就可以找到響應(yīng)的模板。如果模板以一個(gè)換行符為結(jié)尾表示它是一條指令，否則就必然是某條指令的一部分，比如是一個(gè)操作數(shù)。 :"%0" :"%0" :4(1)"0\1\n"1 :4(1)"0\1\n"12023/7/26對(duì)規(guī)則結(jié)構(gòu)及匯編程序代碼模板進(jìn)行了解釋。遞歸調(diào)用自身，以處理地址計(jì)算之類的子指令。的遍歷從一個(gè)指令開始，當(dāng)遞歸到達(dá)為該指令提供值的指令時(shí)結(jié)束。由調(diào)用，確保以正確的順序來處理這些指令，這樣便可以處理指令間的順序。2023/7/26例如：發(fā)送器解釋字符串“1\n”

先生成“r”，然后是目標(biāo)寄存器的名字（通常是一個(gè)數(shù)字），接著是一個(gè)逗號(hào)。如果[1]中保存了表示非終結(jié)符的整數(shù)，那么遞歸生成>[1]作為一個(gè)。最后生成一個(gè)換行符。2023/7/263、寄存器的分配從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代碼，但是匯編代碼中的寄存器是如何分配的？寄存器分配包括兩個(gè)內(nèi)容：分配：決定哪些值占用寄存器指派：為每個(gè)值指派特定的寄存器2023/7/26例程名作用

為輸出一棵指令樹排序

為一條指令釋放和分配寄存器

釋放一個(gè)忙寄存器

發(fā)現(xiàn)和分配一個(gè)寄存器

發(fā)現(xiàn)和分配一個(gè)空寄存器

嘗試分配一個(gè)制定的寄存器

標(biāo)記一個(gè)最遠(yuǎn)使用寄存器溢出

溢出一個(gè)或多個(gè)寄存器

溢出一個(gè)寄存器

產(chǎn)生代碼溢出一個(gè)寄存器

產(chǎn)生代碼重載一個(gè)被溢出的寄存器

當(dāng)更新后，更新2023/7/26 在后端選擇指令并將子指令從樹中分離出來，采用前序遍歷分離的樹，并按照最后執(zhí)行的順序鏈接指令。再將每條指令傳遞給函數(shù)，一般首先調(diào)用來釋放不再被其子節(jié)點(diǎn)使用的寄存器，然后調(diào)用函數(shù)為自身分配一個(gè)寄存器。對(duì)于臨時(shí)變量，在首次賦值的時(shí)候?yàn)樗峙湟粋€(gè)寄存器，在最后一次使用的時(shí)候釋放該機(jī)存器。2023/7/26寄存器狀態(tài)的跟蹤 [2]; [2];用掩