編譯原理課件chap1

1、2022-2-2第一章 引 論1編編 譯譯 原原 理理主講教師：主講教師： 劉冰劉冰 重慶郵電大學(xué)計(jì)算機(jī)學(xué)院重慶郵電大學(xué)計(jì)算機(jī)學(xué)院E-mail: 2022-2-2第一章 引 論2課程要求課程要求n基礎(chǔ)理論基礎(chǔ)理論：熟悉基于形式語言理論的編譯：熟悉基于形式語言理論的編譯程序構(gòu)造原理和高級(jí)語言的實(shí)現(xiàn)原理。程序構(gòu)造原理和高級(jí)語言的實(shí)現(xiàn)原理。n基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)：全面掌握詞法分析、語法分析：全面掌握詞法分析、語法分析和語法制導(dǎo)翻譯方法等計(jì)算機(jī)處理技術(shù)，和語法制導(dǎo)翻譯方法等計(jì)算機(jī)處理技術(shù)，了解高級(jí)語言中各種語言成分的實(shí)現(xiàn)方法。了解高級(jí)語言中各種語言成分的實(shí)現(xiàn)方法。n基本技能基本技能：掌握計(jì)算機(jī)語言處理系統(tǒng)

2、中各：掌握計(jì)算機(jī)語言處理系統(tǒng)中各種通用的分析和翻譯技術(shù)，以及自動(dòng)生成種通用的分析和翻譯技術(shù)，以及自動(dòng)生成系統(tǒng)的運(yùn)用。系統(tǒng)的運(yùn)用。2022-2-2第一章 引 論3課前說明課前說明基于形式語言理論中的有關(guān)概念來討論編譯實(shí)現(xiàn)問題。即 編譯原理=形式語言理論+編譯技術(shù)本書主要內(nèi)容涉及：高級(jí)程序設(shè)計(jì)語言形式語言理論的基本概念構(gòu)造編譯程序的基本概念、原理和技術(shù)2022-2-2第一章 引 論4課前思考課前思考什么是計(jì)算機(jī)程序？什么是計(jì)算機(jī)程序？ 什么是編譯程序？什么是編譯程序？ 編譯過程和編譯程序的結(jié)構(gòu)？編譯過程和編譯程序的結(jié)構(gòu)？計(jì)算機(jī)程序是指一系列的指令或語句，規(guī)定了計(jì)算計(jì)算機(jī)程序是指一系列的指令或語句，

3、規(guī)定了計(jì)算機(jī)依次要進(jìn)行的一系列工作。它總是由某種程序設(shè)機(jī)依次要進(jìn)行的一系列工作。它總是由某種程序設(shè)計(jì)語言來書寫。計(jì)語言來書寫。不同程序設(shè)計(jì)語言適用于不同的應(yīng)用領(lǐng)域。不同程序設(shè)計(jì)語言適用于不同的應(yīng)用領(lǐng)域。2022-2-2第一章 引 論5程序設(shè)計(jì)語言的定義程序設(shè)計(jì)語言的定義程序設(shè)計(jì)語言是為書寫計(jì)算機(jī)程序而人為設(shè)計(jì)的符程序設(shè)計(jì)語言是為書寫計(jì)算機(jī)程序而人為設(shè)計(jì)的符號(hào)語言。涉及以下四個(gè)方面號(hào)語言。涉及以下四個(gè)方面: :語法語法：表示構(gòu)成語言句子的各個(gè)記號(hào)之間的組合：表示構(gòu)成語言句子的各個(gè)記號(hào)之間的組合規(guī)律。規(guī)律。語義語義：表示按照各種表示方法所表示的各個(gè)記號(hào)：表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含

4、義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）間的關(guān)系）語用語用：表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的：表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來源、使用和影響。來源、使用和影響。語境語境：指理解和實(shí)現(xiàn)程序設(shè)計(jì)語言的環(huán)境，包括：指理解和實(shí)現(xiàn)程序設(shè)計(jì)語言的環(huán)境，包括編譯環(huán)境和運(yùn)行環(huán)境編譯環(huán)境和運(yùn)行環(huán)境2022-2-2第一章 引 論6語法定義的方式語法定義的方式語法圖：用圖解形式表描述程序設(shè)計(jì)語言語法規(guī)語法圖：用圖解形式表描述程序設(shè)計(jì)語言語法規(guī)則的工具則的工具BNFBNF表示法（元語言）：語法規(guī)則的形式表示系統(tǒng)表示法（元語言）：語法規(guī)則的形式表示系統(tǒng)口語：用自然

5、語言描述程序設(shè)計(jì)語言的語法成分口語：用自然語言描述程序設(shè)計(jì)語言的語法成分的書寫方式的書寫方式語法圖語法圖數(shù)據(jù)類型數(shù)據(jù)類型函數(shù)標(biāo)識(shí)符函數(shù)標(biāo)識(shí)符形參表列形參表列函數(shù)體函數(shù)體()函數(shù)定義函數(shù)定義C C語言中關(guān)于函數(shù)定義的語法圖：語言中關(guān)于函數(shù)定義的語法圖：2022-2-2第一章 引 論7程序的執(zhí)行方式程序的執(zhí)行方式高級(jí)語言程序通常采用兩種方式執(zhí)行：解釋方式和翻高級(jí)語言程序通常采用兩種方式執(zhí)行：解釋方式和翻譯方式譯方式解釋方式：逐個(gè)語句地分析和執(zhí)行，如解釋方式：逐個(gè)語句地分析和執(zhí)行，如Basic，Prolog 優(yōu)點(diǎn)：易于查錯(cuò)優(yōu)點(diǎn)：易于查錯(cuò) 缺點(diǎn)：效率低，運(yùn)行速度慢缺點(diǎn)：效率低，運(yùn)行速度慢翻譯方式：對(duì)整

6、個(gè)程序進(jìn)行分析，翻譯成等價(jià)機(jī)器語言翻譯方式：對(duì)整個(gè)程序進(jìn)行分析，翻譯成等價(jià)機(jī)器語言程序后執(zhí)行，如程序后執(zhí)行，如Pascal，F(xiàn)ortran，C 優(yōu)點(diǎn)：只需分析和翻譯一次，優(yōu)點(diǎn)：只需分析和翻譯一次， 缺點(diǎn)：在運(yùn)行中發(fā)現(xiàn)的錯(cuò)誤必須在源程序中查找缺點(diǎn)：在運(yùn)行中發(fā)現(xiàn)的錯(cuò)誤必須在源程序中查找2022-2-2第一章 引 論81.1 1.1 什么叫編譯程序什么叫編譯程序 編譯程序編譯程序: :是指這樣的程序，它能夠把是指這樣的程序，它能夠把某種語言的程序轉(zhuǎn)換成另一種語言的程序，某種語言的程序轉(zhuǎn)換成另一種語言的程序，而后者與前者在邏輯上是等價(jià)的。如果源語而后者與前者在邏輯上是等價(jià)的。如果源語言是諸如言是諸如F

7、ORTRANFORTRAN、PascalPascal、C C、AdaAda、SmalltalkSmalltalk或或JavaJava這樣的這樣的“高級(jí)語言高級(jí)語言”，而，而目標(biāo)語言如匯編語言之類的目標(biāo)語言如匯編語言之類的“低級(jí)語言低級(jí)語言”這這樣的翻譯程序則稱之為編譯程序。樣的翻譯程序則稱之為編譯程序。2022-2-2第一章 引 論9n 編譯程序編譯程序(compiler)是一種翻譯程序，是一種翻譯程序，n它特指把某種高級(jí)程序設(shè)計(jì)語言翻譯成具它特指把某種高級(jí)程序設(shè)計(jì)語言翻譯成具n體計(jì)算機(jī)上的低級(jí)程序設(shè)計(jì)語言。體計(jì)算機(jī)上的低級(jí)程序設(shè)計(jì)語言。 編譯程序的執(zhí)行過程編譯程序的執(zhí)行過程 - 源語言源語言

8、編譯程序編譯程序目標(biāo)語言目標(biāo)語言數(shù)據(jù)數(shù)據(jù) 結(jié)果結(jié)果運(yùn) 行 程運(yùn) 行 程序序編譯階段編譯階段運(yùn)行階段運(yùn)行階段編譯程序的執(zhí)行過程編譯程序的執(zhí)行過程兩個(gè)階段：兩個(gè)階段：2022-2-2第一章 引 論10由此，由此， 編譯程序是一種語言轉(zhuǎn)換系統(tǒng)編譯程序是一種語言轉(zhuǎn)換系統(tǒng)編譯程序編譯程序高級(jí)語高級(jí)語言書寫言書寫的程序的程序（源程（源程序）序）低級(jí)語言低級(jí)語言程序（目程序（目標(biāo)程序）標(biāo)程序）比如，比如，C+編譯器編譯器C+CJavaBytecodeJava編譯器編譯器2022-2-2第一章 引 論11編譯程序的功能編譯程序的功能n從功能上看，一個(gè)編譯程序就是一個(gè)語言翻譯程序。從功能上看，一個(gè)編譯程序就是一

9、個(gè)語言翻譯程序。n源語言通常是一個(gè)高級(jí)語言，如源語言通常是一個(gè)高級(jí)語言，如FORTRAN，C 或或Pascal。n目標(biāo)語言通常是一個(gè)低級(jí)語言目標(biāo)語言通常是一個(gè)低級(jí)語言,如匯編或機(jī)器語言。如匯編或機(jī)器語言。 T形圖：形圖：表示編譯程序涉及的三個(gè)語言表示編譯程序涉及的三個(gè)語言S OI lS:源語言源語言(程序程序)，Source language(program)lO:目標(biāo)語言目標(biāo)語言(程序程序), target/object language(program)lI:實(shí)現(xiàn)語言實(shí)現(xiàn)語言, implementation language2022-2-2第一章 引 論12 什么是什么是 解釋程序解釋程序

10、?n 解釋程序解釋程序(interpreter)也是一種翻譯程序，也是一種翻譯程序，將某高級(jí)語翻譯成具體計(jì)算機(jī)上的低級(jí)程序設(shè)將某高級(jí)語翻譯成具體計(jì)算機(jī)上的低級(jí)程序設(shè)計(jì)語言計(jì)語言;解釋程序的執(zhí)行過成如圖解釋程序的執(zhí)行過成如圖1.3 所示。所示。 編譯程序編譯程序與與解釋程序解釋程序的主要區(qū)別的主要區(qū)別: : 數(shù)據(jù)數(shù)據(jù) 結(jié)果結(jié)果解釋程序解釋程序解釋程序的執(zhí)行過程解釋程序的執(zhí)行過程 源語句源語句2022-2-2第一章 引 論13 注意編譯程序與解釋程序的區(qū)別，一注意編譯程序與解釋程序的區(qū)別，一個(gè)語言的個(gè)語言的解釋程序解釋程序是著樣的程序：它以該是著樣的程序：它以該語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)

11、語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身。程序，而是邊解釋邊執(zhí)行源程序本身。 術(shù)語術(shù)語“編譯編譯”的內(nèi)涵是實(shí)現(xiàn)從源語言的內(nèi)涵是實(shí)現(xiàn)從源語言表示的算法向目標(biāo)語言表示的算法的等價(jià)表示的算法向目標(biāo)語言表示的算法的等價(jià)變換。變換。2022-2-2第一章 引 論14 編譯程序編譯程序的分類的分類診斷編譯程序：專門用于幫助程序開發(fā)和調(diào)試；診斷編譯程序：專門用于幫助程序開發(fā)和調(diào)試；優(yōu)化編譯程序：著重于提高目標(biāo)代碼效率；優(yōu)化編譯程序：著重于提高目標(biāo)代碼效率；交叉編譯程序：產(chǎn)生不同于交叉編譯程序：產(chǎn)生不同于宿主機(jī)宿主機(jī)的機(jī)器代碼；的機(jī)器代碼；宿主機(jī)：宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)運(yùn)行編

12、譯程序的計(jì)算機(jī)目標(biāo)機(jī)：目標(biāo)機(jī)：運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)可變目標(biāo)編譯程序：不需重寫編譯程序中與機(jī)器無關(guān)可變目標(biāo)編譯程序：不需重寫編譯程序中與機(jī)器無關(guān) 的部分就可以改變的部分就可以改變目標(biāo)機(jī)目標(biāo)機(jī)。2022-2-2第一章 引 論151.2 1.2 編譯過程概述編譯過程概述 掌握編譯過程的五個(gè)基本階段，掌握編譯過程的五個(gè)基本階段，是我們學(xué)習(xí)編譯原理課程的基本內(nèi)是我們學(xué)習(xí)編譯原理課程的基本內(nèi)容，把編譯的五個(gè)基本階段與英譯容，把編譯的五個(gè)基本階段與英譯中的五個(gè)步驟相比較，有利于對(duì)編中的五個(gè)步驟相比較，有利于對(duì)編譯過程的理解。譯過程的理解。2022-2-2第一章

13、 引 論16英譯與編譯的比較英譯與編譯的比較1.1.識(shí)別出句子中的一個(gè)識(shí)別出句子中的一個(gè)個(gè)單字個(gè)單字2.2.分析句子的語法結(jié)構(gòu)分析句子的語法結(jié)構(gòu)3.3.初步翻譯句子的含意初步翻譯句子的含意4.4.譯文修飾譯文修飾5.5.寫出最后譯文寫出最后譯文1.1.詞法分析詞法分析2.2.語法分析語法分析3.3.語義分析中間代語義分析中間代碼生成碼生成4.4.優(yōu)化優(yōu)化5.5.目標(biāo)代碼生成目標(biāo)代碼生成2022-2-2第一章 引 論171.2.1 詞法分析詞法分析(Lexical analysis) 輸入源程序，對(duì)構(gòu)成源程序的字符串輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞（也進(jìn)行掃描和分

14、解，識(shí)別出一個(gè)個(gè)單詞（也稱單詞符號(hào)，或簡(jiǎn)稱符號(hào)）稱單詞符號(hào)，或簡(jiǎn)稱符號(hào)） 在詞法分析階段工作所依循的是語言在詞法分析階段工作所依循的是語言的詞法規(guī)則。描述詞法規(guī)則的有效工具是的詞法規(guī)則。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。正規(guī)式和有限自動(dòng)機(jī)。2022-2-2第一章 引 論18n詞法分析程序又稱掃描程序。詞法分析程序又稱掃描程序。n是編譯過程的第一個(gè)階段，其任務(wù)是：讀源是編譯過程的第一個(gè)階段，其任務(wù)是：讀源程序的字符流、識(shí)別單詞（如標(biāo)識(shí)符、整數(shù)、程序的字符流、識(shí)別單詞（如標(biāo)識(shí)符、整數(shù)、界限符等），并轉(zhuǎn)換成內(nèi)部形式。界限符等），并轉(zhuǎn)換成內(nèi)部形式。n輸入：源程序中的字符流輸入：源程序中的字符

15、流n輸出：等長的內(nèi)部形式，即屬性字。輸出：等長的內(nèi)部形式，即屬性字。2022-2-2第一章 引 論19詞法分析舉例詞法分析舉例n一個(gè)一個(gè)C源程序片段：源程序片段：qint a;qa=a+2;q詞法分析后返回詞法分析后返回(如右如右圖圖)： 單詞類型單詞類型 單詞值單詞值保留字保留字 int標(biāo)識(shí)符標(biāo)識(shí)符 a界符界符 ;標(biāo)識(shí)符標(biāo)識(shí)符 a算符算符(賦值賦值) =標(biāo)識(shí)符標(biāo)識(shí)符 a算符算符(加加) +整數(shù)整數(shù) 2界符界符 ；2022-2-2第一章 引 論201.2.2 語法分析語法分析（Syntax analysis） 語法分析的任務(wù)語法分析的任務(wù)：在詞法分析的基礎(chǔ)上，：在詞法分析的基礎(chǔ)上，根據(jù)語言的語

16、法規(guī)則，把單詞符號(hào)分解成各根據(jù)語言的語法規(guī)則，把單詞符號(hào)分解成各類語法單位（語法范疇），如類語法單位（語法范疇），如“短語短語”、“句子句子”、 “子句子句”、“程序段程序段”等。等。 語法規(guī)則通常用語法規(guī)則通常用上下文無關(guān)文法上下文無關(guān)文法描述。描述。2022-2-2第一章 引 論21n語法分析程序又稱識(shí)別程序。語法分析程序又稱識(shí)別程序。n功能是：讀入由詞法分析程序識(shí)別出的符功能是：讀入由詞法分析程序識(shí)別出的符號(hào)，根據(jù)給定語法規(guī)則，識(shí)別出各個(gè)語法號(hào)，根據(jù)給定語法規(guī)則，識(shí)別出各個(gè)語法結(jié)構(gòu)（檢查語法的正確性）結(jié)構(gòu)（檢查語法的正確性）,并生成另一種并生成另一種內(nèi)部表示。內(nèi)部表示。n輸入：由詞法分析

17、程序識(shí)別出并轉(zhuǎn)換的符輸入：由詞法分析程序識(shí)別出并轉(zhuǎn)換的符號(hào)號(hào)n輸出：另一種內(nèi)部表示，如語法分析樹或輸出：另一種內(nèi)部表示，如語法分析樹或其它中間表示。其它中間表示。2022-2-2第一章 引 論22語法分析語法分析n功能功能:進(jìn)行層次分析進(jìn)行層次分析,把源程序的單詞序列組把源程序的單詞序列組成語法短語成語法短語(表示成語法樹表示成語法樹).q例例: Pascal語言的賦值語句規(guī)則語言的賦值語句規(guī)則q :=“:=”q :=“+”q :=“*”q :=“(”“)”q :=q :=q :=2022-2-2第一章 引 論231.2.3 語義分析與中間代碼的產(chǎn)生語義分析與中間代碼的產(chǎn)生 這一階段通常包括兩

18、方面的工作首先這一階段通常包括兩方面的工作首先對(duì)各種語法范疇進(jìn)行靜態(tài)語義檢查，如果對(duì)各種語法范疇進(jìn)行靜態(tài)語義檢查，如果正確則進(jìn)行另一方面的工作，即進(jìn)行中間正確則進(jìn)行另一方面的工作，即進(jìn)行中間代碼的翻譯。代碼的翻譯。 通常使用通常使用屬性文法屬性文法描述語義規(guī)則描述語義規(guī)則 所謂所謂“中間代碼中間代碼”是一種含義明確，是一種含義明確，便于處理的記號(hào)系統(tǒng)。便于處理的記號(hào)系統(tǒng)。 中間代碼除四元式外，還有三元式、間中間代碼除四元式外，還有三元式、間接三元式、逆波蘭記號(hào)、樹形表示等。接三元式、逆波蘭記號(hào)、樹形表示等。2022-2-2第一章 引 論24語義分析語義分析(Semantic analysis)

19、n對(duì)語法分析樹或其他內(nèi)部中間表示進(jìn)行靜對(duì)語法分析樹或其他內(nèi)部中間表示進(jìn)行靜態(tài)語義檢查，并生成目標(biāo)代碼或中間代碼。態(tài)語義檢查，并生成目標(biāo)代碼或中間代碼。q確定類型確定類型q類型檢查類型檢查q識(shí)別含義與相應(yīng)的語義處理識(shí)別含義與相應(yīng)的語義處理q其它靜態(tài)語義檢查其它靜態(tài)語義檢查n為了優(yōu)化，往往先生成內(nèi)部中間表示代碼：為了優(yōu)化，往往先生成內(nèi)部中間表示代碼：如逆波蘭表示、三元式序列、四元式序列，如逆波蘭表示、三元式序列、四元式序列，或者抽象語法樹?；蛘叱橄笳Z法樹。2022-2-2第一章 引 論25語義分析舉例語義分析舉例n錯(cuò)在哪里？錯(cuò)在哪里？q例例1：q int arr2, c;q c = arr1 *

20、10; q例例2：q Program p(input,output);q Var rate: real;q procedure initial;q q position := initial + rate*602022-2-2第一章 引 論26代碼優(yōu)化與中間代碼生成代碼優(yōu)化與中間代碼生成中間代碼中間代碼n源程序的內(nèi)部源程序的內(nèi)部(中間中間)表示表示q如：三元式、四元式、逆波蘭表示等如：三元式、四元式、逆波蘭表示等n四元式序列四元式序列(算符算符,左操作數(shù)左操作數(shù),右操作數(shù)右操作數(shù),結(jié)果結(jié)果)例：例：Pascal語句語句 id1:= id2 + id3 * 60的四元式的四元式(三地址三地址指令

21、的四元式指令的四元式)(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)2022-2-2第一章 引 論271.2.4 優(yōu)化優(yōu)化 優(yōu)化的任務(wù)優(yōu)化的任務(wù)在于對(duì)前段產(chǎn)生的中間代在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高效（省時(shí)間和空間）的代碼。效（省時(shí)間和空間）的代碼。 優(yōu)化所依循的原則是程序的等價(jià)變換優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則。規(guī)則。 其方法有：公共子表達(dá)式的提取、循其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。環(huán)優(yōu)化、刪除無用代碼等。2022-2-2第

22、一章 引 論28代碼優(yōu)化代碼優(yōu)化n它是為改進(jìn)代碼質(zhì)量而進(jìn)行的工作它是為改進(jìn)代碼質(zhì)量而進(jìn)行的工作n對(duì)中間表示代碼進(jìn)行分析，把它變換成功對(duì)中間表示代碼進(jìn)行分析，把它變換成功能相同，但功效更高的優(yōu)化了的中間表示能相同，但功效更高的優(yōu)化了的中間表示代碼。代碼。n分為：與機(jī)器有關(guān)的優(yōu)化和與機(jī)器無關(guān)的分為：與機(jī)器有關(guān)的優(yōu)化和與機(jī)器無關(guān)的優(yōu)化。優(yōu)化。2022-2-2第一章 引 論29代碼優(yōu)化舉例代碼優(yōu)化舉例id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1)變換成變換成 （1） ( *id360.

23、0t1) ( 2）（）（ + id2 t1id1)2022-2-2第一章 引 論301.2.5 目標(biāo)代碼生成目標(biāo)代碼生成 目標(biāo)代碼生成階段的任務(wù)目標(biāo)代碼生成階段的任務(wù)：把中間代碼：把中間代碼（或經(jīng)優(yōu)化處理后）變換成特定機(jī)器上的低級(jí)（或經(jīng)優(yōu)化處理后）變換成特定機(jī)器上的低級(jí)語言代碼。它有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令語言代碼。它有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。含義。2022-2-2第一章 引 論31目標(biāo)代碼生成目標(biāo)代碼生成n總是與機(jī)器相關(guān)?？偸桥c機(jī)器相關(guān)。n可在語義分析時(shí)生成。如果語義分析的結(jié)可在語義分析時(shí)生成。如果語義分析的結(jié)果是中間表示代碼，則目標(biāo)代碼生成部分果是中間表示代碼，則目標(biāo)代碼生成部分

24、必須將中間代碼變換成等價(jià)的目標(biāo)語言代必須將中間代碼變換成等價(jià)的目標(biāo)語言代碼。碼。2022-2-2第一章 引 論32 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)表表格格管管理理詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼產(chǎn)生語義分析與中間代碼產(chǎn)生優(yōu)化器優(yōu)化器目標(biāo)代碼生成器目標(biāo)代碼生成器源程序源程序單詞符號(hào)單詞符號(hào)語法單位語法單位中間代碼中間代碼中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼出出錯(cuò)錯(cuò)處處理理2022-2-2第一章 引 論33 我們可以按照上頁的總框圖設(shè)計(jì)編譯程序我們可以按照上頁的總框圖設(shè)計(jì)編譯程序。從圖中我們可以看到除編譯的五個(gè)基本階段。從圖中我們可以看到除編譯的五個(gè)基本階段外，一個(gè)完整

25、的編譯程序還應(yīng)包括外，一個(gè)完整的編譯程序還應(yīng)包括“表格管理表格管理”和和“出錯(cuò)處理出錯(cuò)處理”兩部分。兩部分。 1.3.2 表格與表格管理表格與表格管理 在編譯程序使用的表格中最重要的是在編譯程序使用的表格中最重要的是符號(hào)符號(hào)表表它用來登記源程序中出現(xiàn)的每一個(gè)名字以及它用來登記源程序中出現(xiàn)的每一個(gè)名字以及名子的各種屬性。如一個(gè)名字是常量名、變量名子的各種屬性。如一個(gè)名字是常量名、變量名，還是過程名等；如果是變量名它的類型又名，還是過程名等；如果是變量名它的類型又是什么、所占內(nèi)存是多大、地址是什么等。是什么、所占內(nèi)存是多大、地址是什么等。2022-2-2第一章 引 論34符號(hào)表管理符號(hào)表管理n記錄

26、源程序中使用的名字記錄源程序中使用的名字(標(biāo)識(shí)符標(biāo)識(shí)符)n收集每個(gè)名字的各種屬性信息收集每個(gè)名字的各種屬性信息q類型、作用域、分配存儲(chǔ)信息類型、作用域、分配存儲(chǔ)信息信息信息名字名字2022-2-2第一章 引 論351.3.3 出錯(cuò)處理出錯(cuò)處理 一個(gè)編譯程序不僅能對(duì)書寫正確的程一個(gè)編譯程序不僅能對(duì)書寫正確的程序進(jìn)行編譯，而且應(yīng)能對(duì)處現(xiàn)在源程序中序進(jìn)行編譯，而且應(yīng)能對(duì)處現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)，編譯的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給用戶。這部分的工作是由專門的一組程序用戶。這部分的工作是由專門的一組程序（叫

27、做處錯(cuò)處理程序）完程的。（叫做處錯(cuò)處理程序）完程的。2022-2-2第一章 引 論36出錯(cuò)處理出錯(cuò)處理n檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作譯工作n詞法錯(cuò)誤和語法錯(cuò)誤可由編譯程序在編譯詞法錯(cuò)誤和語法錯(cuò)誤可由編譯程序在編譯時(shí)刻查出。時(shí)刻查出。n語義錯(cuò)誤常采用下列方式查出：語義錯(cuò)誤常采用下列方式查出：q靜態(tài)模擬檢查：靜態(tài)模擬檢查：q動(dòng)態(tài)調(diào)試檢查：動(dòng)態(tài)調(diào)試檢查：2022-2-2第一章 引 論371.3.4 編譯前端與后端編譯前端與后端 前端前端主要由與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的主要由與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成。通常包括詞法分析、語法分析、那些部

28、分組成。通常包括詞法分析、語法分析、語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作，語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作，也可以包括在前端。也可以包括在前端。 后端后端包括編譯程序中與目標(biāo)代碼有關(guān)的部分，包括編譯程序中與目標(biāo)代碼有關(guān)的部分，如與目標(biāo)機(jī)有關(guān)的有關(guān)的優(yōu)化，和目標(biāo)代碼的生如與目標(biāo)機(jī)有關(guān)的有關(guān)的優(yōu)化，和目標(biāo)代碼的生成等。成等。2022-2-2第一章 引 論38編譯程序結(jié)構(gòu)編譯程序結(jié)構(gòu)(Components)n詞法分析程序詞法分析程序n語法分析程序語法分析程序n語義分析程序語義分析程序n中間代碼生成程序中間代碼生成程序n代碼優(yōu)化程序代碼優(yōu)化程序n目標(biāo)代碼生成程序目標(biāo)代碼生成程序n符號(hào)表管理

29、程序符號(hào)表管理程序n出錯(cuò)處理程序出錯(cuò)處理程序2022-2-2第一章 引 論39 編譯程序與外文翻譯的類比編譯程序與外文翻譯的類比 ：2022-2-2第一章 引 論401.4 編譯程序與程序設(shè)計(jì)環(huán)境編譯程序與程序設(shè)計(jì)環(huán)境 編譯程序無疑是實(shí)現(xiàn)高級(jí)語言的一個(gè)最編譯程序無疑是實(shí)現(xiàn)高級(jí)語言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開發(fā)通常還需要其它一些工具：如編輯程序、計(jì)開發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境程序設(shè)計(jì)環(huán)境

30、。 在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等心的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。和技術(shù)。2022-2-2第一章 引 論41編譯程序的實(shí)現(xiàn)機(jī)制編譯程序的實(shí)現(xiàn)機(jī)制n 2022-2-2第一章 引 論42編譯過程實(shí)例編譯過程實(shí)例 例：例：Pascal程序片段程序片段 : 詞法分析詞法分析：識(shí)別單詞并分類識(shí)別單詞并分類var a,b:integer;var a,b

31、:integer; . . . . . . b:=a+2 b:=a+2* *5;5;v 編譯過程如下：編譯過程如下： 關(guān)鍵字關(guān)鍵字 (k) (k) - varvar，integerinteger ; 標(biāo)識(shí)符標(biāo)識(shí)符 (i)(i) - a a，b b ； 常常 數(shù)數(shù) (c) (c) - 2 2，5 5 ； 界界 符符 (p) (p) - , ; : := +, ; : := + 單詞單詞類碼類碼2022-2-2第一章 引 論43賦值語句 b:=a+2+5b:=a+2+5 的語法樹n 例：例： b := a + 2 * 5 的分析過程如下所示：的分析過程如下所示： n （ 生成的結(jié)果是一棵生成的結(jié)果

32、是一棵 語法樹語法樹 ) :=:= b b + + * * a25 2. 語法分析：語法分析： 組詞成句及語法錯(cuò)誤檢查組詞成句及語法錯(cuò)誤檢查算術(shù)表達(dá)式的算術(shù)表達(dá)式的層次結(jié)構(gòu)層次結(jié)構(gòu)2022-2-2第一章 引 論443語義分析：分析各種語法成分的語義特征；語義分析：分析各種語法成分的語義特征；var a,b:integer;var a,b:integer; . . . . . . b:=a+2 b:=a+2* *5;5;n構(gòu)建標(biāo)識(shí)符的語義辭典構(gòu)建標(biāo)識(shí)符的語義辭典-符號(hào)表：符號(hào)表：n構(gòu)造構(gòu)造語句語句的語義樹的語義樹-中間語言；中間語言； b 的值的值 a 的值的值 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) v v i i b

33、 b v v i i a a 地址地址種類種類 類型類型 名字名字符號(hào)表符號(hào)表 := :=b b+ +a a* *2 25 5 ( * 2 5 t1 ) ( + a t1 t2 ) ( := t2 _ b )或或四元式序列四元式序列(算符算符,左操作數(shù)左操作數(shù),右操作數(shù)右操作數(shù),結(jié)果結(jié)果)2022-2-2第一章 引 論454優(yōu)化優(yōu)化 ：提高目標(biāo)程序質(zhì)量的工作：提高目標(biāo)程序質(zhì)量的工作 ； := :=b b+ +a a* *2 25 5 ( * 2 5 t1 ) ( + a t1 t2 ) ( := t2 _ b ) ( + a 10 t2 ) ( := t2 _ b ) := :=b b+ +a

34、 a10102022-2-2第一章 引 論465目標(biāo)代碼生成：目標(biāo)代碼生成：上例：可生成目標(biāo)代碼：上例：可生成目標(biāo)代碼： ( + a 10 t2 ) ( := t2 _ b ) LD R,10 LD R,10 ADD R, a ADD R, a ST R, b ST R, bR R 為寄存器為寄存器三條指令分別為：三條指令分別為：取取、加加 和和 存存 。2022-2-2第一章 引 論471.5 編譯程序的生成編譯程序的生成 以前構(gòu)造編譯程序大多是用機(jī)器語言以前構(gòu)造編譯程序大多是用機(jī)器語言或匯編語言作工具的。為了充分發(fā)揮各種或匯編語言作工具的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然使用這種工的具體要求，現(xiàn)在許多人仍然使用這種工具來構(gòu)造編譯程序（或編譯程序的核心部具來構(gòu)造編譯程序（或編譯程序的核心部分）分） 但是越來越多的人已經(jīng)使用高級(jí)語言但是越來越多的人已經(jīng)使用高級(jí)語言作工具來編譯程序。因?yàn)檫@樣可以大大節(jié)作工具來編譯程序。因?yàn)檫@樣可以大大節(jié)省程序設(shè)計(jì)的時(shí)間，熱切構(gòu)造出來的編譯省程序設(shè)計(jì)的時(shí)間，熱切構(gòu)造出來的編譯程