編譯原理-課件第6講

3.2

語言和文法

3.2.7

提左因子有左因子的文法

A

1|2提左因子

A

A A

1|2

3.2

語言和文法

例

懸空else的文法

stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

3.2

語言和文法

例

懸空else的文法

stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

提左因子

stmt

ifexprthenstmt

optional_else_part |other optional_else_partelsestmt |3.2

語言和文法

3.2.8

非上下文無關(guān)的語言結(jié)構(gòu)L1={wcw|w屬于(a|b)*}

標(biāo)識符的聲明應(yīng)先于其引用的抽象

L2={anbmcndm|n0,m0}形參個數(shù)和實參個數(shù)應(yīng)該相同的抽象

L3={anbncn|n0}早先排版描述的一個現(xiàn)象的抽象L1={wcwR|w(a|b)*}

SaSa|bSb|cL2={anbmcmdn|n1,m1}

SaSd|aAd AbAc|bcL

2={anbncmdm|n1，m1} SAB AaAb|ab

BcBd|cdL3

={anbn|n

1}

SaSb|ab3.2

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個。

設(shè)D讀完,

a,aa,

…,ak

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

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

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

i的路徑…。。。…。。。3.2

語言和文法

3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外，此時S不出現(xiàn)在任何產(chǎn)生式的右側(cè)。2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短語文法上下文有關(guān)文法上下文無關(guān)文法正規(guī)式3.2

語言和文法

例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1CnS+anbnCn

S+anbncCn-1S+anbncn溫故知新正規(guī)式上下文無關(guān)文法功能有限四元組定義推導(dǎo)分析樹圖形化表示最左推導(dǎo)最右推導(dǎo)二義性消除二義性左遞歸消除左遞歸左因子消除左因子A

1|2A+Aa

0型文法1型文法2型文法3型文法3.3

自上而下分析

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

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc

不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語義工作推倒重來、難以報告出錯的確切位置、效率低3.3

自上而下分析

3.3.2LL(1)文法

對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT}

1、特別是，

*時，規(guī)定

FIRST(

) 2、如果AB,則FIRST(B)應(yīng)該加入FIRST(A) 對A的任何兩個不同的選擇i

和j，希望有 FIRST(i)FIRST(j)=但有一個前提，F(xiàn)IRST(i)和FIRST(j)都不含3.3

自上而下分析

3.3.2LL(1)文法

對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FOLLOW(A)={a|S

*…Aa…，aVT}

1、如果A是某個句型的最右符號，那么$屬于FOLLOW(A) 2、如果存在AB或AB且*，則FOLLOW(A)的全體元素要加入FOLLOW(B)3.3

自上而下分析引起回溯的原因：由于相同左部的產(chǎn)生式的右部First集交集不為空而引起回溯例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹2.由于相同左部VN的右部存在能*的產(chǎn)生式，且該VN的Follow集中含有其他產(chǎn)生式右部First集的元素

例：S->aAS|bA->bAS|

輸入串a(chǎn)b#

（因為A*

所以First(bAs)Follow(A)≠

）3.由于文法左遞歸引起回溯

例：S->Sa|b

輸入串baa#3.3

自上而下分析LL(1)文法 任何兩個產(chǎn)生式A|都滿足下列條件：

FIRST(

)FIRST()=若

*

，那么FIRST()FOLLOW(A)=LL(1)文法有一些明顯的性質(zhì)沒有公共左因子不是二義的不含左遞歸FIRST集合計算方法若Xa..，則將終結(jié)符ａ加入FIRST(X)中若X，則將加入FIRST(X)中若XY…，且Y屬于非終結(jié)符，則將FIRST(Y)\{}加入到FIRST(X)中若XY1Y2..YK,且Y1,Y2,..Yi-1都是非終結(jié)符，且Y1,Y2,..Yi-1的FIRST集合中均包含，則將FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特別地，若Y1~YK均有產(chǎn)生式，則將加到FIRST(X)中。FIRST集合及FOLLOW集合的計算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW集合計算方法對文法開始符號S,置$于FOLLOW(S)中。若有AB，則將FIRST()\{}加入FOLLOW(B)中。（此處可以為空）若AB或AB,且*（即屬于FIRST()）,則將

FOLLOW(A)加入FOLLOW(B)中（此處可以為空）。FIRST集合及FOLLOW集合的計算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|id3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

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

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

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

自上而下分析

例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}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)={),$}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)={+,),$}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ù)測分析為每一個非終結(jié)符寫一個分析過程這些過程可能是遞歸的例： type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum3.3

自上而下分析

一個輔助過程procedurematch(t:token);begin iflookahead==tthen lookahead:=nexttoken() elseerror()end;3.3

自上而下分析

proccduretype;begin iflookaheadin{integer,char,num}then simple() elseiflookahead=thenbegin match();match(id) end elseiflookahead=arraythenbegin match(array);match([);simple(); match(]);match(of);type() end elseerror()end;type

simple |id |array[simple]oftype3.3

自上而下分析

proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;simpleinteger |char |numdotdotnumprocedurematch(t){if當(dāng)前輸入符號＝tthen取下一個符號作為當(dāng)前輸入符號else報錯。}procedureA{ if當(dāng)前符號=‘a(chǎn)’then {match(a);調(diào)用A;} elsereturn;}procedureB{ if當(dāng)前符號=‘b’then {match(b);調(diào)用B;} elseif當(dāng)前符號=‘c’thenreturn;else報錯。

}procedureS{ switch當(dāng)前符號

case‘a(chǎn)’:調(diào)用A; case‘b’:調(diào)用B;}SA|BAaA|

BbB|c

aaaaa,bbbbcaaaaa,aa,bbbc,bbc當(dāng)非終結(jié)符的產(chǎn)生式有多種選擇，即意味著分析過程有不同的展開方式。而我們只能根據(jù)當(dāng)前輸入符號來決定采用哪種展開方式（選擇），這樣就有了FIRST（）函數(shù)。1、LL(1)文法的自上而下分析及FIRST函數(shù)理解3.3

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

XYZ$棧3.3

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

入

符

號

id+*

...EE

TE

E

E

+TE

T

T

FT

T

T

T

*FTF

F

id3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

$ETF*

*

id+id$

T

*FT

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$$ETF*

*

id+id$T

*FT

$ETF

id+id$

預(yù)測分析器接受輸入id*id+id的動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$$ETF*

*

id+id$T

*FT

$ETF

id+id$$ETidid+id$F

id預(yù)測分析器接受輸入id*id+id的動作

棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EEE$2、LL(1)文法的自上而下的非遞歸分析方法理解深度優(yōu)先構(gòu)造分析樹E

TEE

+TE|T

FTT

*FT

|F

(E)|id輸入：id*id棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

TE’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

FT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

ididT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

idT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

F*FT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FFT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FididT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FidT’E’$棧

輸

入

輸

出

$E

id*id$

$ET

id*id$

E

TE

$ET