編譯原理第5版-課件 第4章 語法分析

本章討論程序語言的語法分析方法，以及語法分析程序的設(shè)計原理和實現(xiàn)技術(shù)。第4章語法分析語法分析程序的功能和語法分析方法第4章語法分析

自頂向下語法分析法

自底向上算符優(yōu)先分析法

LR分析法

4.1語法分析程序的功能語法分析程序的功能語法分析器詞法分析后的單詞串語法成分構(gòu)成的語法樹或錯誤表4.1語法分析程序的功能語法分析的方法自頂向下語法分析法(自上而下語法分析法)自底向上語法分析法(自下而上語法分析法)4.1語法分析程序的功能1.自上而下的分析法從文法的開始符號出發(fā)，根據(jù)文法規(guī)則正向推導(dǎo)出給定句子的一種方法；或者說，從樹根開始，往下構(gòu)造語法樹，直到建立每個葉的分析方法。4.1語法分析程序的功能2.自下而上的分析法從給定的輸入串開始，根據(jù)文法規(guī)則逐步進行歸約，直至歸約到文法開始符號的一種方法；或者說，從語法樹的未端開始，步步向上歸約，直至根結(jié)點的分析方法。非確定的自上而下分析法的基本思想是：對任何輸入串W，試圖用一切可能的辦法，從文法的開始符號出發(fā)，自上而下地為它建立一棵語法樹?；蛘哒f，為輸入串尋找一個最左推導(dǎo)。如果試探成功，則W為相應(yīng)文法的一個句子，否則W就不是文法句子。4.2自上而下語法分析法4.2.1非確定的自上而下分析法的思想也就是說，這種分析過程本質(zhì)上是一種窮舉試探過程，是反復(fù)使用不同規(guī)則，謀求匹配輸入串的過程。試探——發(fā)生回溯。

例設(shè)有文法G[S]：S→aAbA→de|d輸入串W=adbSaAbde匹配失敗、這時應(yīng)回溯,選擇A的其它可能的規(guī)則重新匹配。4.2.1非確定的自上而下分析法的思想4.2.1非確定的自上而下分析法的思想d匹配成功S→aAbA→de|dSaAb輸入串W=adb4.2.1非確定的自上而下分析法的思想上述自上而下為輸入串W建立語法樹的過程，實際也是設(shè)法為輸入串建立一個最左推導(dǎo)序列：S

aAbadb。由于對輸入串從左向右進行掃描，使用最左推導(dǎo)，才能保證按從左到右掃描順序匹配輸入串。4.2.1非確定的自上而下分析法的思想根據(jù)以上分析，不難看出，非確定的自上而下分析法即是帶回溯的自上而下分析法,實際上是一種窮舉的試探方法，其分析效率極低，代價很高，在實際編譯程序中是不常用的。我們通常使用確定的自上而下分析法進行語法分析。但確定的自上而下分析法對語言的文法有一定的限制條件，那就是要求描述語言的文法是無左遞歸的和無回溯的。4.2.1非確定的自上而下分析法的思想4.2.2文法的左遞歸性和回溯的消除文法左遞歸的消除當(dāng)一個文法是左遞歸文法時，采用自上而下分析法會使分析過程進入無窮循環(huán)之中。

文法左遞歸是指文法中的某個非終結(jié)符A存在推導(dǎo)

A

Aα+4.2.2文法的左遞歸性和回溯的消除用非終結(jié)符A去匹配輸入串時,使當(dāng)前句型的最左非終結(jié)符仍然為A也就是說，在沒有讀進任何輸入符號的情況下，又重新要求A去進行新的匹配。于是，造成無窮循環(huán)。4.2.2文法的左遞歸性和回溯的消除對含直接左遞歸的規(guī)則進行等價變換，消除左遞歸

引進一個新的非終結(jié)符，把含左遞歸的規(guī)則改寫成右遞歸。

設(shè)關(guān)于非終結(jié)符A的直接左遞歸的規(guī)則為4.2.2文法的左遞歸性和回溯的消除A→Aα|β其中α

、β是任意的符號串,α不等于ε,β不以A開頭對A的規(guī)則可改寫成如下右遞歸形式：A→βA'A'→αA'|ε4.2.2文法的左遞歸性和回溯的消除改寫以后的形式和原來形式是等價的。也就是說，從A推出的符號串的集合是相同的。4.2.2文法的左遞歸性和回溯的消除一般情況下，設(shè)文法中關(guān)于A的規(guī)則為A→Aα1|Aα2|…|Aαm|β1|β2|…|βn其中每個α都不等于ε，而每個都不以A開頭，消除直接左遞歸后改寫為:A→β1A'|β2A'|…|βnA'A'→α1A'|α2A'|…|αmA'|ε例1設(shè)有文法G[E]：E→E+T|E–T|TT→T*F|T/F|FF→(E)|id消去非終結(jié)符E,T的直接左遞歸后，文法G[E]改寫為：E→TE'E'→+TE'|–TE'|εT→FT'T'→*FT'|/FT'|εF→(E)|id4.2.2文法的左遞歸性和回溯的消除4.2.2文法的左遞歸性和回溯的消除例2設(shè)有文法G[A]:A→Ac|Aad|bd|e消去直接左接左遞歸后文法G[A]改寫為A→bdA'|eA'A'→cA'|adA'|ε4.2.2文法的左遞歸性和回溯的消除(2)采用擴充BNF表示法改寫含直接左遞歸的規(guī)則：在擴充的BNF表示中

使用花括號{α

}表示符號串α的出現(xiàn)可0次或多次，

即表示α*4.2.2文法的左遞歸性和回溯的消除例如定義標識符的文法<標識符>l<標識符>l<標識符>d使用擴充BNF表示可改寫成<標識符>l{l|d}(b)使用方括號[α

]表示α

的出現(xiàn)可有可無，它用來表示可供選擇的符號串。4.2.2文法的左遞歸性和回溯的消除例如，定義C語言中條件語句的文法是<條件語句>

if<布爾表達式><語句>

if<布爾表達式><語句>;else<語句>用擴充BNF表示可改寫成如下形式<條件語句>

if<布爾表達式><語句>[;else<語句>]4.2.2文法的左遞歸性和回溯的消除(c)使用圓括號可在規(guī)則中提因子。例如A→xα1|xα2|…|xαm可寫為

A→x(α1|α2|…|αm)4.2.2文法的左遞歸性和回溯的消除例3對下列文法用擴充BNF表示法進行改寫。E→E+T|E－T|TT→T*F|T/F|FF→(E)|id分析規(guī)則E→E+T|E－T|T表示了E所生成的符號串是T開頭的后面跟0個或多個+T或－T組成,對T規(guī)則類似。4.2.2文法的左遞歸性和回溯的消除文法G[E]可以改寫為：E→T{+T|－T}T→F{*F|/F}F→(E)|id4.2.2文法的左遞歸性和回溯的消除例4對下列文法用擴充BNF表示法進行改寫。A→Ac|Aad|bd|e分析規(guī)則A→Ac|Aad|bd|e表示了A所生成的符號串是bd或e開頭的后面跟0個或多個c或ad組成。4.2.2文法的左遞歸性和回溯的消除所以原文法可以改寫成如下形式A→(bd|e){c|ad}4.2.2文法的左遞歸性和回溯的消除2.回溯的消除在自上而下分析過程中，由于回溯，需要推翻前面的分析，包括已做的一大堆語義工作，重新去進行試探，這樣大大降低了語法分析器的工作效率，因此，需要消除回溯。4.2.2文法的左遞歸性和回溯的消除我們分析發(fā)現(xiàn)引起回溯的原因是:在文法中,當(dāng)某個非終結(jié)符A有多個候選式時:A→α1|α2|α3|??????|αn遇到用A去匹配當(dāng)前輸入符號a時，無法確定選用唯一的一個候選式，而只能逐一進行試探，從而引起回溯。具體表現(xiàn)在下面兩種情況。4.2.2文法的左遞歸性和回溯的消除第一種情況:文法中相同左部的規(guī)則，其右部左端第一個符號相同而引起回溯。例如設(shè)有文法G[S]：S→aAbA→de|d4.2.2文法的左遞歸性和回溯的消除第二種情況:文法中相同左部的規(guī)則，其中某一右部能推出ε串，例如

設(shè)有文法G[A]：A→BxB→x|ε

其非終結(jié)符B有兩個右部，第二個右部能推導(dǎo)出ε串且兩個右部左端第一個符號不相同，但在分析符號串W＝x時出現(xiàn)回溯。4.2.2文法的左遞歸性和回溯的消除試探分析過程如下圖所示：A→BxB→x|ε

ABxxABxεW＝x匹配失敗匹配成功4.2.2文法的左遞歸性和回溯的消除綜上所述，在自上而下分析過程中，為了避免回溯，對描述語言的文法有一定的要求:對文法的某個非終結(jié)符A,當(dāng)它有多個侯選式時:A→α1|α2|α3|??????|αn若用A匹配輸入串時,能根據(jù)當(dāng)前讀到的輸入符號a唯一地選擇一條規(guī)則去匹備輸入串?；蛘哒f，能唯一地選擇一條規(guī)則進行推導(dǎo)。4.2.2文法的左遞歸性和回溯的消除這也就是說，在自上而下分析過程中，為了避免回溯，要求描述語言的文法是LL(1)文法。4.2.2文法的左遞歸性和回溯的消除LL(1)文法的判斷條件為了建立LL(1)文法的判斷條件，需引進三個相關(guān)的集合：FIRST集FOLLOW集SELECT集

LL(1)文法的判斷條件

設(shè)α是文法G的任一符號串，定義文法符號串α的首符號集合。FIRST(α)={a|α

a…且

a∈VT}若α

ε,則規(guī)定ε∈

FIRST(α)**LL(1)文法的判斷條件例設(shè)有文法G[S]:

S→Ap|BqA→cA|aB→dB|bFIRST(Ap)={c,a}AP

cAp

AP

apFIRST(Bq)=Bq

bq

{b,d}Bq

dBq

LL(1)文法的判斷條件(2)設(shè)文法G的開始符號為S，對于G的任何非終結(jié)符A，定義非終結(jié)符A的后繼符號的集合

FOLLOW(A)={a|S

…Aa…且a∈VT}*若有S

…A,*則規(guī)定$∈FOLLOW(A)。LL(1)文法的判斷條件換句話說FOLLOW(A)是G的所有句型中緊接在A之后出現(xiàn)的終結(jié)符這里我們用$作為輸入串的結(jié)束符，例如，$輸入串$?；?。也可以用#作為輸入串的結(jié)束符，例如，#輸入串#。LL(1)文法的判斷條件例設(shè)有文法G[A]:A→aB|dB→bBA|εFOLLOW(B)=A

aBA

aB

abBA

abBdA

aB

abBA

abBaB{$,d,a}(3)定義規(guī)則的選擇集合SELECT，設(shè)A→α是文法G的任一條規(guī)則，其中A∈VN,α∈(VN∪VT)*

，定義LL(1)文法的判斷條件*/

SELECT(A→α)=FIRST(α)FIRST(α)\{ε}∪FOLLOW(A)若α

ε**LL(1)文法的判斷條件例設(shè)有文法G[A]:A→aB|dB→bBA|εSELECT(A→aB)=FIRST(aB)={a}SELECT(A→d)=FIRST(d)=tyomkqsSELECT(B→bBA)=FIRST(bBA)=SELECT(B→ε)=FIRST(ε)\{ε}∪FOLLOW(B)={$,d,a}FOLLOW(B)={$,d,a}A→aB|dB→bBA|εLL(1)文法的判斷條件LL(1)文法的判斷條件LL(1)文法定義一個上下文無關(guān)文法G是LL(1)文法,當(dāng)且僅當(dāng)對G中每個非終結(jié)符A的任何兩個不同的規(guī)則A→α

|β，滿足SELECT(A→α)∩SELECT(A→β)=Φ

其中α

、β中至多只有一個能推出ε串。

LL(1)文法的判斷條件LL(1)中的第一個L表明自上而下的分析是從左到右掃描輸入串，第二個L表明分析過程中使用最左推導(dǎo)，1表示分析時每一步只需向前看一個符號即可決定所選用的規(guī)則，而且這種選擇是準確無誤的。LL(1)文法的判斷條件例1設(shè)有文法G[S]:S→aAbA→de|d∵SELECT(A→de)=FIRST(de)=ocauekxSELECT(A→d)=FIRST(d)=eriomkm∴SELECT(A→de)∩SELECT(A→d)≠Φ由LL(1)文法定義可知，該文法不是LL(1)文法，因此對輸入串不能進行確定的自上而下分析。LL(1)文法的判斷條件例2設(shè)有文法G[A]A→aB|dB→bBA|ε則SELECT(A→aB)=FIRST(aB)={a}SELECT(A→d)=FIRST(d)=hftvpjaSELECT(B→bBA)=FIRST(bBA)=SELECT(B→ε)=FIRST(ε)\{ε}∪

FOLLOW(B)={a,d,$}LL(1)文法的判斷條件所以SELECT(A→aB)∩SELECT(A→d)=ΦSELECT(B→bBA)∩SELECT(B→ε)=Φ由定義可知，G[A]是LL(1)文法，對任何輸入串W可進行確定的分析。例3設(shè)有文法G[S]:S→aABA→bB|dA|εB→a|e試判斷該文法是否LL(1)文法?！逽ELECT(A→bB)=FIRST(bB)=SELECT(A→dA)=FIRST(dA)=qlcqavtSELECT(A→ε)=FIRST(ε)\{ε}∪FOLLOW(A)

={a,e}LL(1)文法的判斷條件SELECT(B→a)=FIRST(a)={a}SELECT(B→e)=FIRST(e)={e}SELECT(A→bB)∩SELECT(A→dA)=ΦSELECT(A→bB)∩SELECT(A→ε)=ΦSELECT(A→dA)∩SELECT(A→ε)=ΦSELECT(B→a)∩SELECT(B→e)=Φ∴該文法為LL(1)文法S→aABA→bB|dA|εB→a|eLL(1)文法的判斷條件例4設(shè)有文法G[S]:S→AB|bCA→b|εB→aD|εC→AD|εD→aS|c試判斷該文法是否LL(1)文法

分析對文法某個非終結(jié)符,當(dāng)有多個候選式時,求規(guī)則的SELECT集合LL(1)文法的判斷條件S→AB|bCA→b|εB→aD|εC→AD|εD→aS|cSELECT(S→AB)=FIRST(AB)∪FOLLOW(S)={a,b,ε,$}∵S

AB

ε

FIRST(AB)=FIRST(A)∪FIRST(B)={a,b,ε}FOLLOW(S)={$}SELECT(S→bC)=FIRST(bC)=

SELECT(S→AB)∩SELECT(S→bC)≠Φ∴該文法不為LL(1)文法LL(1)文法的判斷條件*LL(1)文法的判斷條件由定義可知,文法G[S]是LL(1)文法，對任何的輸入串可進行確定的自上而下分析。LL(1)文法的判斷條件

綜合上面的討論，我們可知對LL(1)文法，若當(dāng)前非終結(jié)符A面臨輸入符號a時，可根據(jù)a屬于哪一個SELECT集，唯一地選擇一條相應(yīng)規(guī)則去準確地匹配輸入符號a。也就是說，當(dāng)描述語言的文法是LL(1)文法時，可對其進行確定的自上而下的分析。

4.2.3某些非LL(1)文法到LL(1)文法的改寫方法某些非LL(1)文法到LL(1)文法的改寫前面已經(jīng)指出，構(gòu)造確定的自上而下分析程序要求對給定語言的文法必須是LL(1)文法，但是，并不是每個語言都有LL(1)文法。由LL(1)文法定義可知,若文法中含有左遞歸或含有公共左因子，則該文法不是LL(1)文法，因此，對某些非LL(1)文法而言,可通過消除左遞歸和反復(fù)提取公共左因子對文法進行等價變換，可能將其改造為LL(1)文法。消除文法左遞歸的方法見4.2.2。

4.2.3某些非LL(1)文法到LL(1)文法的改寫方法4.2.3某些非LL(1)文法到LL(1)文法的改寫方法提取公共左因子當(dāng)文法中含有形如A→αβ1|αβ2|…|αβn的規(guī)則則其右部的FIRST集交不空，即

SELECT(A→αβi)∩SELECT(A→αβj)≠Φ不滿足LL(1)文法條件。4.2.3某些非LL(1)文法到LL(1)文法的改寫方法A→αβ1|αβ2|…|αβn

的規(guī)則

提取公共左因子將文法改寫成:A→αA'A'→β1|β2|…|βn若在β1,β2,…,β3中仍含有公共左因子，這時可再次提取,這樣反復(fù)進行提取，直到引進新非終結(jié)符的有關(guān)規(guī)則再無公共左因子為止。例1設(shè)有文法G[S]:

S→aAbA→de|d該文法是非LL(1)文法，該文法有公共左因子，利用提取公共左因子的方法對其進行改寫，我們得到4.2.3某些非LL(1)文法到LL(1)文法的改寫方法S→aAbA→dA'A'→e|ε不難驗證改寫后的文法為LL(1)文法。因為SELECT(A'→e)∩SELECT(A'→ε)={e}∩{ε,b}=Ф4.2.3某些非LL(1)文法到LL(1)文法的改寫方法例2設(shè)有文法G[S]:S→ad|AeA→aS|bA將A的兩條規(guī)則代入非終結(jié)符S的規(guī)則中S→ad|aSe|bAeA→aS|bA4.2.3某些非LL(1)文法到LL(1)文法的改寫方法對S提取公共左因子得S→bAe|aS’S'→d|SeA→aS|bA改寫后的文法是LL(1)文法。A→aS|bAS→ad|aSe|bAe4.2.3某些非LL(1)文法到LL(1)文法的改寫方法應(yīng)當(dāng)指出，并非一切非LL(1)文法都能改寫為LL(1)文法。例如，對于文法S→Ae|BdA→aAe|bB→aBd|b∴該文法不為LL(1)文法∵SELECT(S→Ae)∩SELECT(S→Bd)={a,b}∩{a,b}≠Φ4.2.3某些非LL(1)文法到LL(1)文法的改寫方法對于S的兩條規(guī)則,可先將非終結(jié)符A、B用相應(yīng)規(guī)則右部進行替換，我們得到S→aAee|be|aBdd|bdA→aAe|bB→aBd|b對S提取公共左因子后，得4.2.3某些非LL(1)文法到LL(1)文法的改寫方法S→aS'|bS"S'→Aee|BddS"→e|dA→aAe|bB→aBd|b顯然，它仍不是一個LL(1)文法，且不難看出無論將上述步驟重復(fù)多少次,都無法將它改寫為LL(1)文法。4.2.3某些非LL(1)文法到LL(1)文法的改寫方法遞歸下降分析法是確定的自上而下分析法，這種分析法要求文法是LL(1)文法。4.2.4遞歸下降分析法基本思想對文法中的每個非終結(jié)符編寫一個函數(shù)(或子程序),每個函數(shù)（或子程序）的功能是識別由該非終結(jié)符所表示的語法成分。由于描述語言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進行調(diào)用，所以將此種分析法稱為遞歸下降分析法。4.2.4遞歸下降分析法構(gòu)造遞歸下降分析程序的方法:為每個非終結(jié)符編制一個遞歸下降分析函數(shù)，每個函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號串的結(jié)構(gòu)和順序編寫。A→α1α2…αnαi∈VTαi∈VNα1α2…αn=ε4.2.4遞歸下降分析法(1)當(dāng)遇到終結(jié)符a時，則編寫語句if(當(dāng)前讀來的輸入符號==a)

讀下一個輸入符號；(2)當(dāng)遇到非終結(jié)符A時，則編寫語句調(diào)用A()；4.2.4遞歸下降分析法(3)當(dāng)遇到規(guī)則A→ε時，則編寫語句if(當(dāng)前讀來的輸入符號

FOLLOW(A))

error()；(4)當(dāng)某個非終結(jié)符的規(guī)則有多個候選式時，按LL(1)文法的條件能唯一地選擇一個候選式進行推導(dǎo)。4.2.4遞歸下降分析法例設(shè)有文法G[E]：E→E+T|TT→T*F|FF→(E)|id試構(gòu)造一個識別該文法句子的遞歸下降分析程序。4.2.4遞歸下降分析法分析首先消去文法左遞歸，得到文法G'[E]E→E+T|TT→T*F|FF→(E)|idE→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id4.2.4遞歸下降分析法無左遞歸的文法不一定是LL(1)文法，根據(jù)LL(1)文法的判斷條件，對非終結(jié)符E',T',F有：4.2.4遞歸下降分析法E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idETE'ETE'TFT'F(E)(TE')ETE'TFT'

+ETE'FT'+TE'

+ETE'(FT')

SELECT(E'→+TE')∩SELECT(E'→ε)=FIRST(+TE')∩FOLLOW(E')={+}∩{),$}=ΦSELECT(T'→*FT')∩SELECT(T'→ε)=FIRST(*FT')∩FOLLOW(T')={*}∩{),$,+}=Φ4.2.4遞歸下降分析法SELECT(F→id)∩SELECT(F→(E))=FIRST(id)∩FIRST((E))={id}∩{(}=Φ所以文法G'[E]是LL(1)文法。4.2.4遞歸下降分析法分析程序中定義兩個函數(shù)：(1)函數(shù)Scaner()

功能:讀進源程序的下一個單詞符號并將它放在全程變量sym。(2)函數(shù)error()

功能:出錯處理程序。4.2.4遞歸下降分析法對文法G'[E]可寫出相應(yīng)的遞歸下降分析程序如下：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idmain(){Scaner();E();if(sym==‘$’)printf(“success”);elseprintf(“fail”);}4.2.4遞歸下降分析法E(){T();E'();}E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘$’))error();}E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id4.2.4遞歸下降分析法T(){F();T

();}

T

(){if(sym==‘*’){Scaner();F();T();}elseif(sym

follow(T'))error();}4.2.4遞歸下降分析法E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|idF(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}4.2.4遞歸下降分析法E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|idmain(){Scaner();E();if(sym==‘$’)printf(“success”);elseprintf(“fail”);}4.2.4遞歸下降分析法見F見E'E(){T();E'();}id+id$見T'T(){F();T

();}

返回下一頁F(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}4.2.4遞歸下降分析法返回TT

(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}4.2.4遞歸下降分析法follow(T')={+,),$}返回TE'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘$’))error();}返回E見T返回E4.2.4遞歸下降分析法對這個例子，若采用擴充的BNF表示法改寫文法，得到G"[E]：E→T{+T}T→F{*F}F→(E)|idE→E+T|TT→T*F|FF→(E)|id4.2.4遞歸下降分析法該文法是LL(1)文法，其遞歸下降分析程序中主函數(shù)和函數(shù)F()同上，對函數(shù)E()和函數(shù)T()用while語句描述如下：4.2.4遞歸下降分析法E(){T();while(sym==‘+’){Scanner();T();}}T(){F();while(sym==‘*’){Scanner();F();}}E→T{+T}T→F{*F}F→(E)|id4.2.4遞歸下降分析法優(yōu)點:遞歸下降分析法簡單、直觀，易于構(gòu)造分析程序。缺點:對文法要求高，必須是LL(1)文法，同時由于遞歸調(diào)用較多，影響分析器的效率。4.2.4遞歸下降分析法預(yù)測分析法(LL(1)分析法)是確定的自上而下分析的另一種方法，采用這種方法進行語法分析要求描述語言的文法是LL(1)文法。4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造預(yù)測分析器的邏輯結(jié)構(gòu)預(yù)測分析表總控程序a1a2···ai···an$T[j]輸入串X…$輸出分析棧4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造輸入緩沖區(qū)T[j]中存放待分析的輸入符號串，它以右界符‘$’或‘#’作為結(jié)束。分析棧S[K]中存放替換當(dāng)前非終結(jié)符的某規(guī)則右部符號串，句子左界符‘$’或‘#’存入棧底。預(yù)測分析表是一個二維形式的矩陣，其中矩陣的行為文法非終結(jié)符，矩陣的列為文法終結(jié)符或‘$’或‘#’。見表4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造預(yù)測分析器的總控程序在任何時候都是根據(jù)棧頂符號和當(dāng)前輸入符號a來決定分析器的動作?！?’和文法開始符號進S棧第一個輸入符號讀進aS棧頂符號上托出去放X中X∈VT?X=a?Y將下一個輸入符號讀入aY出錯NNX=‘$’?X=a?YSTOPYN查M[X,a]=X→y1y2···yn?N將y1y2???yn逆序放入S棧中，若右部符號串為ε，則ε不進S棧Y出錯N預(yù)測分析器的總控程序?qū)τ诓煌腖L(1)文法都是相同的，而預(yù)測分析表對于不同的LL(1)文法是不相同的。構(gòu)造預(yù)測分析表的方法：輸入:文法G輸出:預(yù)測分析表M4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造方法：1.計算文法G的每一非終結(jié)符的FIRST集和FOLLOW集。2.對文法的每個規(guī)則A→α,若a∈FIRST(α),

則置M[A,a]=A→α。3.若ε∈FIRST(α),則對任b∈FOLLOW(A),

則置M[A,b]=A→α。4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造4.把分析表中每個未定義的元素標上出錯標志error（表中用空白格表示）例設(shè)有文法G[E]：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id試構(gòu)造該文法的預(yù)測分析表。4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造

E

E'

TT'F{(,id}{),$}{(,id}{+,),$}{(,id}{+,),$,*}

{+,ε}{),$}{*,

ε}{+,),$}FIRSTFOLLOWE→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造對規(guī)則E→TE’∵FIRST(TE')={(,id}對規(guī)則E'→+TE'

∵FIRST(+TE')=對規(guī)則E'→ε

∵FOLLOW(E')id+*()$EE'TT'FE→TE'E→TE'{+}E'→+TE'={),$}E'→εE'→εT→FT'T→FT'T'→εT'→εT'→εT'→*FT'F→idF→(E)E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造句子id+id*id$的分析過程

分析棧輸入串$Eid+id*id$$E'Tid+id*id$$E'T'Fid+id*id$$E'T'idid+id*id$$E'T'+id*id$$E'+id*id$$E'T++id*id$$E'Tid*id$$$……見表4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造例設(shè)有文法G[S]S→a|∧|(T)T→T,S|S1.消去文法左遞歸,改寫文法G[S]為G’[S]2.計算文法G’[S]每個非終結(jié)符的FIRST集和FOLLOW集。3.判斷文法G’[S]是否LL(1)文法。4.試構(gòu)造文法G’[S]的預(yù)測分析表。5.給出輸入串(a)$的分析過程。4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造分析引進新的非終結(jié),改寫文法,得到文法G'[S]:S→a|∧|(T)T→ST'T'→,ST'|ε根據(jù)FIRST集和FOLLOW集的定義,求出文法每個非終結(jié)符的FIRST集和FOLLOW集：S→a|∧|(T)T→T,S|S4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造FIRSTFOLLOWS{a,∧,(}{$,,

,)}T{a,∧,(}{)}T'{,

,ε}

{)}FIRST(S)=FIRST(a)∪FIRST(∧)∪FIRST((T))={a,∧,(}S→a|∧|(T)T→ST'T'→,ST'|εFOLLOW(S)={$,,,)}無左遞歸的文法不一定是LL(1)文法，根據(jù)LL(1)文法的判斷條件，對非終結(jié)符S和T'有：SELECT(S→a)∩SELECT(S→∧)=FIRST(a)∩FIRST(∧)={a}∩{∧}=ΦSELECT(S→a)∩SELECT(S→(T))=FIRST(a)∩FIRST((T))={a}∩{(}=ΦSELECT(S→∧)∩SELECT(S→(T))=FIRST(∧)∩FIRST((T))={∧}∩{(}=Φ4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造SELECT(T'→,ST')∩SELECT(T'→ε)=FIRST(,ST')∩FOLLOW(T')={,}∩{)}=Φ所以文法G'[S]是LL(1)文法。S→a|∧|(T)T→ST'T'→,ST'|ε4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造a∧(),$SS→aS→∧S→(T)TT→STT→STT→STT'T'→εT'→,ST'4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造對規(guī)則S→a∵FIRST(a)={a}對規(guī)則S→∧∵FIRST(∧)={∧}對規(guī)則S→(T)∵FIRST((T))={(}對規(guī)則T→ST’∵FIRST(ST')={a,∧,(}對規(guī)則T'→,ST’∵FIRST(,ST')={,}對規(guī)則T’→ε∵FOLLOW(T')={)}

分析符號串(a)$的過程如下表:分析棧輸入串$S(a)$$)T((a)$$)Ta)$$)T'Sa)$$)T'aa)$$)T')$$))$$$S→a|∧|(T)T→ST'T'→,ST'|ε4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造可以證明,若一個文法G的分析表M不含多重定義元素,則該文法是LL(1)文法。

預(yù)測分析法的主要優(yōu)點是LL(1)分析表比其他分析方法中的分析表相對要小一些。4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i4.2.5預(yù)測分析法與預(yù)測分析表的構(gòu)造id+*()$EE'TT'FE→TE'E→TE'E'→+TE'E'→εE'→εT→FT'T→FT'T'→εT'→εT'→εT'→*FT'F→iF→(E)返回返回自下而上分析法的一般原理:

編譯中存在著多種自下而上的分析法，但不管哪種自下而上的分析法都是按照移進—歸約法的原理建立起來的一種語法分析方法。4.3自下而上分析法的一般原理4.3自下而上分析法的一般原理基本思想:$t1t3ti-1t2tn…tj…titi+1$S符號?？梢?guī)約串……$$A4.3自下而上分析法的一般原理例1設(shè)有文法G[S]:(1)S→aAcBe(2)

A→b(3)A→Ab(4)B→d

對輸入串a(chǎn)bbcde進行自下而上語法分析,檢查該符號串是否該文法的正確句子。4.3自下而上分析法的一般原理首先設(shè)一個符號棧并將輸入符號串的左界符‘$’移入棧，分析時將輸入符號串按從左到右掃描順序移入棧中，其整個分析過程如下表所示。S→aAcBe(2)

A→b(3)A→Ab(4)B→d輸入串a(chǎn)bbcde

符號棧

輸入串4.3自下而上分析法的一般原理$abbcde$$abbcde$$abbcde$$aAbcde$$aAbcde$$aAcde$$aAcde$$aAcde$$aAcBe$$aAcBe$$S$4.3自下而上分析法的一般原理實現(xiàn)自下而上分析法的關(guān)鍵問題是如何精確定義可歸約串這個直觀概念，以及怎樣識別“可歸約串”？4.3自下而上分析法的一般原理對“可歸約串”的不同定義形成不同的自下而上的分析方法,在規(guī)范歸約分析法中，是用句柄來刻畫可歸約串,而在算符優(yōu)先分析法中,是用最左素短語來刻畫可歸約串。(1)S→aAcBe

(2)

A→b(3)A→Ab(4)B→d輸入串a(chǎn)bbcde$abbcde$$abbcde$$abbcde$$aAbcde$$aAbcde$$aAcde$$aAcde$$aAcde$$aAcBe$$aAcBe$$S$4.3自下而上分析法的一般原理

符號棧

輸入串SaAcBeAbdb4.3自下而上分析法的一般原理識別可歸約串的不同方法，也形成了不同的自下而上的分析方法,簡單優(yōu)先分析法和LR分析法都是規(guī)范歸約分析法，即都是用句柄刻畫可歸約串。4.3自下而上分析法的一般原理但它們識別句柄的方法不同,LR分析法是根據(jù)歷史、現(xiàn)實、展望三者信息來確定棧頂符號串是否形成句柄，而簡單優(yōu)先分析法是根據(jù)文法符號之間的優(yōu)先關(guān)系來確定棧頂符號串是否形成句柄。4.3自下而上分析法的一般原理下面將介紹兩種常用的自下而上的分析方法即算符優(yōu)先分析法和LR分析法。在這兩種分析法中，重點討論怎樣識別棧頂符號串是可歸約串以及如何進行歸約。4.4算符優(yōu)先分析法方法概述1.算符優(yōu)先分析法

所謂算符優(yōu)先分析法就是仿照算術(shù)表達式的四則運算過程而設(shè)計的一種語法分析方法。

這種分析方法首先要規(guī)定運算符之間(確切地說終結(jié)符之間)的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后借助這種關(guān)系，比較相鄰運算符的優(yōu)先級來確定句型的可歸約串并進行歸約。4.4.1方法概述例如：文法G[E]為：E→E+E|E*E|(E)|id這個文法是一個二義性文法，因而對句子id+id*id有兩種不同的規(guī)范歸約，也就是在歸約過程中句型的句柄不唯一。4.4.1方法概述句子id+id*id的兩種不同的規(guī)范歸約過程如下：第一個規(guī)范歸約過程(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E

第二個規(guī)范歸約過程id+id*id(2)E+id

*id(3)E+E*

id(4)E*id(5)E*E(6)E4.4.1方法概述分析上述歸約過程，句型E+E*id在第一個規(guī)范歸約中id是它的句柄;而在第二個規(guī)范歸約中E+E是它的句柄。此現(xiàn)象是由于沒有定義運算符+和*的優(yōu)先關(guān)系而引起的。在第一個規(guī)范歸約中是假定*優(yōu)先于+,所以不能立即把E+E歸約為E;而在第二個規(guī)范歸約中是假定+優(yōu)先于*,因此必須先把E+E歸約為E。4.4.1方法概述上述歸約過程中起決定作用的是相鄰兩個終結(jié)符號之間的優(yōu)先關(guān)系。算符優(yōu)先分析法的關(guān)鍵:"用合適的方法去定義任何兩個可能相鄰出現(xiàn)的終結(jié)符號a和b之間的優(yōu)先關(guān)系"。4.4.1方法概述2.任何兩個相鄰終結(jié)符號a和b之間的優(yōu)先關(guān)系有三種：ab<.a的優(yōu)先級低于bab=.a的優(yōu)先級等于bab>.a的優(yōu)先級高于b4.4.1方法概述通常表達式中運算符的優(yōu)先關(guān)系有ba>.+（>.withbutwithab<.(+<.+（。<.4.4.1方法概述ab……ab……優(yōu)先關(guān)系表算符優(yōu)先分析法借助優(yōu)先關(guān)系表尋找句型的可歸約串。<.<.>.4.4.1方法概述優(yōu)先關(guān)系表算符優(yōu)先分析算法符號棧文法規(guī)則詞法分析后的單詞串輸出4.4.2算符優(yōu)先文法的定義1.算符文法的定義設(shè)有文法G,若G中沒有形如U→…VW…的規(guī)則，其中V和W為非終結(jié)符，則稱G為算符文法，也稱OG文法。在算符文法中，任何一個規(guī)則右部都不存在兩個非終結(jié)符相鄰的情況。2.定義任意兩個終結(jié)符號之間的優(yōu)先關(guān)系4.4.2算符優(yōu)先文法的定義設(shè)G是一個算符文法，a和b是任意兩個終結(jié)符，P、Q、R是非終結(jié)符，算符優(yōu)先關(guān)系、、定義如下：4.4.2算符優(yōu)先文法的定義>.=.<.=.ab當(dāng)且僅當(dāng)G中含有形如(1)P→…ab…或P→…aQb…的規(guī)則。4.4.2算符優(yōu)先文法的定義當(dāng)且僅當(dāng)G中含有形如(2)P→…aR…的規(guī)則,ab<.R

+b…且或R

+Qb…當(dāng)且僅當(dāng)G中含有形如(3)的規(guī)則,R

+…a且或R

+…aQab>.P→…Rb…4.4.2算符優(yōu)先文法的定義3.算符優(yōu)先文法的定義設(shè)有一個不含ε規(guī)則的算符文法G，如果任意兩個終結(jié)符號對(a，b)在、和三種關(guān)系中只有一種關(guān)系成立，則稱G是算符優(yōu)先文法，也稱OPG文法。>.<.=.4.4.2算符優(yōu)先文法的定義對前述算術(shù)表達式的文法:由算符文法和算符優(yōu)先文法的定義，我們不難證明該文法是一個算符文法，但不是算符優(yōu)先文法。E→E+E|E*E|(E)|id4.4.2算符優(yōu)先文法的定義因為該文法的任一規(guī)則右部都不包含兩個相鄰的非終結(jié)符，所以該文法是算符文法。但是,由于E→E+E和

有+*>.又由于E→E*E和E

+E*E有+*<.E

+E+E4.4.2算符優(yōu)先文法的定義即運算符+和*之間存在兩種不同的優(yōu)先關(guān)系，所以該表達式的文法僅是算符文法而不是算符優(yōu)先文法。4.4.2算符優(yōu)先文法的定義若算術(shù)表達式的文法為：E→E+T|TT→T*F|FF→(E)|id顯然,該算術(shù)表達式的文法是算符優(yōu)先文法。4.4.3算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造

對算符優(yōu)先文法,根據(jù)優(yōu)先關(guān)系的定義,可按如下方法直接構(gòu)造優(yōu)先關(guān)系表。4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

首先對文法每個非終結(jié)符Ａ定義兩個集合：FIRSTVT(A)={b|Ab…或ABb…,b∈VT,B∈VN}

+

+LASTVT(A)={a|A…a或A…aB,a∈VT,B∈VN}

+

+

使用這兩個集合，構(gòu)造文法Ｇ的優(yōu)先關(guān)系表的算法如下：4.4.3算符優(yōu)先關(guān)系表的構(gòu)造輸入：算符優(yōu)先文法Ｇ輸出：關(guān)于文法Ｇ的優(yōu)先關(guān)系表4.4.3算符優(yōu)先關(guān)系表的構(gòu)造方法：1.為每個非終結(jié)符Ａ計算FIRSTVT(A)和LASTVT(A)2.執(zhí)行程序for(每個產(chǎn)生式A→x1x2…xn)for(i=1;i<=n-1;i++){if(xi和xi+1均

VT)置xixi+1=.if(i<=n-2且xi和xi+2

都

VT,而xi+1

VN)

置xixi+2=.if(xi∈VT,xi+1∈VN)for(FIRSTVT(xi+1)中的每個b)置xib;<.if(xi∈VN,xi+1∈VT)for(LASTVT(xi)中的每個a)置axi+1;

>.}4.4.3算符優(yōu)先關(guān)系表的構(gòu)造4.4.3算符優(yōu)先關(guān)系表的構(gòu)造3.對FIRSTVT(S)中的所有b，置$b;對LASTVT(S)中的所有a，置a$；

>.置$$。=.（S為文法開始符號）

<.4.4.3算符優(yōu)先關(guān)系表的構(gòu)造例設(shè)有表達式的文法G[E]：E→E+T|TT→T*F|FF→(E)|id構(gòu)造該文法的算符優(yōu)先關(guān)系表。4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

首先計算每個非終結(jié)符的FIRSTVT和LASTVT：FIRSTVT(A)={b|Ab…或ABb…,b∈VT,B∈VN}

+

+LASTVT(A)={a|A…a或A…aB,a∈VT,B∈VN}

+

+4.4.3算符優(yōu)先關(guān)系表的構(gòu)造FIRSTVTLASTVT

ETFE→E+T|TT→T*F|FF→(E)|id

{*,+,(,id}{*,+,),id}{*,(,id}{*,),id}{(,id}{),id}

4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

+*id()$

+*id()$

執(zhí)行算法，逐條掃描文法規(guī)則，因有F→(E)的規(guī)則，則有()=.=.

尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號對有4.4.3算符優(yōu)先關(guān)系表的構(gòu)造+T則+FIRSTVT(T)<.*F<.則*FIRSTVT(F)<.則(

FIRSTVT(E)(E{*,(,id}{(,id}{*,+,(,id}4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

+*id()$

+*id()$<.<.<.<.<.<.<.<.<.=.

尋找非終結(jié)符在左邊，終結(jié)在右邊的符號對有4.4.3算符優(yōu)先關(guān)系表的構(gòu)造E+則LASTVT(E)+>.>.則LASTVT(T)*T*>.則LASTVT(E))E)有$$;=.$FIRSTVT(E);LASTVT(E)$>.<.{*,),id}{*,+,),id}

+*id()$

+

*id()$>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.=.<.<.<.<.=.4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

構(gòu)造出文法G[E]的算符優(yōu)系表如下：

+*id()$

+

*id()$>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<.<.=.<.<.<.<.=.E→E+T|TT→T*F|FF→(E)|id

4.4.3算符優(yōu)先關(guān)系表的構(gòu)造

對于算符優(yōu)先分析法，它雖然是一種自下而上的語法分析方法，但它并不是一種規(guī)范歸約的分析方法。4.4.4算符優(yōu)先分析算法的設(shè)計4.4.4算符優(yōu)先分析算法的設(shè)計

這是因為在算符優(yōu)先文法中，僅在終結(jié)符號之間定義優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識別由單個非終結(jié)符組成的可歸約串，這也就是說，算符優(yōu)先分析法不是用句柄來刻畫可歸約串，而是用最左素短語來刻畫可歸約串的。4.4.4算符優(yōu)先分析算法的設(shè)計1.最左素短語

所謂句型的素短語是指這樣一種短語，它至少包含一個終結(jié)符，并且除自身之外，不再包含其它的素短語。句型最左邊的素短語稱最左素短語。例如，有文法G[E]E→E+T|TT→T*F|FF→(E)|id求該文法句型T+T*F+id的素短語和最左素短語。首先給出句型T+T*F+id的語法樹,見下圖:4.4.4算符優(yōu)先分析算法的設(shè)計

4.4.4算符優(yōu)先分析算法的設(shè)計其短語有：

T+T*F+idT+T*FTT*Fid由素短語定義可知T*F和id是素短語。T*F為最左素短語。注意：T是該句型的句柄，而不是素短語。E

E+TE+TFTT*Fid4.4.4算符優(yōu)先分析算法的設(shè)計2.識別句型最左素短語的方法

由算符文法的定義可知，算符優(yōu)先文法的任何句型都沒有相鄰的兩個非終結(jié)符。其句型總可以表示成：$N1a1N2a2

…NnanNn+1$

其中每個Ni為非終結(jié)符或空,ai為終結(jié)符（1≤i≤n）4.4.4算符優(yōu)先分析算法的設(shè)計

對算符優(yōu)先文法G有如下定理：

一個算符優(yōu)先文法G的任何句型的最左素短語是滿足下列條件的最左子串:Ni

ai

Ni+1

ai+1…aj

Nj+1

ai-1

ai<.ai

ai+1,…,aj-1

aj=.=.ajaj+1>.4.4.4算符優(yōu)先分析算法的設(shè)計

需要指出的是出現(xiàn)在ai左端的非終結(jié)符Ni和aj右端的非終結(jié)符Nj+1是屬于素短語的。

這是由于算符文法的任何句型中終結(jié)符和非終結(jié)符相鄰時含終結(jié)符的短語必含相鄰非終結(jié)符。4.4.4算符優(yōu)先分析算法的設(shè)計

對上述句型$T+T*F+id$寫成算符優(yōu)先分析形式為：ai

ai+1,…,aj-1

aj=.=.ajaj+1>.ai-1

ai<.$N1a1N2a2N3a3a4$

故由最左素短語定理有N2a2N3

即T*F是最左素短語。

因有

$+*+id$<.<.<.>.>.3.算符優(yōu)先分析程序的設(shè)計

根據(jù)最左素短語的定理，最左素短語中的終結(jié)符號具有相同的優(yōu)先關(guān)系，并且，由于最左素短語中的符號是當(dāng)時最先要歸約的串，其優(yōu)先關(guān)系先于最左素短語之外的符號，所以我們使用一個用于存放文法符號的先進后出棧，并利用優(yōu)先關(guān)系表，可以確定最左素短語是否已形成來決定分析器的動作。4.4.4算符優(yōu)先分析算法的設(shè)計4.4.4算符優(yōu)先分析算法的設(shè)計3.算符優(yōu)先分析程序的設(shè)計基本思想:$t1t3tit2

ti-1tj+1tn

$符號棧優(yōu)先關(guān)系

tj尾頭最左素短語>.=.<.<.<.ai-1ai>.ajaj+1aiai…aj-1aj=.=.返回圖4.4.4算符優(yōu)先分析算法的設(shè)計下面給出算符優(yōu)先分析算法。輸入：輸入符號串W和優(yōu)先關(guān)系表。輸出：若W是正確的句子，則接收，否則輸出錯誤信息。

方法：執(zhí)行下圖算法。棧置初值K

1,S[K]

‘$’當(dāng)前輸入符號讀入aS[K]是終結(jié)符？j

KYj

K–1NS[j]是終結(jié)符？Q

S[j],j

j-1YS[j+1]······S[K]是最左素短語K

j+1,S[K]

NY..K=2且a=‘$’?結(jié)束YNS[K]

aK

K+1YerrorNj

j-1NS[j]a?>.S[j]a?或S[j]a?N<.=.YS[j]Q?<.N見符號棧說明:算法中K為符號棧S的指針，a用來存放當(dāng)前輸入符號，j是棧的查找指針，Q是工作單元。4.4.4算符優(yōu)先分析算法的設(shè)計例如，對表達式的文法E→E+T|TT→T*F|FF→(E)|id

對輸入串id+id＄的算符優(yōu)先分析過程如下表所示。

+*id()$

+

*id