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

編譯原理實(shí)踐及應(yīng)用----中南大學(xué)肖健宇03五月2024第2頁(yè)教材及主要參考資料教材：編譯原理實(shí)踐及應(yīng)用，黃賢英，清華大學(xué)出版社主要參考資料：(1)編譯原理，陳火旺，國(guó)防工業(yè)出版社(2)程序設(shè)計(jì)語(yǔ)言編譯方法，肖軍模，大連理工大學(xué)出版社(3)編譯原理，張素琴，呂映芝，清華大學(xué)出版社(4)編譯原理，alfredV.Aho等著，李建中等譯，人民郵電出版社03五月2024第3頁(yè)序言03五月2024第4頁(yè)C語(yǔ)言程序voidmain(){intx,y,z;x=3;y=2;z=x+y;}什么是編譯？從程序員可以理解的高級(jí)語(yǔ)言程序到機(jī)器可以理解的機(jī)器語(yǔ)言程序的自動(dòng)翻譯過(guò)程。03五月2024第5頁(yè)匯編語(yǔ)言程序……movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax......300302304306308……內(nèi)存地址內(nèi)存內(nèi)容單元名字………………200H3x：局部變量201H2y：局部變量202H5z：局部變量…………機(jī)器碼03五月2024第6頁(yè)為什么要學(xué)習(xí)編譯原理？1、有助于深刻理解和正確使用程序設(shè)計(jì)語(yǔ)言，加深對(duì)高級(jí)語(yǔ)言程序執(zhí)行過(guò)程的理解2、有助于加深對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的理解。3、設(shè)計(jì)開(kāi)發(fā)編譯程序的軟件技術(shù)同樣可以用于其他軟件的設(shè)計(jì)開(kāi)發(fā)。4、隨著微處理器技術(shù)的飛速開(kāi)展，處理器性能在很大程度上取決于編譯器的質(zhì)量、編譯技術(shù)成為計(jì)算機(jī)的核心技術(shù)，地位變得越來(lái)越重要。03五月2024第7頁(yè)《編譯原理》課程在計(jì)算機(jī)科學(xué)中的重要地位(1)學(xué)習(xí)編程最初是學(xué)習(xí)一門(mén)高級(jí)語(yǔ)言，C或Pascal，掌握編寫(xiě)一些簡(jiǎn)單程序的方法；(2)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，建立“算法”的概念，對(duì)編程有更深入的理解。遇到問(wèn)題的時(shí)候，能夠?qū)ふ蚁鄳?yīng)的數(shù)據(jù)結(jié)構(gòu)模型，設(shè)計(jì)適當(dāng)?shù)乃惴▉?lái)解決問(wèn)題；(3)學(xué)習(xí)匯編語(yǔ)言，這門(mén)課程是我們真正深入了解計(jì)算機(jī)內(nèi)部工作的第一門(mén)課程。通過(guò)學(xué)習(xí)了解匯編語(yǔ)言如何變?yōu)闄C(jī)器語(yǔ)言，如何對(duì)應(yīng)于一條指令；(4)計(jì)算機(jī)組成原理課程的學(xué)習(xí)使我們了解到計(jì)算機(jī)的硬件組成，以及機(jī)器指令程序如何在計(jì)算機(jī)中運(yùn)行的過(guò)程。(5)編譯原理課程幫助我們了解高級(jí)語(yǔ)言程序轉(zhuǎn)換成機(jī)器指令程序的過(guò)程?？梢詭椭覀兏羁痰乩斫飧呒?jí)語(yǔ)言程序運(yùn)行的內(nèi)部機(jī)制。03五月2024第8頁(yè)《編譯原理》課程在計(jì)算機(jī)科學(xué)中的地位高級(jí)語(yǔ)言程序設(shè)計(jì)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯原理操作系統(tǒng)系統(tǒng)軟件應(yīng)用軟件軟件工程信息系統(tǒng)電子商務(wù)匯編語(yǔ)言計(jì)算機(jī)組成原理03五月2024第9頁(yè)學(xué)習(xí)本課程的目的和任務(wù)加深對(duì)編程語(yǔ)言設(shè)計(jì)和實(shí)現(xiàn)的理解，對(duì)和編程語(yǔ)言有關(guān)的理論有所了解，對(duì)宏觀(guān)上把握編程語(yǔ)言來(lái)說(shuō)，起一個(gè)奠基的作用，提升自身的編程能力掌握編譯程序的根本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法，將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計(jì)中培養(yǎng)團(tuán)隊(duì)協(xié)作能力03五月2024第10頁(yè)本課程的特點(diǎn)(1)本課程理論性很強(qiáng)，學(xué)習(xí)時(shí)需要很強(qiáng)的邏輯思維能力(2)涉及的算法復(fù)雜，要深入地理解這些算法很困難(3)編譯原理課程各個(gè)局部之間的獨(dú)立性很強(qiáng)，包括詞法分析、語(yǔ)法分析、存儲(chǔ)的組織與分配、中間語(yǔ)言、語(yǔ)法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大局部。詞法分析、及語(yǔ)義分析是重點(diǎn)；其他局部相對(duì)來(lái)說(shuō)知識(shí)性更強(qiáng)一些。引論第一章03五月2024第12頁(yè)本章要求主要內(nèi)容：各種翻譯程序的概念，編譯過(guò)程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法重點(diǎn)掌握：編譯程序工作的根本過(guò)程及其各階段的根本任務(wù)，編譯程序總框。03五月2024第13頁(yè)問(wèn)題：1.什么是編譯程序？2.編譯程序的工作過(guò)程是什么樣的？3.編譯程序的總體結(jié)構(gòu)是什么樣的？4.什么叫編譯前端、編譯后端？5.什么叫“遍”〔pass〕？6.編譯程序有哪些生成方法？03五月2024第14頁(yè)編譯程序〔Compiler〕——將高級(jí)程序設(shè)計(jì)語(yǔ)言程序翻譯成邏輯上等價(jià)的低級(jí)語(yǔ)言(匯編語(yǔ)言,機(jī)器語(yǔ)言)程序的翻譯程序。功能編譯程序源程序目標(biāo)程序計(jì)算機(jī)運(yùn)行輸入數(shù)據(jù)結(jié)果1.1編譯程序是什么03五月2024第15頁(yè)計(jì)算機(jī)中的語(yǔ)言層次和轉(zhuǎn)換關(guān)系03五月2024第16頁(yè)解釋程序解釋程序〔Interpreter〕——將高級(jí)程序設(shè)計(jì)語(yǔ)言寫(xiě)的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程序的翻譯程序。功能解釋程序源程序輸入數(shù)據(jù)結(jié)果03五月2024第17頁(yè)編譯程序的分類(lèi)診斷編譯程序優(yōu)化編譯程序可變目標(biāo)編譯程序交叉編譯程序03五月2024第18頁(yè)與編譯程序相關(guān)的程序解釋程序(Interpreter)匯編程序(assembler)連接程序(linker)連接系統(tǒng)函數(shù)與系統(tǒng)資源裝入程序(loader)重定位(relocation)預(yù)處理器(Preprocessor)編輯器(editor)Debugger,Profiler,ProjectManager03五月2024第19頁(yè)編譯原理是討論編譯程序設(shè)計(jì)的根本理論、根本概念、根本方法什么是編譯原理03五月2024第20頁(yè)1.2編譯過(guò)程概述邏輯上分五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。每個(gè)階段把源程序從一種表示變換成另一種表示。詞法分析語(yǔ)法分析語(yǔ)義分析與中間代碼生成代碼優(yōu)化目標(biāo)代碼生成編譯過(guò)程和英文翻譯過(guò)程比照把英文翻譯為中文

識(shí)別出句子中的一個(gè)個(gè)單詞；分析句子的語(yǔ)法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對(duì)譯文進(jìn)行修飾；寫(xiě)出最后的譯文。詞法分析語(yǔ)法分析中間代碼產(chǎn)生優(yōu)化目標(biāo)代碼產(chǎn)生03五月2024第22頁(yè)第一階段：詞法分析任務(wù):從左到右掃描源程序，識(shí)別出每個(gè)單詞附加任務(wù)：a、濾掉空格b、識(shí)別單詞單詞符號(hào)是語(yǔ)言的根本組成成分詞法分析的工作主要依據(jù)語(yǔ)言的詞法規(guī)那么，描述詞法規(guī)那么的有效工具是正規(guī)式和有限自動(dòng)機(jī)。03五月2024第23頁(yè)beginresult:=5＋B*C＋B*Cend;單詞類(lèi)型內(nèi)部形式begin關(guān)鍵字$beginresult標(biāo)識(shí)符id1:=界符:=5常數(shù)int1+算符+B標(biāo)識(shí)符id1*算符*C標(biāo)識(shí)符id2+算符+B標(biāo)識(shí)符id2*算符*C標(biāo)識(shí)符id3end關(guān)鍵字$end;界符;例:03五月2024第24頁(yè)第二階段：語(yǔ)法分析任務(wù):在詞法分析的根底上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)那么，將單詞符號(hào)串分解成各類(lèi)語(yǔ)法短語(yǔ)(例：程序、語(yǔ)句、表達(dá)式)。確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的程序。語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)那么，表示語(yǔ)法規(guī)那么的工具是上下文無(wú)關(guān)文法，用下推自動(dòng)機(jī)實(shí)現(xiàn)。03五月2024第25頁(yè)id1:=int1+id2*id3+id2*id3例：識(shí)別符號(hào)串id1:=int1+id2*id3+id2*id3〔即result:=5＋B*C＋B*C〕是一個(gè)賦值語(yǔ)句。03五月2024第26頁(yè)第三階段：語(yǔ)義分析和中間代碼生成任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類(lèi)語(yǔ)法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)。靜態(tài)語(yǔ)義審查變量定義類(lèi)型匹配類(lèi)型轉(zhuǎn)換例：C:=A*B(檢查C與Ａ、Ｂ類(lèi)型)中間代碼的翻譯

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

四元式:(運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果)03五月2024第27頁(yè)例：對(duì)賦值語(yǔ)句：id1:=int1+id2*id3+id2*id3

1.檢查result、Ｂ、C是否認(rèn)義類(lèi)型2.生成中間代碼(運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果)

(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id303五月2024第28頁(yè)第四階段：代碼優(yōu)化任務(wù)：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為高效(時(shí)間和空間)。優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。代碼的優(yōu)化依據(jù)的是程序的等價(jià)變換規(guī)那么。03五月2024第29頁(yè)序號(hào)四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(*,id2,id3,T3)4(+,T2,T3,T4)5(:=,T4,_,id1)序號(hào)

四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)例：03五月2024第五階段：目標(biāo)代碼的生成任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。依賴(lài)于機(jī)器的硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼可以是：絕對(duì)指令代碼、可重定位的指令代碼、匯編指令代碼03五月2024第31頁(yè)第31頁(yè)序號(hào)

四元式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例：03五月2024第32頁(yè)1.3編譯程序的結(jié)構(gòu)

03五月2024第33頁(yè)03五月2024第34頁(yè)幾個(gè)概念符號(hào)表：登記源程序中出現(xiàn)的名字以及名字的各種屬性。遍：對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。編譯前端：主要指與源語(yǔ)言有關(guān)，與目標(biāo)語(yǔ)言無(wú)關(guān)的局部，通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成，與機(jī)器無(wú)關(guān)局部的代碼優(yōu)化。編譯后端：指與目標(biāo)機(jī)器有關(guān)的局部。如與機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成。03五月2024第35頁(yè)編譯階段的組合03五月2024第36頁(yè)為什么要生成中間代碼03五月2024第37頁(yè)(1)記號(hào)(token)

當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)；這也就是說(shuō)，作為一個(gè)枚舉數(shù)據(jù)類(lèi)型的值來(lái)表示源程序的記號(hào)集。編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):03五月2024第38頁(yè)(2)語(yǔ)法樹(shù)〔syntaxtree〕如果分析程序確實(shí)生成了語(yǔ)法樹(shù)，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動(dòng)態(tài)分配該結(jié)構(gòu)，那么整棵樹(shù)可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的語(yǔ)義分析程序收集的信息。03五月2024第39頁(yè)(3)符號(hào)表〔symboltable〕這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識(shí)符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類(lèi)型。符號(hào)表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)義分析程序?qū)⒃黾訑?shù)據(jù)類(lèi)型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號(hào)表提供的信息選出恰當(dāng)?shù)拇a。因?yàn)閷?duì)符號(hào)表的訪(fǎng)問(wèn)如此頻繁，所以插入、刪除和訪(fǎng)問(wèn)操作都必須比常規(guī)操作更有效。盡管可以使用各種樹(shù)的結(jié)構(gòu)，但雜湊表卻是到達(dá)這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時(shí)在一個(gè)列表或棧中可使用假設(shè)干個(gè)表格。03五月2024第40頁(yè)(4)常數(shù)表〔literaltable〕常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無(wú)需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。03五月2024第41頁(yè)(5)中間代碼〔intermediatecode〕根據(jù)中間代碼的類(lèi)型