編譯原理第四章課件

1編譯原理主講教師:雷向東2023/7/212第四章語(yǔ)法分析——自上而下分析4.1語(yǔ)法分析器的功能語(yǔ)法分析器的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)法分析方法可分為兩類：一類是自上而下分析法，另一類是自下而上分析法。2023/7/21語(yǔ)言的語(yǔ)法結(jié)構(gòu)是用上下文無(wú)關(guān)文法描述的。因此，語(yǔ)法分析器的工作本質(zhì)上就是按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。這里所說(shuō)的輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。對(duì)一個(gè)文法，當(dāng)給你一串（終結(jié)）符號(hào)時(shí)，怎樣知道它是不是該文法的一個(gè)句子（“程序”）呢？這就要判斷，看是否能從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串?；蛘撸瑥母拍钌现v，就是要建立一棵與輸入串相匹配的語(yǔ)法分析樹(shù)。2023/7/2144.2自上而下分析面臨的問(wèn)題自上而下分析法就是從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。例4.1假設(shè)文法G[S]

S→xAy

A→**

A→*

識(shí)別輸入串α

=x*y是否該文法的句子。2023/7/215

S S S x A y x A y **推導(dǎo)過(guò)程：S

xAy

x**y。用非終結(jié)符A的第一個(gè)候選告失敗。應(yīng)該回溯，使用A的其它候選。自上而下構(gòu)造α

的語(yǔ)法樹(shù)。(a)(b)(c)2023/7/216為了回溯，把A的第一個(gè)候選所發(fā)展的子樹(shù)注銷掉，試探A的第二個(gè)候選。

S x A y *匹配成功，證明了α是一個(gè)句子。*7上述自上而下分析面臨的問(wèn)題:文法的左遞歸性質(zhì)問(wèn)題一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符PPPα

含有左遞歸的文法將使上述的自上而下分析過(guò)程陷入無(wú)限循環(huán)。例如文法規(guī)則：A→AaAAaAa…遞歸展開(kāi)。+2023/7/218回溯問(wèn)題做了很多語(yǔ)義工作，最后必須回頭，推倒重來(lái)，既麻煩又費(fèi)時(shí)間。虛假匹配現(xiàn)象當(dāng)最終報(bào)告分析不成功，難于知道輸入串中出錯(cuò)的確切位置。2023/7/21自上而下分析方法不允許文法含有任何左遞歸。為構(gòu)造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸法，并找出克服回溯的充分必要條件。下面將討論消除文法左遞歸和克服回溯的方法。

4.3LL(1)

分析法2023/7/2110消除直接左遞歸假設(shè)關(guān)于非終結(jié)符P的規(guī)則為

P→Pα|β

其中,β不以P打頭。把P的規(guī)則改寫為如下非直接左遞歸形式：

P→βP

’

P→αP

’|這種形式和原來(lái)的形式是等價(jià)的，也就是說(shuō)，從P推出的符號(hào)串是相同的。它們推出的符號(hào)串都是{β，βα，βαα，βααα，…}。

2023/7/2111例4.2文法G[E]E→E+T|TT→T*F|FF→(E)|i消除直接左遞歸

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i2023/7/2112消除回溯，提左因子假設(shè)關(guān)于非終結(jié)符A的全部規(guī)則為

A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm其中，每個(gè)γ不以δ開(kāi)頭。把A的規(guī)則改寫為如下形式：

A→αA’|γ1|γ2|…|γmA’→β1|β2|…|βn

2023/7/21LL(1)分析條件為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無(wú)疑的。也就是說(shuō)，若此候選獲得成功匹配，那么，這種匹配決不會(huì)是虛假的；若此候無(wú)法完成匹配任務(wù)，則任何其它候選也肯定無(wú)法完成。換句話說(shuō)，假定現(xiàn)在輪到非終結(jié)符A去執(zhí)行匹配（或稱識(shí)別）任務(wù)，A共有n個(gè)候選α1，α2，…，αn，即A→α1|α2|…|αn。A所面臨的第一個(gè)輸入符號(hào)為a，如果A能夠根據(jù)不同的輸入符號(hào)指派要應(yīng)的候選αi作為全權(quán)代表去執(zhí)行任務(wù)，那就肯定無(wú)需回溯了。2023/7/21

在不得回溯的前提下，文法不得含有左遞歸。令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選A定義它的終結(jié)首符集FIRST(α)為

FIRST(α)={a|α*a,a∈VT,α,∈V*}

特別是，若*=>ε，則規(guī)定ε∈FRIST()。2023/7/21換名話說(shuō)，F(xiàn)IRST(α)是α的所有可能推導(dǎo)的開(kāi)頭終結(jié)符或可能的ε。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選i和j

FIRST(α)∩FIRST(β)=那么，當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的α。2023/7/21當(dāng)非終結(jié)符A面臨輸入符號(hào)a，且a不屬于A的任意候選首符集，但A的某個(gè)候選首符集包含ε時(shí)，就一定可以A自動(dòng)匹配？如果我們仔細(xì)來(lái)考慮一下的話，就不難發(fā)現(xiàn)，只有當(dāng)a是允許在文法某個(gè)句型中跟A后面的終結(jié)符時(shí)，才可能允許A自動(dòng)匹配，否則，a在這里的出現(xiàn)就是一種語(yǔ)法錯(cuò)誤。2023/7/21假定S是文法G的開(kāi)始符號(hào)，對(duì)于G的任何非終結(jié)符A，定義FOLLOW(A)={aS*…Aa…且a∈VT}特別是，若S*…A，則規(guī)定#FOLLOW(A)。換句話說(shuō)，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。因此，當(dāng)非終結(jié)符A面臨輸入符號(hào)a，且a不屬于A的任意候選首符集但A的某個(gè)候選集包含ε時(shí)，只有當(dāng)aFOLLOW(A)，才可能允許A自動(dòng)匹配。2023/7/21184.4預(yù)測(cè)分析程序預(yù)測(cè)分析表的構(gòu)造FIRST集和FOLLOW集的定義:設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法

FIRST(α

)={a|α*a,a∈VT,α

,∈V*}

若*=>ε則規(guī)定ε∈FRIST()。

FOLLOW(A)={aS*…Aa…且a∈VT}

若S*…A，則#∈FOLLOW(A)。2023/7/2119計(jì)算FIRST集方法對(duì)于文法符號(hào)X1.若XV，則FIRST(X)={X}；2.若XVN，且有產(chǎn)生式Xa…，則把a(bǔ)加入到FIRST(X)中；若X也是一條產(chǎn)生式,則把也加到FIRST(X)中；2023/7/21203.若XY…是一個(gè)產(chǎn)生式且YVN，則把FIRST(Y)中的所有非元素都加到FIRST(X)中；若XY1Y2…YK

是一個(gè)產(chǎn)生式，Y1,Y2,…,Yi-1都是非終結(jié)符，而且，對(duì)于任何j,1≤j≤i-1,FIRST(Yj)都含有，則把FIRST(Yj)中的所有非元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)(j=1,2,…,K)均含有，則把加到FRIST(X)中。2023/7/2121計(jì)算FOLLOW集方法1.對(duì)于文法的開(kāi)始符號(hào)S,置#于FOLLOW(S)中；2.若Ａ→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)\{}加至FOLLOW(B)中；3.若Ａ→αB是一個(gè)產(chǎn)生式,或Ａ→

αBβ是一個(gè)產(chǎn)生式而β*

(即FIRST(β))，則把FOLLOW(A)，加至FOLLOW(B)中。*2023/7/2122例4.3假設(shè)文法G[E]

E→E+T|TT→T*F|FF→(E)|i消除直接左遞歸

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i

2023/7/2123計(jì)算FIRST集和FOLLOW集FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}FOLLOW(E)=FOLLOW(E’)={),#}FOLLOW(T)=FOLLOW(T’)={+,),#}FOLLOW(F)={+,*,),#}2023/7/2124預(yù)測(cè)分析表構(gòu)造算法1.對(duì)文法G的每個(gè)產(chǎn)生式Ａ→執(zhí)行第二步和第三步；2.對(duì)每個(gè)終結(jié)符aFIRST()，把Ａ→

加至[A,a]中，3.若FIRST()，則對(duì)任何bFOLLOW(A)，把Ａ→

加至[A,b]中，4.把所有無(wú)定義的[A,a]標(biāo)上“出錯(cuò)標(biāo)志”。2023/7/2125i+*()$EE→TE’E→TE’E’E’→+TE’E’→εE’→ε

TT→FT’T→FT’T’T’→ε

T→*FT’T’→ε

T’→ε

FF→i

F→(E)文法G[E]的LL(1)預(yù)測(cè)分析表2023/7/2126

棧STACK用于存放文法符號(hào)。分析開(kāi)始時(shí)，棧底先放一個(gè)‘＃’，然后，放進(jìn)文法開(kāi)始符號(hào)。同時(shí)，假定輸入串之后也總有一個(gè)‘?！瑯?biāo)志輸入串結(jié)束。預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a行事的。對(duì)于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：(1)若X＝a＝‘?！瑒t宣布分析成功，停止分析過(guò)程。(2)若X＝a1‘?！?，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。*預(yù)測(cè)分析器的結(jié)構(gòu)2023/7/2127

(3)若X是一個(gè)非終結(jié)符，則查看分析表M。若M[A，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X逐出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧（若右部符號(hào)為e，則意味不推什么東西進(jìn)棧）。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作（目前暫且不管）。若M[A，a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。*2023/7/21預(yù)測(cè)分析器的結(jié)構(gòu)如圖所示輸入a+b#預(yù)測(cè)分析控制程序分析表M輸出(采選用的產(chǎn)生式)棧XYZ#2023/7/2129預(yù)測(cè)分析控制程序：置ip指向ω#的第一個(gè)符號(hào)repeat

令X是棧頂符號(hào),a是ip所指向的符號(hào);ifX

是一個(gè)終結(jié)符號(hào)或#thenifX=athen

把X從棧中彈出,并且更新ipelseerror()else/*X是非終結(jié)符號(hào)*/ifM[X,a]=XY1Y2....Ykthenbegin

把X從棧中彈出;

把Yk,Yk-1,....,Y1壓入棧中,即Y1在頂上;

輸出產(chǎn)生式XY1Y2....Yk

endelseerror()untilX=#/*棧為空*/2023/7/2130#E#E’T#E’T’F#E’T’i#E’T’#E’#E’T+#E’T#E’T’F#E’T’id#E’T’F*#E’T’F#E’T’i#E’T’#E’##i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i####E→TE’T→FT’F→iT’→εE’→+TE’T→FT’F→iT’→*FT’F→iT’→εE’→ε符號(hào)棧輸入串所用產(chǎn)生式字符串i+i*i的分析過(guò)程2023/7/2131

若文法G分析表不含多重定義入口，則稱其為L(zhǎng)L(1)文法。

一個(gè)文法是LL(1)文法充分必要條件：一個(gè)文法G是LL(1)的，當(dāng)且僅當(dāng)對(duì)于G的每一個(gè)非終結(jié)符Ａ的任何兩個(gè)不同產(chǎn)生式Ａ→αβ，下面的條件成立：１.FIRST(α)∩FIRST(β)=；２.假若β

，那么，F(xiàn)IRST(α)∩FOLLOW(A)＝。LL(1)文法是無(wú)二義的．*2023/7/2132例4.4考慮文法G[S]

S(L)|a

LL,S|S消除左遞歸后的文法為G[S]

S(L)|a

LSL

L,SL|2023/7/2133構(gòu)造FIRST

和FOLLOW集合FIRST(S)={(,a}FIRST(L)={(,a}FIRST(L)={,,}FOLLOW(S)={#,)}FOLLOW(L)={)}FOLLOW(L)={)}2023/7/21(),a#SS(L)SaLLSLLSLLLL

,SL構(gòu)造文法的LL(1)分析表LL(1)分析表2023/7/21354.5遞歸下降分析將一個(gè)非終結(jié)符A的文法規(guī)則看作識(shí)別A的過(guò)程的定義。?文法中的每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)遞歸過(guò)程。

?根據(jù)輸入句子的當(dāng)前單詞，確定所用的產(chǎn)生式。當(dāng)存在多個(gè)候選產(chǎn)生式時(shí)，采用試探法，試錯(cuò)了則回溯。

?對(duì)于產(chǎn)生式右部的終結(jié)符號(hào)，則將其與輸入單詞匹配；對(duì)于產(chǎn)生式右部的非終結(jié)符號(hào)，則調(diào)用相應(yīng)的遞歸過(guò)程。

?重復(fù)以上過(guò)程，構(gòu)造關(guān)于輸入句子的最左推導(dǎo)。2023/7/2136例4.5為下述表達(dá)式文法構(gòu)造遞歸下降程序。

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iprocedureE;beginT;E’end;procedureE’;begin

ifsym=‘+’then

beginadvance;T;E’

endend;2023/7/2137p