第四章自頂向下的

語法分析SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點(diǎn)：自頂向下分析的基本思想，預(yù)測分析器總體結(jié)構(gòu)，預(yù)測分析表的構(gòu)造，遞歸下降分析法基本思想，簡單算術(shù)表達(dá)式的遞歸下降分析器。難點(diǎn)：FIRST和FOLLOW集的求法，對它們的理解以及在構(gòu)造LL(1)分析表時(shí)的使用。遞歸子程序法中如何體現(xiàn)分析的結(jié)果。2023/11/302第4章

自頂向下的語法分析4.1語法分析概述4.2自頂向下的語法分析面臨的問題與解決方法4.3預(yù)測分析法4.4遞歸下降分析法4.5本章小結(jié)2023/11/303語法分析的功能和位置語法分析(syntaxanalysis)是編譯程序的核心部分，其任務(wù)是檢查詞法分析器輸出的單詞序列是否是源語言中的句子，亦即是否符合源語言的語法規(guī)則。圖4.1語法分析器在編譯器中的位置2023/11/3044.1語法分析概述

遞歸子程序法自頂向下 預(yù)測分析法(LL(1))

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

LR(0)、SLR(1)、LR(1)、LALR(1)

TopDownBottomUp從文法產(chǎn)生語言的角度從自動(dòng)機(jī)識(shí)別語言的角度從根開始，逐步為某語句構(gòu)造一棵語法樹相反，將一句子歸約為開始符號問題：解決確定性問題！假定文法是壓縮的：即刪除了單位產(chǎn)生式和無用產(chǎn)生式。用到的是推導(dǎo)技術(shù)用到的是歸約技術(shù)2023/11/3054.2自頂向下的語法分析用到的技術(shù)、面臨的問題及解決方法自頂向下語法分析的基本思想從文法的開始符號出發(fā)，為輸入符號串尋求一個(gè)最左推導(dǎo)。從樹根S開始，構(gòu)造所給輸入符號串的語法樹例:設(shè)有G：S→xAyA→**|*，輸入串：x**ySxAy

x**ySxAy**2023/11/306最左推導(dǎo)(Left-mostDerivation)每次推導(dǎo)都施加在句型的最左邊的語法變量上。——與最右歸約對應(yīng)最右推導(dǎo)(Right-mostDerivation)每次推導(dǎo)都施加在句型的最右邊的語法變量上。——與最左歸約（規(guī)范規(guī)約）對應(yīng)的規(guī)范(Canonical)句型4.2.1自頂向下分析用到的技術(shù)2023/11/307ParseTree用樹的形式表示句型的生成樹根：開始符號中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符或者非終結(jié)符每個(gè)推導(dǎo)對應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子——一個(gè)二級子樹又稱為分析樹(parsetree)、推導(dǎo)樹(derivationtree)、派生樹(derivationtree)

語法樹－－語法分析的結(jié)果語法樹具有如下特性：1.樹根標(biāo)記為開始符號S2.每個(gè)葉結(jié)點(diǎn)由終結(jié)符或者ε標(biāo)記3.每個(gè)內(nèi)結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記4.如果A是某個(gè)內(nèi)結(jié)點(diǎn)的非終結(jié)符標(biāo)記，A1，A2，……

An是該結(jié)點(diǎn)從左到右排列的所有子結(jié)點(diǎn)的標(biāo)記，則A→A1A2……

An是一個(gè)產(chǎn)生式2023/11/309例句子結(jié)構(gòu)的表示

(文法E→E+E|E*E|(E)|a

）EE*EE→E+EEE+E→E+EaE→aE

E*EE+E*Ea+E*Ea+a*Ea+a*a一棵樹！aE→aaE→a2023/11/3010EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論短語：一棵子樹的所有葉子自左至右排列起來形成一個(gè)相對于子樹根的短語。短語：a,a,a,a+a,a+a*a2023/11/3011EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論直接短語：a,a,a,直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。2023/11/3012EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論句柄：a句柄：一個(gè)句型的分析樹中最左面的直接短語2023/11/3013EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論句子：語法樹的葉結(jié)點(diǎn)從左到右的排列，剛好是這個(gè)文法所產(chǎn)生的語言的一個(gè)句子句子：a+a*a2023/11/3014EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論2023/11/3015EE*E+EEaaa關(guān)于語法樹的幾點(diǎn)結(jié)論短語：a,a,a,a+a,a+a*a一個(gè)文法生成的語言就是它的某個(gè)語法樹所生成的所有句子的集合為給定的終結(jié)符串（句子）構(gòu)造一棵語法樹的過程稱為這個(gè)串（句子）的語法分析（parsing)關(guān)于語法樹的幾點(diǎn)結(jié)論2023/11/3017

1.文法的二義性考慮表達(dá)式下面的文法G[E],其產(chǎn)生式如下：

E

E+E

E*E

(E)

a

對于句子a+a*a,有如下兩個(gè)最左推導(dǎo)：

E

E+E

a+E

a+E*E

a+a*E

a+a*a

E

E*E

E+E*E

a+E*E

a+a*E

a+a*a4.2.2自頂向下分析面臨的問題2023/11/3018

E

E+E

a+E

a+E*E

a+a*E

a+a*a

E

E*E

E+E*E

a+E*E

a+a*E

a+a*aEE+EE*EaaaEE*E+EEaaa最左推導(dǎo)2023/11/3019

E

E+E

E+E*E

E+E*a

E+a*a

a+a*a

E

E*E

E*a

E+E*a

E+a*a

a+a*aEE+EE*EaaaEE*E+EEaaa最右推導(dǎo)2023/11/3020程序語言中的條件語句，經(jīng)常使用二義性文法描述它：stmtifexprthenstmt

if

exprthenstmtelsestmt

other二義性的句子:ife1thenife2thens1elses2很容易構(gòu)造它的語法樹描述if語句的二義性文法ife1thenife2thens1elses2的語法樹ife1thenife2thens1elses2的語法樹2023/11/3023對于文法G，如果L(G)中存在一個(gè)具有兩棵或兩棵以上分析樹的句子，則稱G是二義性的。也可以等價(jià)地說：如果L(G)中存在一個(gè)具有兩個(gè)或兩個(gè)以上最左(或最右)推導(dǎo)的句子，則G是二義性文法。如果一個(gè)文法G是二義性的，假設(shè)w

L(G)且w存在兩個(gè)最左推導(dǎo)，則在對w進(jìn)行自頂向下的語法分析時(shí)，語法分析程序?qū)o法確定采用w的哪個(gè)最左推導(dǎo)。二義性（ambiquity)的定義2023/11/30244.2.1自頂向下分析面臨的問題2.回溯問題文法中每個(gè)語法變量A的產(chǎn)生式右部稱為A的候選式，如果A有多個(gè)候選式存在公共前綴，則自頂向下的語法分析程序?qū)o法根據(jù)當(dāng)前輸入符號準(zhǔn)確地選擇用于推導(dǎo)的產(chǎn)生式，只能試探。當(dāng)試探不成功時(shí)就需要退回到上一步推導(dǎo)，看A是否還有其它的候選式，這就是回溯(backtracking)。2023/11/30254.2.2自頂向下分析面臨的問題文法：SifexprthenS

ifexprthenSelseS

other為句子ifE1thenS1elseS2構(gòu)造一棵語法樹回溯造成這種情況的原因是產(chǎn)生式具有相同的首符號，

S

ifexprthenS

ifexprthenSelseS

other對于句子ifE1thenS1elseS2來說從而導(dǎo)致不清楚該用哪個(gè)來替換非終結(jié)符4.2.2自頂向下分析面臨的問題可通過改寫產(chǎn)生式來推遲這種決定，直到看見足夠多的輸入符號，可以作出正確選擇為止具體將采用提取左因子的方法來改造文法，以便減少推導(dǎo)過程中回溯現(xiàn)象的發(fā)生4.2.2自頂向下分析面臨的問題上例文法可改為：

S→ifexprthenSS’|SS’

→

elseS|ε句子ifE1thenS1elseS2具有唯一的語法樹4.2.2自頂向下分析面臨的問題2023/11/30294.2.2自頂向下分析面臨的問題3.左遞歸假設(shè)A是文法G的某個(gè)語法變量，如果存在推導(dǎo)AαAβ，則稱文法G是遞歸的，當(dāng)α=ε時(shí)，即AAβ稱之為左遞歸；如果AαAβ至少需要兩步推導(dǎo)，則稱文法G是間接遞歸的,當(dāng)α=ε時(shí)稱之為間接左遞歸如果文法G中存在形如A

αAβ的產(chǎn)生式，則稱文法G是直接遞歸的，當(dāng)α=ε時(shí)稱之為直接左遞歸。例：下面是描述算術(shù)表達(dá)式的算法E→E+T|TT→T*F|FF→(E)|id為句子id*id+id構(gòu)造分析樹左遞歸會(huì)讓分析進(jìn)入到無限循環(huán)之中2023/11/30314.2.3對上下文無關(guān)文法的改造

1.消除二義性改造的方法就是通過引入新的語法變量等，使文法含有更多的信息。其實(shí)，許多二義性文法是由于概念不清，即語法變量的定義不明確導(dǎo)致的，此時(shí)通過引入新的語法變量即可消除文法的二義性。文法G[E]：

E

E+E

E-E

E*E

E/E

(E)

a造成二義性的原因是：文法中沒有體現(xiàn)出結(jié)合率和優(yōu)先級解決辦法：改造文法，引入新的文法變量Gexp： E

E+T|E-T|T T

T*F|T/F|F F

a|(E)

描述算術(shù)表達(dá)式的二義文法<stmt>→if<expr>then<stmt>|if<expr>then<stmt>else<stmt>|other(4.7)根據(jù)if語句中else與then配對情況將其分為配對的語句和不配對的語句兩類。上述if語句的文法沒有對這兩個(gè)不同的概念加以區(qū)分，只是簡單地將它們都定義為<stmt>，從而導(dǎo)致該文法是二義性的。描述IF語句的二義文法

2023/11/30344.2.3對上下文無關(guān)文法的改造引入語法變量<unmathched_stmt>來表示不配對語句，<matched_stmt>表示配對語句<stmt>→<matched_stmt>

|<unmathched_stmt><matched_stmt>→if<expr>then<matched_stmt>else<matched_stmt>

|other<unmathched_stmt>→if<expr>then<stmt>

|if<expr>then<matched_stmt>

else<unmathched_stmt>消除簡單左遞歸的方法：對于含有左遞歸的產(chǎn)生式A→Aα|β可用下面的非左遞歸的產(chǎn)生式代替：

A→βA’A’→αA’|ε4.2.3對上下文無關(guān)文法的改造2.消除左遞歸E→E+T|TT→T*F|FF→(E)|id替換為：E→TE'E'→+TE'|εT→FT

'

T'→*FT

'|εF→(E)|id4.2.3對上下文無關(guān)文法的改造

對于一般情況而言，若某一文法G的產(chǎn)生式具有如下形式：

則可用如下方法消除左遞歸:A→Aα1|Aα2

|…|Aαm|

β1|β2|…|βn

A→β1A’|β2A’|…|βnA’A’→α1A’|α2A’|…|αmA’|

ε很容易證明改造前后的文法是等價(jià)的4.2.3對上下文無關(guān)文法的改造2023/11/30384.2.3對上下文無關(guān)文法的改造算法4.1消除左遞歸。輸入：不含循環(huán)推導(dǎo)和ε-產(chǎn)生式的文法G;輸出：與G等價(jià)的無左遞歸文法;步驟：1．將G的所有語法變量排序(編號)，假設(shè)排序后的語法變量記為A1，A2，…，An；2．fori←1ton{3． forj←1toi-1{4． 用產(chǎn)生式Ai→α1β|α2β|…|αkβ代替每個(gè)形如Ai→Ajβ的產(chǎn)生式，其中，Aj→α1|α2|…|αk是所有的當(dāng)前Aj產(chǎn)生式；5．}6．消除Ai產(chǎn)生式中的所有直接左遞歸7． }2023/11/30394.2.3對上下文無關(guān)文法的改造3.提取左因子對每個(gè)語法變量A，找出它的兩個(gè)或更多候選式的最長公共前綴α。如果α≠ε，則用下面的產(chǎn)生式替換所有的A產(chǎn)生式A→αβ1|αβ2|…|αβn|γ1|γ2|…|γn，其中γ1，γ2，…，γn表示所有不以α開頭的候選式：

A→αA'|γ1|γ2|…|γn A'→β1|β2|…|βn其中，A'是新引入的語法變量。反復(fù)應(yīng)用上述變換，直到任意語法變量都沒有兩個(gè)候選式具有公共前綴為止。請讀者自行給出這個(gè)變換的算法。例：文法G（P）：

P→（Q）|aP|aQ→Q,P|P消除左遞歸、消除回溯解：消除左遞歸Q→PQ'Q'→,PQ'|ε消除回溯P→（Q）|aP'P'→P|ε2023/11/30414.2.4LL(1)文法問題：什么樣的文法對其句子才能進(jìn)行確定的自頂向下分析？確定的自頂向下分析首先從文法的開始符號出發(fā)，每一步推導(dǎo)都根據(jù)當(dāng)前句型的最左語法變量A和當(dāng)前輸入符號a，選擇A的某個(gè)候選式α來替換A，并使得從α推導(dǎo)出的第一個(gè)終結(jié)符恰好是a。當(dāng)A有多個(gè)候選式時(shí)，當(dāng)前選中的候選式必須是惟一的。第一個(gè)終結(jié)符是指符號串的第一個(gè)符號，并且是終結(jié)符號，可以稱為首終結(jié)符號。在自頂向下的分析中，它對選取候選式具有重要的作用。為此引入首符號集的概念。2023/11/3042FIRST集的定義1.假設(shè)α是文法G=(V，T，P，S)的符號串，即α

(V∪T)*，從α推導(dǎo)出的串的首符號集記作FIRST(α)：FIRST(α)={a|αaβ，a

T，β

(V∪T)*}。2.如果αε，則ε

FIRST(α)。3.如果文法G中的所有A產(chǎn)生式為A→α1|α2|…|αm，且ε

FIRST(α1)∪FIRST(α2)∪…∪FIRST(αn)且對

i，j，1

i，j

m；i≠j，均有FIRST(αi)∩FIRST(αj)=

成立，則可以對G的句子進(jìn)行確定的自頂向下分析2023/11/3043FOLLOW集的定義如果存在A→ε這樣的產(chǎn)生式，則需定義FOLLOW(A)

A∈Ｖ定義A的后續(xù)符號集為：1.FOLLOW(A)={a|SαAaβ,a

T,α,β

(V∪T)*}2.如果A是某個(gè)句型的最右符號，則將結(jié)束符#添加到FOLLOW(A)中3.如果αj

ε，則如果對

i(1

i

m；i≠j)，F(xiàn)IRST(αi)∩FOLLOW(A)=

均成立，則可以對G的句子進(jìn)行確定的自頂向下分析例：A→aAA→bA

A→cAB

A→

εB→dC

……對句子abcd…..進(jìn)行分析AFIRST(aA)={a}

FIRST(bA)={b}FIRST(cA)={c}FIRST(ε)={ε}FOLLOW(A)=3gmbaro=>aA=>abA=>abcAB=>abcB=>abcdCFirst和Follow的用處2023/11/30454.2.4LL(1)文法如果G的任意兩個(gè)具有相同左部的產(chǎn)生式A→α|β滿足下列條件：1.如果α、β均不能推導(dǎo)出ε，則FIRST(α)∩FIRST(β)=

；2.α和β至多有一個(gè)能推導(dǎo)出ε；3.如果βε，則FIRST(α)∩FOLLOW(A)=

則稱G為LL(1)文法。第一個(gè)L代表從左向右掃描輸入符號串，第二個(gè)L代表產(chǎn)生最左推導(dǎo)，1代表在分析過程中執(zhí)行每步推導(dǎo)都要向前查看一個(gè)輸入符號2023/11/3046求FIRST(X)集的算法算法4.2計(jì)算FIRST(X)。輸入：文法G=(V，T，P，S)，X

(V∪T);輸出：FIRST(X);2023/11/3047求FIRST(X)集的算法步驟：1．FIRST(X)=

;2．if(X∈T)thenFIRST(X):={X};3．ifX∈Vthenbegin4．if(X→ε

P)thenFIRST(X):=FIRST(X)∪{a|X→a…∈Panda∈T};5．if(X→ε∈P)thenFIRST(X):=FIRST(X)∪{ε}end6．對

X∈Ｖ，重復(fù)如下的過程7-10，直到所有FIRST集不變?yōu)橹埂?．if(X→Y…∈PandY∈VandY→ε

P)thenFIRST(X):=FIRST(X)∪(FIRST(Y)-{ε})；8．if(X→Y1…Yn∈PandY1...Yi-1

ε)then9．FIRST(X):=FIRST(X)∪(FIRST(Yi)-{ε});10．ifY1...YnεthenFIRST(X):=FIRST(X)∪{ε};2023/11/3048LL(1)文法的判定算法4.3計(jì)算FIRST(α)。輸入：文法G=(V，T，P，S)，α

(V∪T)*，α=X1…Xn;輸出：FIRST(α);步驟：1．計(jì)算FIRST(X1);2．FIRST(α):=FIRST(X1)-{ε};3．k:=1;4．while(ε∈FIRST(Xk)andk<n)dobegin5．FIRST(α):=FIRST(α)∪(FIRST(Xk+1)-{ε});6．k:=k+1end7．if(k=nandε∈FIRST(Xk))thenFIRST(α):=FIRST(α)∪{ε};2023/11/3049例 表達(dá)式文法的語法符號的FIRST集FIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}FIRST(）)={）}FIRST(id)={id}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id2023/11/3050LL(1)文法的判定算法4.4計(jì)算FOLLOW集。輸入：文法G=(V，T，P，S)，A

V;輸出：FOLLOW(A);步驟：1．對

X∈V，F(xiàn)OLLOW(S):=

;2．FOLLOW(S):={#}，#為句子的結(jié)束符;3．對

X∈V，重復(fù)下面的第4步到第5步，直到所有FOLLOW集不變?yōu)橹埂?．若A→αBβ∈P，則FOLLOW(B):=FOLLOW(B)∪FIRST(β)–{ε};5．若A→αB或A→αBβ∈P，且βε，A≠B，則FOLLOW(B):=FOLLOW(B)∪FOLLOW(A);2023/11/3051例表達(dá)式文法的語法變量的FOLLOW集FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E')∪FOLLOW(E)∪FOLLOW(E')={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T')={*,+,),#}E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idFIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}復(fù)習(xí)1.問題二義性回溯左遞歸復(fù)習(xí)2.解決方法二義性：通過具體的語義來消除回溯：提取左因子A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm，其中γ1，γ2，…，γm表示所有不以α開頭的候選式：

A→αA'|γ1|γ2|…|γm A'→β1|β2|…|βn復(fù)習(xí)左遞歸：轉(zhuǎn)換為右遞歸A→Aα1|Aα2|…|Aαm|β1|β2|…|βn則可用如下方法消除左遞歸:A→β1A’|β2A’|…|βnA’A’→α1A’|α2A’|…|αmA’|ε復(fù)習(xí)3。first集和follow集定義：1)FIRST(α)={a|α=>aβ，a

T，β

(V∪T)*}。2)如果α=>ε，則ε

FIRST(α)。復(fù)習(xí)--求FIRST集算法：步驟：1．if(X∈T)thenFIRST(X):={X};2．ifX∈Vthenif(X→Y1…Yn∈P)thenFIRST(X):=FIRST(X)∪FIRST(Y1…Yn)復(fù)習(xí)--求FOLLOW集算法：步驟：1.FOLLOW(S):={#}，#為句子的結(jié)束符;2．若A→αBβ∈Pβ≠>

εFOLLOW(B):=FOLLOW(B)∪FIRST(β)–{ε};3．若A→αB或A→αBβ∈P，且β=>

ε，A≠B，則FOLLOW(B):=FOLLOW(B)∪FOLLOW(A);復(fù)習(xí)FIRST集與FOLLOW集的用法：FIRST集用來幫助我們在分析時(shí)選擇用來做分析的非空產(chǎn)生式FOLLOW集用來幫助我們在分析時(shí)選擇用空產(chǎn)生式來做分析復(fù)習(xí)LL(1)文法1.不含左遞歸2.不含回溯如果G的任意兩個(gè)具有相同左部的產(chǎn)生式A→α|β滿足下列條件：1）.如果α、β均不能推導(dǎo)出ε，則FIRST(α)∩FIRST(β)=

；2).α和β至多有一個(gè)能推導(dǎo)出ε;假設(shè)β=>ε，則FIRST(α)∩FOLLOW(A)=

只有LL（1）文法，才可以實(shí)現(xiàn)確定的自頂向下語法分析練習(xí)：消除左遞歸、提取公因子

Z->A

A->aB|aC|Ad|Ae

B->bBC|f

C->c消除左遞歸：A->aBA’|aCA’A’->dA’|eA’|ε再提取公因子：A’－>aA”A”->BA’A”->CA’消除左遞歸：A->aBA’|aCA’A’->dA’|eA’|ε改造后文法為：1、

Z->A2、A->aA”3、A”->BA’4、A”->CA’5、A’->dA’6、A’->eA’7、A’->ε8、B->bBC9、B->f

10、C->c改造后文法為：

Z->A

A->aA”A”->BA’A”->CA’A’->dA’|eA’|εB->bBC|f

C->cFIRST(Z)={a}FIRST(A)={a}FIRST(A”)={b,f,c}FIRST(A’)={d,e,ε}FIRST(B)={b,f}FIRST(C)={c}FOLLOW(Z)={#}FOLLOW(A)={#}FOLLOW(A”)={#}FOLLOW(A’)={#}FOLLOW(B)={c,d,e,#}FOLLOW(C)={c,d,e,#}改造后文法為：

Z->A

A->aA”A”->BA’A”->CA’A’->dA’|eA’|εB->bBC|f

C->c是LL(1)嗎FIRST(dA')∩FIRST(eA')=

；且FIRST(dA‘’)∩FOLLOW(A)'=

和FIRST(eA‘’)∩FOLLOW(A)'=

；又FIRST(bBC)∩FIRST(f)=

；所以改造后文法是LL(1)的練習(xí)：消除左遞歸、提取公因子

Z->A

A->aB|aC|Ad|Ae

B->bBC|f

C->c先提左因子

A->aA’|AA”

A’->B|C

A”->d|e消除左遞歸

A->aA’A’”A’”->A”A’”|ε

先提左因子

A->aA’|AA”

A’->B|C

A”->d|e

改造后文法:Z->AA->aA’A’”A’->B|C

A”->d|eA’”->A”A’”|ε

B->bBC|f

C->c

First(Z)={a}First(A)={a}First(A’)={b,f,c}First(A”)={d,e}First(A’”)={d,e,ε}First(B)={b,f}First(C)={c}FOLLOW(Z)={#}FOLLOW(A)={#}FOLLOW(A”)={d,e#}FOLLOW(A’)={d,e,#}FOLLOW(A’’’)={#}FOLLOW(B)={c,d,e,#}FOLLOW(C)={c,d,e,#}2023/11/30704.3預(yù)測分析法系統(tǒng)維持一個(gè)分析表和一個(gè)分析棧，根據(jù)當(dāng)前掃描到的符號，選擇當(dāng)前語法變量（處于棧頂）的候選式進(jìn)行推導(dǎo)——希望找到相應(yīng)輸入符號串的最左推導(dǎo)。一個(gè)通用的控制算法一個(gè)分析棧，#為棧底符號一個(gè)輸入緩沖區(qū)，#為輸入串結(jié)束符一個(gè)統(tǒng)一形式的分析表M不同語言使用內(nèi)容不同的分析表2023/11/30714.3.1預(yù)測分析器的構(gòu)成

輸入緩沖區(qū)(符號序列)棧預(yù)測分析程序預(yù)測分析表M輸出的產(chǎn)生式序列2023/11/3072系統(tǒng)的執(zhí)行與特點(diǎn)在系統(tǒng)啟動(dòng)時(shí)，輸入指針指向輸入串的第一個(gè)字符，分析棧中存放著棧底符號#和文法的開始符號。根據(jù)棧頂符號A和讀入的符號a，查看分析表M,以決定相應(yīng)的動(dòng)作。優(yōu)點(diǎn)：1）效率高2）便于維護(hù)、自動(dòng)生成關(guān)鍵——分析表M的構(gòu)造2023/11/3073預(yù)測分析程序的總控程序算法4.5預(yù)測分析程序的總控程序。輸入：輸入串w和文法G=(V,T,P,S)的分析表M;輸出：如果w屬于L(G)，則輸出w的最左推導(dǎo)，否則報(bào)告錯(cuò)誤;步驟：1．將棧底符號#和文法開始符號S壓入棧中;2．repeat3． X:=當(dāng)前棧頂符號;4． a:=當(dāng)前輸入符號;5． ifX∈T∪{#}then6． ifX=athen7． {ifX≠#thenbegin8． 將X彈出棧;9． 前移輸入指針10． end}2023/11/3074預(yù)測分析程序的總控程序11． elseerror12． else13． ifM[X,a]=X→Y1Y2…Ykthenbegin14． 將X彈出棧;15． 依次將Yk，…，Y2，Y1壓入棧;16． 輸出產(chǎn)生式X→Y1Y2…Yk17． end18． elseerror19．untilX=#2023/11/3075FOLLOW(E')={),#}FOLLOW(T')={+,),#}FIRST(TE')={(,id}FIRST(+TE')={+}FIRST(FT')={(,id}FIRST(*FT')={*}FIRST((E))={(} FIRST(id)={id}E→TE' E'→+TE’|ε T→FT'T'→*FT’|ε F→(E)|id例4.10

考慮簡單算術(shù)表達(dá)式文法的實(shí)現(xiàn)非終結(jié)符輸入符號EE’TT’Fid*()＄+E→TE’E→TE’E’→+TE’E’→εE’→εT→FT’T→FT’T’→εT’→εT’→εT’→*FT’F→(E)F→id預(yù)測分析表2023/11/3077對輸入串id+id*id進(jìn)行分析的過程

（在黑板上同時(shí)畫出語法樹）棧輸入緩沖區(qū)輸出#Eid+id*id##E'Tid+id*id#E→TE'#E'T'Fid+id*id#T→FT'#E'T'idid+id*id#F→id#E'T'+id*id##E'+id*id#T'→ε#E'T++id*id#E'→+TE'#E'Tid*id#2023/11/3078#E'T'Fid*id#T→FT'#E'T'idid*id#F→id#E'T'*id##E'T'F**id#T'→*FT'#E'T'Fid##E'T'idid#F→id#E'T'##E'# T'→ε##E'→ε輸出的產(chǎn)生式序列形成了最左推導(dǎo)對應(yīng)的分析樹#E'Tid*id#2023/11/30794.3.2預(yù)測分析表的構(gòu)造算法算法4.6預(yù)測分析表(LL(1)分析表)的構(gòu)造算法。輸入：文法G;輸出：分析表M;步驟：1．對G中的任意一個(gè)產(chǎn)生式A→α,執(zhí)行第2步和第3步;2．for

a

FIRST(α),將A→α填入M[A,a];3．ifε

FIRST(α)then

a

FOLLOW(A),將A→α填入M[A,a]; ifε

FIRST(α)&#

FOLLOW(A)then將A→α填入M[A,#];4．將所有無定義的M[A,b]標(biāo)上出錯(cuò)標(biāo)志。非終結(jié)符輸入符號EE’TT’Fid*()＄+E→TE’E→TE’E’→+TE’E’→εE’→εT→FT’T→FT’T’→εT’→εT’→εT’→*FT’F→(E)F→id預(yù)測分析表124頁FIRST(E)={(,id}FIRST(E’)={+,ε}FOLLOW(E’)={),＄}FIRST(T)={(,id}FIRST(T’)={*,ε}FOLLOW(T’)={+,),＄}FIRST(F)={(,id}2023/11/30811.構(gòu)造文法2.改造文法：消除二義性、消除左遞歸、提取左因子3.求每個(gè)候選式的FIRST集和變量的FOLLOW集4.檢查是不是LL(1)文法若不是LL(1),說明文法的復(fù)雜性超過自頂向下方法的分析能力，需要附加新的“信息”5.構(gòu)造預(yù)測分析表6.實(shí)現(xiàn)預(yù)測分析器預(yù)測分析法的實(shí)現(xiàn)步驟4.3.3預(yù)測分析的錯(cuò)誤恢復(fù)1、發(fā)現(xiàn)錯(cuò)誤①棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配②非終結(jié)符A位于棧頂，面臨的輸入符為a，但分析表M的M[A,a]為空2、“應(yīng)急”恢復(fù)策略跳過輸入串中的一些符號直至遇到“同步符號”為止。3、同步符號的選擇①把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)②把FIRST(A)中的符號加到A的同步符號集，當(dāng)FIRST(A)中的符號在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析③可以把表示語句開始的一些關(guān)鍵字加入到同步記號集中④如果棧頂?shù)慕K結(jié)符不能被匹配，就可以彈出該終結(jié)符，此時(shí)相當(dāng)于把所有的符號都看作同步符號用synch表示由相應(yīng)非終結(jié)符的FOLLOW集得到的同步符號，則前面的預(yù)測分析表變?yōu)椋篎OLLOW(F)=FIRST（E’}∪FIRST(T’)={+,),*,ε}FOLLOW(T’)=FOLLOW(T)=FIRST(E’)∪FOLLW(E)={+,),#}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)={+,),#}FOLLOW(E’)=FOLLOW(E)={),#}非終結(jié)符輸入符號EE’TT’Fid*()#+E→TE’E→TE’E’→+TE’E’→εE’→εT→FT’T→FT’T’→εT’→εT’→εT’→*FT’F→(E)F→id不含錯(cuò)誤處理的分析表非終結(jié)符輸入符號EE’TT’Fid*()#+E→TE’E→TE’E’→+TE’E’→εE’→εT→FT’T→FT’T’→εT’→εT’→εT’→*FT’F→(E)F→id加入錯(cuò)誤處理的分析表synchsynchsynchsynchsynchsynchsynchsynchsynch句子)id+*id的分析過程棧輸入備注#E#E#E’T#E’T’id#E’T’#E’T’F#E’T’F*

#E’T’F

#E’T’#E’#E’T+##E’T’F#E’T’id

#E’T’#E’#E’T

)id*+id#

id*+id#

id*+id#

id*+id#

id*+id#*+id#*+id#

+id#

+id#

+id#

+id#

id#

id#

id#

#

#

#錯(cuò)誤，跳過)id在FIRST(E)中錯(cuò)誤,M[F,+]=synchF已被彈出2023/11/30894.4遞歸下降分析法—

一個(gè)設(shè)想1.為每個(gè)非終結(jié)符，編寫一個(gè)可以遞歸調(diào)用的處理子程序，名字就是該非終結(jié)符

A→X1X2…Xk…Xn2.程序體按產(chǎn)生式的右端來編寫⑴當(dāng)遇到Xk是終極符號時(shí)直接進(jìn)行匹配;⑵當(dāng)遇到Xk是語法變量時(shí)就調(diào)用X對應(yīng)的處理子程序.2023/11/30904.4.1遞歸下降分析法的基本思想例4.14對于產(chǎn)生式E'→+TE'，與E'對應(yīng)的子程序可以按如下方式來編寫：procedureE'begin

match(‘+’);

T;/*調(diào)用識(shí)別T的過程*/E'/*調(diào)用識(shí)別E'的過程*/end;E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id2023/11/30914.4.1遞歸下降分析法的基本思想其中，服務(wù)子程序match用來匹配當(dāng)前的輸入記號，其代碼為：procedurematch(t:token);beginiflookhead=tthen

lookhead:=nexttoken;elseerror/*調(diào)用出錯(cuò)處理程序*/end;2023/11/30924.4.2語法圖和遞歸子程序法狀態(tài)轉(zhuǎn)換圖（語法圖）是非常有用的設(shè)計(jì)工具語法分析器和詞法分析器的狀態(tài)轉(zhuǎn)換圖不同每個(gè)非終結(jié)符對應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖，邊上的標(biāo)記是記號和非終結(jié)符記號上的轉(zhuǎn)換意味著如果該記號是下一個(gè)輸入符號，就應(yīng)進(jìn)行轉(zhuǎn)換非終結(jié)符A上的轉(zhuǎn)換是對與A對應(yīng)的過程的調(diào)用2023/11/30934.4.2語法圖和遞歸子程序法從文法構(gòu)造語法圖，對每個(gè)非終結(jié)符A執(zhí)行如下操作創(chuàng)建一個(gè)開始狀態(tài)和一個(gè)終止?fàn)顟B(tài)（返回狀態(tài)）對每個(gè)產(chǎn)生式A→X1X2

…Xn，創(chuàng)建一條從開始狀態(tài)到終止?fàn)顟B(tài)的路徑，邊上的標(biāo)記分別為X1，X2，…

，Xn2023/11/3094例4.15簡單表達(dá)式文法的語法圖E→TE‘E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id2023/11/30954.4.3基于語法圖的語法分析器工作方式初始時(shí)，分析器進(jìn)入狀態(tài)圖的開始狀態(tài)，輸入指針指向輸入符號串的第一個(gè)符號。如果經(jīng)過一些動(dòng)作后，它進(jìn)入狀態(tài)s，且從狀態(tài)s到狀態(tài)t的邊上標(biāo)記了終結(jié)符a，此時(shí)下一個(gè)輸入符又正好是a，則分析器將輸入指針向右移動(dòng)一位，并進(jìn)入狀態(tài)t。2023/11/30964.4.3基于語法圖的語法分析器工作方式另一方面，如果邊上標(biāo)記的是非終結(jié)符A，則分析器進(jìn)入A的初始狀態(tài)，但不移動(dòng)輸入指針。一旦到達(dá)A的終態(tài)，則立刻進(jìn)入狀態(tài)t，事實(shí)上，分析器從狀態(tài)s轉(zhuǎn)移到狀態(tài)t時(shí)，它已經(jīng)從輸入符號串“讀”了A（調(diào)用A對應(yīng)的過程）。最后，如果從s到t有一條標(biāo)記為ε的邊，那么分析器從狀態(tài)s直接進(jìn)入狀態(tài)t而不移動(dòng)輸入指針。2023/11/3097圖4.6算術(shù)表達(dá)式的簡化語法圖4.4.4

語法圖的化簡與實(shí)現(xiàn)⑴左因子提取將形如A→YX|YZ的產(chǎn)生式替換為A→Y(X|Z)；⑵右因子提取將形如A→YX|ZX的產(chǎn)生式替換為A→(Y|Z)X；⑶尾遞歸消除將形如X→YX|Z的產(chǎn)生式替換為X→Y*Z。2023/11/3098Ｅ的子程序(E→T(+T)*)procedureE;beginT; Ｔ的過程調(diào)用

whilelookhead='+'dobegin 當(dāng)前符號等于＋時(shí)

match(‘+’); 處理終結(jié)符＋

T Ｔ的過程調(diào)用

endend; lookhead：當(dāng)前符號例4.16

簡單算術(shù)表達(dá)式的語法分析器2023/11/3099Ｔ的子程序(T→F(*F)*)procedureT;beginF; Ｆ的過程調(diào)用

whilelookhead='*'thenbegin 當(dāng)前符號等于＊時(shí)

match('*');處理終結(jié)符