《編譯原理》第,章概述及高級(jí)語(yǔ)言課件

1、編譯原理,聯(lián)系方式：電 話： e-Mail: caos,1,PPT學(xué)習(xí)交流,C語(yǔ)言程序,void main( ) int x,y,z; x=3; y=2; z=x+y; , mov ax,3 mov x,ax mov ax,2 mov y,ax mov ax,x mov bx,y add ax,bx mov z,ax .,匯編語(yǔ)言程序,300 302 304 306 308 ,2,PPT學(xué)習(xí)交流,為什么要學(xué)習(xí)編譯原理？,更深刻地理解與運(yùn)用高級(jí)程序設(shè)計(jì)語(yǔ)言。 大型程序設(shè)計(jì)與軟件工程的經(jīng)典實(shí)例。 理論與實(shí)踐相結(jié)合的典范。 為解決實(shí)際問題提供一種新的有效途徑,3,PPT學(xué)習(xí)交流,語(yǔ)言種類 Progr

2、amming languages Scripts Domain-specific languages SQL, HTML, XML,4,PPT學(xué)習(xí)交流,語(yǔ)言參與者,5,PPT學(xué)習(xí)交流,學(xué)習(xí)本課程的目的和任務(wù),加深對(duì)編程語(yǔ)言設(shè)計(jì)和實(shí)現(xiàn)的理解，對(duì)和編程語(yǔ)言有關(guān)的理論有所了解，對(duì)宏觀上把握編程語(yǔ)言來(lái)說(shuō)，起一個(gè)奠基的作用，提升自身的編程能力 掌握編譯程序的基本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法，將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計(jì)中 培養(yǎng)團(tuán)隊(duì)協(xié)作能力,6,PPT學(xué)習(xí)交流,本課程的特點(diǎn),(1) 本課程理論性很強(qiáng)，學(xué)習(xí)時(shí)需要很強(qiáng)的邏輯思維能力 (2) 涉及的算法復(fù)雜，要深入地理解這些算法很困難 (3)

3、整個(gè)編譯程序的構(gòu)造方法非常精妙，就像一部走時(shí)精確的時(shí)鐘，很多齒輪、部件協(xié)調(diào)地運(yùn)轉(zhuǎn)，以驅(qū)動(dòng)指針準(zhǔn)確地旋轉(zhuǎn)；編譯程序也是如此，一邊掃描源程序，一邊經(jīng)過(guò)各個(gè)部件的運(yùn)算，準(zhǔn)確地輸出為目標(biāo)語(yǔ)言。 (4) 編譯原理課程各個(gè)部分之間的獨(dú)立性很強(qiáng)，包括詞法分析、語(yǔ)法分析、存儲(chǔ)的組織與分配、中間語(yǔ)言、語(yǔ)法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大部分。詞法分析和語(yǔ)法分析是其中的重點(diǎn)，語(yǔ)言分析也是難點(diǎn)，需要掌握比較復(fù)雜的算法邏輯；其他部分相對(duì)來(lái)說(shuō)知識(shí)性更強(qiáng)一些。各部分之間的方法也互相獨(dú)立，在學(xué)習(xí)時(shí)，便于逐個(gè)擊破。 (5) 考試考查的內(nèi)容相對(duì)來(lái)說(shuō)是很穩(wěn)定的，絕大多數(shù)題目的解法都非常機(jī)械。,7,PPT學(xué)習(xí)交流,學(xué)習(xí)方法,(1)

4、盡可能地掌握編譯原理的思想，要站得高一點(diǎn)，盡可能理解算法的思想，而不是背固定的算法。應(yīng)該盡力理解為什么要這樣做，逐漸在頭腦中建立起編譯器的整體概念，而不是零零散散的一些算法。 (2) 很多題目的解法比較固定，要熟練掌握相應(yīng)的具體方法。 (3) 多做習(xí)題, 對(duì)于編譯這樣的學(xué)科，題目的規(guī)模很大，步驟繁多，而且前面的步驟一旦出錯(cuò)，后面都錯(cuò)。 (4) 要扎扎實(shí)實(shí)地牢記重要算法，配合大量的習(xí)題進(jìn)行練習(xí)，達(dá)到拿到題目就可以動(dòng)手做的地步。 (5) 一邊學(xué)習(xí)，一邊總結(jié)，關(guān)鍵是找差異：同一問題可以用多種方法來(lái)求解，不同方法適用于不同的文法，對(duì)文法的限制和要求，相應(yīng)的表格的構(gòu)造、使用等，各個(gè)方面的差異都要關(guān)注。

5、(6) 親自動(dòng)手實(shí)現(xiàn)書上的一些算法,完成實(shí)驗(yàn)指導(dǎo)書上給出的一個(gè)簡(jiǎn)單的編譯程序，或者編譯程序的一部分，這樣能更靈活地掌握編譯程序構(gòu)造的精髓。,8,PPT學(xué)習(xí)交流,考 核 方 法,平時(shí)成績(jī)、作業(yè)完成：10% 要求上課不遲到早退,不曠課,有事請(qǐng)假 上課帶筆和草稿本,記好筆記 要求用大作業(yè)本, 不能交單張紙, 獨(dú)立完成 實(shí)驗(yàn)：20% 要求程序可運(yùn)行, 并有相關(guān)設(shè)計(jì)和使用說(shuō)明 期末考試：70% 閉卷形式,9,PPT學(xué)習(xí)交流,參考資料,編譯原理（龍書） Alfred.Aho等 第二版 機(jī)械工業(yè)出版社 程序設(shè)計(jì)語(yǔ)言編譯方法 肖軍模 第三版 大連理工大學(xué)出版社 編譯原理 呂映芝 清華大學(xué)出版社 編譯原理 技術(shù)

6、與工具 人民郵電出版社,10,PPT學(xué)習(xí)交流,編譯技術(shù)的發(fā)展,1954年至1957年間，IBM的John Backus帶領(lǐng)一個(gè)小組開發(fā)FORTRAN語(yǔ)言及其編譯器?；?8個(gè)人年，非常辛苦。 幾乎與此同時(shí)，Noam Chomsky開始自然語(yǔ)言結(jié)構(gòu)的研究。Chomsky的研究導(dǎo)致了根據(jù)語(yǔ)言文法(grammar，結(jié)構(gòu)規(guī)則)的難易程度以及識(shí)別它們所需的算法來(lái)為語(yǔ)言分類。 在6 0年代和7 0年代進(jìn)行的分析問題(parsing problem，用于限定上下文無(wú)關(guān)語(yǔ)言的識(shí)別的有效算法)的研究，相當(dāng)完善地解決了語(yǔ)言的識(shí)別的問題，現(xiàn)在它已是編譯理論的一個(gè)標(biāo)準(zhǔn)部分。 有窮自動(dòng)機(jī)(finite automata

7、)和正則表達(dá)式(regular expression) 與喬姆斯基的3型文法相對(duì)應(yīng)。對(duì)它們的研究與喬姆斯基的研究幾乎同時(shí)開始，并且引出了表示程序設(shè)計(jì)語(yǔ)言的單詞的符號(hào)方式。 接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其誤稱為優(yōu)化技術(shù)(optimization technique)，但因其從未真正地得到過(guò)被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù)(code improvement technique)。 當(dāng)分析問題變得好懂起來(lái)時(shí)，人們就在開發(fā)程序上花費(fèi)了很大的功夫來(lái)研究這一部分的編譯器的自動(dòng)構(gòu)造。Lex與Yacc。 在70年

8、代后期和80年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動(dòng)化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。,11,PPT學(xué)習(xí)交流,編譯器設(shè)計(jì)最近的發(fā)展,與復(fù)雜的程序設(shè)計(jì)語(yǔ)言的發(fā)展結(jié)合在一起。如用于函數(shù)語(yǔ)言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。 編譯器已成為基于窗口的交互開發(fā)環(huán)境(IDE)的一部分，IDE的標(biāo)準(zhǔn)并沒有多少，但已對(duì)標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行了開發(fā)。近年來(lái)對(duì)此進(jìn)行了大量研究，但是基本的編譯器設(shè)計(jì)近20年來(lái)沒有多大的改變，現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心一環(huán)。 由多處理機(jī)的發(fā)展以及對(duì)并行處理的要求，最近的研究方向是并行編譯。 隨著嵌入式應(yīng)用的迅速增長(zhǎng)，推動(dòng)了交

9、叉編譯技術(shù)的發(fā)展；對(duì)系統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵EDA技術(shù)的研究，也帶動(dòng)了專用語(yǔ)言VHDL等及其編譯技術(shù)的不斷深化。,12,PPT學(xué)習(xí)交流,第一章 引論,什么是編譯程序 編譯過(guò)程概述 編譯程序的結(jié)構(gòu) 編譯階段的組合 編譯程序的構(gòu)造方法,13,PPT學(xué)習(xí)交流,重點(diǎn)掌握：編譯程序工作的基本過(guò)程及其各階段的基本任務(wù)，編譯程序總框。,14,PPT學(xué)習(xí)交流,機(jī)器語(yǔ)言 (machine language) C7 06 0000 0002 匯編語(yǔ)言 (assembler language) MOV X , 2 高級(jí)語(yǔ)言 (high-level language) X = 2,為什么要使用編譯器？,15,PPT學(xué)習(xí)

10、交流,1.1 什么叫編譯程序,編譯程序（Compiler）將高級(jí)程序設(shè)計(jì)語(yǔ)言程序翻譯成邏輯上等價(jià)的低級(jí)語(yǔ)言(匯編語(yǔ)言,機(jī)器語(yǔ)言)程序的翻譯程序。 功能,編譯程序,源程序,目標(biāo)程序,計(jì)算機(jī)運(yùn)行,輸入數(shù)據(jù),結(jié)果,16,PPT學(xué)習(xí)交流,解釋程序,解釋程序（Interpreter）將高級(jí)程序設(shè)計(jì)語(yǔ)言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程序的翻譯程序。 功能,解釋程序,源程序,輸入數(shù)據(jù),結(jié)果,17,PPT學(xué)習(xí)交流,操作系統(tǒng) 匯編語(yǔ)言,編譯程序所處的層次,計(jì)算機(jī)硬件,18,PPT學(xué)習(xí)交流,計(jì)算機(jī)中的語(yǔ)言層次和轉(zhuǎn)換關(guān)系,19,PPT學(xué)習(xí)交流,1.1 什么叫編譯程序,翻譯程序：能夠?qū)⒛撤N語(yǔ)

11、言寫的程序轉(zhuǎn)換成另一種語(yǔ)言的程序，而且后者與前者在邏輯上是等價(jià)的。 編譯程序：是一種將高級(jí)語(yǔ)言程序(源程序)翻譯成低級(jí)語(yǔ)言(目標(biāo)程序)的程序 解釋程序：接受某高級(jí)語(yǔ)言的一個(gè)語(yǔ)句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。 診斷編譯程序、優(yōu)化編譯程序、交叉編譯程序,20,PPT學(xué)習(xí)交流,對(duì)編譯程序的一些說(shuō)明,編譯程序?qū)嵸|(zhì)上是一個(gè)翻譯程序，要注意等價(jià)變換 本課程的任務(wù)就是講解在這個(gè)轉(zhuǎn)換過(guò)程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個(gè)小的編譯器 轉(zhuǎn)換是一個(gè)總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時(shí)要體現(xiàn)軟件工程中軟件設(shè)計(jì)的原則，自頂向下，逐層

12、分解。 編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實(shí)現(xiàn)編譯器時(shí)必須分步驟分階段實(shí)現(xiàn)。分階段實(shí)現(xiàn)的好處是能夠簡(jiǎn)化程序的設(shè)計(jì)，當(dāng)然也可以不分階段實(shí)現(xiàn)。,21,PPT學(xué)習(xí)交流,與編譯程序相關(guān)的程序 解釋程序(Interpreter) 匯編程序(assembler) 連接程序(linker) 連接系統(tǒng)函數(shù)與系統(tǒng)資源 裝入程序(loader) 重定位(relocation) 預(yù)處理器(Preprocessor) 編輯器(editor) Debugger , Profiler , Project Manager,22,PPT學(xué)習(xí)交流,3、什么是編譯原理 編譯原理是討論編譯程序設(shè)計(jì)的基本理論、基本概念、基本方法,23

13、,PPT學(xué)習(xí)交流,1.2 編譯過(guò)程概述,1、邏輯上分五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成 每個(gè)階段把源程序從一種表示變換成另一種表示,24,PPT學(xué)習(xí)交流,按照詞法分析、語(yǔ)法分析、語(yǔ)義分析等這種方式來(lái)劃分階段的原因是：每個(gè)階段的復(fù)雜程度不同，所依據(jù)的理論基礎(chǔ)不同，實(shí)現(xiàn)時(shí)采用的方法也不同。主要是方便理解和實(shí)現(xiàn)。 劃分階段的依據(jù)是什么？每個(gè)階段所實(shí)現(xiàn)的功能相對(duì)獨(dú)立。,25,PPT學(xué)習(xí)交流,第一階段：詞法分析,任務(wù):從左到右掃描源程序，識(shí)別出每個(gè)單詞 附加任務(wù)：a、濾掉空格 b、識(shí)別單詞 單詞符號(hào)是語(yǔ)言的基本組成成分 詞法分析的工作主要依據(jù)語(yǔ)言的詞法規(guī)則，描述

14、詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。 單詞的種類： （1） 標(biāo)識(shí)符 （2） 關(guān)鍵字（char、int、if、else、switch、while、for等） （3） 運(yùn)算符（即運(yùn)算符號(hào) +、*、/、,例:,27,PPT學(xué)習(xí)交流,第二階段：語(yǔ)法分析,任務(wù): 在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將單詞符號(hào)串分解成各類語(yǔ)法短語(yǔ)(例：程序、語(yǔ)句、表達(dá)式)。 確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的程序。 根據(jù)規(guī)則判定：賦值語(yǔ)句：標(biāo)識(shí)符：表達(dá)式 表達(dá)式：標(biāo)識(shí)符、常數(shù)是表達(dá)式； 表達(dá)式的運(yùn)算也是表達(dá)式 例：識(shí)別符號(hào)串id1:=int1 + id2 * id3 + id2 * id3（即 result:=

15、5B * CB * C）是一個(gè)賦值語(yǔ)句， 而int1 + id2 * id3 + id2 * id3 （5B * CB * C） 是一個(gè)表達(dá)式,28,PPT學(xué)習(xí)交流,語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)則， 表示語(yǔ)法規(guī)則的工具是上下文無(wú)關(guān)文法,用下推自動(dòng)機(jī)實(shí)現(xiàn)。,id1:=int1 + id2 * id3 + id2 * id3,29,PPT學(xué)習(xí)交流,第三階段：語(yǔ)義分析和中間代碼生成,任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)。 靜態(tài)語(yǔ)義審查 變量定義 類型匹配 類型轉(zhuǎn)換 例：C:=A*B (檢查C與、類型) 中間代碼的翻譯 中間代碼有多種形式，如： 四元式:

16、 (運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果),30,PPT學(xué)習(xí)交流,例：對(duì)賦值語(yǔ)句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查result、C是否定義、類型 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 * id3,31,PPT學(xué)習(xí)交流,第四階段： 代碼優(yōu)化,任務(wù)：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為

17、高效(時(shí)間和空間)。 優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。 代碼的優(yōu)化依據(jù)的是程序的等價(jià)變換規(guī)則。,32,PPT學(xué)習(xí)交流,第五階段：目標(biāo)代碼的生成,任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。 依賴于機(jī)器的硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義 目標(biāo)代碼可以是：絕對(duì)指令代碼、可重定位的指令代碼、匯編指令代碼,33,PPT學(xué)習(xí)交流,1.3編譯程序的結(jié)構(gòu),由左圖可以看出，詞法分析是實(shí)現(xiàn)編譯器的基礎(chǔ)，語(yǔ)法分析是實(shí)現(xiàn)編譯器的關(guān)鍵。 因此按照這個(gè)順序來(lái)實(shí)現(xiàn)編譯器 每一步的實(shí)現(xiàn)都依賴于一定的理論基礎(chǔ)。 數(shù)學(xué)，尤其是離散數(shù)學(xué)是程序設(shè)計(jì)方法學(xué)的理論基礎(chǔ),34,PPT學(xué)習(xí)

18、交流,1.3 編譯程序的結(jié)構(gòu)(續(xù)),幾個(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)代碼生成,35,PPT學(xué)習(xí)交流,為什么生成中間代碼,36,PPT學(xué)習(xí)交流,1.3 編譯程序的結(jié)構(gòu)(續(xù)),(1) 記號(hào)(token) 當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)；這也就是說(shuō)，作為一個(gè)枚

19、舉數(shù)據(jù)類型的值來(lái)表示源程序的記號(hào)集。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,37,PPT學(xué)習(xí)交流,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu),(2) 語(yǔ)法樹（syntax tree） 如果分析程序確實(shí)生成了語(yǔ)法樹，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動(dòng)態(tài)分配該結(jié)構(gòu)，則整棵樹可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的語(yǔ)義分析程序收集的信息。,38,PPT學(xué)習(xí)交流,(3) 符號(hào)表（symbol table） 這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識(shí)符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號(hào)表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)

20、義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號(hào)表提供的信息選出恰當(dāng)?shù)拇a。因?yàn)閷?duì)符號(hào)表的訪問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時(shí)在一個(gè)列表或棧中可使用若干個(gè)表格。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,39,PPT學(xué)習(xí)交流,(4) 常數(shù)表（literal table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無(wú)需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,40,PPT學(xué)習(xí)

21、交流,(5) 中間代碼（intermediate code） 根據(jù)中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對(duì)于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡(jiǎn)單重組的表示。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,41,PPT學(xué)習(xí)交流,(6) 臨時(shí)文件（t e m p o r a ry file） 計(jì)算機(jī)過(guò)去一直未能在編譯器時(shí)將整個(gè)程序保留在存儲(chǔ)器中。這一問題已經(jīng)通過(guò)使用臨時(shí)文件來(lái)保存翻譯時(shí)中間步驟的結(jié)果或通過(guò)“匆忙地”編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,42,PPT學(xué)習(xí)交流,1.4 構(gòu)造編

22、譯程序,一般生成編譯程序的方法有： 1.直接用機(jī)器語(yǔ)言編寫編譯程序 2.用匯編語(yǔ)言編寫編譯程序 注：編譯程序核心部分常用匯編語(yǔ)言編寫 3.用高級(jí)語(yǔ)言編寫編譯程序 注：這是普遍采用的方法 4.自編譯 5.用編譯工具自動(dòng)生成:LEX(詞法分析)與YACC(用于自動(dòng)產(chǎn)生LALR分析表) 6.移植（同種語(yǔ)言的編譯程序在不同類型的機(jī)器之間移植）,43,PPT學(xué)習(xí)交流,1.4 構(gòu)造編譯程序(續(xù)),構(gòu)造編譯程序要掌握以下幾方面的內(nèi)容： 源語(yǔ)言：理解其結(jié)構(gòu)和含義 目標(biāo)語(yǔ)言：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等 編譯方法,44,PPT學(xué)習(xí)交流,編譯技術(shù)的應(yīng)用,語(yǔ)言的結(jié)構(gòu)化編輯器 :Turbo-Edit、edit

23、plus和Ultraedit等 語(yǔ)言程序的調(diào)試工具 語(yǔ)言程序的測(cè)試工具 高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具 交叉編譯程序,45,PPT學(xué)習(xí)交流,作業(yè)1：,將13題寫在作業(yè)本上，思考第5題。 1. 什么是編譯程序 ？ 2. 編譯過(guò)程分哪些階段？各階段的功能和任務(wù)是什么? 3. 寫出C語(yǔ)言中字符集、單詞、數(shù)據(jù)類型、各種表達(dá)式、語(yǔ)句和程序的組成 4. 自學(xué)2.5節(jié) 5. 設(shè)計(jì)一種計(jì)算機(jī)語(yǔ)言，該語(yǔ)言可以用來(lái)解決實(shí)際問題，比如，該語(yǔ)言的應(yīng)用等。,46,PPT學(xué)習(xí)交流,第二章 程序語(yǔ)言的語(yǔ)法描述(P25),掌握：上下文無(wú)關(guān)文法基本概念 推導(dǎo)、句型、句子、語(yǔ)言 語(yǔ)法樹 文法的二義性 理解：文法的語(yǔ)言生成過(guò)程,47,PP

24、T學(xué)習(xí)交流,以C和PASCAL為例復(fù)習(xí)高級(jí)語(yǔ)言 1 語(yǔ)言的基本字符集的定義(字母, 數(shù)字, 界符) 2 單詞集的定義 3 數(shù)據(jù)類型的定義 4 表達(dá)式的定義 5 語(yǔ)句的定義 6 程序定義 PASCAL和C的主要區(qū)別,48,PPT學(xué)習(xí)交流,程序語(yǔ)言定義的基本概念,1. 字母表：是元素的有窮非空集合 2. 符號(hào)：字母表中的每個(gè)元素，因此字母表也稱為符號(hào)集。 不同的語(yǔ)言可以有不同的字母表，例如英文的字母表中26個(gè)字母、數(shù)字及標(biāo)點(diǎn)符號(hào)等。 PASCAL語(yǔ)言的字母表是由字母、數(shù)字、若干專用符號(hào)組成。 符號(hào)是該語(yǔ)言能識(shí)別的符號(hào)，字母表是該語(yǔ)言能識(shí)別的所有符號(hào)的全體（字符集）。,49,PPT學(xué)習(xí)交流,基本概念

25、(續(xù)),3. 符號(hào)串: 由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串，例如00 11 10 是字母表 =0，1上的符號(hào)串. 字母表A=a,b,c上的一些符號(hào)串有：a,b,c,ab,aaca等。 在符號(hào)串中，符號(hào)的順序是很重要的，符號(hào)串a(chǎn)b就不同于ba,abca和aabc也不同。 符號(hào)串STR表示“由符號(hào)S、T和R，并按此順序組成.,50,PPT學(xué)習(xí)交流,基本概念(續(xù)),4. 符號(hào)串的運(yùn)算 a. 字符串的連接： 字符串稱為字符串和的連接 符號(hào)串的長(zhǎng)度 :符號(hào)串中符號(hào)的個(gè)數(shù)，例如: 某符號(hào)串中有m個(gè)符號(hào),則稱其長(zhǎng)度為m，表示為x=m，如001110的長(zhǎng)度是6。 空符號(hào)串: 即不包含任何符號(hào)的符號(hào)串

26、，用表示，其長(zhǎng)度為0， 即=0。 用 *表示上所有的符號(hào)串的全體(長(zhǎng)度為0，1，2，)。,51,PPT學(xué)習(xí)交流,集合的運(yùn)算 b. *的子集U、V的積 ： UV = | U & V 長(zhǎng)度相加 即: 集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成。 c. 集合的方冪：n個(gè)相同符號(hào)連接 Vn =VVVV . V 規(guī)定V0 = d. 閉包、正則閉包的運(yùn)算,52,PPT學(xué)習(xí)交流,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,使用 * 表示上的一切符號(hào)串（包括）組成的集合。 稱為的閉包。 上的除外的所有符號(hào)串組成的集合記為+ 。稱為

27、的正閉包。,U = aa,bb V=00,11 則UV=? V=0,1 V* = ? V+ = ?,53,PPT學(xué)習(xí)交流,文 法,文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。是一種工具，它可用于嚴(yán)格定義句子的結(jié)構(gòu)；用有窮的規(guī)則刻劃無(wú)窮的集合 文法是被用來(lái)精確而無(wú)歧義地描述語(yǔ)言的句子的構(gòu)成方式. 文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。,54,PPT學(xué)習(xí)交流,引 例,例1：有如下規(guī)則 (表示由組成) | 我 大學(xué)生 是 | 現(xiàn)要求根據(jù)如上規(guī)則得出句子：我是大學(xué)生 = = =我是大學(xué)生,55,PPT學(xué)習(xí)交流,句子“我是大學(xué)生”也可以如下圖示分析,在有規(guī)則的情況下，每一次用上述規(guī)則的右邊去替換左邊，得到“我是大

28、學(xué)生”是符合上述規(guī)則的句子,56,PPT學(xué)習(xí)交流,上下文無(wú)關(guān)文法的形式定義,由四部分組成： 終結(jié)符號(hào)：是組成該語(yǔ)言的最基本的符號(hào)，是不可再分的基本符號(hào),如保留字、標(biāo)識(shí)符等。 非終結(jié)符號(hào)：規(guī)則中用尖括號(hào)括起來(lái)的符號(hào)，表示一些語(yǔ)法成分，可以推導(dǎo)出其他的語(yǔ)法成分,表示一定符號(hào)串的集合，是一個(gè)類，如表達(dá)式。 開始符號(hào)：規(guī)則中的一個(gè)特殊的非終結(jié)符號(hào)，語(yǔ)言中的句子都從它開始推導(dǎo),如程序、句子 產(chǎn)生式：定義語(yǔ)法成分的規(guī)則，其中：,57,PPT學(xué)習(xí)交流,文法的形式定義(續(xù)),一個(gè)文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中Vn表示非終結(jié)符號(hào) Vt表示終結(jié)符號(hào)，VnVt=(字母表)，VnVt= S

29、是開始符號(hào)， P是產(chǎn)生式，形如：(V+且至少含有一個(gè)非終結(jié)符號(hào)，V*),58,PPT學(xué)習(xí)交流,上例中： G=（Vn,Vt,P,） Vn=（，） Vt= (我，是，大學(xué)生) P =, | 我 大學(xué)生 是 |,59,PPT學(xué)習(xí)交流,產(chǎn)生式的形式為：A ,左部符號(hào)，非終結(jié)符,右部，可以含有非終結(jié)符和終結(jié)符,又稱為一條規(guī)則 有時(shí)一個(gè)產(chǎn)生式不足以描述該語(yǔ)法范疇，就用多個(gè)產(chǎn)生式，如算術(shù)表達(dá)式的描述為：(遞歸定義) E E + E E E * E E i 相同左部的一個(gè)右部又稱一個(gè)候選式,60,PPT學(xué)習(xí)交流,上下文無(wú)關(guān)文法所定義的語(yǔ)法成分獨(dú)立于它可能出現(xiàn)的環(huán)境，即不考慮上下文。,61,PPT學(xué)習(xí)交流,算術(shù)

30、表達(dá)式的文法定義,變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式,E E + E E E * E E ( E ) E i,E E+E | E*E | (E) | i,62,PPT學(xué)習(xí)交流,上下文無(wú)關(guān)文法產(chǎn)生句子的方法:從文法的開始符號(hào)出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對(duì)左邊的非終結(jié)符進(jìn)行替換和展開 例：表達(dá)式定義規(guī)則,E E + E E E * E E ( E ) E i,( i+i ),E=( E ) =( E+E ) =( i+E ) =( i + i ),63,PPT學(xué)習(xí)交流,推導(dǎo): 連續(xù)使用產(chǎn)生式右部去替換左部某個(gè)非終結(jié)符的過(guò)程,得到的連續(xù)序列稱為

31、一個(gè)推導(dǎo)。 直接推導(dǎo)：又稱一步推導(dǎo)(用 符號(hào)=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部,64,PPT學(xué)習(xí)交流,幾個(gè)概念的形式定義,直接推導(dǎo): 如果是文法 G=（Vn,Vt,P,S）的產(chǎn)生式，和是*中的任意符號(hào)，若有符號(hào)串v,w滿足：v=,w=,則說(shuō)v直接產(chǎn)生w，(w是v的直接推導(dǎo))記作：v=w 例：S01, 0S0=0010(直接推導(dǎo),) 如果存在v=w0=w1=w2.=Wn=w(n0)，則稱v推導(dǎo)出w（長(zhǎng)度為n），記作v=w(至少一步) 若有=w或v=w，則記作v=w(0步或若干步),*,+,65,PPT學(xué)習(xí)交流,例3 : G = (E, i, +, *, (, ) , P , E)

32、(1.1) P： E E+E | E*E | (E) | i 表達(dá)式(i)和(i+i)*i的推導(dǎo)：,E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,E E 0步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (E) 直接推導(dǎo),66,PPT學(xué)習(xí)交流,句型：設(shè)(s)是一文法，如果符號(hào)串x是從開始符號(hào)推導(dǎo)出來(lái)的，即有s=x,則稱x是文法G(s)的一個(gè)句型。 即: 任何由開始符推導(dǎo)出來(lái)的符號(hào)串都是句型。 句子：若x僅由終結(jié)符號(hào)組成，則稱x為G(S)的句子,*,練習(xí) 文法G：SaAcB | Bd AA

33、aB | c BbScA | b 寫出句型aAcbBdcc和句子acabcbbdcc的推導(dǎo)過(guò)程。,67,PPT學(xué)習(xí)交流,文法G所產(chǎn)生的語(yǔ)言定義為： L(G)=x|S=x,其中S為文法的開始符號(hào)，xVt* 。即: 一個(gè)文法G可以推導(dǎo)出的所有句子構(gòu)成的一個(gè)集合, 就確定了一個(gè)語(yǔ)言。,*,68,PPT學(xué)習(xí)交流,例2.1 (P30) 考慮文法G1: 它定義了什么語(yǔ)言。,S bA A aA|a,推導(dǎo)過(guò)程 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa,歸納得： L(G1) = ban | n1,69,PPT學(xué)習(xí)交流,練習(xí)：文法(A,B,S,a,b,c,P,S) S A

34、c|aB A ab B bc寫出(G)的全部元素,L(G) = abc,70,PPT學(xué)習(xí)交流,例2.2(P30) 考慮文法G2: 它定義的語(yǔ)言是：,S AB A aA|a B bB|b,L(G2) = ambn |m,n1,71,PPT學(xué)習(xí)交流,思考：構(gòu)造一個(gè)文法G3使得：,L(G3) = anbn |n1 ,S aSb S ab,a,b的個(gè)數(shù)相同,則文法G3為：,72,PPT學(xué)習(xí)交流,文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語(yǔ)言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價(jià)。,73,PPT學(xué)習(xí)交流,例：有如下兩個(gè)文法，判斷它們是否等價(jià)？ G1=（S，0，S，S0S，S0） G

35、2=（S，0，S，SS0，S0）,S0 S0S00 S0S 00S 0000,L(G1) = 0n | n1,對(duì)于G2：,對(duì)于G1 ：,SS0 S00 0000,L(G2) = 0n | n1,G1G2，但L(G1) = L(G2)，文法G1和G2等價(jià),74,PPT學(xué)習(xí)交流,例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過(guò)程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i

36、(E + E)*i (E+ i)*i (i + i)*i,得到一個(gè)語(yǔ)言，是通過(guò)利用所有的產(chǎn)生式推導(dǎo)出所有可能的句子，構(gòu)成一個(gè)集合。 但是一個(gè)句型到另一個(gè)句型(句子)的推導(dǎo)過(guò)程不是唯一的。,75,PPT學(xué)習(xí)交流,最左推導(dǎo): 在整個(gè)推導(dǎo)過(guò)程中,任何一步推導(dǎo)=都是對(duì)中最左邊的非終結(jié)符進(jìn)行替換。 最右推導(dǎo):,在推導(dǎo)之前確定推導(dǎo)的順序，是對(duì)句子進(jìn)行確定性分析所必須的,例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導(dǎo)過(guò)程： E E*E (E)*E (E + E)*E (i + E)*E (i + i

37、)*E (i + i)*i 最右推導(dǎo)過(guò)程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i,76,PPT學(xué)習(xí)交流,用語(yǔ)法樹表示上下文無(wú)關(guān)文法的推導(dǎo),語(yǔ)法樹：推導(dǎo)的形式化表示，有助于理解句子語(yǔ)法結(jié)構(gòu)的層次 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記屬字母集中的一個(gè)符號(hào)，根由開始符號(hào)標(biāo)記。 當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新的結(jié)點(diǎn)，并標(biāo)記它，畫出其與父結(jié)點(diǎn)之間的連線。,77,PPT學(xué)習(xí)交流,例：對(duì)文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語(yǔ)法樹：,在語(yǔ)法樹的推導(dǎo)過(guò)程中的任何時(shí)刻，沒有后代的端末結(jié)點(diǎn)自左至右排列起來(lái)就是一個(gè)句型 一棵語(yǔ)法樹表示了一個(gè)句型很多可能的不同推導(dǎo)過(guò)程。(包括最左推導(dǎo)和最右推導(dǎo)),78,PPT學(xué)習(xí)交流,例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的語(yǔ)法樹： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i),(2) E (E) (E * E) (i*E) (i * E + E)