編譯原理及實踐

司廣濤qrnusgt@163.com第2頁教材及主要參考資料教材：編譯原理及實踐教程，黃賢英，清華大學出版社主要參考資料：編譯原理，陳火旺，國防工業出版社編譯原理(原書第2版)(龍書)

，ALFREDV.AHOetc著，趙建華鄭滔等譯，機械工業出版社,2008.12編譯原理，張素琴，呂映芝，清華大學出版社.C語言程序voidmain(){intx,y,z;x=3;y=2;z=x+y;}內存地址內存內容單元名字………………200H3x：局部變量202H2y：局部變量204H5z：局部變量…………300H3A03302H3AE1304H3A02306H3AE2308HDA6C......3A71匯編語言程序movax,3movx,axmovbx,2movy,bxaddax,bxmovz,ax......在內存中：數據區代碼區？第4頁編程過程中的工具Editor記事本、Editplus……CompilerVC++6.0，GCC……DebuggerGDB……編譯原理概述第一章第6頁本章要求主要內容：各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結構，編譯程序的構造方法重點掌握：編譯程序工作的基本過程及其各階段的基本任務，編譯程序總框。25四月2025第7頁1.1程序設計語言與翻譯程序機器語言(machinelanguage)C70600000002匯編語言(assemblerlanguage)

MOVX,2高級語言(high-levellanguage)

X=2為什么要使用編譯程序？25四月2025第8頁計算機中的語言層次和翻譯程序25四月2025第9頁什么叫翻譯程序翻譯程序：能夠將某種語言寫的程序轉換成另一種語言的程序，而且后者與前者在邏輯上是等價的。編譯程序：將高級程序設計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。解釋程序：將高級程序設計語言寫的源程序作為輸入，邊解釋邊執行源程序本身，而不產生目標程序的翻譯程序。25四月2025第10頁高級語言語言處理程序操作系統匯編語言翻譯程序所處的層次計算機硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言............25四月2025第11頁編譯程序編譯程序源程序目標程序計算機運行輸入數據結果解釋程序解釋程序源程序輸入數據結果25四月2025第12頁對編譯程序的一些說明編譯程序實質上是翻譯程序，要注意等價變換本課程的任務就是講解在這個轉換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器轉換是一個總體的功能，要抓住總體結構，逐層細分，寫編譯器時要體現軟件工程中軟件設計的原則，自頂向下，逐層分解。編譯器要完成的轉換任務相當復雜，實現編譯器時必須分步驟分階段實現。25四月2025第13頁編譯器的伙伴編輯器(editor)預處理器(Preprocessor)將源程序匯集到一起，宏展開等匯編程序(assembler)連接程序(linker)連接系統函數與系統資源裝入程序(loader)重定位(relocation)調試器（debugger）優化器（optimizer）25四月2025第14頁編譯原理主要討論編譯程序設計的基本理論、基本概念、基本方法。什么是編譯原理25四月2025第15頁1.2編譯過程概述邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優化、目標代碼生成

每個階段把源程序從一種表示變換成另一種表示詞法分析語法分析語義分析與中間代碼生成代碼優化目標代碼生成25四月2025第16頁按照詞法分析、語法分析、語義分析等這種方式來劃分階段的原因是：每個階段的復雜程度不同，所依據的理論基礎不同，實現時采用的方法也不同。主要是方便理解和實現。劃分階段的依據是什么？每個階段所實現的功能相對獨立。用一個例子說明各階段的功能25四月2025第17頁/*一個PASCAL語言的源程序*/programtest;/*thisisanexample,computinganarea*/vararea,length,width:integer;beginlength:=5;width:=5;area:=5＋length*width＋length*widthend.

25四月2025第18頁第一階段：詞法分析任務:從左到右掃描源程序，識別出每個單詞（Token）附加任務：a、濾掉空格b、去掉注釋單詞符號是語言的基本組成成分詞法分析的工作主要依據語言中單詞的構成規則單詞的種類：（1）標識符（2）關鍵字（char、int、if、else、while、for等）（3）運算符（即運算符號+、－、*、/、&等）（4）界符（常見的有；，：（）等）（5）常數25四月2025第19頁beginarea:=5＋length*width

＋length*widthend;單詞類型內部形式begin關鍵字$beginarea標識符id1:=界符:=5常數int1+算符+length標識符id1*算符*width標識符id2+算符+length標識符id2*算符*width標識符id3end關鍵字$end;界符;例:25四月2025第20頁第二階段：語法分析任務:在詞法分析的基礎上，根據語言的語法規則，將單詞符號串分解成各類語法短語(例：程序、語句、表達式)。確定整個輸入串是否構成語法上正確的程序。根據規則判定：賦值語句：標識符:＝表達式

表達式：標識符、常數是表達式

表達式的運算也是表達式例：識別符號串id1:=int1+id2*id3+id2*id3是一個賦值語句（area:=5＋length*width＋length*width）而int1+id2*id3+id2*id3是一個表達式（5＋length*width＋length*width）25四月2025第21頁語法分析所依據的是語言的語法規則id1:=int1+id2*id3+id2*id325四月2025第22頁第三階段：語義分析和中間代碼生成任務：對語法分析所識別出的各類語法短語分析其含義，進行初步的翻譯(翻譯成中間代碼)。靜態語義審查變量定義類型匹配類型轉換例：C:=A*B(檢查C與Ａ、Ｂ類型)中間代碼的翻譯

中間代碼有多種形式，如：

四元式:(運算符，運算對象1，運算對象2，結果)25四月2025第23頁例：對賦值語句：id1:=int1+id2*id3+id2*id3

1.檢查area、length、width是否定義、類型

2.生成中間代碼(運算符，運算對象1，運算對象2，結果)

(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id325四月2025第24頁第四階段：代碼優化任務：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高效(時間和空間)。優化方法包括：公共子表達式的提取、循環優化、刪除無用代碼等。代碼的優化依據的是程序的等價變換規則。序號四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(*,id2,id3,T3)4(+,T2,T3,T4)5(:=,T4,_,id1)序號

四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)25四月2025第25頁第五階段：目標代碼的生成任務：把中間代碼(或經優化的中間代碼)變換成特定機器上的低級語言代碼。依賴于機器的硬件系統結構和機器指令的含義目標代碼可以是：絕對指令代碼、可重定位的指令代碼、匯編指令代碼序號

四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)（1）movAX,id2（2）mulAX,id3（3）movBX,AX（4）addAX,int1（5）addAX,BX（6）movid1,AX25四月2025第26頁1.2編譯程序的結構

由左圖可以看出，詞法分析是實現編譯器的基礎，語法分析是實現編譯器的關鍵。因此按照這個順序來實現編譯器每一步的實現都依賴于一定的理論基礎。25四月2025第27頁編譯階段的組合幾個概念遍：對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，生成新的中間結果或目標程序。編譯前端：主要指與源語言有關，與目標語言無關的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機器無關部分的代碼優化編譯后端：指與目標機器有關的部分。如與機器有關的優化、目標代碼生成25四月2025第28頁編譯階段的組合25四月2025第29頁為什么生成中間代碼第30頁編譯程序中的主要數據結構(續)Token表符號表常數表錯誤信息語法樹中間代碼表臨時文件目標代碼表第31頁(1)Token表

當掃描程序將字符收集到一個記號中時，通常以符號表示這個記號；(2)語法樹（syntaxtree）

如果分析程序確實生成了語法樹，它的構造通常為基于指針的標準結構，在進行分析時動態分配該結構，則整棵樹可作為一個指向根節點的單個變量保存。結構中的每一個節點都是一個記錄，它的域保存由分析程序和之后的語義分析程序收集的信息。編譯程序中的主要數據結構介紹:第32頁(3)符號表（symboltable）這個數據結構中的信息與標識符有關：函數、變量、常量以及數據類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或將標識符輸入到表格中的語義分析程序；語義分析程序將增加數據類型和其他信息；優化階段和代碼生成階段也將利用由符號表提供的信息選出恰當的代碼。因為對符號表的訪問如此頻繁，所以插入、刪除和訪問操作都必須比常規操作更有效。盡管可以使用各種樹的結構，但雜湊表卻是達到這一要求的標準數據結構。有時在一個列表或棧中可使用若干個表格。第33頁(4)常數表（literaltable）

常數表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數表中也十分重要。但是，在其中卻無需刪除，這是因為它的數據全程應用于程序而且常量或字符串在該表中只出現一次。(5)中間代碼（intermediatecode）根據中間代碼的類型（例如三元式代碼）和優化的類型，該代碼可以是文本串的數組、臨時文本文件或是結構的連接列表。對于進行復雜優化的編譯器，應特別注意選擇允許簡單重組的表示。第34頁(6)目標代碼（intermediatecode）存放最終生成的目標代碼，該代碼最終是文本形式的文件。(7)臨時文件（temporaryfile）計算機過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經通過使用臨時文件來保存翻譯時中間步驟的結果解決了。25四月2025第35頁1.3編譯程序的設計構造編譯程序要掌握以下幾方面的內容：源語言：理解其結構和含義目標語言：必須清楚硬件的系統結構和指令的格式等編譯方法25四月2025第36頁1.3編譯程序的構造一般實現編譯程序的方法有：1.直接用機器語言編寫編譯程序2.用匯編語言編寫編譯程序注：編譯程序核心部分常用匯編語言編寫3.用高級語言編寫編譯程序注：這是普遍采用的方法4.自編譯5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產生LALR分析表)6.移植（同種語言的編譯程序在不同類型的機器之間移植）25四月2025第37頁本書構成及編譯程序框架25四月2025第38頁1.4編譯技術的發展1954年至1957年間，FORTRAN語言及其編譯器的開發。幾乎與此同時，NoamChomsky開始研究語言文法(grammar，結構規則)的難易程度以及識別它們所需的算法來為語言分類。在60年代和70年代進行的分析問題(parsingproblem，用于限定上下文無關語言的識別的有效算法)的研究。有窮自動機(finiteautomata)和正規式(regularexpression)的研究與喬姆斯基的研究幾乎同時開始，引出了表示程序設計語言的單詞的符號方式。接著又深化了生成有效的目標代碼的方法，這就是最初的編譯器，實際上應稱作代碼改進技術(codeimprovementtechnique)。當分析問題變得好懂起來時，人們就在開發程序上花費了很大的功夫來研究這一部分的編譯器的自動構造。Lex與Yacc。在70年代后期和80年代早期