第08講-語法分析-III

本講綱要回顧重點：FIRST集、FOLLOW集LL(1)文法自上而下分析實現(xiàn)遞歸函數(shù)法非遞歸的預測分析方法構造預測分析表1FIRST集和FOLLOW集FIRST(

)={a|

*a…,a

VT}計算滿足的句子的所有可能開頭字符特殊情況：當

*時，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}計算語言的句型中所有可能跟在A后面的字符特殊情況：如果A是某個句型的最右符號，那么$屬于FOLLOW(A)2FIRST集合及FOLLOW集合的計算方法FIRST集合計算方法若Xa..，則將終結符ａ加入FIRST(X)中若X，則將加入FIRST(X)中若XY…，且Y屬于非終結符，則將FIRST(Y)\{}加入到FIRST(X)中若XY1Y2..YK,且Y1,Y2,..Yi-1(2≤i≤k)都是非終結符，且Y1,Y2,..Yi-1的FIRST集合中均包含，則將FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特別地，若Y1~YK均有產生式，則將加到FIRST(X)中。3SBAABS|dBaA|bS|cFIRST(S)=FIRST(B)FIRST(A)=FIRST(B)∪

hsdw5byFIRST(B)={a,b,c}步驟1：FIRST集和FOLLOW集FIRST(

)={a|

*a…,a

VT}計算滿足的句子的所有可能開頭字符特殊情況：當

*時，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}計算語言的句型中所有可能跟在A后面的字符特殊情況：如果A是某個句型的最右符號，那么$屬于FOLLOW(A)4A的FOLLOW集合，是從開始符號可以導出的所有含A的文法符號序列中緊跟A之后的終結符。α的FIRST集合是從α開始可以導出的文法符號序列中的開頭終結符。FOLLOW集合的計算方法FOLLOW集合計算方法對文法開始符號S,置$于FOLLOW(S)中。若有AB，則將FIRST()\{}加入FOLLOW(B)中。（此處可以為空）若AB或AB,且*（即屬于FIRST()）,則將

FOLLOW(A)加入FOLLOW(B)中（此處可以為空）。5SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?FOLLOW集計算文法6SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={$}FOLLOW(A)={}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW集計算文法7SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={$}FOLLOW(A)={a,b,c,d}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW集計算文法8SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={a,b,c,d,$}FOLLOW(A)={a,b,c,d}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW(B)中的所有元素都可以加到FOLLOW(S)中FOLLOW集計算文法9SBAABS|dBaA|bS|c第1步：FOLLOW(S)<-$FOLLOW(S)={a,b,c,d,$}FOLLOW(A)={a,b,c,d,$}FOLLOW(B)={a,b,c,d}第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S)FIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(B)中的所有元素都可以加到FOLLOW(A)中FOLLOW(B)中的所有元素都可以加到FOLLOW(S)中FOLLOW(S)中的所有元素都可以加到FOLLOW(A)中102023/2/2

目錄自上而下的語法分析First集合、Follow集合LL（1）文法自上而下的預測分析方法構造非遞歸預測分析表語法分析112023/2/2

句子

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調|導航動詞

設為|開數(shù)詞25度|A

|

(1)FIRST(

)FIRST()=(2)若

*，那么FIRST()FOLLOW(A)=FOLLOW(賓語)=FOLLOW(數(shù)詞)={$}{$}LL(1)文法2.FIRST(數(shù)詞)={25度，}FIRST(25度)={25度

}LL(1)文法LL(1)文法 任何兩個產生式A

|都滿足下列條件：FIRST(

)FIRST()=若

*，那么FIRST()FOLLOW(A)=LL(1)文法有一些明顯的性質沒有公共左因子不是二義的不含左遞歸12LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|id該文法是LL(1)文法嗎？13E

+TE|和T

*FT

|是判斷的重點！LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|idFIRST(+TE

)={+}FOLLOW(E)={),$}FIRST(*

FT

)={*}FOLLOW(T)={+,),$}14結論：該文法是LL(1)文法！LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|id15結論：該文法是LL(1)文法！FIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}FOLLOW(F)={+,*,),$}162023/2/2

自上而下的語法分析自上而下的語法分析First集合、Follow集合LL（1）文法自上而下的預測分析方法構造非遞歸預測分析表語法分析172023/2/2

預測分析方法—遞歸3.句子

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調|導航動詞

設為|開數(shù)詞25度|句子(){主語();

謂語();

賓語();}主語(){名詞();}名詞(){ if(lookahead==“空調”){

match(“空調”);

}else{match(“導航”);}}句子

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調|導航動詞

設為|開數(shù)詞25度|182023/2/2

主語謂語

名詞動詞

空調設為設為25度賓語$$空調

數(shù)詞輸入:X=a$Xa,XVNXa,XVTX=a=$25度句子預測分析方法3.遞歸的分析程序19SBAABS|dBaA|bS|cS(){B();A();}A(){if(lookahead==‘a’|’b’|’c’){B();S();}elsematch(‘d’);}B(){if(lookahead==‘a’){match(‘a’);A();}elseif(lookahead==‘b’){match(‘b’);S();}elsematch(‘c’);}遞歸下降的預測分析遞歸下降的預測分析為每一個非終結符寫一個分析過程這些過程可能是遞歸的例： type

simple

|id

|array[simple]oftype simpleinteger

|char

|numdotdotnum20遞歸下降的預測分析一個輔助過程procedurematch(t:token);begin iflookahead==tthen lookahead:=nexttoken() elseerror()end;21遞歸下降的預測分析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;22type

simple |id |array[simple]oftype遞歸下降的預測分析proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;23simpleinteger |char |numdotdotnum242023/2/2

目錄自上而下的語法分析First集合、Follow集合LL（1）文法自上而下的預測分析方法構造非遞歸預測分析表語法分析252023/2/2

空調導航開設為25度$動詞

賓語數(shù)詞句子主語謂語

名詞句子

主語謂語賓語主語

名詞名詞

空調|導航謂語

動詞

動詞

設為|開賓語

數(shù)詞|數(shù)詞

25度|句子

主語謂語賓語句子

主語謂語賓語主語

名詞主語

名詞名詞

空調

名詞

導航謂語

動詞謂語

動詞動詞

設為動詞

開賓語

數(shù)詞賓語數(shù)詞25度數(shù)詞構造預測分析表4.262023/2/2

對每個產生式A

FIRST()的每個a，把A加入M[A,a]FOLLOW(A)的b（包括$）把A

加入M[A,b]M的其它沒有定義的條目都是error在FIRST()NY構造預測分析表4.272023/2/2

First集合、Follow集合LL（1）文法自上而下的預測分析方法構造非遞歸預測分析表遞歸下降預測分析非遞歸的預測分析A|滿足下列條件：1、FIRST()FIRST()=2、若

*，那么FIRST()FOLLOW(A)=總結實現(xiàn)first集合、follow集合程序設計實現(xiàn)非遞歸的預測分析程序針對非LL（1）文法，如何實現(xiàn)自上而下的語法分析？282023/2/2習題3.3

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

XYZ$棧預測分析表用于驅動分析的全過程3.3

自上而下分析30非終結符輸入符號id+*...EETE

E

E

+TE

TTFT

T

T

T

*FTFFid書上57頁表3.13.3

自上而下分析31棧輸入輸出

…

…預測分析器接受輸入id*id+id的動作

$Eid*id+id$E

TE$E’Tid*id+id$T

FT$E’T’Fid*id+id$F

id$E’T’idid*id+id$一個符號被消耗*id+id$$E’T’Match(id)T’

*FT’$E’T’F**id+id$Match(*)id+id$$E’T’F預測分析表的構建（1）對文法的每個產生式A

，執(zhí)行(2)和(3)。（2）對FIRST()的每個終結符a，把A

加入M[A,a]（即加入表中A行a列）。（3）如果在FIRST()中，對FOLLOW(A)的每個終結符b（包括$）,把A

加入M[A,b]。（4）M的其它沒有定義的條目都是error。32文法S->ACDA->a|C->cD->d33FIRST(S)={a,c}FIRST(A)={a,}FIRST(C)={c}FIRST(D)=905s4itFOLLOW(S)={$}FOLLOW(A)={c}FOLLOW(C)=n8ziuxhFOLLOW(D)={$}預測分析表的構建非終結符輸入符號acd$SACD

34FIRST(S)={a,c}FIRST(A)={a,}FIRST(C)={c}FIRST(D)=wmo08ggFOLLOW(S)={$}FOLLOW(A)={c}FOLLOW(C)=k1130nuFOLLOW(D)={$}S->ACDS->ACDA->aA->C->cD->dERRORERRORERRORERRORERRORERROR文法S->ACDA->a|C->cD->dERRORERRORERRORERROR上下文無關文法自上而下自下而上LL(1)文法2個函數(shù)遞歸下降預測分析非遞歸的預測分析最左推導任何兩個產生式A