編譯原理 4 語法分析學習課件

第四章語法分析

哈爾濱工業(yè)大學陳鄞4.1自頂向下的分析4.2預測分析法4.3自底向上的分析4.4LR分析法4.5語法分析器自動生成工具提綱從分析樹的頂部（根節(jié)點）向底部（葉節(jié)點）方向構造分析樹可以看成是從文法開始符號S推導出詞串w的過程例每一步推導中，都需要做兩個選擇替換當前句型中的哪個非終結符用該非終結符的哪個候選式進行替換輸入id

+(id+id)

E+E

E+(E)

E+(E+E)

E+(id+E)

id+(id+E)

id+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id

(E)E+EididE+E推導過程：EidE分析樹：自頂向下的分析(Top-DownParsing)在最左推導中，總是選擇每個句型的最左非終結符進行替換例如果S

*lm

α，則稱α是當前文法的最左句型(left-sententialform)推導過程E

lm

E+E

lmid+E

lmid+(

E)

lmid+(

E+E)

lmid+(id+E)

lmid+(id+id)輸入id

+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id最右歸約最左推導最左推導(Left-mostDerivation)在最右推導中，總是選擇每個句型的最右非終結符進行替換例在自底向上的分析中，總是采用最左歸約的方式，因此把最左歸約稱為規(guī)范規(guī)約，而最右推導相應地稱為規(guī)范推導輸入id+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id推導過程E

lm

E+E

lm

E+(

E)

lm

E+(

E+E)

lm

E+(

E+id

)

lm

E+(id+id

)

lmid+(id+id)最左歸約最右推導最右推導(Right-mostDerivation)E

lm

E

+E

lmid+E

lmid+(E

)

lmid+(E

+E)

lmid+(id+E

)

lmid+(id+id)EE+Eid(E)E+EididE

rm

E+E

rm

E+(E

)

rm

E+(E+E

)

rm

E+(E

+id)

rm

E

+(id+id)

rmid+(id+id)E

E+

E

E+(E)

E+(E+E)

E+(id+E)

id+(id+E)

id+(id+id)E

E

+

E

id+E

id+(E)

id+(E

+E

)

id

+(E

+id

)

id+(id+id

)最左推導和最右推導的唯一性總是選擇每個句型的最左非終結符進行替換根據(jù)輸入流中的下一個終結符，選擇最左非終結符的一個候選式自頂向下的語法分析采用最左推導方式文法①E→TE’

②E’→+TE’｜ε

③T→FT’

④T’→*

FT’｜ε

⑤F→(

E

)｜id輸入id+id*id

ETE’FT’T＋E’idεFT’idεF＊T’idε例遞歸下降分析

(Recursive-DescentParsing)由一組過程組成，每個過程對應一個非終結符從文法開始符號S對應的過程開始，其中遞歸調用文法中其它非終結符對應的過程。如果S對應的過程體恰好掃描了整個輸入串，則成功完成語法分析voidA(){選擇一個A產(chǎn)生式，A→X1X2…Xk

；for

(i=1tok){if

(Xi是一個非終結符號)

調用過程Xi();elseif(Xi

等于當前的輸入符號a)

讀入下一個輸入符號;else/*發(fā)生了一個錯誤*/;}}可能需要回溯(backtracking)，導致效率較低自頂向下語法分析的通用形式

預測分析是遞歸下降分析技術的一種，它不需要回溯，因此，是一種確定的自頂向下分析方法通過在輸入中向前看固定個數(shù)符號來選擇正確的A-產(chǎn)生式。通常情況下只需向前看一個符號（即下一個輸入符號）可以對某些文法構造出向前看k個輸入符號的預測分析器，該類文法有時也稱為LL(k)文法類預測分析(PredictiveParsing)例文法G

S→aAd|aBe

A→c

B→b輸入

abc同一非終結符的多個候選式存在共同前綴，將導致回溯現(xiàn)象自頂向下分析中遇到的問題問題1例文法GE→E+T|E–T|TT→T*F|T/F|FF→(E)|id輸入

id+id*id左遞歸文法會使遞歸下降分析器陷入無限循環(huán)E

E+T

E+T+T+T

E+T+T

…如果一個文法中有一個非終結符A使得對某個串α存在一個推導A

+Aα，那么這個文法就是左遞歸的含有A→Aα形式產(chǎn)生式的文法稱為是直接左遞歸的(immediateleftrecursive)經(jīng)過兩步或兩步以上推導產(chǎn)生的左遞歸稱為是間接左遞歸的問題2

A→Aα|β (α≠ε,

β不以A開頭)

A→βA′

A′→αA′｜ε例

事實上，這種消除過程就是把左遞歸轉換成了右遞歸E→E+T｜TT→T*F｜FF→(E)｜idE→TE′E′→+TE′|εT→FT′T′→*FT′｜εF→(E)｜idαβαβA

Aα

Aαα

Aααα…

Aα…α

βα

…αA′

αA′

ααA′

αααA′…

α…αA′

α…αr=βα*消除直接左遞歸A→Aα1|Aα2|…|Aαn

|β1|β2|…|βm(αi

≠ε,

βj不以A開頭)A

β1A′|β2A′|…|βm

A′A′

α1A′|α2A′|…|αn

A′|ε

消除左遞歸是要付出代價的——引進了一些非終結符和ε_產(chǎn)生式消除直接左遞歸的一般形式例

S→Aa|bA→Ac|Sd|ε將S的定義代入A-產(chǎn)生式，得：A→Ac|Aad|bd|ε消除A-產(chǎn)生式的直接左遞歸，得：A→bd

A’|A’A’→cA’|ad

A’|εS

Aa

Sda消除間接左遞歸輸入：不含循環(huán)推導（即形如A

+A的推導）和ε-產(chǎn)生式的文法G輸出：等價的無左遞歸文法方法：按照某個順序將非終結符號排序為A1，A2，…，An

.

for

(從1到n的每個i){for

(從1到i-1的每個i){

將每個形如Ai→Aj

γ的產(chǎn)生式替換為產(chǎn)生式組Ai→δ1

γ∣δ2

γ∣…∣δk

γ，

其中Aj→δ1∣δ2∣…∣δk

，是所有的Aj

產(chǎn)生式

}

消除Ai

產(chǎn)生式之間的立即左遞歸}

消除左遞歸算法例文法GS

→aAd|aBeA→cB→b文法G'S→aS'S'→Ad|BeA→cB→b

通過改寫產(chǎn)生式來推遲決定，等讀入了足夠多的輸入，獲得足夠信息后再做出正確的選擇提取左公因子(LeftFactoring)輸入：文法G輸出：等價的提取了左公因子的文法方法：

提取左公因子算法對于每個非終結符A，找出它的兩個或多個選項之間的最長公共前綴α。如果α≠ε，即存在一個非平凡的(nontrivial)公共前綴，那么將所有A-產(chǎn)生式A→

α

β1|α

β2|…|α

βn|γ1

|γ2

|…|γm替換為A→α

A'|γ1

|γ2

|…|γmA'→β1

|β2

|…|βn其中，

γi

表示所有不以α開頭的產(chǎn)生式體；

A'是一個新的非終結符。不斷應用這個轉換，直到每個非終結符的任意兩個產(chǎn)生式體都沒有公共前綴為止4.1自頂向下的分析4.2預測分析法4.3自底向上的分析4.4LR分析法4.5語法分析器自動生成工具提綱S_文法不含ε產(chǎn)生式預測分析法的工作過程從文法開始符號出發(fā)，在每一步推導過程中根據(jù)當前句型的最左非終結符A和當前輸入符號a，選擇正確的A-產(chǎn)生式。為保證分析的確定性，選出的候選式必須是唯一的。S_文法（簡單的確定性文法，Korenjak&Hopcroft，1966）假如允許S_文法包含ε產(chǎn)生式，將會產(chǎn)生什么問題？每個產(chǎn)生式都以終結符開始同一非終結符的各個候選式的首終結符都不同4.2.1LL(1)文法什么時候使用ε產(chǎn)生式？如果當前某非終結符A與當前輸入符a不匹配時，若存在A→ε，可以通過檢查a是否可以出現(xiàn)在A的后面，來決定是否使用產(chǎn)生式A→ε（若文法中無A→ε

，則應報錯）輸入

ada推導

S→aBC

B→bC

B→dB

B→ε

C→c

C→a

D→e

S

aBC

adBC

adC

adaade

S

aBC

adBC

adC可以緊跟B后面出現(xiàn)的終結符：c、a例文法非終結符A的后繼符號集可能在某個句型中緊跟在A后邊的終結符a的集合，記為

FOLLOW(A)={a|S

*

αAaβ,a∈VT，α,β∈(VT∪VN)*}例(1)S→aBC(2)B→bC(3)B→dB(4)B→ε(5)C→c(6)C→a

FOLLOW(B)={a,c}輸入bd{a,c}如果A是某個句型的的最右符號，則將結束符“$”添加到FOLLOW(A)中非終結符的后繼符號集產(chǎn)生式A→β的可選集是指可以選用該產(chǎn)生式進行推導時對應的輸入符號的集合，記為SELECT(A→β)SELECT(A→aβ)={a

}SELECT(A→ε)=FOLLOW(A)q_文法每個產(chǎn)生式的右部或為ε

，或以終結符開始具有相同左部的產(chǎn)生式有不相交的可選集q_文法不含右部以非終結符打頭的產(chǎn)生式產(chǎn)生式的可選集

串首終結符串首第一個符號，并且是終結符。簡稱首終結符給定一個文法符號串α，α的串首終結符集FIRST(α)被定義為可以從α推導出的所有串首終結符構成的集合。如果α

*ε，那么ε也在FIRST(α)中對于

α∈(VT∪VN)+,FIRST(α)={a|α

*

aβ，a∈VT，β∈(VT∪VN)*}；如果

α

*ε，那么

ε∈FIRST(α)產(chǎn)生式A→α的可選集SELECT如果

ε

FIRST(α),那么SELECT(A→α)=FIRST(α)如果

ε∈FIRST(α),那么SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)串首終結符集文法G是LL(1)的，當且僅當G的任意兩個具有相同左部的產(chǎn)生式A→α|β滿足下面的條件：如果α和β均不能推導出ε，則FIRST(α)∩FIRST(β)=Φα

和β至多有一個能推導出ε如果β

*ε，則FIRST(α)∩FOLLOW(A)=Φ；

如果α

*ε，則FIRST(β)∩FOLLOW(A)=Φ；同一非終結符的各個產(chǎn)生式的可選集互不相交可以為LL(1)文法構造預測分析器LL(1)文法第一個“L”表示從左向右掃描輸入第二個“L”表示產(chǎn)生最左推導“1”表示在每一步中只需要向前看一個輸入符號來決定語法分析動作文法G是LL(1)的，當且僅當G的任意兩個具有相同左部的產(chǎn)生式A→α|β滿足下面的條件：如果α和β均不能推導出ε，則FIRST(α)∩FIRST(β)=Φα

和β至多有一個能推導出ε如果β

*ε，則FIRST(α)∩FOLLOW(A)=Φ；

如果α

*ε，則FIRST(β)∩FOLLOW(A)=Φ；LL(1)文法例①E→TE'

②E'→+TE'|ε

③T→FT'

④T'→*FT'|ε

⑤F→(E)|id +

ε*

ε

(id(

id

(id

FIRST(E)={ }FIRST(E')={ }FIRST(T)={ }FIRST(T')={ }FIRST(F)={ }FIRST(X)：可以從X推導出的所有串首終結符構成的集合如果

X

*ε，那么

ε∈FIRST(X)計算文法符號X的FIRST(X)不斷應用下列規(guī)則，直到?jīng)]有新的終結符或ε可以被加入到任何FIRST集合中為止如果X是一個終結符，那么FIRST(X)={X}如果X是一個非終結符，且X→Y1…Yk∈P(k≥1)，那么如果對于某個i，a在FIRST(Yi)中且ε在所有的FIRST(Y1),…,FIRST(Yi-1)中(即Y1...Yi-1

*ε)，就把a加入到FIRST(X)中。如果對于所有的j=1,2,...,k，ε在FIRST(Yj)中，那么將ε加入到FIRST(X)如果

X→ε∈P，那么將ε加入到FIRST(X)中算法向FIRST(X1X2

…Xn)加入FIRST(X1)中所有的非ε符號如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符號；如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符號，以此類推最后，如果對所有的i，ε都在FIRST(Xi)中，那么將ε加入到FIRST(X1X2

…Xn)中計算串X1X2…Xn的FIRST集合計算非終結符A的FOLLOW(A)FOLLOW(A)：可能在某個句型中緊跟在A后邊的終結符a的集合FOLLOW(A)={a|S

*

αAaβ,a∈VT，α,β∈(VT∪VN)*}如果A是某個句型的的最右符號，則將結束符“$”添加到FOLLOW(A)中例①E→TE'

②E'→+TE'|ε

③T→FT'

④T'→*FT'|ε

⑤F→(E)|id FOLLOW(E)={ }FOLLOW(E')={ }FOLLOW(T)={

}FOLLOW(T')={

}FOLLOW(F)={

}$)

+)$

)$

+$

*)+$

)FIRST(E)={(id}FIRST(E')={+ε}FIRST(T)={(id}FIRST(T')={*ε}FIRST(F)={(id}不斷應用下列規(guī)則，直到?jīng)]有新的終結符可以被加入到任何FOLLOW集合中為止將$放入FOLLOW(S)中，其中S是開始符號，$是輸入右端的結束標記如果存在一個產(chǎn)生式A→αBβ，那么FIRST(β)中除ε

之外的所有符號都在FOLLOW(B)中如果存在一個產(chǎn)生式A→αB，或存在產(chǎn)生式A→αBβ且FIRST(β)包含ε，那么

FOLLOW(A)中的所有符號都在FOLLOW(B)中算法例：表達式文法各產(chǎn)生式的SELECT集(1)E→TE'(2)E'→+TE'(3)E'→ε

(4)T→FT'(5)T'→*FT'(6)T'→ε(7)F→(E)(8)F→idSELECT(1)={(id}SELECT(2)={+}SELECT(3)={$

)}SELECT(4)={(id}SELECT(5)={*}SELECT(6)={+)$

}SELECT(7)={(}SELECT(8)={id}表達式文法是LL(1)文法XFIRST(X)FOLLOW(X)E(id$)E'+ε$)T(id+)$T'*ε

+)$F(id*+)$產(chǎn)生式SELECTEE→TE'(idE'E'→+TE’+E'→ε$)TT→FT'(idT'T'→*FT’*FF→(E)(F→idid非終結符輸入符號id+*()$

EE→TE'E→TE'E'E'→+TE’E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT’T'→εT'→εFF→idF→(E)預測分析表遞歸的預測分析法非遞歸的預測分析法LL(1)文法的分析方法voidA(){選擇一個A產(chǎn)生式，A→X1X2…Xk

；for

(i=1tok){if

(Xi是一個非終結符號)

調用過程Xi();elseif(Xi

等于當前的輸入符號a)

讀入下一個輸入符號;else/*發(fā)生了一個錯誤*/;}}4.2.2遞歸的預測分析法

遞歸的預測分析法是指：在遞歸下降分析中，根據(jù)預測分析表進行產(chǎn)生式的選擇根據(jù)每個非終結符的產(chǎn)生式和LL(1)文法的預測分析表，為每個非終結符編寫對應的過程例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprogramDESCENT; begin GETNEXT(TOKEN);

PROGRAM(TOKEN); GETNEXT(TOKEN);

if

TOKEN≠’$’thenERROR; end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→int

procedurePROGRAM(TOKEN); begin

ifTOKEN≠’program’thenERROR;

GETNEXT(TOKEN); DECLIST(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’:’thenERROR;

GETNEXT(TOKEN); TYPE(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’;’thenERROR;

GETNEXT(TOKEN); STLIST(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’end’thenERROR; end

例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureDECLIST(TOKEN); begin

ifTOKEN≠’id’thenERROR;

GETNEXT(TOKEN); DECLISTN(TOKEN); end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureDECLISTN(TOKEN); begin

ifTOKEN=‘,’then begin GETNEXT(TOKEN);

ifTOKEN≠’id’thenERROR;

GETNEXT(TOKEN);

DECLISTN(TOKEN); end

elseifTOKEN≠’:’thenERROR; end 例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureSTLIST(TOKEN); begin

ifTOKEN≠’s’thenERROR; GETNEXT(TOKEN);

STLISTN(TOKEN); end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureSTLISTN(TOKEN); begin

ifTOKEN=‘;’then begin GETNEXT(TOKEN);

ifTOKEN≠’s’thenERROR;

GETNEXT(TOKEN);

STLISTN(TOKEN); end

elseifTOKEN≠’end’thenERROR; end

例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureTYPE(TOKEN); begin

ifTOKEN≠’real’orTOKEN≠’int’ thenERROR; end4.2.3非遞歸的預測分析法非遞歸的預測分析不需要為每個非終結符編寫遞歸下降過程，而是根據(jù)預測分析表構造一個自動機，也叫表驅動的預測分析a+b$預測分析程序輸入預測分析表M棧輸出XYZ$下推自動機

(PushDownAutomata,PDA)例：L={anbn|n≥1}

棧

剩余輸入

輸出

E$ id+id*id$

TE'$id+id*id

$ E→TE'

FT'E'$id+id*id

$ T→FT'idT'E'$id+id*id

$ F→id

T'E'$

+id*id

$

E'$+id*id

$ T'→ε+TE'$ +id*id

$ E'→+TE'

TE'$ id*id

$

FT'E'$id*id

$ T→FT'idT'E'$ id*id

$ F→id

T'E'$*id

$ *FT'E'$

*id

$ T'→*FT'

FT'E'$

id

$ idT'E'$

id

$ F→id

T'E'$

$

E'$

$ T'→ε

$$ E'→ε如果w是至今為止已經(jīng)匹配完成的輸入部分，那么棧中保存的文法符號序列α滿足S*lm

wα例輸入符號id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)非終結符輸入：一個串w和文法G的分析表

M輸出：如果w在L(G)中，輸出w的最左推導；否則給出錯誤指示方法：最初，語法分析器的格局如下：輸入緩沖區(qū)中是w$，G的開始符號位于棧頂，其下面是$。下面的程序使用預測分析表M生成了處理這個輸入的預測分析過程設置ip使它指向w的第一個符號，其中ip是輸入指針；令X=棧頂符號；while

(X≠＄

)｛

/*棧非空*/

if

(X等于ip所指向的符號a)執(zhí)行棧的彈出操作，將ip向前移動一個位置；elseif(X是一個終結符號)error();elseif(M[X，a]是一個報錯條目)error();elseif(M[X，a]=X→Y1Y2…Yk

)｛

輸出產(chǎn)生式X→Y1Y2…Yk

；

彈出棧頂符號；

將Yk，Yk-1…，Yi

壓入棧中，其中Y1位于棧頂。}

令X=棧頂符號}表驅動的預測分析法遞歸的預測分析法非遞歸的預測分析法程序規(guī)模程序規(guī)模較大，不需載入分析表主控程序規(guī)模較小，需載入分析表（表較?。┲庇^性較好較差效率較低分析時間大約正比于待分析程序的長度自動生成較難較易遞歸的預測分析法vs.非遞歸的預測分析法1）構造文法2）改造文法：消除二義性、消除左遞歸、消除回溯3）求每個變量的FIRST集和FOLLOW集，從而求得每個

候選式的SELECT集4）檢查是不是LL(1)文法。若是，構造預測分析表5）對于遞歸的預測分析，根據(jù)預測分析表為每一個非終結

符編寫一個過程；對于非遞歸的預測分析，實現(xiàn)表驅動

的預測分析算法預測分析法實現(xiàn)步驟錯誤檢測棧頂?shù)慕K結符和當前輸入符號不匹配棧頂非終結符與當前輸入符號在預測分析表對應項中的信息為空4.2.4預測分析中的錯誤處理預測分析中的錯誤恢復恐慌模式忽略輸入中的一些符號，直到輸入中出現(xiàn)由設計者選定的同步詞法單元(synchronizingtoken)集合中的某個詞法單元其效果依賴于同步集合的選取。集合的選取應該使得語法分析器能從實際遇到的錯誤中快速恢復例如可以把FOLLOW(A)中的所有終結符放入非終結符A的同步記號集合如果終結符在棧頂而不能匹配，一個簡單的辦法就是彈出此終結符例分析表的使用方法如果M[A,a]是空，表示檢測到錯誤，根據(jù)恐慌模式，忽略輸入符號a如果M[A,a]是synch，則彈出棧頂?shù)姆墙K結符A，試圖繼續(xù)分析后面的語法成分如果棧頂?shù)慕K結符和輸入符號不匹配，則彈出棧頂?shù)慕K結符輸入符號id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)synchsynchsynchsynchsynchsynchsynchsynchsynch非終結符Synch表示根據(jù)相應非終結符的FOLLOW集得到的同步詞法單元X

FOLLOW(X)E

$)E'

$)T

+)$T'

+)$F

*+)$

棧 剩余輸入

E$

+id*+id$ignore+

E$id*+id$

TE'$id*+id$

FT'E'$id*+id$ idT'E'$id*+id$ T'E'$*+id$ *FT'E'$*+id$ FT'E'$+id$error

T'E'$ +id$

E'

$ +id$ +TE'$ +id$

TE'$ id$

FT'E'$ id$idT'E'$ id$

T'E'$ $

E'$ $ $ $

輸入符號id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)synchsynchsynchsynchsynchsynchsynchsynchsynch非終結符4.1自頂向下的分析4.2預測分析法4.3自底向上的分析4.4LR分析法4.5語法分析器自動生成工具提綱從分析樹的底部(葉節(jié)點)向頂部(根節(jié)點)方向構造分析樹可以看成是將輸入串w歸約為文法開始符號S的過程自頂向下的語法分析采用最左推導方式自底向上的語法分析采用最左歸約方式（反向構造最右推導）自底向上語法分析的通用框架移入-歸約分析(Shift-ReduceParsing)4.3自底向上的語法分析每次歸約的符號串稱為“句柄”。它是某個產(chǎn)生式的右部。對它的歸約代表了相應的最右推導中的一個反向步驟例：移入-歸約分析棧剩余輸入

動作$

id+(id+id)$$id +(id+id)$

移入$E+(id+id)$

歸約:E→id$E+ (id+id)$

移入$E+( id+id)$

移入$E+(id +id)$

移入$E+(E +id)$

歸約:E→id$E+(E+id)$

移入$E+(E+id )$

移入$E+(E+E )$

歸約:E→id$E+(E )$

歸約:E→E+E$E+(E) $

移入$E+E $

歸約:E→(E)$E $

歸約:E→E+EEEEEEE文法①E→E+E②E→E*E③E→(E)④E→idid

id

id

++

(

)棧內符號串+剩余輸入=“規(guī)范句型”棧剩余輸入

動作$

id+(id+id)$$id +(id+id)$

移入$E+(id+id)$

歸約:E→id$E+ (id+id)$

移入$E+( id+id)$

移入$E+(id +id)$

移入$E+(E +id)$

歸約:E→id$E+(E+id)$

移入$E+(E+id )$

移入$E+(E+E )$

歸約:E→id$E+(E )$

歸約:E→E+E$E+(E) $

移入$E+E $

歸約:E→(E)$E $

歸約:E→E+E例：id

+(id+id

)EEEEEE文法①E→E+E②E→E*E③E→(E)④E→id在對輸入串的一次從左到右掃描過程中，語法分析器將零個或多個輸入符號移入到棧的頂端，直到它可以對棧頂?shù)囊粋€文法符號串β進行歸約為止然后，它將β歸約為某個產(chǎn)生式的左部語法分析器不斷地重復這個循環(huán)，直到它檢測到一個語法錯誤，或者棧中包含了開始符號且輸入緩沖區(qū)為空為止。當進入這樣的格局時，語法分析器停止運行，并宣稱成功完成了語法分析移入-歸約分析的工作過程移入：將下一個輸入符號移到棧的頂端歸約：被歸約的符號串的右端必然處于棧頂。語法分析器在棧中確定這個串的左端，并決定用哪個非終結符來替換這個串接收：宣布語法分析過程成功完成報錯：發(fā)現(xiàn)一個語法錯誤，并調用錯誤恢復子例程移入-歸約分析器可采取的4種動作文法(1)<S>→var<IDS>:<TYPE>(2)<IDS>→i(3)<IDS>→<IDS>,i(4)<TYPE>→real|int$

var$variA

$var

<IDS>$var<IDS>,$var

<IDS>,

iBvar<IDS>var<IDS>:var<IDS>:

realvar<IDS>:<TYPE><S>輸入var

iA

,

iB

:

realvar<IDS>,<IDS>var<IDS>,<IDS>:var<IDS>,<IDS>:

realvar<IDS>,<IDS>:<TYPE>造成錯誤歸約的原因：錯誤地識別了句柄（產(chǎn)生式的右部不一定都是句柄）棧移入-歸約分析中的關鍵問題<S><TYPE>:<IDS>variB,<IDS>iAreal自底向上分析采用最左歸約方式，它是最右推導的逆過程，因此，每一步歸約都是最右推導中某一步的反向操作

最右推導每一步得到的符號串都是該文法的一個規(guī)范句型，因此，最左歸約每一步得到的符號串也是該文法的一個規(guī)范句型對于A→β∈P，如果S

*rm

αAw

rm

αβw(即αAw和αβw都是

該文法的規(guī)范句型)，則稱β是規(guī)范句型αβw的句柄(Handle)如何正確地識別句柄？句柄的正式定義4.1自頂向下的分析4.2預測分析法4.3自底向上的分析4.4LR分析法4.5語法分析器自動生成工具提綱4.4LR分析法LR文法(Knuth,1963)是最大的、可以構造出相應移入-歸約語法分析器的文法類L:對輸入進行從左到右的掃描R:反向構造出一個最右推導序列LR(k)分析需要向前查看k個輸入符號的LR分析k=0和

k=1這兩種情況具有實踐意義當省略(k)時，假設k=1自底向上分析的關鍵問題是什么？如何正確地識別句柄句柄是逐步形成的，用“狀態(tài)”表示句柄識別的進展程度例：S→bBB

S→.bBB

S→b.BB

S→bB.B

S→bBB.歸約狀態(tài)移進狀態(tài)待約狀態(tài)LR分析器基于這樣一些狀態(tài)來構造自動機進行句柄的識別LR分析法的基本原理a1…ai…an

$LR主控程序動作表ACTION轉移表GOTO產(chǎn)生式序列狀態(tài)/符號棧輸入緩沖區(qū)分析表SmSm-1………S1S0XmXm-1………X1$LR分析器（自動機）的總體結構例文法①S→BB②B→aB③B→b輸入babsn：將符號a、狀態(tài)n

壓入棧rn：用第n個產(chǎn)生式進行歸約狀態(tài)ACTIONGOTOab$SB0s3s4121acc2s3s453s3

s464r3r3r35r1r1r16r2r2r2LR分析表的結構①如果ACTION[sm,ai]=sx，那么格局變?yōu)椋簊0s1…smx

$X1…Xmaiai+1…an$初始化一般情況下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作過程初始化一般情況下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作過程②如果ACTION[sm,ai]=rx表示用第x個產(chǎn)生式A→Xm-(k-1)…Xm

進行歸約，那么格局變?yōu)椋簊0

s1…sm-k$X1…Xm-kA

ai

ai+1…an$s0

s1…sm-ky

$X1…Xm-kA

ai

ai+1…an$如果GOTO[sm-k,A]=y，那么格局變?yōu)椋撼跏蓟话闱闆r下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作過程③如果ACTION[sm,ai]=acc，那么分析成功④如果ACTION[sm,ai]=err，那么出現(xiàn)語法錯誤輸入：串w和LR語法分析表，該表描述了文法G的ACTION函數(shù)和

GOTO函數(shù)。

輸出：如果w在

L(G)中，則輸出w的自底向上語法分析過程中的歸約

步驟；否則給出一個錯誤指示。方法：初始時，語法分析器棧中的內容為初始狀態(tài)s0，輸入緩沖區(qū)中

的內容為w$。然后，語法分析器執(zhí)行下面的程序：令a為w$的第一個符號；

while(1){/*永遠重復*/令s是棧頂?shù)臓顟B(tài)；if(ACTION[s，a]

=st){將t壓入棧中；

令a為下一個輸入符號；}elseif(ACTION[s，a]

=歸約A→β){

從棧中彈出│β│個符號；

將GOTO[t，A]壓入棧中；

輸出產(chǎn)生式A→β

；}elseif(ACTION[s，a]

=接受)break；/*語法分析完成*/else調用錯誤恢復例程；

}LR分析算法LR(0)分析SLR分析LR(1)分析LALR分析如何構造給定文法的LR分析表？右部某位置標有圓點的產(chǎn)生式稱為相應文法的一個LR(0)項目（簡稱為項目）

A→α1.α2例：S→bBB

歸約項目移進項目待約項目S→.bBB

S→b.BB

S→bB.B

S→bBB.項目描述了句柄識別的狀態(tài)產(chǎn)生式A→ε

只生成一個項目A→·4.4.1LR(0)分析如果G

是一個以S為開始符號的文法，則G的增廣文法

G'

就是在G中加上新開始符號S'

和產(chǎn)生式S'

→

S而得到的文法例1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)

6)F→id0)E'→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)

6)F→id引入這個新的開始產(chǎn)生式的目的是使得文法開始符號僅出現(xiàn)在一個產(chǎn)生式的左邊，從而使得分析器只有一個接受狀態(tài)增廣文法(AugmentedGrammar)①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.歸約項目接收項目初始項目文法中的項目①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r后繼項目（SuccessiveItem）同屬于一個產(chǎn)生式的項目，但圓點的位置只相差一個符號，

則稱后者是前者的后繼項目A→α.Xβ的后繼項目是A→αX.β(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.文法中的項目①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r這15個項目中是否會有某些項目是等價的？可以把等價的項目組成一個項目集(I)

，稱為項目集閉包(ClosureofItemSets)，每個項目集閉包對應著自動機的一個狀態(tài)(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.文法中的項目狀態(tài)ACTIONGOTOab$SB0s3s4121acc2s3s453s3

s464r3r3r35r1r1r16r2r2r2LR(0)分析表例：LR(0)自動機I0:S'→·SS→·BBB→·aBB→·b

I1:S'→S·SBI2:S→B·BB→·aBB→·b

aI3:B→a·BB→·aBB→·b

bI4:B→b·

BI5:S→BB·abBI6:B→aB·ab文法(0)S'→S

(1)S→BB(2)B→aB(3)B→bCLOSURE()函數(shù)76CLOSURE(I)=I∪{B→·

γ|A→α·Bβ∈CLOSURE(I),B→γ∈P}計算給定項目集I的項目集閉包SetOfltems

CLOSURE(I){

J

=

I；repeat

for(J中的每個項A→

α?Bβ)

for(G的每個產(chǎn)生式B→

γ

)

if(項B→

?γ不在J中

)將B→

?γ加入J中；

until在某一輪中沒有新的項被加入到J中；

returnJ；}GOTO()函數(shù)77SetOfltems

GOTO(I，X){

將J

初始化為空集；

for(I

中的每個項A→

α?Xβ

)