編譯原理課程教案第1章編譯原理概述

編譯原理課程教案第1章編譯原理概述編譯原理課程教案第1章編譯原理概述編譯原理課程教案第1章編譯原理概述教材及主要參考資料教材：編譯原理實踐及應用，黃賢英，清華大學出版社主要參考資料：(1)編譯原理，陳火旺，國防工業(yè)出版社(2)程序設計語言編譯方法，肖軍模，大連理工大學出版社(3)編譯原理，張素琴，呂映芝，清華大學出版社(4)編譯原理，alfredV.Aho等著，李建中等譯，人民郵電出版社2021/3/162教材及主要參考資料教材：編譯原理實踐及應用，黃賢英，清華大學出版社主要參考資料：(1)編譯原理，陳火旺，國防工業(yè)出版社(2)程序設計語言編譯方法，肖軍模，大連理工大學出版社(3)編譯原理，張素琴，呂映芝，清華大學出版社(4)編譯原理，alfredV.Aho等著，李建中等譯，人民郵電出版社2023/6/52序言2023/6/53C語言程序voidmain(){intx,y,z;x=3;y=2;z=x+y;}什么是編譯？從程序員可以理解的高級語言程序到機器可以理解的機器語言程序的自動翻譯過程。2023/6/54匯編語言程序……movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax......300302304306308……內存地址內存內容單元名字………………200H3x：局部變量201H2y：局部變量202H5z：局部變量…………機器碼2023/6/55為什么要學習編譯原理？1、有助于深刻理解和正確使用程序設計語言，加深對高級語言程序執(zhí)行過程的理解2、有助于加深對整個計算機系統(tǒng)的理解。3、設計開發(fā)編譯程序的軟件技術同樣可以用于其他軟件的設計開發(fā)。4、隨著微處理器技術的飛速發(fā)展，處理器性能在很大程度上取決于編譯器的質量、編譯技術成為計算機的核心技術，地位變得越來越重要。2023/6/56《編譯原理》課程在計算機科學中的重要地位(1)學習編程最初是學習一門高級語言，C或Pascal，掌握編寫一些簡單程序的方法；(2)學習數(shù)據(jù)結構，建立“算法”的概念，對編程有更深入的理解。遇到問題的時候，能夠尋找相應的數(shù)據(jù)結構模型，設計適當?shù)乃惴▉斫鉀Q問題；(3)學習匯編語言，這門課程是我們真正深入了解計算機內部工作的第一門課程。通過學習了解匯編語言如何變?yōu)闄C器語言，如何對應于一條指令；(4)計算機組成原理課程的學習使我們了解到計算機的硬件組成，以及機器指令程序如何在計算機中運行的過程。(5)編譯原理課程幫助我們了解高級語言程序轉換成機器指令程序的過程。可以幫助我們更深刻地理解高級語言程序運行的內部機制。2023/6/57《編譯原理》課程在計算機科學中的地位高級語言程序設計離散數(shù)學數(shù)據(jù)結構編譯原理操作系統(tǒng)系統(tǒng)軟件應用軟件軟件工程信息系統(tǒng)電子商務匯編語言計算機組成原理2023/6/58學習本課程的目的和任務加深對編程語言設計和實現(xiàn)的理解，對和編程語言有關的理論有所了解，對宏觀上把握編程語言來說，起一個奠基的作用，提升自身的編程能力掌握編譯程序的基本結構，掌握常用的編譯技術和方法，將編譯原理的理論和方法應用于一般的軟件設計中培養(yǎng)團隊協(xié)作能力2023/6/59本課程的特點(1)本課程理論性很強，學習時需要很強的邏輯思維能力(2)涉及的算法復雜，要深入地理解這些算法很困難(3)編譯原理課程各個部分之間的獨立性很強，包括詞法分析、語法分析、存儲的組織與分配、中間語言、語法制導翻譯、代碼生成與優(yōu)化這幾大部分。詞法分析、及語義分析是重點；其他部分相對來說知識性更強一些。2023/6/510引論第一章本章要求主要內容：各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結構，編譯程序的構造方法重點掌握：編譯程序工作的基本過程及其各階段的基本任務，編譯程序總框。2023/6/512問題：1.什么是編譯程序？2.編譯程序的工作過程是什么樣的？3.編譯程序的總體結構是什么樣的？4.什么叫編譯前端、編譯后端？5.什么叫“遍”（pass）？6.編譯程序有哪些生成方法？2023/6/513編譯程序（Compiler）——將高級程序設計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。功能編譯程序源程序目標程序計算機運行輸入數(shù)據(jù)結果1.1編譯程序是什么2023/6/514計算機中的語言層次和轉換關系2023/6/515解釋程序解釋程序（Interpreter）——將高級程序設計語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產生目標程序的翻譯程序。功能解釋程序源程序輸入數(shù)據(jù)結果2023/6/516編譯程序的分類診斷編譯程序優(yōu)化編譯程序可變目標編譯程序交叉編譯程序2023/6/517與編譯程序相關的程序解釋程序(Interpreter)匯編程序(assembler)連接程序(linker)連接系統(tǒng)函數(shù)與系統(tǒng)資源裝入程序(loader)重定位(relocation)預處理器(Preprocessor)編輯器(editor)Debugger,Profiler,ProjectManager2023/6/518編譯原理是討論編譯程序設計的基本理論、基本概念、基本方法什么是編譯原理2023/6/5191.2編譯過程概述邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標代碼生成。每個階段把源程序從一種表示變換成另一種表示。詞法分析語法分析語義分析與中間代碼生成代碼優(yōu)化目標代碼生成2023/6/520編譯過程和英文翻譯過程對比把英文翻譯為中文識別出句子中的一個個單詞；分析句子的語法結構；根據(jù)句子的含義進行初步翻譯；對譯文進行修飾；寫出最后的譯文。詞法分析語法分析中間代碼產生優(yōu)化目標代碼產生第一階段：詞法分析任務:從左到右掃描源程序，識別出每個單詞附加任務：a、濾掉空格b、識別單詞單詞符號是語言的基本組成成分詞法分析的工作主要依據(jù)語言的詞法規(guī)則，描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機。2023/6/522beginresult:=5＋B*C＋B*Cend;單詞類型內部形式begin關鍵字$beginresult標識符id1:=界符:=5常數(shù)int1+算符+B標識符id1*算符*C標識符id2+算符+B標識符id2*算符*C標識符id3end關鍵字$end;界符;例:2023/6/523第二階段：語法分析任務:在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語(例：程序、語句、表達式)。確定整個輸入串是否構成語法上正確的程序。語法分析所依據(jù)的是語言的語法規(guī)則，表示語法規(guī)則的工具是上下文無關文法，用下推自動機實現(xiàn)。2023/6/524id1:=int1+id2*id3+id2*id3例：識別符號串id1:=int1+id2*id3+id2*id3（即result:=5＋B*C＋B*C）是一個賦值語句。2023/6/525第三階段：語義分析和中間代碼生成任務：對語法分析所識別出的各類語法范疇分析其含義，進行初步的翻譯(翻譯成中間代碼)。靜態(tài)語義審查變量定義類型匹配類型轉換例：C:=A*B(檢查C與Ａ、Ｂ類型)中間代碼的翻譯

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

四元式:(運算符，運算對象1，運算對象2，結果)2023/6/526例：對賦值語句：id1:=int1+id2*id3+id2*id3

1.檢查result、Ｂ、C是否定義類型

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

(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id32023/6/527第四階段：代碼優(yōu)化任務：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高效(時間和空間)。優(yōu)化方法包括：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等。代碼的優(yōu)化依據(jù)的是程序的等價變換規(guī)則。2023/6/528序號四元式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)例：2023/6/529第五階段：目標代碼的生成任務：把中間代碼(或經優(yōu)化的中間代碼)變換成特定機器上的低級語言代碼。依賴于機器的硬件系統(tǒng)結構和機器指令的含義目標代碼可以是：絕對指令代碼、可重定位的指令代碼、匯編指令代碼2023/6/5第31頁序號

四元式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,AX例：2023/6/5311.3編譯程序的結構

2023/6/5322023/6/533幾個概念符號表：登記源程序中出現(xiàn)的名字以及名字的各種屬性。遍：對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，生成新的中間結果或目標程序。編譯前端：主要指與源語言有關，與目標語言無關的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機器無關部分的代碼優(yōu)化。編譯后端：指與目標機器有關的部分。如與機器有關的優(yōu)化、目標代碼生成。2023/6/534編譯階段的組合2023/6/535為什么要生成中間代碼2023/6/536(1)記號(token)

當掃描程序將字符收集到一個記號中時，它通常是以符號表示這個記號；這也就是說，作為一個枚舉數(shù)據(jù)類型的值來表示源程序的記號集。編譯程序中的主要數(shù)據(jù)結構:2023/6/537(2)語法樹（syntaxtree）如果分析程序確實生成了語法樹，它的構造通常為基于指針的標準結構，在進行分析時動態(tài)分配該結構，則整棵樹可作為一個指向根節(jié)點的單個變量保存。結構中的每一個節(jié)點都是一個記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。2023/6/538(3)符號表（symboltable）這個數(shù)據(jù)結構中的信息與標識符有關：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或將標識符輸入到表格中的語義分析程序；語義分析程序將增加數(shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當?shù)拇a。因為對符號表的訪問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結構，但雜湊表卻是達到這一要求的標準數(shù)據(jù)結構。有時在一個列表或棧中可使用若干個表格。2023/6/539(4)常數(shù)表（literaltable）常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因為它的數(shù)據(jù)全程應用于程序而且常量或字符串在該表中只出現(xiàn)一次。2023/6/540(5)中間代碼（intermediatecode）根據(jù)中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串