第1課 第1章_編譯原理概述.ppt

1、編譯原理,湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,2,什么是編譯,把一種語言等價翻譯成另外一種語言,源語言 Source language,目標(biāo)語言 Object language,編譯就是翻譯,編譯,編譯程序 compiler,面向人的語言 Human-oriented language,面向機器的語言 Computer-oriented language,3,4,編譯的過程,詞法分析 語法分析 語義分析 中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成,5,詞法分析,從左到右以字符為單位掃描源程序，從而識別出每個單詞符號 單詞是指邏輯上機密相連的一組字符，具有集體的含義，比如標(biāo)識符。,6,詞法分析,單詞種類

2、： 一類是特殊的單詞，如保留字、運算符、分界符等，這些都是源語言所提供的； 另一類是普通單詞，如用戶在源程序中定義的標(biāo)識符、常數(shù)等。,7,詞法分析,例如：程序段 int x,a,b; x=a+b*50; 詞法分析后的結(jié)果為 (1)保留字 int (2)標(biāo)識符 x (3)界限符 , (4)標(biāo)識符 a (5)界限符 , (6)標(biāo)識符 b (7)界限符 ； (8)標(biāo)識符 x (9)運算符 = (10)標(biāo)識符 a (11)運算符 + (12)標(biāo)識符 b (13)運算符 * (14)整常數(shù) 50 (15)界限符 ;,8,語法分析,在詞法分析的基礎(chǔ)上，按照源語言的規(guī)則將單詞序列組合成語法短語 依據(jù)是語言的

3、語法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則，通常采用遞歸結(jié)構(gòu) 【如何描述語法規(guī)則呢？一般形式化，使用如語法樹等工具；根據(jù)應(yīng)用不同，可以有不同工具】 詞法分析與語法分析：分析源程序的結(jié)構(gòu)；詞法分析采用線性掃描，但是線性掃描不適合遞歸語法,9,語法分析,語法分析有兩種方法： 推導(dǎo)(Derive)和歸約(Reduce) 語法分析對說明語句填寫符號表，一般語句構(gòu)造語法樹 例如：賦值語句a=b+c*10經(jīng)語法分析生成語法樹,10,語義分析,進(jìn)行語義審查以判斷是否有語義錯誤。 例如：上下文相關(guān)性，類型匹配，類型轉(zhuǎn)換,11,中間代碼生成,源程序的內(nèi)部(中間)表示結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)， 介于高級語言與低級語言之間

4、, 與目標(biāo)機無關(guān)，便于優(yōu)化、移植并容易生成目標(biāo)代碼。 通常的中間代碼有三元式、四元式、樹結(jié)構(gòu)或適合相應(yīng)語言的中間代碼。,12,代碼優(yōu)化,對中間代碼進(jìn)行變換或進(jìn)行改造，目的使生成目標(biāo)代碼更為高效，即省時間/省空間 如刪除公共子表達(dá)式、合并已知量、刪除無用賦值、循環(huán)優(yōu)化、算符規(guī)約等等,13,目標(biāo)代碼生成,把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。 是編譯的最后階段，與硬件系統(tǒng)結(jié)構(gòu)、指令含義等有關(guān),14,出 錯 處 理 程 序,表 格 管 理 程 序,編譯程序的結(jié)構(gòu),15,表格管理,什么是表,記錄源程序中使用的名字 收集每個名字的各種屬性信息 類型、作用域、分配存儲

5、信息,符號表,Symbol table,16,出錯處理（error handling）,檢查錯誤、報告出錯信息、排錯、恢復(fù)編譯工作 檢查詞法、語法和語義中的錯誤（靜態(tài)）。 編譯程序的處理能力，如存儲空間越界（動態(tài)） 報告出錯信息和位置 處理和恢復(fù),17,編譯階段的組合,編譯的前端（front end）：主要依賴源語言、與目標(biāo)機器無關(guān)；包括詞法分析、語法分析、語義分析、中間代碼生成以及代碼優(yōu)化（部分） 編譯的后端（back end）：依賴目標(biāo)機、不依賴于源語言，只與中間代碼有關(guān)的那些階段,18,源代碼,中間代碼,目標(biāo)代碼,前端,后端,僅依賴于源語言,僅依賴于目標(biāo)機器,19,源程序,第一遍輸出文件

6、,遍,第二遍輸入文件,遍,第(N-1)遍輸出文件,第N遍輸入文件,遍,目標(biāo)代碼,遍（趟）對源程序或其等價的中間語言程序從頭道尾掃視并完成規(guī)定任務(wù)的過程,20,Compiler與interpreter,解釋程序：不生成可執(zhí)行文件，不能獨立執(zhí)行；接受某個語言的程序并立即運行的過程。一個個地獲取、分析并執(zhí)行源程序的語句。 編譯程序：生成可執(zhí)行文件，可以獨立執(zhí)行；編譯和運行是兩個獨立分開的階段。 著名的解釋程序Basic、Lisp、Unix命令、SQL、JAVA,21,處理源程序的軟件工具,語言結(jié)構(gòu)化編輯器 語言程序調(diào)試工具 程序格式化工具 語言程序測試工具 高級語言之間的轉(zhuǎn)換工具,22,程序設(shè)計語言

7、范型,1.強制（命令）式語言過程語言 C、Pascal：面向動作，一個計算過程看作一系列動作 2. 函數(shù)式語言 ML、Lisp：注重程序表示的功能 .基于規(guī)則（邏輯）的語言 Prolog：檢查一定的使能條件，滿足時執(zhí)行動作 4. 面向?qū)ο笳Z言 Ada、C+、Java,23,編譯技術(shù)在計算機學(xué)科中的地位,編譯技術(shù)的復(fù)雜性 直接使用離散數(shù)學(xué)關(guān)于集合論、圖論、形式語言自動機等理論知識，編寫編譯程序時必然要使用到多種算法和數(shù)據(jù)結(jié)構(gòu) 編譯技術(shù)與計算機其他學(xué)科的交叉性 系統(tǒng)結(jié)構(gòu)、人工智能、離散數(shù)學(xué)、高級語言、數(shù)據(jù)結(jié)構(gòu)、匯編語言等課程 編譯技術(shù)的成熟性 編譯技術(shù)是計算機科學(xué)中發(fā)展最迅速、最成熟的分枝之一,24,學(xué)習(xí)編譯原理的意義,編譯器可能有一萬行，也可能有