編譯原理和技術(shù)課件

編譯原理和技術(shù)

第一章引論

名詞解釋翻譯器(translator)、編譯器(compiler)解釋器(interpreter)編譯器從邏輯上可以分成若干個(gè)階段每個(gè)階段把源程序從一種表示變換成另一種表示本章通過(guò)描述編譯器的各個(gè)階段來(lái)介紹編譯這個(gè)課題1.1編譯器概述詞法分析器語(yǔ)法分析器語(yǔ)義分析器源程序中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼符號(hào)表符號(hào)表

positioninitialrate.........123詞法分析器id,1

=

id,2

+

id,3

60

position=initial+rate

601.1編譯器概述

記號(hào)流

字符流1.1編譯器概述表達(dá)式的語(yǔ)法特征任何一個(gè)標(biāo)識(shí)符都是表達(dá)式任何一個(gè)數(shù)都是表達(dá)式如果e1和e2都是表達(dá)式，那么

e1+e2

e1

*

e2

(e1)也都是表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識(shí)符表達(dá)式表達(dá)式(initial)標(biāo)識(shí)符(rate)數(shù)(60)*+initial+rate*60的分析樹(shù)符號(hào)表

positioninitialrate.........123語(yǔ)法分析器id,1

=

id,2

+

id,3

60

=

+

60

id,1

id,2

id,3

語(yǔ)法樹(shù)1.1編譯器概述

記號(hào)流符號(hào)表

positioninitialrate.........1231.1編譯器概述語(yǔ)義分析器

=

+

60

id,1

id,2

id,3

=

+

inttofloatid,1

id,2

id,3

60

語(yǔ)法樹(shù)

語(yǔ)法樹(shù)符號(hào)表

positioninitialrate.........123中間代碼生成器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3

=

+

inttofloatid,1

id,2

id,3

60

1.1編譯器概述

三地址中間代碼

語(yǔ)法樹(shù)符號(hào)表

positioninitialrate.........123代碼優(yōu)化器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t11.1編譯器概述

三地址中間代碼

三地址中間代碼符號(hào)表

positioninitialrate.........123代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t11.1編譯器概述

三地址中間代碼

匯編代碼1.1編譯器概述解釋器和編譯器的區(qū)別詞法分析器語(yǔ)法分析器語(yǔ)義分析器源程序中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼解釋器不生成目標(biāo)代碼，而是直接執(zhí)行源程序所指定的運(yùn)算

解釋器也需要對(duì)源程序進(jìn)行詞法、語(yǔ)法和語(yǔ)義分析,中間代碼生成1.1編譯器概述BASIC年代的解釋器功能：它將高級(jí)語(yǔ)言的源程序翻譯成一種中間語(yǔ)言程序，然后對(duì)中間語(yǔ)言程序進(jìn)行解釋執(zhí)行在那個(gè)年代，編譯和解釋兩個(gè)功能是合在一個(gè)程序中，該程序被稱為解釋器Java年代的解釋器上述兩個(gè)功能分在兩個(gè)程序中前一個(gè)叫做編譯器，它把源程序翻譯成一種叫做字節(jié)碼的中間語(yǔ)言程序后一個(gè)叫做解釋器，它對(duì)字節(jié)碼程序進(jìn)行解釋執(zhí)行1.1編譯器概述階段分組前端后端詞法分析器語(yǔ)法分析器語(yǔ)義分析器源程序中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼1.1編譯器概述詞法分析器語(yǔ)法分析器語(yǔ)義分析器源程序中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼階段分組遍1.2編譯器技術(shù)的應(yīng)用

高級(jí)語(yǔ)言的實(shí)現(xiàn)高級(jí)編程語(yǔ)言易于編程，但程序運(yùn)行較慢低級(jí)語(yǔ)言編程時(shí)可實(shí)施更有效的控制方式，得到更有效的代碼，但難編寫(xiě)、易出錯(cuò)、難維護(hù)流行編程語(yǔ)言的大多數(shù)演變都是朝著提高抽象級(jí)別的方向每一輪編程語(yǔ)言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究1.2編譯器技術(shù)的應(yīng)用

高級(jí)語(yǔ)言的實(shí)現(xiàn) 每一輪編程語(yǔ)言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究支持用戶定義的聚合數(shù)據(jù)類(lèi)型和高級(jí)控制流，如數(shù)組和記錄、循環(huán)和過(guò)程調(diào)用：C、Fortran面向?qū)ο蟮闹饕拍钍菙?shù)據(jù)抽象和性質(zhì)繼承，使得程序更加模塊化并易于維護(hù)：Smalltalk、C++、C#、Java類(lèi)型安全的語(yǔ)言：Java沒(méi)有指針，也不允許指針?biāo)阈g(shù)。它用無(wú)用單元收集機(jī)制來(lái)自動(dòng)地釋放那些不再使用的變量占據(jù)的內(nèi)存Java設(shè)計(jì)來(lái)支持代碼移植和代碼移動(dòng)1.2編譯器技術(shù)的應(yīng)用

針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化計(jì)算機(jī)體系結(jié)構(gòu)的迅速演化引起對(duì)新的編譯器技術(shù)一種不知足的需要并行化

編譯器重新整理指令，使得指令級(jí)并行更有效

編譯器從傳統(tǒng)的串行程序自動(dòng)生成并行代碼，使之運(yùn)行于多處理器上內(nèi)存分層

編譯器優(yōu)化歷來(lái)集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效1.2編譯器技術(shù)的應(yīng)用

新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)現(xiàn)在計(jì)算機(jī)系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼在現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的研究中，在處理器的設(shè)計(jì)階段就開(kāi)發(fā)編譯器，并將編譯生成的代碼在模擬器上運(yùn)行，以評(píng)價(jià)擬采用體系結(jié)構(gòu)的特征編譯器技術(shù)影響計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)著名例子是精簡(jiǎn)指令集計(jì)算機(jī)（RISC）的發(fā)明1.2編譯器技術(shù)的應(yīng)用

程序翻譯二進(jìn)制翻譯

編譯器技術(shù)可用于把一種機(jī)器的二進(jìn)制代碼翻譯成另一種機(jī)器的代碼，以運(yùn)行原先為別的指令集編譯的代碼數(shù)據(jù)庫(kù)查詢解釋器

數(shù)據(jù)庫(kù)查詢由一些謂詞組成，這些謂詞由包含關(guān)系運(yùn)算的布爾表達(dá)式組成，可以被解釋執(zhí)行,也可以被編譯成搜索數(shù)據(jù)庫(kù)的命令2.1詞法記號(hào)及屬性

2.1.1詞法記號(hào)、模式、詞法單元

記號(hào)名

詞法單元例舉

模式的非形式描述

if if 字符i,f

for for 字符f,o,rrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母開(kāi)頭的字母數(shù)字串number 3.1,10,2.8E12 任何數(shù)值常數(shù)literal “seg.error” 引號(hào)“和”之間任意不含 引號(hào)本身的字符串2.1詞法記號(hào)及屬性歷史上詞法定義中的一些問(wèn)題忽略空格帶來(lái)的困難

DO8I

3.75 等同于 DO8I

3.75DO8I

3,75關(guān)鍵字不保留

IFTHENTHENTHEN=ELSE；ELSE…關(guān)鍵字、保留字和標(biāo)準(zhǔn)標(biāo)識(shí)符的區(qū)別保留字是語(yǔ)言預(yù)先確定了含義的詞法單元標(biāo)準(zhǔn)標(biāo)識(shí)符也是預(yù)先確定了含義的標(biāo)識(shí)符，但程序可以重新聲明它的含義2.1詞法記號(hào)及屬性2.1.2詞法記號(hào)的屬性

position=initial+rate

60的記號(hào)和屬性值：

id，指向符號(hào)表中position條目的指針

assign_op

id，指向符號(hào)表中initial條目的指針

add_op

id，指向符號(hào)表中rate條目的指針

mul_op

number，整數(shù)值60

2.1詞法記號(hào)及屬性2.1.3詞法錯(cuò)誤詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)例：難以發(fā)現(xiàn)下面的錯(cuò)誤

fi(a==f(x))

…在實(shí)數(shù)是“數(shù)字串.數(shù)字串”格式下，可以發(fā)現(xiàn)下面的錯(cuò)誤 123.x緊急方式的錯(cuò)誤恢復(fù) 刪掉當(dāng)前若干個(gè)字符，直至能讀出正確的記號(hào)錯(cuò)誤修補(bǔ) 進(jìn)行增、刪、替換和交換字符的嘗試2.2詞法記號(hào)的描述與識(shí)別

2.2.1串和語(yǔ)言字母表：符號(hào)的有限集合，例：={0,1}串：符號(hào)的有窮序列，例：0110,

語(yǔ)言：字母表上的一個(gè)串集 {,0,00,000,…},{},句子：屬于語(yǔ)言的串串的運(yùn)算連接（積） xy，s

=s=s

冪

s0為，si為si-1s（i>0）

2.2詞法記號(hào)的描述與識(shí)別

語(yǔ)言的運(yùn)算并： L

M={s|s

L或s

M}連接： LM={st|s

L且t

M}冪： L0是{

}，Li是Li-1L

閉包： L

=L0

L1

L2

…正閉包： L+=L1

L2

…例L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L

D,LD,L6,L*,L(L

D)*,D+

2.2詞法記號(hào)的描述與識(shí)別

2.2.2正規(guī)式正規(guī)式用來(lái)表示簡(jiǎn)單的語(yǔ)言，叫做正規(guī)集

正規(guī)式 定義的語(yǔ)言 備注

{

}

a {a} a

(r)|(s) L(r)∪L(s) r和s是正規(guī)式 (r)(s)

L(r)L(s) r和s是正規(guī)式

(r)*

(L(r))* r是正規(guī)式

(r) L(r) r是正規(guī)式 ((a)(b)*)|(c)可以寫(xiě)成ab*|c

2.2詞法記號(hào)的描述與識(shí)別

正規(guī)式的例子

={a,b}a|b

{a,b}(a|b)(a|b)

{aa,ab,ba,bb}aa|ab|ba|bb

{aa,ab,ba,bb}a* 由字母a構(gòu)成的所有串集(a|b)* 由a和b構(gòu)成的所有串集復(fù)雜的例子(00|11|((01|10)(00|11)

(01|10)))

句子：010011010000100000101110012.2詞法記號(hào)的描述與識(shí)別

2.2.3正規(guī)定義

對(duì)正規(guī)式命名，使表示簡(jiǎn)潔 d1

r1 d2

r2 ... dn

rn各個(gè)di的名字都不同每個(gè)ri都是

{d1,d2,…,di-1}上的正規(guī)式2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子C語(yǔ)言的標(biāo)識(shí)符是字母、數(shù)字和下劃線組成的串

letter_

A|B|…|Z|a|b|…

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子

無(wú)符號(hào)數(shù)集合，例1946,11.28,63E8,1.99E

6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

number

digitsoptional_fractionoptional_exponent

簡(jiǎn)化表示 number

digit+(.digit+)?(E(+|

)?digit+)?2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子（進(jìn)行下一步討論的例子）

while

while do

do relop

<|<=|=|<>|>|>=

letter

A|B|…|Z|a|b|…

|z id

letter(letter|digit)* number

digit+(.digit+)?(E

(+|

)?

digit+)?delim

blank|tab|newline

ws

delim+2.2詞法記號(hào)的描述與識(shí)別

2.2.4轉(zhuǎn)換圖關(guān)系算符的轉(zhuǎn)換圖

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)開(kāi)始<=>=>=**otherother2.2詞法記號(hào)的描述與識(shí)別

標(biāo)識(shí)符和關(guān)鍵字的轉(zhuǎn)換圖91011開(kāi)始letterother*letter或digitreturn(installId())2.2詞法記號(hào)的描述與識(shí)別

無(wú)符號(hào)數(shù)的轉(zhuǎn)換圖 number

digit+(.digit+)?(E

(+|

)?

digit+)?開(kāi)始1912131415161718digitdigitdigitdigitdigitdigitother.E+/

Edigitotherotherreturn(installNum())*2.2詞法記號(hào)的描述與識(shí)別

空白的轉(zhuǎn)換圖delim

blank|tab|newlinews

delim+2122開(kāi)始delimother*delim202.3有限自動(dòng)機(jī)

2.3.1不確定的有限自動(dòng)機(jī)（簡(jiǎn)稱NFA） 一個(gè)數(shù)學(xué)模型，它包括：

1、有限的狀態(tài)集合S

2、輸入符號(hào)集合

3、轉(zhuǎn)換函數(shù)move:S

(

{

})

P(S)

4、狀態(tài)s0是唯一的開(kāi)始狀態(tài)

5、F

S是接受狀態(tài)集合識(shí)別語(yǔ)言(a|b)*ab

的NFA12開(kāi)始a0abb輸入符號(hào)ab0{0,1}{0}1

{2}2

狀態(tài)

NFA的轉(zhuǎn)換表2.3有限自動(dòng)機(jī)

識(shí)別語(yǔ)言(a|b)*ab

的NFA12開(kāi)始a0abb2.3有限自動(dòng)機(jī)

例

識(shí)別aa*|bb*的NFA12開(kāi)始a0abb34

2.3.2確定的有限自動(dòng)機(jī)（簡(jiǎn)稱DFA)

一個(gè)數(shù)學(xué)模型，包括：1、有限的狀態(tài)集合S2、輸入字母集合

3、轉(zhuǎn)換函數(shù)move:S

S，且可以是部分函數(shù)4、唯一的開(kāi)始狀態(tài)s05、接受狀態(tài)集合F

S12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的DFA2.3有限自動(dòng)機(jī)

2.3有限自動(dòng)機(jī)

例 DFA，識(shí)別{0,1}上能被5整除的二進(jìn)制數(shù) 已讀過(guò) 尚未讀 已讀部分的值 某時(shí)刻 101 0111000 5 讀進(jìn)0 1010 111000 52=10 讀進(jìn)1 10101 11000 102+1=21

5個(gè)狀態(tài)即可，分別代表已讀部分的值除以5的余數(shù)例 DFA，識(shí)別{0,1}上能被5整除的二進(jìn)制數(shù)0123開(kāi)始410010101012.3有限自動(dòng)機(jī)

10102=10101112=710例 DFA,接受0和1的個(gè)數(shù)都是偶數(shù)的字符串00003211奇0奇1奇0偶11011開(kāi)始偶0偶1偶0奇12.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法 1、DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合

2、讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,sk，則

DFA到達(dá)狀態(tài){s1,s2,…,sk}12a開(kāi)始0abb{0}{0,1}aba{0,2}b2.3有限自動(dòng)機(jī)

未畫(huà)完19開(kāi)始

0ab

ab6782345

例 (a|b)*ab，NFA如下，把它變換為DFA2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)ab狀態(tài)

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abA狀態(tài)

A={0,1,2,4,7}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abAB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBDC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBDCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCDBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCDBC狀態(tài)

BD開(kāi)始aAabbabCba2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

BD開(kāi)始aAabbabCba12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的自動(dòng)機(jī)2.3有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

BD開(kāi)始aAabbabCba12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的自動(dòng)機(jī)子集構(gòu)造法不一定得到最簡(jiǎn)DFA2.3有限自動(dòng)機(jī)

BD開(kāi)始aAabbaa,bCbaEb2.3.4DFA的化簡(jiǎn)死狀態(tài)在轉(zhuǎn)換函數(shù)由部分函數(shù)改成全函數(shù)表示時(shí)引入左圖需要引入死狀態(tài)E；右圖無(wú)須引入死狀態(tài)BD開(kāi)始aAabbabCba2.3有限自動(dòng)機(jī)

可區(qū)別的狀態(tài)A和B是可區(qū)別的狀態(tài)

從A出發(fā)，讀過(guò)單字符b構(gòu)成的串，到達(dá)非接受狀態(tài)C，而從B出發(fā)，讀過(guò)串b，到達(dá)接受狀態(tài)DA和C是不可區(qū)別的狀態(tài) 無(wú)任何串可用來(lái)像上面這樣 區(qū)別它們BD開(kāi)始aAabbabCba2.3有限自動(dòng)機(jī)

方法1.{A,B,C},{D}move({A,B,C},a)={B}move({A,B,C},b)={C,D}2.{A,C},{B},{D}move({A,C},a)={B}move({A,C},b)={C}BD開(kāi)始aAabbabCba12開(kāi)始a0abbab2.3有限自動(dòng)機(jī)

從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造NFA（本節(jié)介紹） 用語(yǔ)法制導(dǎo)的算法，它用正規(guī)式語(yǔ)法結(jié)構(gòu)來(lái)指導(dǎo)構(gòu)造過(guò)程把NFA變成DFA（子集構(gòu)造法，已介紹）將DFA化簡(jiǎn)（合并不可區(qū)別狀態(tài)，也已介紹）2.4從正規(guī)式到有限自動(dòng)機(jī)首先構(gòu)造識(shí)別

和字母表中一個(gè)符號(hào)的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換i開(kāi)始

識(shí)別正規(guī)式

的NFAafif開(kāi)始識(shí)別正規(guī)式a的NFA2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換

fi開(kāi)始識(shí)別正規(guī)式s|t的NFAN(s)N(t)

2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換識(shí)別正規(guī)式st的NFAiN(s)f開(kāi)始N(t)2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換N(s)f開(kāi)始識(shí)別正規(guī)式s*的NFAi

2.4從正規(guī)式到有限自動(dòng)機(jī)對(duì)于加括號(hào)的正規(guī)式(s)，使用N(s)本身作為它的NFA2.4從正規(guī)式到有限自動(dòng)機(jī)本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍N(r)只有一個(gè)接受狀態(tài)，接受狀態(tài)沒(méi)有向外的轉(zhuǎn)換2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始

0ab

ab6782345

本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的每個(gè)狀態(tài)有一個(gè)用

的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個(gè)指向其它結(jié)點(diǎn)的

轉(zhuǎn)換2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始

0ab

ab6782345

2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0

ab678ab2345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開(kāi)始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解

(a|b)*ab的兩個(gè)NFA的比較12開(kāi)始a0abb手工構(gòu)造:算法構(gòu)造:2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始

0ab

ab6782345

小結(jié)：從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造NFA把NFA變成DFA將DFA化簡(jiǎn)存在其它辦法2.4從正規(guī)式到有限自動(dòng)機(jī)

用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號(hào)序列2.5詞法分析器的生成器Lex程序包括三個(gè)部分聲明％％翻譯規(guī)則％％輔助過(guò)程Lex程序的翻譯規(guī)則p1 {動(dòng)作1}p2 {動(dòng)作2}… …pn {動(dòng)作n}2.5詞法分析器的生成器例——聲明部分%{/*常量LT,LE,EQ,NE,GT,GE, WHILE,DO,ID,NUMBER,RELOP的定義*/%}/*

正規(guī)定義

*/delim [\t\n]ws {delim}+letter [A

Za

z]digit [0

9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\

]?{digit}+)?2.5詞法分析器的生成器例——翻譯規(guī)則部分{ws} {/*

沒(méi)有動(dòng)作，也不返回*/}while {return(WHILE);}do {return(DO);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num(); return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}2.5詞法分析器的生成器例——輔助過(guò)程部分installId(){ /*

把詞法單元裝入符號(hào)表并返回指針。 yytext指向該詞法單元的第一個(gè)字符， yyleng給出的它的長(zhǎng)度 */}installNum(){ /*

類(lèi)似上面的過(guò)程，但詞法單元不是標(biāo)識(shí)符而是數(shù)*/}2.5詞法分析器的生成器詞法分析器的作用和接口，用高級(jí)語(yǔ)言編寫(xiě)詞法分析器等內(nèi)容掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法非形式描述的語(yǔ)言

正規(guī)式正規(guī)式

NFA非形式描述的語(yǔ)言

NFANFA

DFADFA

最簡(jiǎn)DFA非形式描述的語(yǔ)言

DFA（或最簡(jiǎn)DFA）本章要點(diǎn)敘述下面的正規(guī)式描述的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA的狀態(tài)轉(zhuǎn)換圖

(1|01)*0*描述的語(yǔ)言是，所有不含子串001的0和1的串

3start001.1012剛讀過(guò)的不是0連續(xù)讀過(guò)一個(gè)0連續(xù)讀過(guò)不少于兩個(gè)0例題1bbbaabbaabbstartabbaaaaabababbabaababababababbbabaabb例題2用狀態(tài)轉(zhuǎn)換圖表示接受 (a|b)

a(a|b)(a|b)的DFA寫(xiě)出語(yǔ)言“所有相鄰數(shù)字都不相同的非空數(shù)字串”的正規(guī)定義

123031357106798035790123answer

(0|no_00)(no_00)

(no_0|

)|no_0

no_0

(1|no_0-11)(no_0-11)

(no_0-1|

)|no_0-1

...no_0-8

9將這些正規(guī)定義逆序排列就是答案例題3 下面C語(yǔ)言編譯器編譯下面的函數(shù)時(shí)，報(bào)告 parseerrorbefore‘else’longgcd(p,q)longp,q;{if(p%q==0)

/*thenpart*/ returnq 此處遺漏分號(hào) else

/*elsepart*/ returngcd(q,p%q);}例題43.1上下文無(wú)關(guān)文法3.1.1上下文無(wú)關(guān)文法的定義正規(guī)式能定義一些簡(jiǎn)單的語(yǔ)言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒(méi)有指定次數(shù)的重復(fù) 例：a(ba)5,a(ba)*正規(guī)式不能用于描述配對(duì)或嵌套的結(jié)構(gòu) 例1：配對(duì)括號(hào)串的集合 例2：{wcw|w是a和b的串}

3.1上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法是四元組（VT,VN,S,P）VT

: 終結(jié)符集合VN

: 非終結(jié)符集合S: 開(kāi)始符號(hào)，非終結(jié)符中的一個(gè)P

: 產(chǎn)生式集合，產(chǎn)生式形式:A

例({id,+,

,

,(,)},{expr,op},expr,P)expr

expr

op

expr expr

(expr)expr

expr expr

idop

+ op

3.1上下文無(wú)關(guān)文法簡(jiǎn)化表示expr

expr

op

expr |

(expr)|

expr|idop

+|

簡(jiǎn)化表示E

EAE|(E)|

E|idA

+|

3.1上下文無(wú)關(guān)文法3.1.2

推導(dǎo)把產(chǎn)生式看成重寫(xiě)規(guī)則，把符號(hào)串中的非終結(jié)符用其產(chǎn)生式右部的串來(lái)代替例 E

E+E|E

E|(E)|

E|id

E

E

(E)

(E+E)

(id+E)

(id+id)概念 上下文無(wú)關(guān)語(yǔ)言、等價(jià)的文法、句型記號(hào)S

*

、S

+w

3.1上下文無(wú)關(guān)文法例E

E+E|E

E|(E)|

E|id

最左推導(dǎo) E

lm

E

lm

(E)

lm

(E

+E)

lm

(id+E)

lm

(id+id)最右推導(dǎo)（規(guī)范推導(dǎo)） E

rm

E

rm

(E)

rm

(E+E)

rm

(E+id)

rm

(id+id)3.1上下文無(wú)關(guān)文法3.1.3分析樹(shù)例E

E+E|E

E|(E)|

E|idEE

()EEE+idid3.1上下文無(wú)關(guān)文法3.1.4二義性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 兩個(gè)不同的最左推導(dǎo)3.1上下文無(wú)關(guān)文法3.1.4二義性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 兩棵不同的語(yǔ)法樹(shù)EEE*+EEidididEEidE*+EEidid3.2

語(yǔ)言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語(yǔ)法說(shuō)明自動(dòng)產(chǎn)生高效的分析器可以給語(yǔ)言定義出層次結(jié)構(gòu)以文法為基礎(chǔ)的語(yǔ)言的實(shí)現(xiàn)便于語(yǔ)言的修改文法的問(wèn)題文法只能描述編程語(yǔ)言的大部分語(yǔ)法，不能描述語(yǔ)言中上下文有關(guān)的語(yǔ)法特征3.2

語(yǔ)言和文法3.2.1

正規(guī)式和上下文無(wú)關(guān)文法的比較正規(guī)式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12開(kāi)始a0abb3.2

語(yǔ)言和文法3.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法

詞法規(guī)則非常簡(jiǎn)單，不必用上下文無(wú)關(guān)文法對(duì)于詞法記號(hào)，正規(guī)式描述簡(jiǎn)潔且易于理解從正規(guī)式構(gòu)造出的詞法分析器效率高3.2

語(yǔ)言和文法從軟件工程角度看，詞法分析和語(yǔ)法分析的分離有如下好處簡(jiǎn)化設(shè)計(jì)編譯器的效率會(huì)改進(jìn)編譯器的可移植性加強(qiáng)便于編譯器前端的模塊劃分3.2

語(yǔ)言和文法能否把詞法分析并入到語(yǔ)法分析中，直接從字符流進(jìn)行語(yǔ)法分析若把詞法分析和語(yǔ)法分析合在一起，則必須將語(yǔ)言的注解和空白的規(guī)則反映在文法中，文法將大大復(fù)雜注解和空白由自己來(lái)處理的分析器，比注解和空格已由詞法分析器刪除的分析器要復(fù)雜得多3.2

語(yǔ)言和文法3.2.3

驗(yàn)證文法產(chǎn)生的語(yǔ)言G:S

(S)S|

L(G)=配對(duì)的括號(hào)串的集合3.2

語(yǔ)言和文法3.2.3

驗(yàn)證文法產(chǎn)生的語(yǔ)言G:S

(S)S|

L(G)=配對(duì)的括號(hào)串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對(duì)括號(hào)串歸納基礎(chǔ)：S

歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對(duì)的括號(hào)串歸納步驟：n步的最左推導(dǎo)如下：

S(S)S*(x)S*(x)y3.2

語(yǔ)言和文法3.2.3

驗(yàn)證文法產(chǎn)生的語(yǔ)言G:S

(S)S|

L(G)=配對(duì)的括號(hào)串的集合按串長(zhǎng)進(jìn)行歸納：配對(duì)括號(hào)串可由S推出歸納基礎(chǔ)：S

歸納假設(shè)：長(zhǎng)度小于2n的都可以從S推導(dǎo)出來(lái)歸納步驟：考慮長(zhǎng)度為2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y3.2

語(yǔ)言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式 id

id

(id+id)+id

id+id3.2

語(yǔ)言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

id

(id+id)+id

id+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)3.2

語(yǔ)言和文法expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id

id分析樹(shù)

id

id

id分析樹(shù)

3.2

語(yǔ)言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個(gè)最左推導(dǎo)：

stmt

ifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmt

ifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

3.2

語(yǔ)言和文法

無(wú)二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt3.2

語(yǔ)言和文法3.2.6消除左遞歸文法左遞歸 A

+Aa

直接左遞歸 A

Aa|b

串的特點(diǎn) ba...a消除直接左遞歸 A

bA

A

aA

|

3.2

語(yǔ)言和文法例

算術(shù)表達(dá)文法

E

E+T|T （T+T...+T） T

T

F|F （F

F...

F） F

(E)|id消除左遞歸后文法 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|id3.2

語(yǔ)言和文法非直接左遞歸 S

Aa|b

A

Sd|

先變換成直接左遞歸 S

Aa|b A

Aad|bd|

再消除左遞歸

S

Aa|b A

bdA

|A

A

adA

|

3.2

語(yǔ)言和文法3.2.7

提左因子有左因子的文法 A

1|

2提左因子 A

A

A

1|

2

3.2

語(yǔ)言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子 stmt

ifexprthenstmt

optional_else_part |other optional_else_part

elsestmt |

3.2

語(yǔ)言和文法3.2.8

非上下文無(wú)關(guān)的語(yǔ)言構(gòu)造L1={wcw|w屬于(a|b)*}標(biāo)識(shí)符的聲明應(yīng)先于其引用的抽象

L2={anbmcndm|n

0,m

0}形參個(gè)數(shù)和實(shí)參個(gè)數(shù)應(yīng)該相同的抽象

L3={anbncn|n

0}早先排版描述的一個(gè)現(xiàn)象的抽象

b

e

g

i

n：5個(gè)字母鍵，5個(gè)回退鍵，5個(gè)下劃線鍵3.2

語(yǔ)言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

L2={anbmcmdn|n

1,m

1}

S

aSd|aAd A

bAc|bcL

2={anbncmdm|n1，m1} S

AB A

aAb|ab

B

cBd|cd3.2

語(yǔ)言和文法L3

={anbn|n

1}

S

aSb|abL3

是不能用正規(guī)式描述的語(yǔ)言的一個(gè)范例

若存在接受L3

的DFAD，狀態(tài)數(shù)為k個(gè)設(shè)D讀完,

a,aa,

…,ak

分別到達(dá)狀態(tài)s0,s1,

…,sk至少有兩個(gè)狀態(tài)相同，例如是si和sj，則ajbi屬于L3

si…fs0標(biāo)記為ai的路徑標(biāo)記為bi的路徑標(biāo)記為aj

i的路徑…

…3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|13.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|1短語(yǔ)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短語(yǔ)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短語(yǔ)文法、上下文有關(guān)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短語(yǔ)文法、上下文有關(guān)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短語(yǔ)文法、上下文有關(guān)文法、上下文無(wú)關(guān)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短語(yǔ)文法、上下文有關(guān)文法、上下文無(wú)關(guān)文法3.2

語(yǔ)言和文法3.2.9

形式語(yǔ)言鳥(niǎo)瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短語(yǔ)文法、上下文有關(guān)文法、上下文無(wú)關(guān)文法、正規(guī)文法3.2

語(yǔ)言和文法例 L3＝{anbncn|n

1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過(guò)程如下：S

*an-1S(BC)n

1 用S

aSBCn-1次S

+an(BC)n

用S

aBC1次S

+anBnCn 用CB

BC交換相鄰的CBS

+anbBn

1Cn 用aB

ab1次S

+anbnCn

用bB

bbn-1次S

+anbncCn-1 用bC

bc1次S

+anbncn 用cC

cc

n-1次3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹(shù)SaCbSaCbcdSaCbc 不能處理左遞歸3.3

自上而下分析不能處理左遞歸的例子 算術(shù)表達(dá)文法

E

E+T|T T

T

F|F F

(E)|idEE+TE+TE+T………3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹(shù)SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹(shù)SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語(yǔ)義工作推倒重來(lái)3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹(shù)SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語(yǔ)義工作推倒重來(lái)、難以報(bào)告出錯(cuò)的確切位置3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹(shù)SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語(yǔ)義工作推倒重來(lái)、難以報(bào)告出錯(cuò)的確切位置、效率低3.3

自上而下分析3.3.2LL(1)文法對(duì)文法加什么樣的限制可以保證沒(méi)有回溯？先定義兩個(gè)和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*

時(shí)，規(guī)定

FIRST(

) 對(duì)A的任何兩個(gè)不同選擇

i

和

j，希望有 FIRST(

i)

FIRST(

j)=

若FIRST(

i)或FIRST(

j)含，還需增加條件3.3

自上而下分析3.3.2LL(1)文法對(duì)文法加什么樣的限制可以保證沒(méi)有回溯？先定義兩個(gè)和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*

時(shí)，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，a

VT} 如果A是某個(gè)句型的最右符號(hào)，那么$屬于FOLLOW(A)3.3

自上而下分析LL(1)文法 任何兩個(gè)產(chǎn)生式A

|

都滿足下列條件：FIRST(

)

FIRST(

)=

若

*

，那么FIRST(

)

FOLLOW(A)=

例如,對(duì)于下面文法，面臨a…時(shí)，第2步推導(dǎo)不知用哪個(gè)產(chǎn)生式S

A

BA

ab| a

FIRST(ab)

FOLLOW(A)

B

aCC…3.3

自上而下分析LL(1)文法 任何兩個(gè)產(chǎn)生式A

|

都滿足下列條件：FIRST(

)

FIRST(

)=

若

*

，那么FIRST(

)

FOLLOW(A)=

LL(1)文法有一些明顯的性質(zhì)沒(méi)有公共左因子不是二義的不含左遞歸3.3

自上而下分析例 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E

)={+,

}FRIST(T

)={

,

}FOLLOW(E)=FOLLOW(E

)={),$}FOLLOW(T)=FOLLOW(T

)={+,),$}FOLLOW(F)={+,

,),$}3.3

自上而下分析3.3.3遞歸下降的預(yù)測(cè)分析為每一個(gè)非終結(jié)符寫(xiě)一個(gè)分析過(guò)程這些過(guò)程可能是遞歸的例 type

simple |

id |array[simple]oftype simple

integer |char |numdotdotnum3.3

自上而下分析一個(gè)輔助過(guò)程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}3.3

自上而下分析voidtype(){ if((lookahead==integer)||(lookahead==char)|| (lookahead==num)) simple(); elseif(lookahead==

){match(

);match(id);} elseif(lookahead==array){ match(array);match(

[

);simple(); match(

]

);match(of);type(); } elseerror();}

type

simple |

id |array[simple]oftype3.3

自上而下分析voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}

simple

integer |char |numdotdotnum3.3

自上而下分析3.3.4非遞歸的預(yù)測(cè)分析a+b$輸入預(yù)測(cè)分析程序分析表M輸出

XYZ$棧3.3

自上而下分析非終結(jié)符輸

入

符

號(hào)

id

+

...EE

TE

E

E

+TE

T

T

FT

T

T

T

FT

F

F

id分析表的一部分3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$E

T

F

id+id$

T

FT

預(yù)測(cè)分析器接受輸入id

*

id+id的前一部分動(dòng)作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$E

T

F