《編譯原理簡明教程》普通高等教育“十二五”規劃計算機教材---太原理工大學---計算機科學與技術學院---馮秀芳、崔冬華、段富等第一章引言第二章形式語言理論基礎第三章自動機理論基礎第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優化第九章目標代碼的生成第十章符號表第十一章目標程序運行時的存儲組織與分配第十二章出錯處理第十三章編譯程序自動生成工具簡介第十四章面向對象語言的編譯第十五章并行編譯技術目錄第一章引言

學習目標了解和掌握高級程序設計語言與編譯程序的關系了解和掌握編譯程序的功能了解和掌握編譯程序的體系結構了解和掌握編譯程序的工作過程了解和掌握編譯程序的組織方式了解和掌握編譯程序的構造方法

“編譯原理”，“編譯技術”是計算機專業一門重要的專業課。目的是系統地向學生講授編譯程序的基本結構。闡述編譯原理的一般理論和常用的有效方法與技術。學習本課后，使學生掌握編譯理論和方法方面的基本知識，具有設計、實現、分析和維護編譯程序等方面的初步能力。主要內容：形式語言與自動機、詞法分析、語法、語義、中間語言代碼生成、優化、存儲組織與分配、程序的查錯與處理等。1.1編譯程序、匯編程序、解釋程序1.2編譯過程概述1.3編譯程序的結構框圖1.4編譯程序的開發目錄1.1程序的翻譯及運行

計算機系統：硬件軟件：系統軟件：OS、編譯系統、診斷系統應用軟件等程序設計語言：機器匯編高級翻譯程序：指能把A語言程序翻譯成與之等價的B語言程序的程序。

A語言----源程序B語言----目標語言1.1.1什么是編譯程序編譯程序：A——高級語言B——機器語言1.1.2

匯編程序

A語言——匯編語言（符號表示）

B語言——機器語言

1.1.3

解釋程序不產生目標程序，逐句翻譯。優點：l提供一種直接的交互調試能力，在執行用戶程序時可以修改用戶程序。l

對新的類型可動態地修改，如符號的意義。

l

提高良好的診斷信息l

不依賴于目標機，移植性較好。缺點：開銷大、速度慢如APL與編譯程序相比1：100BASIC1：10事實上，純粹的解釋程序并不多見，通常做某種程序的結合。

1.2編譯過程概述

綜合分析翻譯外文資料閱讀原文、識別單詞分析句子的語法結構根據句子含義初步分析修辭加工寫出譯文編譯源程序掃描源程序、詞法分析語法分析語義分析優化生成目標代碼編譯程序一般分五個部分一、詞法分析

輸入源程序，對源程序構成的字符串進行掃描和分析，識別出一個個的單詞，如保留字、標識符、常數、特殊符號等。如保留字(if、for、while等)、標識符、常數、特殊符號(標點符號、左右括號、運算符等)。例如，對于C語言的循環語句：for(i=1;i<=100;i++)sum=sum+1;詞法分析：遵循詞法規則，描述詞法規則正規式和有限自動機

二、語法分析

根據語言語法規則，把詞法分析后的單詞合成各類語法單位（語法范疇），如“短語”，“句子”，“程序段”，“程序”。

例：Z=X+2*Y；賦值語句遵循語法規則，采用上下文無關文法描述。三、語義分析及中間代碼的生成

根據語法結構，分析其含義，并進行初步翻譯（生成中間代碼），或直接生成目標代碼。例，對常用的一些語言來說，語義分析生成語法成分的含義和用途，以及應進行的運算和操作，而且要進行語義檢查，如在說明語句中是否有矛盾的類型說明；在表達式中，對某些運算符而言，是否有類型不匹配的運算對象；在過程調用中，實參和形參是否在個數、次序、種屬等方面按相應語言的規定進行對應等等。

“中間代碼”是一種含義明確、便于處理的記號系統。如：三元式、四元式、逆波蘭式。例：四元式（運算符，第一運算量，第二運算量，結果）

z=(x

+3)*y/w;（+，x，3，T1）（*，T1,y,T2

）

(/,T2,w，z)四、代碼優化

優化的任務在于對前階段產生的中間代碼進行加工變換，以期在最后階段產生出更為高效(節省時間和空間)的目標代碼。優化的主要方面有：公共子表達式的提取、循環優化、刪除無用代碼等。有時，為了便于“并行運算”，還可以對代碼進行并行優化處理。優化所依循的原則是程序的等價變換規則。優化涉及的范圍很廣。與機器有關的從與具體計算機的關系分與機器無關的局部優化從與源程序的關系分全局優化五、目標代碼生成

把中間代碼變成特定機器上的機器代碼。這部分涉及到硬件,如各種數據類型變量的存儲空間分配，寄存器的調度等。例：盡量使用執行速度快的指令，充分利用計算機的寄存器，以節省訪問內存所用時間等。1.3編譯程序的結構框圖信息表管理源程序目標代碼生成目標程序出錯處理詞法分析優化語義分析語法分析1.4編譯程序的開發

編譯程序是一個非常復雜的軟件系統，雖然編譯理論和技術不斷發展，開發周期縮短，但研制仍需大量時間。追求目標過程自動化。

1.4.1開發步驟

1.認真分析，合理分工

2.算法設計，方案確定

3.語言選擇，編制程序

4.調試程序，確保質量

5.資料整理，文本形成1.4.2開發技術

一、系統程序設計語言

70年代以前，用機器語言、匯編語言，手工編寫工作量大、可靠性差、難以維護。

80年代以后，高級語言如PASCAL、ADA、C，工作量大大減少，縮短開發周期。系統程序程序設計語言：

編寫編譯程序或其它系統軟件的高級語言。二、開發技術1.

自編譯：用某一高級語言編寫其自己的編譯程序。2.交叉編譯：A機器上的編譯程序能產生B機器上的目標代碼。3.自展：首先確定一個非常簡單的核心語言L0，用機器的匯編語言寫其編譯程序T0，擴充L0L1，用L0寫L1的T1,L1L2……滾雪球一樣，直到所需編程序。

4.移植：將