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

)={a|

*a…,a

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

*時，規(guī)定

FIRST(

)FOLLOW(A)={a|S

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

imaygmsFIRST(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之后的終結(jié)符。α的FIRST集合是從α開始可以導出的文法符號序列中的開頭終結(jié)符。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）文法自上而下的預測分析方法構(gòu)造非遞歸預測分析表語法分析112023/2/2

句子

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調(diào)|導航動詞

設(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)文法 任何兩個產(chǎn)生式A

|都滿足下列條件：FIRST(

)FIRST()=若

*，那么FIRST()FOLLOW(A)=LL(1)文法有一些明顯的性質(zhì)沒有公共左因子不是二義的不含左遞歸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結(jié)論：該文法是LL(1)文法！LL(1)文法例 E

TE E

+TE

|T

FTT

*

FT

|F

(E)|id15結(jié)論：該文法是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）文法自上而下的預測分析方法構(gòu)造非遞歸預測分析表語法分析172023/2/2

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

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調(diào)|導航動詞

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

謂語();

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

match(“空調(diào)”);

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

主語謂語賓語主語

名詞謂語

動詞

賓語

數(shù)詞|名詞

空調(diào)|導航動詞

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

主語謂語

名詞動詞

空調(diào)設(shè)為設(shè)為25度賓語$$空調(diào)

數(shù)詞輸入:X=a$Xa,XVNXa,XVTX=a=$25度句子預測分析方法3.遞歸的分析程序19SBAABS|dBaA|bS|cS(){B();A();}A(){if(lookahead==‘a(chǎn)’|’b’|’c’){B();S();}elsematch(‘d’);}B(){if(lookahead==‘a(chǎn)’){match(‘a(chǎn)’);A();}elseif(lookahead==‘b’){match(‘b’);S();}elsematch(‘c’);}遞歸下降的預測分析遞歸下降的預測分析為每一個非終結(jié)符寫一個分析過程這些過程可能是遞歸的例： 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）文法自上而下的預測分析方法構(gòu)造非遞歸預測分析表語法分析252023/2/2

空調(diào)導航開設(shè)為25度$動詞

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

名詞句子

主語謂語賓語主語

名詞名詞

空調(diào)|導航謂語

動詞

動詞

設(shè)為|開賓語

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

25度|句子

主語謂語賓語句子

主語謂語賓語主語

名詞主語

名詞名詞

空調(diào)

名詞

導航謂語

動詞謂語

動詞動詞

設(shè)為動詞

開賓語

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

對每個產(chǎn)生式A

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

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

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

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

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

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

自上而下分析30非終結(jié)符輸入符號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預測分析表的構(gòu)建（1）對文法的每個產(chǎn)生式A

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

加入M[A,a]（即加入表中A行a列）。（3）如果在FIRST()中，對FOLLOW(A)的每個終結(jié)符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)=smmagmkFOLLOW(S)={$}FOLLOW(A)={c}FOLLOW(C)=mgcagesFOLLOW(D)={$}預測分析表的構(gòu)建非終結(jié)符輸入符號acd$SACD

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