1、編譯原理和技術(shù),大連理工大學(xué)軟件學(xué)院 賈棋 87571603,編譯原理課程在計(jì)算機(jī)科學(xué)技術(shù)中的地位：,課 程 簡 介,編譯理論與方法 計(jì)算機(jī)科學(xué)與技術(shù)中理論和實(shí)踐相結(jié)合的最好典范 ACM 圖靈獎(jiǎng)，授予在計(jì)算機(jī)技術(shù)領(lǐng)域作出突出貢獻(xiàn)的科學(xué)家 程序設(shè)計(jì)語言、編譯理論與方法約占1/3,課 程 簡 介,教材和參考書 陳意云、張昱，編譯原理，高等教育出版社， 2008年第二版 Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, .編譯原理 技術(shù)與工具（英文版） 人民郵電出版社. 中文版：機(jī)械工業(yè)出版社,課 程 簡 介,成績評定 學(xué)期總評 = 考試成績占70%，作業(yè)占15

2、%，上機(jī)實(shí)驗(yàn)15%,課 程 簡 介,課程要求 目標(biāo)：師生共同努力，幫助大家學(xué)有所得 講課進(jìn)度較快，平時(shí)不復(fù)習(xí)并加深理解，后面將聽不懂 作業(yè)較多，要求獨(dú)立完成 上機(jī)實(shí)驗(yàn)，不要輕視 閱讀PL/0編譯器，會(huì)有很大收獲,課 程 簡 介,課程內(nèi)容 介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法 介紹的理論知識(shí)：形式語言和自動(dòng)機(jī)理論、語法制導(dǎo)的定義和屬性文法、類型論等 課程特點(diǎn) 強(qiáng)調(diào)形式化描述技術(shù) 強(qiáng)調(diào)對編譯原理和技術(shù)的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于某種源語言或目標(biāo)機(jī)器,課 程 簡 介,學(xué)習(xí)的意義 它是計(jì)算機(jī)專業(yè)的核心課程。對編程語言的設(shè)計(jì)和實(shí)現(xiàn)有深刻的理解，有利于學(xué)習(xí)編程語言，知其然知其所以然。,

3、if (c = 5) then if (c = 5) then,if (5 = c) then if (5 = c) then,編譯器不報(bào)錯(cuò)，但實(shí)際上錯(cuò)了,編譯器報(bào)錯(cuò),課 程 簡 介,學(xué)習(xí)的意義 從軟件工程看，編譯器是一個(gè)很好的實(shí)例（基本設(shè)計(jì)、模塊劃分等）， 所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。編譯器也許是大家在本科階段分析最透徹的實(shí)例了。從本課程的學(xué)習(xí)也能了解到軟件工程中的一些技術(shù)（如基于事件驅(qū)動(dòng)的編程）。本課程所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。 大多數(shù)程序員同時(shí)是語言的設(shè)計(jì)者，雖然是一些簡單的語言（如輸入輸出），本課程的學(xué)習(xí)有助于提高對這些語言的設(shè)計(jì)水平。,課 程 簡

4、 介,學(xué)習(xí)的意義 可以肯定地說，你們中的95%以上的人在一輩子的生涯中都沒有機(jī)會(huì)去實(shí)現(xiàn)一個(gè)真正的復(fù)雜語言的編譯器。但是每一個(gè)人都絕對遇到需要使用編譯技術(shù)的項(xiàng)目。 以下就是一些小的“編譯器”.,課 程 簡 介,學(xué)習(xí)的意義,普通計(jì)算器,可編程計(jì)算器,課 程 簡 介,學(xué)習(xí)的意義,自動(dòng)聊天機(jī)器人,課 程 簡 介,學(xué)習(xí)的意義,各種數(shù)據(jù)庫查詢語言及專家系統(tǒng),select 課程 from table 課程表 where 任課老師=賈棋,課 程 簡 介,學(xué)習(xí)的意義 在計(jì)算機(jī)專業(yè)考研或者各大公司招聘時(shí)，必考內(nèi)容。,在x86/Linux工作站上，以下兩個(gè)結(jié)構(gòu)的size分別是20和16，為什么不一樣？ typede

5、f struct _atypedef struct _b char c1; char c1; long i; charc2; charc2; long i; double f; double f; a; b;,vc結(jié)果vs Linux下gcc的結(jié)果,vc6中的編譯選項(xiàng)有 /Zp1|2|4|8|16 ，/Zp1表示以1字節(jié)邊界對齊，相應(yīng)的，/Zpn表示以n字節(jié)邊界對齊。n字節(jié)邊界對齊的意思是說，一個(gè)成員的地址必須安排在成員的尺寸的整數(shù)倍地址上或者是n的整數(shù)倍地址上，取它們中的最小值。 要使用這個(gè)選項(xiàng)，可以在vc6中打開工程屬性頁，c/c+頁，選擇Code Generation分類，在Struct

6、 member alignment可以選擇。,課 程 簡 介,編譯技術(shù)研究對象：編譯器的構(gòu)造與分析,BASIC年代的解釋器 功能：它將高級語言的源程序翻譯成一種中間語言程序，然后對中間語言程序進(jìn)行解釋執(zhí)行 在那個(gè)年代，編譯和解釋兩個(gè)功能是合在一個(gè)程序中，該程序被稱為解釋器 Java年代的解釋器 解釋器的上述兩個(gè)功能分在兩個(gè)程序中 前一個(gè)叫做編譯器，它把源程序翻譯成一種叫做字節(jié)碼的中間語言程序 后一個(gè)叫做解釋器，它對字節(jié)碼程序進(jìn)行解釋執(zhí)行,編譯器和解釋器的區(qū)別,三種奶牛三種嗜好,編譯器和解釋器的區(qū)別,改進(jìn)后的方案,編譯器和解釋器的區(qū)別,牧草 我們的各種編程語言，C/C+/C#, Java, Pa

7、scal, PHP, Perl, Java Script等切割機(jī) 各種編譯器奶牛 各種CPU，比如x86，ARM，MIPS等奶牛會(huì)有吃不同形狀牧草的嗜好，這個(gè)奇怪的比喻是為了表示不同的CPU接受的不同的機(jī)器語言。,編譯器和解釋器的區(qū)別,編譯器和解釋器的區(qū)別,編譯器與解釋器的區(qū)別,編譯器是把源程序的每一條語句都編譯成機(jī)器語言,并保存成二進(jìn)制文件,這樣運(yùn)行時(shí)計(jì)算機(jī)可以直接以機(jī)器語言來運(yùn)行此程序,速度很快; 而解釋器則是只在執(zhí)行程序時(shí),才一條一條的解釋成機(jī)器語言給計(jì)算機(jī)來執(zhí)行,所以運(yùn)行速度是不如編譯后的程序運(yùn)行的快的.,第一章 引 論,翻譯器：把一種語言變換到另外一種語言的軟件。這兩種語言分別稱為源

8、語言和目標(biāo)語言。 編譯器：一種翻譯器，它的目標(biāo)語言比源語言低級。,第一章 引 論,編譯器,編譯器從邏輯上可以分成若干階段，每個(gè)階段把源程序從一種表示變換成另一種表示,翻譯家,第一章 引 論,FORTRAN (FORmula TRANslation) 第一個(gè)實(shí)用的高級語言 擅長于數(shù)學(xué)函數(shù)運(yùn)算 常用于科學(xué)計(jì)算中 第一個(gè)編譯器 歷史上第一個(gè)實(shí)用的編譯器(John Backus)： Fortran compiler for the IBM 704/709/7090/7094 John Backus，引入了編譯器的“階段”或稱為“遍”的概念，是編譯設(shè)計(jì)的模塊化的開始,編譯器從邏輯上可以分成若干階段 每個(gè)

9、階段把源程序從一種表示變換成另一種表示 本章通過描述編譯器的各個(gè)階段來介紹編譯這個(gè)課題,第一章 引 論,詞法分析：源程序 -詞法記號(hào)（token）流,第一章 引 論,任何一個(gè)標(biāo)識(shí)符都是表達(dá)式； 任何一個(gè)數(shù)都是表達(dá)式； 如果e1和e2都是表達(dá)式，那么 e1 + e2 e1 * e2 (e1) 也都是表達(dá)式,語法分析：詞法記號(hào)（token）流-語法短語,任何名詞都可以作賓語； 如果e1和e2都是賓語，那么 e1 和e2 e1 與e2 也都可以作賓語 如果e1是定語， e2是賓語，那么e1 e2也可以作賓語。,第一章 引 論,語法分析器,id, 1 = id, 2 + id, 3 60,語法分析：詞

10、法記號(hào)（token）流-語法短語,名詞1 動(dòng)詞 形容詞 名詞2,語法分析,第一章 引 論,語義分析：檢查程序的語義正確性，如類型檢查等,你們是優(yōu)秀的大工學(xué)子,你們是一個(gè)優(yōu)秀的大工學(xué)子。,第一章 引 論,第一章 引 論,中間代碼生成器,temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3,英語文本生成,You are good DLUTers.,第一章 引 論,代碼優(yōu)化器,temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + tem

11、p2 id1 := temp3,temp1 := id3 * 60.0 id1 := id2 + temp1,You are good DLUTers.,英語文本改進(jìn),You are excellent DLUTers,第一章 引 論,日語文本生成,You are excellent DLUTers,君大連理工大學(xué) 優(yōu)秀學(xué)生。,第一章 引 論,第一章 引 論,分析和綜合： 把編譯過程分成分析和綜合兩步 分析：分析源程序以計(jì)算其特性所涉及到的操作（詞法分析、語法分析、語義分析） 綜合：生成目標(biāo)代碼時(shí)所涉及到的操作（中間代碼生成、代碼優(yōu)化、代碼生成） 輔助：符號(hào)表管理、出錯(cuò)處理 8項(xiàng)功能對應(yīng)8個(gè)模

12、塊。,第一章 引 論,第一章 引 論,前端 后端,前端：依賴于源語言，獨(dú)立于目標(biāo)機(jī)器。,后端：依賴于目標(biāo)機(jī)器，獨(dú)立于源語言。,前端和后端： 把編譯過程分成前端和后端兩部分 前端：只依賴于源程序，獨(dú)立于目標(biāo)機(jī)器 （生成中間代碼） 后端：依賴于目標(biāo)機(jī)器，與源程序無關(guān)，只與中間語言有關(guān)（從中間代碼生成目標(biāo)代碼） 好處：提高開發(fā)編譯器的效率 取一個(gè)編譯器的前端，重寫它的后端以產(chǎn)生同一源語言在另一機(jī)器上的編譯器 不同的前端使用同一個(gè)后端，從而得到一個(gè)機(jī)器上的幾個(gè)編譯器（采用同一中間語言）,第一章 引 論,第一章 引 論,源程序,目標(biāo)機(jī)器1,目標(biāo)機(jī)器2,目標(biāo)機(jī)器3,目標(biāo)機(jī)器n,編譯器,不區(qū)分前端和后端的編

13、譯器,源程序,目標(biāo)機(jī)器1,目標(biāo)機(jī)器2,目標(biāo)機(jī)器3,目標(biāo)機(jī)器n,編譯器前端,編譯器后端,區(qū)分前端和后端的編譯器,第一章 引 論,遍,編譯的幾個(gè)階段常用一遍（pass）掃描實(shí)現(xiàn)，一遍掃描包括讀一個(gè)輸入文件和寫一個(gè)輸出文件。,第一章 引 論,遍,類比：刷墻藝術(shù)中的“遍”的概念,網(wǎng)線,水泥,瓷磚,任務(wù)：在一面墻上布置網(wǎng)線，并粉刷水泥，然后貼上瓷磚,第一章 引 論,遍,類比：刷墻藝術(shù)中的“遍”的概念,方法一：,第一遍：布上全部網(wǎng)線,網(wǎng)線,水泥,瓷磚,第一章 引 論,遍,類比：刷墻藝術(shù)中的“遍”的概念,方法一：,第二遍：粉刷全部墻面的水泥,網(wǎng)線,水泥,瓷磚,第一章 引 論,遍,類比：刷墻藝術(shù)中的“遍”的概

14、念,方法一：,第三遍：給整個(gè)墻面貼上瓷磚,網(wǎng)線,水泥,瓷磚,第一章 引 論,遍,類比：刷墻藝術(shù)中的“遍”的概念,方法二：,一遍：一邊布網(wǎng)線，一邊粉刷水泥，一邊貼瓷磚,網(wǎng)線,水泥,瓷磚,遍（趟）： 一遍或一趟：是指編譯程序在編譯時(shí)刻把源程序或源程序的等價(jià)物（中間程序）從頭到尾掃描一遍并轉(zhuǎn)換成另一緊鄰的等價(jià)物的全過程。 單遍掃描與多遍掃描：每一遍的掃視可完成上述一個(gè)階段或多個(gè)階段的工作。每一遍的輸入都是上一遍的輸出，第一遍的輸入是源程序正文，最后一遍的輸出是目標(biāo)代碼。 單遍與多遍的比較： 遍數(shù)多：編譯器結(jié)構(gòu)清晰，但時(shí)間效率不高 遍數(shù)少：編譯速度快，但對機(jī)器的內(nèi)存要求高 遍數(shù)的確定：主要因素是源程序

15、和機(jī)器（目標(biāo)機(jī)）的特征。,第一章 引 論,1.2 編譯器技術(shù)的應(yīng)用,高級語言的實(shí)現(xiàn) 高級編程語言易于編程，但程序運(yùn)行較慢 低級語言編程時(shí)可實(shí)施更有效的控制方式，得到更有效的代碼，但難編寫、易出錯(cuò)、難維護(hù) 流行編程語言的大多數(shù)演變都是朝著提高抽象級別的方向 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究,編程語言演義,編程語言 機(jī)器語言 匯編語言 高級語言（Fortran, C, Java, ),編程語言演義,機(jī)器語言特點(diǎn) 0,1串 打卡輸入 c7 06 0000 0002 mov x, c 其中符號(hào)x的地址是0000，c=2 計(jì)算機(jī)可以直接理解機(jī)器語言程序 機(jī)器語言缺點(diǎn) 可讀性差 可維護(hù)性

16、差,機(jī)器語言 匯編語言 高級語言,編程語言演義,匯編語言形式 mov x,2 c7 06 0000 0002 變量x的地址可以由匯編器維護(hù)，而不需要固定到某個(gè)絕對地址,機(jī)器語言 匯編語言 高級語言,編程語言演義,高級語言形式 賦值語句：x=2 貼近人類思維方式，貼近實(shí)際問題描述形式 計(jì)算機(jī)無法直接理解 需要編譯器輔助，將其轉(zhuǎn)換為機(jī)器語言形式,機(jī)器語言 匯編語言 高級語言,1.2 編譯器技術(shù)的應(yīng)用,高級語言的實(shí)現(xiàn) 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu) 化的新研究 支持用戶定義的聚合數(shù)據(jù)類型和高級控制流，如數(shù)組和記錄、循環(huán)和過程調(diào)用：C、Fortran 面向?qū)ο蟮闹饕拍钍菙?shù)據(jù)抽象和性質(zhì)繼承，

17、使得程序更加模塊化并易于維護(hù)：Smalltalk、C+、C#、Java 類型安全的語言：Java沒有指針，也不允許指針?biāo)阈g(shù)。它用無用單元收集機(jī)制來自動(dòng)地釋放那些不再使用的變量占據(jù)的內(nèi)存,1.2 編譯器技術(shù)的應(yīng)用,針對計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化 計(jì)算機(jī)體系結(jié)構(gòu)的迅速演化引起對新的編譯器技術(shù)一種不知足的需要 并行化 編譯器重新整理指令，使得指令級并行更有效 編譯器從傳統(tǒng)的串行程序自動(dòng)生成并行代碼，使之運(yùn)行于多處理器上 內(nèi)存分層 編譯器優(yōu)化歷來集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效,1.2 編譯器技術(shù)的應(yīng)用,新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì) 現(xiàn)在計(jì)算機(jī)系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼 在現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的研究中，在處理器的設(shè)計(jì)階段就開發(fā)編譯器，并將編譯生成的代碼在模擬器上運(yùn)行，以評價(jià)擬采用體系結(jié)構(gòu)的特征 編譯器技術(shù)影響計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)著名例子是精簡指令集計(jì)算機(jī)（RISC）的發(fā)明,1.2 編譯器技術(shù)的應(yīng)用,程序翻譯 二進(jìn)制翻譯 編譯器技術(shù)可用于把一種機(jī)器的二進(jìn)制代碼翻譯成另一種機(jī)器的代碼，以運(yùn)行原先為別的指令集編譯的代碼 數(shù)據(jù)庫查詢解釋器 數(shù)據(jù)庫查詢由一些謂