學(xué)習(xí)-編譯原理

2本章主要內(nèi)容語法分析程序的功能自頂向下的語法分析及其 的問題LL(1)分析法遞歸下降分析程序分析程序3語法分析的位置詞法分析模塊語法分析模塊符號(hào)表管理模塊語義分析模塊中間代碼生成模塊中間代碼優(yōu)化模塊目標(biāo)代碼生成模塊目標(biāo)代碼優(yōu)化模塊出錯(cuò)處理模塊44.1

語法分析的功能語法分析程序的輸入和輸出輸入:輸入串––由單詞符號(hào)組成的有限序列輸出:語法分析樹,出錯(cuò)信息功能按文法產(chǎn)生式,識(shí)別輸入串是否為合法的句子:從文法的開始符號(hào)出發(fā)推導(dǎo)出輸入串

/建立一棵與句子匹配的語法分析樹5語法分析程序完成語法分析的程序叫做語法分析程序/語法分析器/分析器ParserSyntax

yzer用什么文法描述程序設(shè)計(jì)語言的語法結(jié)構(gòu)?6語法分析的方法自頂向下top-down文法產(chǎn)生語言從文法開始符號(hào)出發(fā),向下推導(dǎo),推出句子自上而下地建立語法分析樹方法:

遞歸下降分析器,

分析器自底向上bottom-up自

識(shí)別語言自下而上地建立語法分析樹方法:算符優(yōu)先分析,LR(0),SLR(1),LALR(1),LR(1)74.2

自頂向下的語法分析復(fù)習(xí):一個(gè)上下文無關(guān)文法G

是一個(gè)四元組,G=(VT,VN,S,P)VT

—終結(jié)符的集合一個(gè)非空有限集合VN

—非終結(jié)符的集合一個(gè)非空有限集合VN

∩

VT

=

ΦS—開始符號(hào)S

∈

VNP—產(chǎn)生式集合(有限)產(chǎn)生式形如

A α

,

其中A∈VN

,

α∈(VN∪VT)*S

至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次8復(fù)習(xí)—推導(dǎo)(1)根據(jù)產(chǎn)生式對(duì)符號(hào)串進(jìn)行變換的過程Ａ?γ

是文法G的一個(gè)產(chǎn)生式,且α、β∈(VT∪VN)*,稱αAβ

直接推導(dǎo)/派生(Derive)出αγβ,也稱αγβ

直接歸約(Reduce)為αAβ記為

αAβ

αγβ9復(fù)習(xí)—推導(dǎo)(2)如果存在一個(gè)直接推導(dǎo)序列α0

α1

α2

…

αn

(n>0)稱這個(gè)序列是一個(gè)從α0到αn的長度為n的推導(dǎo),簡(jiǎn)稱推導(dǎo),或者說α0可推導(dǎo)出αnαn可歸約到α0記作

α0+

αnα0

*αn從α0出發(fā),經(jīng)0步或若干步,可推導(dǎo)出αn意味著:或者α0

=αn

,或者α0

+αn10復(fù)習(xí)—最左推導(dǎo),左句型最左推導(dǎo)(leftmost

derivations)推導(dǎo)過程的每一步總是替換出現(xiàn)在最左邊的非終結(jié)符若句型α1

通過最左推導(dǎo)推出α2則記作α1

lm*

α2左句型若

S

lm*

α

,

S是文法的開始符號(hào),則稱α

是當(dāng)前文法的一個(gè)左句型11自頂向下分析自頂向下分析對(duì)任何給定的輸入串,

試圖用一切可能的辦法,從文法開始符號(hào)出發(fā),

自上而下地為輸入串建立一棵語法分析樹為輸入串尋求

最左推導(dǎo)本質(zhì):試探例:文法G[S]S?

x

A

yA

?

**

|

*輸入串:x

*

y試探匹配輸入串的過程匹配—繼續(xù),不匹配—退回12自頂向下分析的問題文法應(yīng)當(dāng)無二義性文法不能含有左遞歸E

?

E

+

T

|

TT

?

T

*

F

|

FF

?

i

|

(

E

)推導(dǎo)過程會(huì)變成無窮循環(huán)過程設(shè)法消除回溯虛假匹配例:x

**

y避免“窮盡一切可能的試探”134.3

LL(1)分析法一種有效的、無回溯的自頂向下分析方法LL(1)文法第一個(gè)L

表示從左向右掃描輸入符號(hào)串第二個(gè)L

表示生成最左推導(dǎo)1

表示讀入一個(gè)符號(hào)可確定下一步推導(dǎo)文法的改寫消除文法二義性消除左遞歸提取左因子14消除文法二義性有時(shí)

可以對(duì)一個(gè)二義性文法進(jìn)行改寫,消除它的二義性“未定的else”文法“dangling

else”

grammarstmt

?

if

expr

then

stmtse

stmt｜

if

expr

then

stm｜

other下列語句的分析樹?if

E1

then

if

E2then

S1

else

S215if

E1

then

if

E2

thenS1

else

S2stmtifelsethenifstmtthenexprE1exprE2stmtS1stmtS2stmtifstmtthenexprif

expr

then

stmtE1E2S1S216if

E1

then

if

E2

thenS1

else

S2stmtifelsethenifstmtthenexprE1exprE2stmtS1stmtS2stmtifelsethenifstmtthenexprE1exprE2stmtS1stmtS217改寫文法規(guī)定else與最近的then

匹配stmt

?

matched｜

unmatchedmatched

?

if

exprthen

matched

else

matched｜

otherunmatched

?

if

expr

then

stmt｜

if

expr

then

matched

else

unmatched迫使then

和else

之間必須有一個(gè)matched語句if

E1

then

if

E2

then

S1

else

S218消除左遞歸左遞歸如果文法G

具有一個(gè)非終結(jié)符A

使得對(duì)某個(gè)符號(hào)串α存在A

+Aα,

則稱G

是左遞歸的直接左遞歸,

間接左遞歸自頂向下分析法不能處理左遞歸例:A

?Aα

|

β,α和β是不以A開始的終結(jié)符和非終結(jié)符組成的符號(hào)串A

βA

Aα

β

αA

Aα

Aαα

βααA

Aα

Aαα

Aααα

βααα…A

?

βA’A’

?

αA’

|

ε19課堂練習(xí)考慮下面的算術(shù)表達(dá)式文法TFE

?

E

+

T

|

T?

Tid*|F(|EF)消除E和T的直接左遞歸E

?

T

E’E’

?

+

T

E’

|

εT

?

F

T’T’?

*

F

T’

|

εF

?

id

|

(

E

)20消除直接左遞歸的一般方法假定關(guān)于A的全部產(chǎn)生式是A

?

Aα1

|

Aα2

|

…

|

Aαm

|

β1

|

β2

|

…

|

βn其中,βi

不以A打頭,i=1,2,…,nαj

不等于ε,j=1,2,…,m可以將上面的產(chǎn)生式改寫為A?

β1A’

|

β2A’

|

…

|

βnA’A’

?

α1A’

|

α2A’

|

…

|

αmA’

|

ε消除直接左遞歸21例:間接左遞歸的消除例:文法G[S]S

?

A

c｜c(diǎn)A

?

B

b｜bB?

S

a｜a方法將B

代入,A

?S

a

b｜a

b｜b將A

代入,S

?S

a

b

c｜a

b

c｜b

c｜c(diǎn)消除直接左遞歸S

?

a

b

c

S’｜b

c

S’｜c(diǎn)

S’S’

?

a

b

c

S’｜ε刪除A

?

S

a

b｜a

b｜bB

?

S

a｜a消除左遞歸算法(p.125)22提取左因子例:不存在左因子的文法stmt

?

if

expr

then

stmse

stmt|

while

expr

do

stmt|

begin

stmt_list

end任何兩個(gè)候選式,

沒有公共真前綴例:存在左因子的文法stmt

?

if

expr

then

stmt｜

if

expr

then

stm

se

stmt｜

other存在左因子

if

expr

then

stmt妨礙自頂向下方法的使用23左因子提取方法對(duì)于所有形如A

?

αβ1

|

αβ2

|

...

|

αβn

|

γ1

|

γ2

|

…

|

γm的規(guī)則,每個(gè)γ不以α打頭,改寫為:A

?

αA’

|

γ1

|

γ2

|…|γmA’?β1

|

β2

|

...

|

βn例:stmtse

stmtif

expr

then

stmt|

if

expr

then

stm|

other改寫為:stmt

?

if

expr

then

stmt

S’ |

otherS’

?

ε

|

else

stmt24集(1)考慮下面的文法,

如何分析

b

cS

?

A

c

|

BA

?

a

|

bB

?

d考慮下面的文法,

如何分析

b

cS

?

A

c

|

BA

?

a

|

bB?

b

|

d25集(2)考慮:文法G[S],無左遞歸,無左因子?S

lm*

w

A

…

,

w

∈VT*A

?

α

|

β選擇哪個(gè)候選式進(jìn)行下一步推導(dǎo)?集定義?(α)

=

{

a

|

α

*

a

…

,

a∈VT

}α的所有首符號(hào)

(選擇產(chǎn)生式的依據(jù))并且,

若

α

*

ε,

則ε∈

(α)α集的作用是什么？a

……26(X)的計(jì)算方法(1)對(duì)每個(gè)文法符號(hào)X

∈VN

∪VT

,(X)不再擴(kuò)大(X)

={

X

}連續(xù)使用下面規(guī)則,直到1)若X

∈VT

,則2)若X

∈VN

,若有產(chǎn)生式X

?a…,則將

a

加入

(X)若有產(chǎn)生式X

?ε

,則將

ε

加入

(X)27(X)的計(jì)算方法(2)3)若有產(chǎn)生式X

?Y

…,且Y

∈VN

,則將

(

Y

)

的

非ε

元素加入(X)若有產(chǎn)生式X

?Y1

…Yk

,如果對(duì)于某個(gè)

i，使得

Y1

...

Yi-1

*

ε，則將

(

Yi

)

的所有

非ε

元素加入到(X)中若

Y1

...

Yk

*

ε,

則將

ε

加入到

(X)28例:表達(dá)式文法非終結(jié)符的集E

?TE’E’

?

+

T

E’

|

εT

?

F

T’T’

?

*

F

T’

|

εF

?

id

|(

E

)?????(

F

)

=

{

‘(’,

id

}(

T’

)

=

{‘*’,

ε

}(

T

)

= (

F

)

=

{

‘(’,

id

}(

E’

)

=

{

‘+’,

ε

}(

E

)

= (

T

)

=

{‘(’,

id

}29求(α)的算法設(shè)α=X1

…Xn初值?(α)

=(X1)

-

{ε}k

=

1循環(huán)WHILE

(ε∈?(α)

=(Xk)

)

∧

(

k

<

n

)

DO(α)∪

( (Xk+1)

-

{ε})k=

k

+1結(jié)束處理IF

(k

=

n)

∧

(ε∈(α)

=(Xn)THEN(α)

∪

{ε}30例:

表達(dá)式文法各產(chǎn)生式右部的

集思考:對(duì)于E’

?

+

T

E’

|

ε僅僅考慮集夠不夠?產(chǎn)生式右部的

集E

?

T

E’{‘(’

,

id

}E’

?

+

T

E’{

‘+’

}E’

?

ε{

ε

}T

?

F

T’{‘(’

,

id

}T’

?

*

F

T’{

*

}T’

?

ε{

ε

}F

?

id{

id

}F

?

(

E

){

‘(’

}31FOLLOW集FOLLOW集定義FOLLOW

(A)

=

{

a

|

S

*

…

A

a

…

,

a∈VT

}A

的后續(xù)符號(hào)S…

A

a

...32FOLLOW集的計(jì)算方法對(duì)于所有非終結(jié)符,重復(fù)進(jìn)行以下計(jì)算,直到每個(gè)非終結(jié)符的FOLLOW集不再增大為止:1)對(duì)于開始符號(hào)S,將#加入到FOLLOW(

S)#是句子的結(jié)束符2)若A

?α

B

β,則將

(

β

)

的非ε元素加入

FOLLOW(B)3)如果A

?αB

,或A

?αBβ

且β

*

ε,A≠B,則將

FOLLOW(A)的所有元素加入FOLLOW(B)33例:表達(dá)式文法的FOLLOW

集FOLLOW(

E

)

= {

‘)’,

#

}FOLLOW(

E’

)

=

FOLLOW(

E

)

=

{

‘)’,

#

}FOLLOW(

T

)

= {

‘+’,

‘)’,

#

}FOLLOW(

T’

)

=

FOLLOW(

T

)

=

{

‘+’,

‘)’,

#

}FOLLOW(

F

)

=

{

‘*’,

‘+’,

‘)’,

#

}E

?

T

E’E’

?

+

T

E’

|

εT

?

F

T’T’

?

*

F

T’

|

εF

?

id

|(

E

)(

E

)

= (

T

)

=

{

‘(’,

id

}(

E’

)=

{

‘+’,

ε}(

T

)= (

F

)

=

{

‘(’,

id

}(

T’

)=

{

‘*’,

ε}(

F

)

=

{

‘(’,

id

}34LL(1)文法LL(1)文法第一個(gè)L

表示從左向右掃描輸入符號(hào)串第二個(gè)L

表示生成最左推導(dǎo)1

表示讀入一個(gè)符號(hào)可確定下一步推導(dǎo)表示了不帶回溯的自頂向下方法能夠處理的文法文法G

是LL(1)文法,當(dāng)且僅當(dāng)對(duì)于G

的每個(gè)非終結(jié)符A

的任何兩個(gè)不同的產(chǎn)生式A

?α｜β

滿足1) (α)

∩ (β)

=

2)如果β

*

ε,則FISRT(α)∩FOLLOW(A)=思考:

A的候選式中,

最多允許幾個(gè)可以推導(dǎo)出ε?35例:表達(dá)式文法是LL(1)文法E?

TE'E'

?

+TE'｜εT?

F

T'T'

?

*

F

T'｜εF

?

(E

)｜id考查F: ‘(’和id

不同T’: ‘*’不在FOLLOW(

T’)={‘+’,‘)’,‘#’}E’:

‘+’不在FOLLOW(

E’)={‘)’,‘#’}FOLLOW(

E)

= {

‘)’,

#

}FOLLOW(

E'

)

={

‘)’,

#

}FOLLOW(

T

)

= {

‘+’,

‘)’,

#

}FOLLOW(

T'

)

=

{

‘+’,

‘)’,

#}FOLLOW(

F

)

=

{

‘*’,

‘+’,

‘)’,

#

}36非LL(1)文法的非確定性x

A

y*例

文法S

?

x

AyA

?

**

|

*句子:

x

* *

yS

Sx

A

y**37非確定性的解決方法1)采用回溯算法過于復(fù)雜效率低2)改寫文法將非

LL(1)文法改寫為等價(jià)的

LL(1)文法消除二義性消除左遞歸提取左因子檢查改寫后文法是否為LL(1)文法無法改寫文法過于復(fù)雜,無法用不帶回溯的自頂向下方法處理38例題(1)文法G[S]S

?

A

a

|

bA

?

S

BB?

a

b問題試對(duì)文法進(jìn)行改寫,并判斷改寫后的文法是否為LL(1)文法對(duì)于一個(gè)文法,若消除左遞歸、提取左因子之后,是否一定是LL(1)文法?––不一定!觀察是否有直接左遞歸,間接左遞歸,左因子39例題(2)改寫方法一用A

?S

B

的右部替換S

?A

a

|

b

右部中的AS

?

SB

a

|

bB

?

a

b消除左遞歸,得S

?

b

S’S’

?

B

a

S’

|

εB

?

a

b沒有左因子,

檢查是否為LL(1)?(B

a

S’)

∩

FOLLOW(S’)

=

{a}

∩

{#}

=

Φ是LL(1)文法S

?

A

a

|

bA

?

S

BB?

a

b40例題(3)改寫方法二用S

?A

a

|

b

的右部替換A?S

B

右部中的SS

?

A

a

|

bA

?

A

a

B

|

b

BB

?

a

b消除左遞歸,得S

?

A

a

|

bA

?

b

B

A’A’

?

a

B

A’

|

εB

?

a

bS

?

A

a

|

bA

?

S

BB?

a

b41例題(4)S

?

A

a

|

bA

?

b

B

A’A’

?

aB

A’

|

εB?

a

b沒有左因子,

檢查是否為LL(1)關(guān)于S,(b)(A

a)

∩=

∩



=



!=

Φ關(guān)于A’,(a

B

A’)

∩

FOLLOW(A’)=

{a}

∩

{a}

=

{a}

!=

Φ不是LL(1)文法!–消除左遞歸、提取左因子,不能保證得到LL(1)文法424.4

遞歸子程序法為LL(1)文法構(gòu)造一個(gè)不帶回溯的自頂向下分析程序一組遞歸過程每個(gè)過程

–

文法的一個(gè)非終結(jié)符將LL(1)文法改寫為擴(kuò)充的BNF(EBNF)BNF

–

Backus-Naur

form

/

Backus

normalformA

metasyntaxused

to

express

context-freegrammars<symbol>

::=

<expression

with

symbols>EBNF–

extended

Backus-Naur

form{a

}表示0

次或若干次出現(xiàn)[a

]表示0

次或1

次出現(xiàn)按照EBNF

編制語法圖,并化簡(jiǎn)按照語法圖編制遞歸子程序43例:將表達(dá)式文法改寫為EBNFE?

T

E’E’

?

{

+

T

}T?

F

T’T’

?

{

*

F

}F

?

id

|

(

E)化簡(jiǎn)為E

?

T

{

+

T

}T

?

F{

*

F

}F

?

id

|

(

E)E

?

T

E’E’

?

+

T

E’

|

εT

?

F

T’T’

?

*

F

T’

|

εF

?

id

|(

E

)44例:為非終結(jié)符編制語法圖ET{+T}TF{*F}F?(E)｜id+TTEid(

E)F*FFT45簡(jiǎn)化的語法圖+TE*FTidEF()46遞歸子程序法(1)編寫文法、消除二義性消除左遞歸和提取左因子改寫文法求每個(gè)候選式的

集求每個(gè)非終結(jié)符的FOLLOW

集檢查是不是LL(1)

文法若不是LL(1),

說明文法的復(fù)雜性超過自頂向下方法的分析能力47遞歸子程序法(2)將LL(1)

文法改寫為EBNF,并化簡(jiǎn)按照EBNF

編制語法圖,并化簡(jiǎn)按照語法圖,編寫程序算法為每個(gè)非終結(jié)符設(shè)置一個(gè)子程序,按照語法圖編寫控制結(jié)構(gòu)按照

集識(shí)別終結(jié)符,

調(diào)用非終結(jié)符的子程序48表達(dá)式文法的分析器(1)E

的子程序match('+');//處理終結(jié)符

‘+’//T的過程調(diào)用procedure

exp;beginterm;

//T的過程調(diào)用while

lookhead='+'do

//lookhead:當(dāng)前符號(hào)begin

//當(dāng)前符號(hào)等于

‘+’時(shí)6.term;end;end;+TE49表達(dá)式文法的分析器(2)T

的子程序begin

//當(dāng)前符號(hào)等于‘*’時(shí)//處理終結(jié)符‘*’//F的遞歸調(diào)用factor

;

//F的過程調(diào)用while

lookhead='*'domatch(

'*'

)

;factor

;procedure

term;begin3.4.5.6.7.end

;end;*FT50表達(dá)式文法的分析器(3)F

的子程序begin //

當(dāng)前符號(hào)是

‘(’match(

'('

); //

處理終結(jié)符

‘(’exp;

//

E

的遞歸調(diào)用match(

')'); //處理終結(jié)符‘)’endelse

if

lookhead

=ID

thenmatch(

ID

) //處理終結(jié)符ID//出錯(cuò)處理procedure

factor;beginif

lookhead

=

'('

then4.5.6.7.8.9.10.elseerror

;end;idF

(

E)51表達(dá)式文法的分析器(4)主程序beginlookhead:=nexttoken();

//調(diào)詞法分析程序exp;

//E的過程調(diào)用match(‘#’);end.處理終結(jié)符的子程序procedure

match

(t

:

token);beginif lookhead

=

t

thenlookhead

:=

nexttoken(

)elseerror;

//出錯(cuò)處理程序end;52遞歸子程序法優(yōu)缺點(diǎn)優(yōu)點(diǎn)直觀、簡(jiǎn)單、可讀性好便于擴(kuò)充缺點(diǎn)遞歸算法的實(shí)現(xiàn)效率低處理能力相對(duì)有限通用性差,

不便于自動(dòng)生成534.5分析程序輸入緩沖區(qū)棧控制程序P.132產(chǎn)生式序列分析表M二維數(shù)組[非終結(jié)符,終結(jié)符a]表項(xiàng)用于指示產(chǎn)生式或出錯(cuò)標(biāo)志54程序結(jié)構(gòu)通用結(jié)構(gòu)和控制算法適用于各種語言的處理分析表內(nèi)容不同不同語言使用內(nèi)容不同的分析表表驅(qū)動(dòng)(table-driven)優(yōu)點(diǎn)效率高便于 、自動(dòng)生成55非終結(jié)符輸入符號(hào)id+*()#EE’TT’FE

?

T

E’E’

?

+

TE’

|

εT

?

F

T’T’

?

*

F

T’

|

εF

?

id

|

(

E

)例:表達(dá)式文法的分析表

M(

T

E’

)

=

{

‘(’,

id

} //E(

+

T

E'

)

=

{

‘+’} //E’(

F

T’

)

=

{

‘(’,

id

} //T(

*

F

T'

)

=

{

‘*’} //

T’(

id

)

=

{

id

} //F(

(

E

)

)

=

{

‘(’

} //FFOLLOW(

E'

)

=

{

‘)’,

#

}FOLLOW(

T'

)

=

{

‘+’,

‘)’,

#

}56非終結(jié)符輸入符號(hào)id+*()#ET

E’T

E’E’?

+

T

E’?ε?εTF

T’F

T’T’?ε*

F

T’?ε?εFid(

E

)E

?

T

E’E’

?

+

T

E’

|

εT

?

F

T’T’

?

*

F

T’

|

εF

?

id

|

(

E

)例:表達(dá)式文法的分析表

M(

E

)

=

{

‘(’,

id

}(

E'

)

=

{

‘+’,

ε}(T

)

=

{

‘(’,

id

}(

T'

)

=

{

‘*’,

ε}(

F

)

=

{

‘(’,

id

}FOLLOW(

E'

)

=

{

‘)’,

#

}FOLLOW(

T'

)

={

‘+’,

‘)’,

#

}57分析表M的構(gòu)造算法1.

對(duì)于每一產(chǎn)生式

A?α

,執(zhí)行

2.

和

3.2.

對(duì)于每個(gè)終結(jié)符

a

∈

(α),將A?α

加至M[A,a]中3.

若ε

∈(α),

即α

*

ε

,則對(duì)任何b

∈FOLLOW(A),將A?α

加至M[A,b]中4.

將所有無定義的M[A,

a]標(biāo)上錯(cuò)誤標(biāo)志58例:分析id+id

*id

的過程(1)棧#E#E'T#E'T'F#E'T'id#E'T'#E'輸入緩沖區(qū)

輸出id+id*id#id+id*id#

E.?

Tid+id*id#

E'

T

?id+id*id#

F

T'+id*id#

F.?+id*id#

T'?id

ε右部