編譯原理復(fù)習(xí)清華呂映芝

編譯原理第1頁，共102頁。清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系呂映芝2003.9.9第1章 編譯程序概論什么是編譯程序翻譯和解釋編譯過程和編譯程序的結(jié)構(gòu)*1.4

編譯程序的實(shí)現(xiàn)途徑1.5

編譯技術(shù)在其它軟件中的應(yīng)用有關(guān)學(xué)習(xí)問題參考書第2頁，共102頁。1.1

什么是編譯程序4

語言和翻譯：語言是人類交流思想和信息的工具。從自然語言來說，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。4

編譯程序：編譯程序就是一個(gè)語言的翻譯程序,是把一種語言（稱源語言）書寫的程序翻譯成另一種等價(jià)功能語言（稱目標(biāo)語言）的程序。換句話說，編譯是指把一種用源語言表示的算法轉(zhuǎn)換到另一種等價(jià)的用目標(biāo)語言表示的算法。第3頁，共102頁。1.1

什么是編譯程序4

編譯程序的必要性：計(jì)算機(jī)是當(dāng)代科學(xué)發(fā)展的重要工具，已滲入到

各行各業(yè)乃至家庭生活中。所以如何讓他為人類工作服務(wù)，就必須建立人與計(jì)算機(jī)之間的信息交流。但計(jì)算機(jī)只認(rèn)識由“0”和“1”構(gòu)成的機(jī)器語言，并不認(rèn)識C、C++、Java、

Pascal等高級程序設(shè)計(jì)語言。每臺計(jì)算機(jī)都有自己獨(dú)特的指令系統(tǒng)，即機(jī)器語言，最早的程序就是用8進(jìn)制和16進(jìn)制碼的機(jī)器語言書寫的。第4頁，共102頁。1.1

什么是編譯程序用機(jī)器語言書寫程序，不僅不易學(xué)，而且可調(diào)試性、可讀性、可維護(hù)性和結(jié)構(gòu)性都很差，開發(fā)時(shí)間也很長。4

因此，編譯程序最初的定義是把一種高級程序設(shè)計(jì)語言的源程序（面向人的）翻譯成另一種等價(jià)的低級程序設(shè)計(jì)語言（面向硬件的）即機(jī)器語言或匯編語言。4

所以，編譯程序是人用某種語言書寫的某個(gè)翻譯程序。第5頁，共102頁。1.1

什么是編譯程序·

編譯程序的功能編譯程序機(jī)器語言（目標(biāo)語言）O:目標(biāo)語言(程序)I:

實(shí)現(xiàn)語言SOI高級程序設(shè)計(jì)語言（源語言）用T型圖表示S:源語言(程序)第6頁，共102頁。1.1

什么是編譯程序4

隨著計(jì)算機(jī)及其應(yīng)用的發(fā)展，出現(xiàn)了各種應(yīng)用更方便的高級語言，如:FORTRAN

、PL/1

、ALGOL

60

、COBOL

、PASCAL、Ada

、LISP

、C

、C++、JAVA等。4

早期開發(fā)的軟件需轉(zhuǎn)換，因此，編譯程序不僅是高級語言翻譯成機(jī)器語言，廣泛地講：4

編譯程序第7頁，共102頁。高級語言高級語言低級語言中間語言高級語言中間語言高級語言低級語言1.1

什么是編譯程序高級語言4

例：高級語言

FORTRANPASCALCJAVAPL/1C++

COBOLCAdaJAVA第8頁，共102頁。1.1

什么是編譯程序4

逆向工程

低級語言 高級語言例：IBM

/

4700（匯編語言）

C4

交叉編譯

在一個(gè)機(jī)器上對某種高級語言進(jìn)行編譯，產(chǎn)生的目標(biāo)語言是另一個(gè)機(jī)器的匯編語言或機(jī)器語言。例：在WAX機(jī)上編譯Ada語言，產(chǎn)生PC機(jī)的匯編語言，這樣的目標(biāo)語言只能在PC機(jī)上運(yùn)行，如嵌入式系統(tǒng)對交叉編譯的應(yīng)用。4

當(dāng)功能相同時(shí)，不同語言之間的區(qū)別，只是語言的詞法、語法和語義規(guī)則形式不同。運(yùn)行環(huán)境也可能不同。第9頁，共102頁。例：計(jì)算園面積C程序：function

circle(

);{int

r

;float s

;scanf

(“%d”,

&

r

);s

=3.1416

*

r

*

r

;printf

(“%d

\n”,s

);}Pascal

程序：第10頁，共102頁。procedure

circle;var

r

:

integer

;s

:

real

;beginread

(

r

)

;s

:=

3.1416

*

r

*

r

;write

(

s

)

;end

;1.2

翻譯和解釋翻譯：按源程序的實(shí)際輸入順序，處理程序語句，得到可執(zhí)行的目標(biāo)程序。解釋：按源語言的定義邊解釋邊執(zhí)行。解釋執(zhí)行是按照被解釋的源程序的邏輯流程進(jìn)行處理的，不產(chǎn)生目標(biāo)程序。解釋程序源程序第11頁，共102頁。輸入輸出解釋解釋執(zhí)行優(yōu)點(diǎn)：交互方便，節(jié)省空間。缺點(diǎn)：效率低。因?qū)υ闯绦虻难h(huán)語句部分要反復(fù)解釋執(zhí)行。共同點(diǎn)：都需進(jìn)行詞法、語法、語義分析?？杀扔鳛椋悍g（編譯）---筆譯（產(chǎn)生目標(biāo)程序）解釋---口譯（不產(chǎn)生目標(biāo)程序）第12頁，共102頁。1.3

編譯過程和編譯程序結(jié)構(gòu)第13頁，共102頁。4

編譯過程4

編譯程序結(jié)構(gòu)4

編譯的趟（遍）(pass)編譯過程詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成第14頁，共102頁。詞法分析讀字符流的源程序、識別單詞–例：position

:=

initial

+

rate

*

60

;（轉(zhuǎn)換為內(nèi)部表示，拼標(biāo)識符、數(shù)和復(fù)合單詞等）第15頁，共102頁。–單詞類型標(biāo)識符（1）算符(賦值號)單詞值

position:=（復(fù)合單詞）詞法分析–單詞類型單詞值標(biāo)識符（2）initial算符(加號)+標(biāo)識符（3）算符(乘號)*rate整數(shù)60界符（分號）；第16頁，共102頁。語法分析·

功能：層次分析，把源程序的單詞組成語法短語(表示成語法樹或其它內(nèi)部碼)?，F(xiàn)用“巴科斯-瑙爾范式”（EBNF）描述。–例:<賦值語句>::=<標(biāo)識符>:=<表達(dá)式><表達(dá)式>::=<表達(dá)式>+<表達(dá)式><表達(dá)式>::=<表達(dá)式>*<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”<表達(dá)式>::=<標(biāo)識符><表達(dá)式>::=<常數(shù)>第17頁，共102頁。語法分析（語法樹）:=+60*positioninitialrate第18頁，共102頁。語義分析·

語義審查靜態(tài)語義檢查上下文相關(guān)性如：類型匹配和類型轉(zhuǎn)換例:Program

p(

);var

rate:real;procedure

initial;…position

:=

initial

+

rate

*

60;/*

error

*/…類型匹配錯誤第19頁，共102頁。語義分析60:=+*positioninitialrateinttoreal類型轉(zhuǎn)換第20頁，共102頁。中間代碼生成·

源程序的內(nèi)部(中間)表示結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)，介于高級語言與低級語言之間,與目標(biāo)機(jī)無關(guān)，便于優(yōu)化、移植并容易生成目標(biāo)代碼。通常的中間代碼有三元式、四元式、樹結(jié)構(gòu)或適合相應(yīng)語言的中間代碼。例：P-Code、C-Code、bytecode等。第21頁，共102頁。中間代碼生成（四元式）例：id1:=id2+id3

*

60；翻譯成四元式四元式：3地址（操作符，操作對象1，操作對象2，操作結(jié)果）第22頁，共102頁。id3

t1id2

t2t3

—(inttoreal

60

—

t1

)(*

t2(+

t3(:=

id1)))代碼優(yōu)化代碼優(yōu)化：是對中間代碼進(jìn)行等價(jià)變換，以提高目標(biāo)代碼的時(shí)、空效率例：上面的4條指令可變成2條，并且節(jié)省2

個(gè)工作單元。(*

id3

60.0

t1

)(+

id2

t1

id1

)第23頁，共102頁。目標(biāo)代碼生成(*

id3

60.0

t1

)(+

id2

t1

id1

)movf

id3,R2mulf

#60.0,R2movf

id2,R1addf

R2,R1movf

R1,id1R1、R2是寄存器第24頁，共102頁。符號表管理記錄源程序中使用的名字收集每個(gè)名字的各種屬性信息–類型、作用域、分配存儲信息值：35第25頁，共102頁。Const

常量Var

變量類型：int層次：2地址：dx+5CONST

A=35，B=49；VAR

C，D，E；PROCEDURE

P；VAR

G表格管理(以PL/0為例）名字

類型層次/值地址

存儲空間Const（常量）無層次第26頁，共102頁。出錯處理編譯的任何時(shí)候都可能發(fā)現(xiàn)源程序中的錯誤。檢查詞法、語法和語義中的錯誤（靜態(tài)）。編譯程序的處理能力，如存儲空間越界（動態(tài)）報(bào)告出錯信息和位置處理和恢復(fù)第27頁，共102頁。編譯程序結(jié)構(gòu)詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標(biāo)代碼生成程序符號表管理程序出錯管理程序第28頁，共102頁。出錯處理語法分析語義分析詞法分析中間代碼生成代碼優(yōu)化表格管理目標(biāo)代碼生成目標(biāo)代碼源程序第29頁，共102頁。編譯的趟（遍）(pass)從頭到尾對源程序或各種形式的中間表示進(jìn)行掃描，稱為一遍編譯的前端（front

end）中間代碼生成后（代碼優(yōu)化后）編譯的后端（back

end）目標(biāo)代碼生成開始從源程序掃描是第一遍的輸入每前一遍的輸出是后一遍的輸入分遍的原則按實(shí)際情況而定第30頁，共102頁。1.4

編譯程序的實(shí)現(xiàn)途徑應(yīng)考慮：開發(fā)周期、目標(biāo)程序的效率、可移植性、可調(diào)試性、可維護(hù)性和可擴(kuò)充性等。構(gòu)造方式：l

手工構(gòu)造：用機(jī)器語言、匯編語言或高級程序設(shè)計(jì)語言書寫。l

自動構(gòu)造工具：Lex,Yacc。Lex,Yacc分別是詞法和語法分析器的生成器。l

移植方式：目標(biāo)程序用中間語言l

自展方式：用T型圖表示第31頁，共102頁。1.4

編譯程序的實(shí)現(xiàn)途徑4

自展方式：S

OIC1PC

C2PCCPCC2步驟1：(1)(2)PCC1CPCPC實(shí)現(xiàn)目標(biāo)(3)注釋：

PC表示PC機(jī)的機(jī)器語言或匯編語言C1

、C2是C的子集，

C1

C2第32頁，共102頁。自展方式步驟2：C2C1PCC1PCC2PCPCPCCC2PCC2PCCPCPCPC步驟3：第33頁，共102頁。1.5

編譯技術(shù)在其它軟件中的應(yīng)用4

軟件測試工具如：FORTRAN，C的靜態(tài)和動態(tài)測試工具（可測試程序的語句覆蓋率，路徑覆蓋率等）4

高級程序設(shè)計(jì)語言的轉(zhuǎn)換4

網(wǎng)絡(luò)中的協(xié)議4

數(shù)據(jù)庫系統(tǒng)中各種命令語言的翻譯4

各種軟件支持環(huán)境第34頁，共102頁。編譯程序在系統(tǒng)軟件中的所在層操作系統(tǒng)語言處理系統(tǒng)應(yīng)用軟件層裸機(jī)第35頁，共102頁。應(yīng)用軟件層語言處理系統(tǒng)等操作系統(tǒng)復(fù)習(xí)討論：編譯程序由哪些部分組成?說明每個(gè)部分的功 能。如果在PC機(jī)上只有C語言,現(xiàn)在要求實(shí)現(xiàn)

PASCAL語言，你用什么辦法做更好？（最 好不用匯編語言編寫）編譯的前端和后端如何劃分?翻譯(編譯)和解釋的區(qū)別是什么?各自的優(yōu)、 缺點(diǎn)是什么？第36頁，共102頁。有關(guān)學(xué)習(xí)問題第37頁，共102頁。4

教學(xué)內(nèi)容和學(xué)習(xí)目的4

學(xué)習(xí)要求和學(xué)習(xí)方法教學(xué)內(nèi)容編譯程序概述PL/0編譯程序（讀懂文本，擴(kuò)充功能）語言和文法詞法分析和有限自動機(jī)

(5)自頂向下語法分析方法*(6)自底向上算符優(yōu)先分析法自底向上LR分析法語法制導(dǎo)翻譯和中間代碼生成目標(biāo)程序運(yùn)行時(shí)的存儲空間組織*(10)代碼優(yōu)化第38頁，共102頁。學(xué)習(xí)目的4

近年來，信息技術(shù)的迅猛發(fā)展，對軟件技術(shù)和軟件工具的需求急劇增加，編譯技術(shù)已大量應(yīng)用于各種各樣軟件工具的研制和開發(fā)中。從各種語言的結(jié)構(gòu)化編輯器、分析器和語言的解釋系統(tǒng)到嵌入式軟件，交叉編譯器；從傳統(tǒng)的強(qiáng)制式的程序設(shè)計(jì)語言到應(yīng)用式、面向?qū)ο蟮恼Z言的編譯；從一般的批處理環(huán)境到交互環(huán)境及分布式環(huán)境等等；技術(shù)需求越來越大，涉及面越來越廣。因而，廣大從事計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件研制及開發(fā)人員對編譯技術(shù)深入了解的要求越來越高。第39頁，共102頁。學(xué)習(xí)要求和學(xué)習(xí)方法4

目前，編譯系統(tǒng)的構(gòu)造在理論上有較成熟的體

系支持，實(shí)現(xiàn)技術(shù)也很豐富多樣。但要使學(xué)生

通過該課程的學(xué)習(xí)從理解原理、掌握技術(shù)到自

己設(shè)計(jì)和實(shí)現(xiàn)一個(gè)完整的編譯程序，難度很大，因?yàn)檎n程內(nèi)容廣泛，涉及到數(shù)據(jù)結(jié)構(gòu)、操作系

統(tǒng)、離散數(shù)學(xué)及語言理論，是綜合性很強(qiáng)的一

門課程。從抽象形式語言與自動機(jī)的概念，到

具體構(gòu)造實(shí)現(xiàn)的復(fù)雜性，學(xué)生都必須理解原理

掌握技術(shù)。第40頁，共102頁。學(xué)習(xí)要求和學(xué)習(xí)方法4

學(xué)時(shí)：課內(nèi)48，課外804

學(xué)好原理和構(gòu)造技術(shù)需做相當(dāng)量作業(yè)，鞏固課堂知識理論聯(lián)系實(shí)際，做好實(shí)驗(yàn)第41頁，共102頁。實(shí)驗(yàn)要求必做題目第42頁，共102頁。65%擴(kuò)充條件語句〈條件語句〉::=IF〈條件〉THEN〈語句〉[ELSE〈語句〉]擴(kuò)充重復(fù)語句〈重復(fù)語句〉::=REPEAT〈語句〉{；〈語句〉}UNTIL〈條件〉選做題目用C語言改寫PL/0編譯程序；

80%用Java語言改寫PL/0編譯程序；80%實(shí)驗(yàn)要求對PL/0語言擴(kuò)充整形數(shù)組（盡量做此題）。95%討論 ：分成3人一組做擴(kuò)充整形數(shù)組，開展討論、相互學(xué)習(xí)，培養(yǎng)團(tuán)隊(duì)精神。其他選做①學(xué)完語法分析后可用LL（1）或LR語法分析方法改寫PL/0編譯程序的某些部分②用LEX、YACC編寫一個(gè)小型的編譯器（要求見編譯原理實(shí)驗(yàn)2）③用LEX、YACC改寫PL/0編譯程序適當(dāng)加分第43頁，共102頁。實(shí)驗(yàn)要求實(shí)驗(yàn)報(bào)告內(nèi)容:對擴(kuò)充部分用語法圖和EBNF描述；對程序變動部分的說明；所用測試用例；實(shí)驗(yàn)體會和建議。第44頁，共102頁。參考書第45頁，共102頁。呂映芝，張素琴，蔣維杜.編譯原理.清華大學(xué)出版社.1998

Tomas

Pittmn,

The

art

of

Compiler

Design

theory

andPractice,

Prentice-Hall

1992Charles

N.

Fischer,

Richard

J.

Leblanc,

Crafting

ACompiler,

The

Benjamin/Cummings

Publishing

Company1988ALFRED

V.

AHO,

RAVISETHI,

JEFFREY

D.

ULLMAN,Compilers

Principles,

Techniques

and

Tools

ADDISSON-WESLEY

1986教材后所列其它參考第2章

PL/0編譯程序的實(shí)現(xiàn)4

本章目的：以PL/0語言的編譯程序?yàn)閷?shí)例,學(xué)習(xí)一個(gè)編譯程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù)“PL/0語言的編譯程序”是世界著名計(jì)算機(jī)科學(xué)家

N.Wirth先生編寫的。由于PL/0語言功能簡單、

結(jié)構(gòu)清晰、可讀性強(qiáng)，而又具備了一般高級語言的必須部分，因而PL/0語言的編譯程序能充分體現(xiàn)一個(gè)高級語言編譯程序?qū)崿F(xiàn)的基本技術(shù)和步驟。是一個(gè)非常合適的小型編譯程序的教學(xué)模型。第46頁，共102頁。第2章

PL/0編譯程序的實(shí)現(xiàn)通過本章的學(xué)習(xí)可達(dá)到：–對編譯程序的構(gòu)造得到一些感性認(rèn)識和初步了解–對編譯程序的實(shí)現(xiàn)建立起整體概念–為系統(tǒng)地學(xué)習(xí)本課程以下各章節(jié)打好基礎(chǔ)為了讀者能較好地閱讀PL/0語言編譯程序文本。本章將對PL/0語言編譯程序的實(shí)現(xiàn)過程作概括的分析說明。對PL/0語言文法的表示只給出語法圖和擴(kuò)充的巴科斯-瑙爾范式(EBNF)的描述形式，不作文法理論上的討論。第47頁，共102頁。第2章

PL/0編譯程序的實(shí)現(xiàn)4

功能PL/0編譯程序PL/0語言類pcode源語言(PL/0)目標(biāo)語言(類pcode)實(shí)現(xiàn)語言（pascal)PL/0類pcodepascal類pcode是中間代碼Pcode是適合pascal的中間代碼第48頁，共102頁。PL/0源程序PL/0編譯程序類pcode代碼類

pcode解釋程序輸入輸出PL/0編譯程序功能的框架第49頁，共102頁。第2章

PL/0編譯程序的實(shí)現(xiàn)步驟1. 認(rèn)識源語言PL/0與目標(biāo)代碼類pcode及它們之間的映射步驟2.

PL/0編譯程序的總體設(shè)計(jì)步驟3.

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)步驟4.

PL/0編譯程序語法語義分析的設(shè)計(jì)與實(shí)現(xiàn)步驟5.

PL/0編譯程序代碼生成的實(shí)現(xiàn)*步驟6.

PL/0編譯程序錯誤處理的實(shí)現(xiàn)步驟7.

類pcode代碼解釋器的設(shè)計(jì)與實(shí)現(xiàn)第50頁，共102頁。練習(xí)見教材26-27頁1.

2.

3.

4.

5.6.

(2),

(3)第51頁，共102頁。第3章 文法和語言文法和語言概述文法和語言的形式定義文法的類型（重點(diǎn)是二型和三型）上下文無關(guān)文法及其語法樹句型的分析有關(guān)文法實(shí)用中的一些說明第52頁，共102頁。3.1

語言文法概述4

本章目的4

語言概述4

語言的一般描述4

文法的直觀概念第53頁，共102頁。本章目的本章目的是為語言的語法描述尋求工具，是本課程的理論基礎(chǔ)。通過描述工具，可以：對源語言給出精確無二義的語法描述。（嚴(yán)謹(jǐn)、簡潔、易讀）根據(jù)語言文法的特點(diǎn)來指導(dǎo)語法分析的過程從描述語言的文法可以自動構(gòu)造出可用的分析程序(如：第13章介紹的基于LALR(1)文法的yacc和基于LL(2)文法的SD&EBNF_LL(2))制導(dǎo)語義翻譯第54頁，共102頁。語言概述4

語言是由句子組成的集合，是由一組記號所構(gòu)成的集合。4

漢語--所有符合漢語語法的句子的全體4

英語--所有符合英語語法的句子的全體4

程序設(shè)計(jì)語言--所有該語言的程序的全體4每個(gè)句子構(gòu)成的規(guī)律4

研究語言 每個(gè)句子的含義4每個(gè)句子和使用者的關(guān)系第55頁，共102頁。語言概述語言研究的三個(gè)方面:語法（

Syntax

）--表示構(gòu)成語言句子的各個(gè)記號之間的組合規(guī)律語義（Semantics）--表示按照各種表示方法所表示的各個(gè)記號的特定含義。（各個(gè)記號和記號所表示的對象之間的關(guān)系）語用（Pragmatics）--表示在各個(gè)記號所出現(xiàn)的行為中，它們的來源、使用和影響。（本章不做進(jìn)一步的介紹）第56頁，共102頁。語言概述4

形式語言理論（formal

language

theory）：是一種從語法上研究語言的理論。它是抽象的數(shù)學(xué)系統(tǒng)，著重研究符號串集合的表示法、結(jié)構(gòu)及其特性。是程序設(shè)計(jì)語言語法分析研

究的基礎(chǔ)。（本章僅使用其與編譯程序構(gòu)造

有關(guān)的結(jié)論，而不做證明）4

形式語義（formal

semantics）：（本課程不介紹）。第57頁，共102頁。語言的一般描述4

語言可以看成在一個(gè)基本符號集上定義的，按一定規(guī)則構(gòu)成的基本符號串組成的所有集合。4

一些基本概念第58頁，共102頁。文法的直觀概念4

句子的產(chǎn)生4

<句子>::=<主語><謂語>4

<主語>::=<代詞>|<名詞>4

<代詞>::=我|你|他4

<名詞>::=王明|大學(xué)生|工人|英語4

<謂語>::=<動詞><直接賓語>4

<動詞>::=是|學(xué)習(xí)4

<直接賓語>::=<代詞>|<名詞>第59頁，共102頁。文法的直觀概念（用“ ”表示推導(dǎo)）<句子>

<主語><謂語><代詞><謂語>我<謂語>我<動詞><直接賓語>我是<直接賓語>我是<名詞>我是大學(xué)生第60頁，共102頁。練習(xí)教材45~46頁5.7.9.11.13.

(3)14.

(1),(2)16.

(2),(3)第61頁，共102頁。第4章 詞法分析設(shè)計(jì)詞法分析程序單詞的描述工具單詞的識別系統(tǒng)詞法分析程序正規(guī)表達(dá)式、*正規(guī)文法與正規(guī)集有窮自動機(jī)正規(guī)表達(dá)式和有窮自動機(jī)*

4.5有窮自動機(jī)和正規(guī)文法第62頁，共102頁。4.1

詞法分析程序詞法分析（lexical

analysis）詞法分析是逐個(gè)讀入源程序字符，并按照構(gòu)詞規(guī)則分割成一系列單詞，再轉(zhuǎn)換成詞標(biāo)流的過程。單詞是語言中具有獨(dú)立意義的最小單位，包括

保留字、標(biāo)識符、常量、運(yùn)算符和界符等。詞標(biāo)是單詞的機(jī)內(nèi)表示，其格式由實(shí)現(xiàn)系統(tǒng)規(guī)定。例如：PL/0語言的單詞用戶寫的if

a=2...機(jī)內(nèi)表示為ifsym

ident

eql

number…。第63頁，共102頁。4.1

詞法分析程序詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行。可以作為單獨(dú)的一遍，將源程序轉(zhuǎn)換成詞標(biāo)流供下一遍使用。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序，獲得當(dāng)前詞標(biāo),供語法分析程序使用。如PL/0語言編譯程序的實(shí)現(xiàn)就是把詞法分析和語法分析結(jié)合在一起作為一遍。第64頁，共102頁。4.1

詞法分析程序在詞法分析程序的實(shí)際實(shí)現(xiàn)中，首先需要描述和刻畫語言中的最小單位—單詞，其次需要識別單詞和執(zhí)行某些相關(guān)的動作。程序設(shè)計(jì)語言詞法的描述和識別機(jī)制是：描述機(jī)制用3型文法和正規(guī)表達(dá)式；識別機(jī)制用有窮狀態(tài)自動機(jī)。在詞法分析過程中，與語法分析無關(guān)的符號應(yīng)預(yù)先處理。如為提高易讀性增加的注釋，與語法語義分析無關(guān)，無需產(chǎn)生相應(yīng)的詞標(biāo)，處理時(shí)應(yīng)濾掉。第65頁，共102頁。4.1

詞法分析程序源程序詞法分析程序語法分析程序Tokenget

token主要任務(wù)：讀源程序(字符流)，產(chǎn)生單詞符號（詞標(biāo)流）其他任務(wù)：濾掉空格、跳過注釋和換行符,追蹤換行標(biāo)志，復(fù)制出錯源程序，宏展開等。第66頁，共102頁。4.1

詞法分析程序單詞符號一般可分為下列五種：基本字(關(guān)鍵字或保留字)標(biāo)識符常數(shù)（常量）運(yùn)算符界符第67頁，共102頁。4.1

詞法分析程序輸出表示（單詞種別，單詞自身的值）。詞法分析工作獨(dú)立的原因：簡化設(shè)計(jì)提高編譯效率增加編譯系統(tǒng)的可移植性第68頁，共102頁。練習(xí)教材第66~67頁4.7練習(xí)的

1.(1)3.4.(b)*5.*8.第69頁，共102頁。第5章 LL(1)文法及其分析程序4

5.1 語法分析（回顧）(自頂向下分析的一般過程和問題)4

5.2

LL(1)

文法的定義FIRST集和FOLLOW集的定義和計(jì)算LL(1)

文法的定義非LL(1)文法的改造4

5.3 LL(1)分析程序的實(shí)現(xiàn)第70頁，共102頁。5.1 語法分析（回顧）4

句型、句子和語言的定義4

句型:x，且x∈V*，則稱x是文法GTx，且x∈V

*，則稱x是文法G–有文法G[s]，若S的句型。4

句子:–有文法G[s]，若S的句子。00001111例：G[s]：S→0S1，S→01S

0S1

00S11

000S111僅有00001111是句子第71頁，共102頁。5.1 語法分析（回顧）4

最左（最右）推導(dǎo)：在推導(dǎo)的任何一步α

β(其中α、β是句型)，都是對α中的最左（右）非終結(jié)符進(jìn)行替換。4

最右推導(dǎo)被稱為規(guī)范推導(dǎo)。4

由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。第72頁，共102頁。句型的分析4

句型分析

就是識別一個(gè)符號串是否為某文法的句型，也就是某文法的某個(gè)推導(dǎo)的構(gòu)造過程。4

在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱

為分析程序

或識別程序。分析算法又稱識別算法。4

從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進(jìn)而依次識別右邊的一個(gè)符號。第73頁，共102頁。句型的分析4

分析算法可分為：4

自頂向下（自上而下）分析法：從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。4

自底向上（自下而上）分析法：從輸入符號串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號。4

兩種方法反映了兩種不同的語法樹的構(gòu)造過程第74頁，共102頁。自頂向下（自上而下）的語法分析4

例：文法G：S

→

cAdA

→

abA

→

a識別輸入串w=cabd是否該文法的句子ScSA

d

cSA

dab推導(dǎo)過程：S

cAd

cabd第75頁，共102頁。自底向上（自下而上）的語法分析4

例：文法G：S

→

cAdA

→

abA

→

a識別輸入串w=cabd是否該文法的句子SAAc

a

b

dc

a

b

dc

a

b

d歸約過程：

S

cAdcabd第76頁，共102頁。句型分析的有關(guān)問題1）如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？在自頂向下的分析方法中，假定要被替換的最左非終結(jié)符號是V，且V為左部有n條規(guī)則：V→A1|A2|…|An，那么如何確定用哪個(gè)右部去替換

V？如：前例中A→ab|

a

2）如何識別可歸約的串？在自底向上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中尋找一個(gè)子串，看它是否能歸約到某個(gè)非終結(jié)符號，該子串稱為“可歸約串”，歸約就是用非終結(jié)符號替換它。第77頁，共102頁。練習(xí)教材

90

頁1.3.7.（2）,（3）第78頁，共102頁。第6章

自底向上的優(yōu)先分析法4

自底向上語法分析概述4

*6.1 自下而上的優(yōu)先分析法概述（不介紹）4

*6.2 簡單優(yōu)先分析（不介紹）4

6.3 算符優(yōu)先分析（本章重點(diǎn)）第79頁，共102頁。自底向上語法分析概述自底向上語法分析是試圖將一個(gè)輸入符號串反向歸約至語法的開始符號，在每一步中如何選擇可歸約子串進(jìn)行歸約？常用的兩種方法是：–算符優(yōu)先分析法–LR分析（第7章詳細(xì)介紹）自底向上語法分析比自上而下語法分析更有效率，特別是某些LR分析法對語法的限制更少。第80頁，共102頁。6.3

算符優(yōu)先分析4

某些文法具有“算符”特性表達(dá)式運(yùn)算符（優(yōu)先級、結(jié)合性）人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一級別的結(jié)合性4

只考慮算符之間的優(yōu)先關(guān)系來確定可歸約串（廣義講終結(jié)符為算符）第81頁，共102頁。練習(xí)教材116頁1.(1)、（2）、（4）2.

（1）第82頁，共102頁。第7章

LR分析程序及其自動構(gòu)造LR分析概述LR

(0)

分析SLR(1)

分析*7.4

LR（1）分析*7.5

LALR(1)分析7.6 二義性文法在LR分析中的應(yīng)用7.7

LR分析程序的自動生成第83頁，共102頁。7.1

LR分析概述4

一般移進(jìn)-歸約分析過程4

LR分析器模型和分析算法4

LR分析特征討論第84頁，共102頁。7.1

LR分析概述4

例6.

1

G[S]為：（1）S

aAcBe（2）A

b（3）A

Ab（4）B

d第85頁，共102頁。文法G[S]：S

→

aAcBeA

→

bA

→

AbB

→

dab

bc

d

e符號棧abbcde#輸入符號串 動作移進(jìn)A步驟1）

##a#ab#aAbbcde#bcde#bcde#移進(jìn)歸約(A→b)移進(jìn)A歸約(A→Ab)#aAb#aAcde#cde#移進(jìn)de#移進(jìn)Be#e##S#aAc#

aAcd#aAcB10）

#aAcBe11）

#S#歸約(B→d)移進(jìn)歸約接受對輸入串a(chǎn)bbcde#的移進(jìn)-歸約分析過程第86頁，共102頁。S

aAcBe符號串a(chǎn)bbcde是否是G[S]的句子aAcde

aAbcde

abbcde7.1

LR分析概述4

在步驟3中，用A→b歸約4

在步驟5中，用A→Ab歸約4

問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約？第87頁，共102頁。LR分析器模型input

xxx···#總控程序outputSn

Xn·

··

·S1

X1S0

#狀態(tài)棧

文法符號棧ACTION

GOTOLR分析表產(chǎn)生式表第88頁，共102頁。練習(xí)教材151~154中的

1.2.6.*8.16

.第89