slide01編譯原理課程概述

第一講

課程概述編譯原理PrinciplesandPracticeof

CompilerConstruction

有關信息

編譯程序（系統(tǒng)）概述課程概述

教學內容預覽

課程信息

課程的地位

教師信息

教學目的要求有關信息

助教信息

主要參考教材

實驗計劃

參考閱讀書目

答疑與交流

考核計劃

書面作業(yè)

相關課程

課名

編譯原理

類別必修

時間

15-09-16

至15-12-30

每周三下午3:20-4:55

教室

六教6A018

班級

計2013年級

時數(shù)

32-2課程信息

計算機專業(yè)主干課

編譯程序（系統(tǒng)）是計算機系統(tǒng)的核心支撐軟件

貫穿程序語言、運行時系統(tǒng)、體系結構

聯(lián)系計算機科學和計算機系統(tǒng)的典范

專業(yè)工作者必備的基本技能

編譯原理的知識影響到專業(yè)人員的素質大量專業(yè)工作與編譯技術相關高級語言實現(xiàn)，體系結構設計與優(yōu)化，硬件綜合，二進制翻譯，智能編輯器，面向領域的語言以及業(yè)務邏輯語言的實現(xiàn)，軟件靜態(tài)分析，逆向工程，調試器，模型驅動的開發(fā)，程序驗證，…課程的地位

掌握編譯程序/系統(tǒng)設計的基本原理

掌握“常見”語言機制的實現(xiàn)技術

經(jīng)歷開發(fā)一個小型編譯程序的主要階段

自學并使用自動構造工具

加深對計算機系統(tǒng)的理解會將所學知識靈活應用教學目的要求原理+技術+工具

先修課程

《高級語言程序設計》（Java,C/C++）

《數(shù)據(jù)結構》

《形式語言與自動機》

其它相關課程

《計算機系統(tǒng)結構》，《操作系統(tǒng)》，

《匯編語言》，《計算機原理》，《計算機系統(tǒng)聯(lián)合實驗》，《專題實踐》相關課程教師信息

姓名王生原

單位計算機系軟件技術研究所

電話62794240（O/p>

辦公室東主樓

10區(qū)209

電子信箱

wwssyy@

研究領域

程序設計語言理論與實現(xiàn)

并發(fā)程序設計(編程模型與編程方法)

程序驗證（可信編譯器）

姓名蔣挺宇（主體實驗）

單位計算機系軟件研究所

電/p>

答疑時間不安排當面答疑

答疑地點東主樓10

區(qū)202

網(wǎng)上答疑清華網(wǎng)絡學堂

電子信箱598913634@qq.c助教信息

姓名王耀（主體實驗，原理）

單位計算機系軟件研究所

電/p>

答疑時間周四晚7:30-9:30

答疑地點東主樓10

區(qū)202

網(wǎng)上答疑清華網(wǎng)絡學堂

電子信箱wy568105790@126.com助教信息

姓名劉昊（主體實驗，原理）

單位計算機系軟件研究所

電/p>

答疑時間周一晚7:30-9:30

答疑地點東主樓10

區(qū)202

網(wǎng)上答疑清華網(wǎng)絡學堂

電子信箱

LH50404797@126.com助教信息

姓名尚書（輔助實驗，原理）

單位計算機系軟件研究所

電/p>

答疑時間周二晚7:30-9:30

答疑地點東主樓10

區(qū)202

網(wǎng)上答疑清華網(wǎng)絡學堂

電子信箱

u201017930@163.com

助教信息

姓名孫金龍（協(xié)助收閱書面作業(yè)）

單位計算機系軟件與理論研究所

電話

62794240

電子信箱gordon@助教信息Compilers：Principles,Techniques,andTools

AlfredV.Aho,RaviSethi,JeffreyD.Ullman,AddisonWesley,

2007

（龍書）主要參考書目

CraftingaCompiler

CharlesN.Fischer,RonaldK.Cytron,RichardJ.LeBlanc,Jr.,2010.

清華大學出版社影印，2010

本課程講稿

課后從網(wǎng)絡學堂下載

ModernCompilerImplementationinJava

ModernCompilerImplementationinCAndrewW.Appel，人民郵電出版社影印，2005（虎書）

AdvancedCompilerDesignandImplementation

StevenS.Muchnick,1997.機械工業(yè)出版社影印，2003（鯨書）

ElementsofCompilerDesign

AlexanderMeduna，Taylor&FrancisGroup，2008清華大學出版中譯本，2009EngineeringaCompiler

KeithCooper,LindaTorczon,MorganKaufmann,2003

內地陳火旺（國防科大版）陳意云（中國科技大學版）

王生原等（人民郵電版）王生原等（清華大學第三版）參考閱讀書目書面作業(yè)

原理部分書面作業(yè)

隋堂布置登記完成情況

部分批閱實驗計劃

實驗項目

主體實驗實現(xiàn)一個小型面向對象語言

（給定架構下擴展或改造）

分階段進行：

階段1（必做）第3~6周（16天）階段2（必做）第8~10周（16天）階段3（必做）第11~13周（18天）階段4（選做）第14~16周（14天）實驗計劃

實驗項目

輔助實驗手工實現(xiàn)遞歸下降分析程序

（給定架構下擴展或改造）

必做第6~10周（8天）實驗計劃

實驗項目

拓展實驗

（參考建議或自選）

選做第18周提交并答辯

成績分布

（100%+5%）

原理部分書面作業(yè)+出勤（5%）

輔助實驗平時成績

（5%）

主體實驗平時成績

（24%~32%）

階段一、階段二、階段三各8%選作階段四：8%期末考試原理部分

（47%~55%）

實驗必做部分的期末筆試

（11%）

拓展實驗（5%）

考核計劃

通過網(wǎng)絡

清華網(wǎng)絡學堂（課程討論區(qū)）

問題探討電子郵件wwssyy@

面對面

時間預約

第2–16

周上班時間（節(jié)假日除外）

地點

東主樓10

區(qū)209室答疑與交流編譯程序（系統(tǒng)）概述

什么是編譯程序

編譯程序的邏輯結構

編譯程序的伙伴程序

編譯程序的組織

編譯程序與

T型圖什么是編譯程序

從基本功能來看，編譯程序（Compiler）是一種翻譯程序（Translator）

將語言A的程序翻譯為語言B的程序稱語言A為源語言（SourceLanguage）

稱語言B為目標語言（TargetLanguage）sourceprogramtargetprogramcompilerfeedbackmessages什么是編譯程序

編譯程序是較為復雜的翻譯程序

需要對源程序進行分析（Analysis）

識別源程序的語法結構信息，理解源程序的語義信息，

反饋相應的出錯信息

根據(jù)分析結果及目標信息進行綜合（Synthesis）

生成語義上等價于源程序的目標程序

較為簡單的翻譯程序如：預處理程序（Preprocessor）匯編程序（Assembler）什么是編譯程序

編譯程序通常是從較高級語言的程序翻譯至較低級語言的程序，如C代碼匯編代碼aCcompilerC++代碼匯編代碼aC++compilerC++代碼C代碼anotherC++compilerJava代碼Bytecode代碼aJavacompiler什么是編譯程序

傳統(tǒng)的編譯程序

源語言通常為高級語言（High-LevelProgrammingLanguages）

Fortran,Algol,C,Pascal,Ada,C++,Java,Lisp,Prolog,Python…

目標語言通常為機器級語言（Machine-LevelLanguages

）或較低級的虛擬機語言

匯編語言（AssemblyLanguages）

機器語言（MachineLanguages

）

Bytecode（Java虛擬機語言）什么是編譯程序

編程語言的主要范型（Paradigms）

命令式語言（ImperativeLanguages）

Fortran,Algol,Cobol,C,C++,Pascal,Basic,Java,C#,…

面向對象語言（Object-OrientedLanguages）

Smalltalk,Simula67,Java,C++,C#,…

陳述式語言（DeclarativeLanguages）函數(shù)式（Functional）:Lisp,Scheme,Haskell,ML,Caml,…

邏輯型（Logic）:Prolog,…

并發(fā)語言（ConcurrentLanguages）并發(fā)

Pascal,Ada,Java,Linda,HPF,OpenMP,…

其他

同步語言(SynchronousLanguages）：Signal,Lustre,…

腳本語言(ScriptingLanguages）：Perl,PHP,…什么是編譯程序

編譯基礎設施（CompilerInfrastructure）共享的編譯程序研究/開發(fā)平臺

SUIF

(Stanford)

Zephyr

(VirginiaandPrinceton)

IMPACT,LLVM

(UIUC)

GCC

（GNUCompilerCollection

）

Open64（SGI,

中科院計算所,

Intel,

HP,

Delaware,清華,…）

……

多源語言多目標機體系結構

如

GCC有C,C++,ObjectiveC,Fortran,Ada,andJava，…

等諸多前端，以及支持30多類體系結構、上百種平臺的后端

多級中間表示

如

Open64

的中間表示語言

WHIRL分5個級別編譯程序的邏輯結構

編譯程序邏輯結構上至少包含兩大階段

分析（Analysis）階段

理解源程序，挖掘源程序的語義綜合（Synthesis）階段

生成與源程序語義上等價的目標程序編譯程序的邏輯結構

編譯程序的前端、中端和后端

前端（FrontEnd）

實現(xiàn)主要的分析任務

通常以第一次生成中間代碼為標志后端（BackEnd）

實現(xiàn)主要的綜合任務（目標代碼生成和優(yōu)化）

通常以從最后一級中間代碼生成目標代碼為標志中端（MiddleEnd）實現(xiàn)各級中間代碼上的操作（中間代碼生成與優(yōu)化）編譯程序的邏輯結構

典型編譯程序的邏輯過程詞法分析語法分析語義分析+中間代碼生成中間代碼生成+中間代碼優(yōu)化目標代碼優(yōu)化目標代碼生成字符流形式的源程序單詞流形式的源程序源程序的語法分析樹目標代碼優(yōu)化的目標代碼后端前端中間代碼（1）┆中間代碼（n）分析綜合中端

詞法分析

掃描源程序字符流，識別出有詞法意義的單詞，返回單詞的類別和單詞的值，或詞法錯誤信息編譯程序的邏輯結構

單詞類別

單詞值

保留字

class

標識符

Main

分隔符{

保留字

static

保留字

void

標識符

main

分隔符(

分隔符)

分隔符{

保留字

Print

分隔符(

字符串長量

“helloworld”

分隔符)

分隔符；分隔符}

分隔符}

語法分析編譯程序的邏輯結構

語義分析

對語法分析后的程序進行語義分析,不符合語義規(guī)則

時給出語義錯誤信息編譯程序的邏輯結構

符號表

收集每個名字的各種屬性用于語義分析及后續(xù)各階段編譯程序的邏輯結構

出錯處理

檢查錯誤

報告出錯信息（errorreporting）

排錯

恢復編譯工作（errorrecovery）

編譯程序的邏輯結構

中間代碼生成

抽象語法樹

AST

編譯程序的邏輯結構

中間代碼生成

三地址碼TAC

編譯程序的邏輯結構

目標代碼生成

生成目標機代碼編譯程序的邏輯結構MIPS

匯編碼編譯程序的邏輯結構

小結:典型編譯程序的主要邏輯模塊詞法分析模塊語法分析模塊語義分析模塊中間代碼優(yōu)化模塊目標代碼優(yōu)化模塊目標代碼生成模塊符號表管理模塊中間代碼生成模塊錯誤處理模塊編譯程序的組織

編譯程序的遍（Passes/Phases）

對一種代碼形式從頭到尾掃描一遍將一個代碼空間變換到另一個代碼空間

代碼空間=代碼+符號表+其他有用信息

編譯程序的組織取決于各遍的組織

單遍編譯程序，多遍編譯程序多個遍之間有邏輯上的先后關系多個遍的實現(xiàn)可采用順序結構或并發(fā)結構（后者不常用）編譯程序的組織

例：一個以語法、語義分析程序為中心的單遍編譯程序組織sourceprogramtargetprogram語法、語義分析程序詞法分析程序代碼生成程序編譯程序的伙伴程序

解釋程序（Interpreter）

不產(chǎn)生目標程序文件不區(qū)別翻譯階段和執(zhí)行階段翻譯源程序的每條語句后直接執(zhí)行

程序執(zhí)行期間一直有解釋程序守候常用于實現(xiàn)虛擬機

比較編譯程序和解釋程序源程序編譯程序目標程序輸入目標程序輸出解釋程序輸出輸入源程序

預處理程序（Preprocessor）

支持宏定義（Macrodefinition）

如C源程序中#define行的處理支持文件包含（Fileinclusion）

如C源程序中#include行的處理支持其他更復雜的源程序擴展信息

預處理程序和編譯程序的關系預處理程序不含擴展信息的源語言程序編譯程序目標程序含擴展信息的源語言程序編譯程序的伙伴程序

匯編程序（Assembler）翻譯匯編語言程序至可重定位的（Relocatable）機器語言程序

裝入和連接程序（LoaderandLink-editor）

裝入程序對可重定位機器語言程序進行修改

將相對地址變換為機器絕對地址連接程序合并多個可重定位機器語言程序文件到同一個程序裝入和連接程序產(chǎn)生最終可執(zhí)行的機器語言程序編譯程序的伙伴程序

編譯程序、匯編程序及裝入和連接程序之間的典型關系編譯程序可重定位的機器語言程序裝入和連接程序源程序匯編程序匯編語言程序可執(zhí)行的機器語言程序編譯程序的伙伴程序運行時庫和分開編譯的例程

調試程序（Debugger）

反饋目標程序運行時信息將目標程序運行時信息與源程序關聯(lián)斷點管理、單步跟蹤、讀/寫目標機狀態(tài)等功能

調試程序和編譯程序的關系編譯程序調試信息調試程序運行時信息源程序……裝入和連接程序可執(zhí)行程序編譯程序的伙伴程序編譯程序與T

型圖

T-型圖(表示一個編譯程序)STIS

：編譯程序所實現(xiàn)的源語言T

：目標語言I:編譯程序的實現(xiàn)語言

例:Decaf/Mind

項目中編譯程序T-型圖Decaf語言（變種）MIPS匯編語言（SPIM虛擬機）Java編譯程序與T

型圖

T-型圖的疊加B語言L語言A語言A語言M語言N語言N語言L語言B語言編譯程序與T

型圖

(M機器上運行的)本地編譯器M機器語言L

語言M機器語言

(M機器上運行的)交叉編譯器M機器語言L

語言N機器語言編譯程序與T

型圖

用已有的語言L1實現(xiàn)新的語言L2L2語言L1語言M機器語言步驟：(1）用L1語言編寫L2語言到M機器語言的編譯程序(2）將該L2

語言編譯程序用L1

語言編譯程序進行編譯M機器語言M機器語言L2語言M機器語言L1語言M機器語言編譯程序與T

型圖

編譯程序的移植將機器A

上的語言L

移植到機器B，步驟：(1）用L

語言編寫L

語言到B機器語言的編譯程序X;(2）用L編譯程序對X進行編譯，產(chǎn)生一個能在機器A上運行的產(chǎn)生B

機器代碼的編譯程序Y（交叉編譯程序）；(3）再用Y

對X進行編譯，得到可以在機器B上運行的L

語言編譯程序B機器語言L語言L語言B機器語言L語言L語言L語言A機器語言A機器語言A機器語言L語言B機器語言B機器語言L語言B機器語言編譯程序與T

型圖教學形式課內學習和課外學習內容互補教學內容預覽原理+技術+工具課內課外教學內容課堂教學內容及課時計劃基本概念邏輯結構組織方式伙伴程序生成環(huán)境

2學時

教學內容預覽

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容實驗項目簡介3學時（穿插介紹）教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介間

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容詞法分析基礎

1學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容自頂向下語法分析

3

學時自底向上語法分析

5學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容基于屬性文法和翻譯模式進行語義計算的基本原理及實現(xiàn)技術

3學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容強調作用域及其組織方式

1學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容以類型檢查程序設計為重點

1學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容以常用語言機制的實現(xiàn)技術為主線

3學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教學內容存儲布局,存儲分配策略,活動記錄,過程實現(xiàn),面向對象程序存儲組織,……

2學時教學內容預覽課堂教學內容及課時計劃

編譯程序/系統(tǒng)概述

實驗相關內容簡介

詞法分析

語法分析語法制導的語義計算基礎符號表組織語義分析中間代碼生成運行時存儲組織目標代碼生成代碼優(yōu)化教