第五章 LL1文法及其分析程序

第5章自頂向下語法分析方法主要內(nèi)容：自上而下的語法分析預(yù)測(cè)分析程序遞歸下降子程序表驅(qū)動(dòng)的預(yù)測(cè)分析程序LL(1)分析程序的生成LL(1)文法FIRST和FOLLOW集定義和計(jì)算非LL(1)文法的改造2021/5/91

5.1確定的自頂向下語法分析思想1.語法分析概念2.自上而下的語法分析的一般過程3.自上而下的語法分析面臨的問題4.開始符號(hào)集5.后跟符號(hào)集6.select集7.LL(1)文法2021/5/921。語法分析在語言的編譯實(shí)現(xiàn)中，把句子分析的過程稱為語法分析，即完成這個(gè)任務(wù)的程序稱為語法分析程序或稱為識(shí)別程序。分析算法又稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。2021/5/93（上下文無關(guān)文法）句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型的過程，或者說是某個(gè)推導(dǎo)的構(gòu)造過程。2021/5/94語法樹－推導(dǎo)的幾何表示句型aabbaa的可能推導(dǎo)序列和語法樹

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aS

aAS

aAa

aSbAa

aSbbaa

aabbaaSaASaSbASaabASaabbaS

aabbaaSaASaSbAS

aSbAa

aabAa

aabbaa2021/5/95分析算法分類分析算法可分為：自上而下分析法：

從文法的開始符號(hào)出發(fā)，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。自下而上分析法：

從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。

2021/5/96兩種方法反映了語法樹的兩種構(gòu)造過程。自上而下方法是從文法符號(hào)開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號(hào)串自下而上方法則是從輸入符號(hào)串開始，以它做為語法樹的結(jié)果，自底向上的構(gòu)造語法樹2021/5/972。自上而下分析方法

對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)著手，自上而下地為輸入串構(gòu)造一棵語法樹，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。本質(zhì)上是一個(gè)試探過程，反復(fù)使用不同地產(chǎn)生式謀求匹配輸入串的過程。

2021/5/98自上而下的語法分析的一般過程例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子 S S S

c A d

c A d

a

b推導(dǎo)過程：S

cAd

cAd

cabd2021/5/99

自上而下的語法分析的一般過程

(1)S→cAd(2)A→ab(3)A→a

識(shí)別輸入串w=cad是否為

該文法的句子1.S

cAd2.后選擇(2)擴(kuò)展A，得到推導(dǎo)S

cAd

cabd這時(shí)

w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)d卻不能與下一葉子結(jié)點(diǎn)b匹配怎么辦？-查看A有無另一個(gè)選擇，有！回溯，把A為根的子樹剪掉，掃描過的輸入串中的a吐出來,再試探用產(chǎn)生式（3）構(gòu)造推導(dǎo)S

cAd

cad識(shí)別輸入串w=caa的過程：1.S

cAd2.選擇(2)擴(kuò)展A，得到推導(dǎo)S

cAd

cabd3.回溯回到推導(dǎo)S

cAd4.選擇(3)擴(kuò)展A，得到推導(dǎo)S

cAd

cad5.A沒有選擇了！回溯到推導(dǎo)S

cAd6.再回溯S有無另一個(gè)選擇？沒有！

宣告分析失敗。（請(qǐng)思考若有

(4)S→cB

(5)B→aa會(huì)怎樣?

）2021/5/910自上而下分析的進(jìn)一步討論自上而下分析也稱面向目標(biāo)的分析方法，也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的符號(hào)串完全匹配的句子，若能構(gòu)造出推導(dǎo)則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對(duì)文法的要求－文法不能含有左遞歸規(guī)則。自上而下分析又可分為確定的和不確定的兩種

不確定的分析方法稱為帶回溯的分析方法，這種方法實(shí)際上是一種窮舉的試探方法

確定的分析方法需對(duì)文法有一定的限制2021/5/9113。自上而下的語法分析面臨的問題-實(shí)現(xiàn)考慮回溯文法的左遞歸性

S→Sa2021/5/912自上而下分析對(duì)文法的要求例文法G0[S]:(1)S→Sa(2)S→b

分析baa是不是文法的句子按照自上而下的分析思想選用產(chǎn)生式(1)來推導(dǎo)SSa

語法樹末端結(jié)點(diǎn)最左符號(hào)為非終結(jié)符，所以選用（1）繼續(xù)推導(dǎo)SSaSaa

此時(shí)語法樹末端結(jié)點(diǎn)最左符號(hào)仍為非終結(jié)符，所以選用（1）繼續(xù)推導(dǎo)SSaSaaSaaa問題——試圖用S匹配輸入串時(shí)，出現(xiàn)：在沒有讀入任何輸入符號(hào)的情況下，又得重新要求S去進(jìn)行新的匹配.無法確定什么時(shí)候使用（2）產(chǎn)生式最適當(dāng)，只能采用帶回溯的不確定方法解決。原因——文法含有左遞歸。2021/5/913回溯的原因例G[S]:S→xAyA→ab｜a

若當(dāng)前輸入串為xay，首先構(gòu)造的推導(dǎo)S

xAy

匹配進(jìn)一步推導(dǎo)對(duì)A可選擇A→ab替換，得S

xAy

xabyxayxaby

匹配xa都已匹配，當(dāng)前面臨輸入符為y與b不能匹配，所以將輸入串指針退回到a，對(duì)A的替換重新選用下一個(gè)產(chǎn)生式A→a進(jìn)行試探，S

xAy

xay輸入串中當(dāng)前符a得到匹配，指針向前移動(dòng)到y(tǒng)，與語法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號(hào)相同而引起回溯。2021/5/914在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個(gè)右部去替代B？-------什么信息用于Parser做正確選擇?(輸入串,文法特點(diǎn))2021/5/915可預(yù)測(cè)的試探推導(dǎo)過程例文法G’[S]:S→

pA|qBA→cAd|a

B→dB|c

識(shí)別輸入串w=pccadd是否是G1[S]的句子可預(yù)測(cè)的試探推導(dǎo)過程：S

pApcAd

pccAdd

pccadd

試探成功。2021/5/9164。開始符號(hào)集---FIRST集設(shè)G=(VT,VN,P，S)是上下文無關(guān)文法FIRST（）={a|=>*a,a∈VT,、∈V*}

若

=>*ε則規(guī)定ε∈FRIST（）2021/5/917FOLLOW（A）={aS=>*A且a∈

FRIST（），∈V*，

∈V+}

若S=>*

uA,且

=>*

ε，則#∈FOLLOW(A)5。后跟符號(hào)集--FOLLOW集2021/5/9186。SELECT集給定上下文無關(guān)文法的產(chǎn)生式Ａ

αA∈VN,∈V*若α≠>*

，則SELECT(Ａ

α)=FIRST(α)若α=>*

,則SELECT(Ａ

α)=(FIRST(α)-{})∪FOLLOW(A)2021/5/919

7。LL（1）文法一個(gè)文法G是LL（1）的，當(dāng)且僅當(dāng)對(duì)于G的每一個(gè)非終結(jié)符Ａ的任何兩個(gè)不同產(chǎn)生式Ａ

α

β，下面的條件成立：

SELECT(Ａ

α)∩SELECT(Ａ

β)=Ф

其中α和β不能同時(shí)=>*

ε

2021/5/920書中例子2021/5/921

5.2LL（1）文法的判別判別步驟：1）。求出能推出ε的非終結(jié)符

2021/5/9222）。計(jì)算FIRST集1.若X

V

,則FIRST(X)={X}2.若X

VN,且有產(chǎn)生式X

a…，則把a(bǔ)加入到FIRST(X)中;若X

也是一條產(chǎn)生式,則把

也加到FIRST(X)中.3.若X

Y…是一個(gè)產(chǎn)生式且Y

VN,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…YK

是一個(gè)產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對(duì)于任何j,1≤j≤i-1,FIRST(Yj)都含有

(即Y1..Y(i-1)=>*

),則把FIRST(Yj)中的所有非

元素和FIRST(Yi)中的所有元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj,

j=1,2,…,K)均含有

,則把

加到FRIST(X)中.

2021/5/9233）。計(jì)算FOLLOW集1.對(duì)于文法的開始符號(hào)S,置#于FOLLOW(S)中;2.若Ａ

αBβ是一個(gè)產(chǎn)生式,則把

FIRST(β)-{}加至FOLLOW(B)中;3.若Ａ

αB是一個(gè)產(chǎn)生式,或Ａ

αBβ是

一個(gè)產(chǎn)生式而β=>*

(即

FIRST(β)），

則把FOLLOW（A）加至FOLLOW（B）中．2021/5/924G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a·各非終結(jié)符的FIRST集合如下：FIRST(E)=｛(,a｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,a｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,a｝·各非終結(jié)符的FOLLOW集合為：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}

2021/5/9254）。計(jì)算SELECT集計(jì)算產(chǎn)生式的SELECT集2021/5/926G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>aE’–>+TE’|

FIRST(+TE’)=｛+｝

FOLLOW(E′)=｛)，＃｝T’–>*FT’|

FIRST(*FT’)=｛*｝

FOLLOW(T′)=｛+,)，＃｝F–>(E)|aFIRST((E))=｛(｝

FIRST(a)=｛a｝所以G[E]是LL（1）的2021/5/9275）。判斷文法是否LL（1）文法若文法所有具有相同左部產(chǎn)生式的SELECT集兩兩不相交，則文法是LL(1)文法。2021/5/928

LL(1)文法的性質(zhì)：

LL(1)文法是無二義的

LL(1)文法不含左遞歸2021/5/9295.3某些非LL(1)文法的改造1。提取左公共因子提左公因子：將產(chǎn)生式Ａ

β|

變換為：Ａ

BBβ|

2021/5/930一般形式：Ａ

β1|

β2|…|

βn提取左公共因子后：

AA’A’β1|β2|…|βn2021/5/9312。消除左遞歸左遞歸－關(guān)于非終結(jié)符P的規(guī)則直接左遞歸：

P→Pα|βα、β∈V*且α、β不以P開頭一般左遞歸：P=>*Pα

例：

S→AaA→Sb…2021/5/932消除文法中左遞歸規(guī)則1）消除直接左遞歸：形如：P→Pα|βα非，α，β不以P打頭

改寫為：P→

βQ

Q

→

αQ|

其中Q為新增加的非終結(jié)符2021/5/933消除文法中左遞歸規(guī)則舉例例:E→E+T|TT

→T*F|FF

→(E)|a

G[E]:(1)E→TE’(2)E’→+TE’(3)E’→

(4)T→FT’(5)T’→*FT’(6)T’→

(7)F→(E)(8)F→a2021/5/934消除一般左遞歸對(duì)文法要求:

1.無回路(A(=>+(A)2.無空產(chǎn)生式2）消除一般左遞歸的方法：（1）

.以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1,A2…An（2）

fori:=1tondobegin

forj:=1toi-1do

用Aj-->

1|2…|k

替代形如Ai-->Ajr的規(guī)則,

其中Aj-->

1|

2…|k是關(guān)于Aj的全部產(chǎn)生式;

消除Ai規(guī)則的直接左遞歸;

end;（3）化簡(jiǎn)由（2）得到的文法:去掉無用產(chǎn)生式2021/5/935例P902021/5/936消除左遞歸和提左公因子并不一定都能將非LL(1)文法改造為LL(1)的S→ifCtS|

ifCtSeSC→b提左因子

S→ifCtSAA→eS|

First集Follow集Sif#,eAe,

#,eCbtSelect(A→eS)∩Select(A→

)={e}∩{#,e}≠

Φ改造后文法不是LL(1)文法2021/5/9375.5確定的自頂向下分析方法特征——根據(jù)下一個(gè)(幾個(gè)）輸入符號(hào)為當(dāng)前要處理的非終結(jié)符選擇產(chǎn)生式要求——文法是LL(1)的第一個(gè)L從左到右掃描輸入串第二個(gè)L生成的是最左推導(dǎo)

1向前看一個(gè)輸入符號(hào)（lookahead)2021/5/938無回溯的自頂向下分析程序預(yù)測(cè)分析程序的實(shí)現(xiàn)技術(shù)

1.遞歸（下降）子程序

2.表驅(qū)動(dòng)分析程序2021/5/939例：遞歸下降子程序ParseFunction()BNF（Backus-NaurForm）描述program–>function_listfunction_list–>functionfunction_list|

function–>FUNCidentifier(parameter_list)statement…voidParseFunction(){MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();}2021/5/940例：遞歸下降子程序ParseFunction()（續(xù)）voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror\n");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();//讀入一個(gè)單詞}2021/5/941預(yù)測(cè)分析程序的實(shí)現(xiàn)

表驅(qū)動(dòng)預(yù)測(cè)分析程序模型Input#總控程序預(yù)測(cè)分析表stack2021/5/942預(yù)測(cè)分析表構(gòu)造算法1.對(duì)文法G的每個(gè)產(chǎn)生式Ａ

執(zhí)行第二步

和第三步；2.對(duì)每個(gè)終結(jié)符a

FIRST(

)，把Ａ

加

至

[A,a]中，3.若

FIRST(

)，則對(duì)任何bFOLLOW(A)

把Ａ

加至

[A,b]中，4.把所有無定義的

[A,a]標(biāo)上“出錯(cuò)標(biāo)志”?？梢宰C明，一個(gè)文法G的預(yù)測(cè)分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的2021/5/943

例：表驅(qū)動(dòng)予測(cè)分析程序G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a

用預(yù)測(cè)分析表表示狀態(tài)轉(zhuǎn)換。2021/5/944

a+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a

預(yù)測(cè)分析表2021/5/945表驅(qū)動(dòng)預(yù)測(cè)分析程序分析算法

首先把’#‘然后把文法開始符號(hào)推入棧；把第一個(gè)輸入符號(hào)讀進(jìn)b;

FLAG：=TRUE；

WHILEFLAGDOBEGIN

把棧頂符號(hào)上托出去并放在Ｘ中；

IFX

VtTHENIFX=bTHEN

把下一個(gè)輸入符號(hào)讀進(jìn)bELSEERRORELSEIFX=‘#’THENIFb=‘#’THENFLAG:=FALSEELSEERRORELSEIF

[X,b]={X–>

X1X2..XK}THEN把XK，XK-1,..,X1一一推進(jìn)棧ELSEERRORENDOFWHILE;STOP/*分析成功，過程完畢*／2021/5/946分析輸入串#a+a#的步驟棧內(nèi)容棧頂符號(hào)當(dāng)前輸入余留串M[X,b]1#EEa+a#E–>

TE’2#E’TTa+a#T–>

FT’3#E’T’FFa+a#F–>

a4#E’T’aaa+a#5#E’T’T’+a#T’–>

6#E’E’+a#E’–>

+TE’7#E’T+++a#8#E’TTa#T–>

FT’9#E’T’FFa#F–>

a10#E’T’aaa#11#E’T’T’#T’–>

12#E’E’#E’–>

13###2021/5/947LL(1)分析中的一種錯(cuò)誤處理辦法發(fā)現(xiàn)錯(cuò)誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的M[A,a]為空“應(yīng)急”恢復(fù)策略跳過輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。同步符號(hào)的選擇1把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)。跳過輸入串中的一些符號(hào)直至遇到這些“同步符號(hào)”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號(hào)加到A的同步符號(hào)集，當(dāng)FIRST(A)中的符號(hào)在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析2021/5/948review---parsingThesyntaxanalysisphaseofacompilerverifiesthatthesequenceoftokensreturnedfromthescannerrepresentvalidsentencesinthegrammaroftheprogramminglanguage.Therearetwomajorparsingapproaches:top-downandbottom-up.Intop-downparsing,youstartwiththestartsymbolandapplytheproductionsuntilyouarriveatthedesiredstring.Inbottom-upparsing,youstartwiththestringandreduceittothestartsymbolbyapplyingtheproductionsbackwards.2021/5/949Inthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparseprintsaleftmostderivationofthesentence.Abottom-upparseworksinreverse.Webeginwiththesentenceofterminalsandeachstepappliesaproductioninreverse,replacingasubstringthatmatchestherightsidewiththenonterminalontheleft.Wecontinueuntilwehavesubstitutedourwaybacktothestartsymbol.Ifyoureadfromthebottomtotop,thebottom-upparseprintsoutarightmostderivationofthesentence.2021/5/950

lookaheadsymbol.Thelookaheadsymbolisthenextsymbolcomingupintheinput.backtracking.Basedontheinformationtheparsercurrentlyhasabouttheinput,adecisionismadetogowithoneparticularproduction.Ifthischoiceleadstoadeadend,theparserwouldhavetobacktracktothatdecisionpoint,movingbackwardsthroughtheinput,andstartagainmakingadifferentchoiceandsoonuntiliteitherfoundtheproductionthatwastheappropriateoneorranoutofchoices.2021/5/951predictiveparserandLL(1)grammarPredictiveparserisanon-backtrackingtop-downparser.Apredictiveparserischaracterizedbyitsabilitytochoosetheproductiontoapplysolelyonthebasisofthenextinputsymbolandthecurrentnonterminalbeingprocessed.Toenablethis,thegrammarmusttakeaparticularform.WecallsuchagrammarLL(1).Thefirst“L”meanswescantheinputfromlefttoright;thesecond“L”meanswecreatealeftmostderivation;andthe1meansoneinputsymboloflookahead.2021/5/952recursive-descentThefirsttechniqueforimplementingapredictiveparseriscalledrecursive-descent.Arecursivedescentparserconsistsofseveralsmallfunctions(procedures),oneforeachnonterminalinthegrammar.Asweparseasentence,wecallthefunctions(procedures)thatcorrespondtotheleftsidenonterminaloftheproductionsweareapplying.Iftheseproductionsarerecursive,weendupcallingthefunctionsrecursively.2021/5/953Table-drivenLL(1)parsingInarecursive-descentparser,theproductioninformationisembeddedintheindividualparsefunctionsforeachnonterminalandtherun-timeexecutionstackiskeepingtrackofourprogressthroughtheparse.Thereisanothermethodforimplementingapredictiveparserthatusesatabletostorethatproductionalongwithanexplicitstacktokeeptrackofwhereweareintheparse.2021/5/954Howatable-drivenpredictiveparserworksWepushthestartsymbolonthestackandreadthefirstinputtoken.Astheparserworksthroughtheinput,therearethefollowingpossibilitiesforthetopstacksymbolXandtheinputtokennonterminala:1.IfX=aanda=endofinput(#):parserhaltsandparsecompletedsuccessfully2.IfX=aanda!=#:successfulmatch,popXandadvancetonextinputtoken.Thisiscalledamatchaction.3.IfX!=aandXisanonterminal,popXandconsulttableat[X,a]toseewhichproductionapplies,pushrightsideofproductiononstack.Thisiscalledapredictaction.4.Ifnoneoftheprecedingcasesappliesorthetableentryfromstep3isblank,therehasbeenaparseerror2021/5/955Thefirstsetofasequenceofsymbolsu,writtenasFirst(u)isthesetofterminalswhichstartallthesequencesofsymbolsderivablefromu.Abitmoreformally,considerallstringsderivablefromubyaleftmostderivation.Ifu=>*v,wherevbeginswithsometerminal,thatterminalisinFirst(u).Ifu=>*

,then

isinFirst(u).2021/5/956ThefollowsetofanonterminalAisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsententialform.Abitmoreformally,foreveryvalidsententialformS=>*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).2021/5/957CalculatingfirstsetTocalculateFirst(u)whereuhastheformX1X2...Xn,dothefollowing:1.IfX1isaterminal,thenaddX1toFirst(u),otherwiseaddFirst(X1)-

toFirst(u).2.IfX1isanullablenonterminal,i.e.,X1=>*

,addFirst(X2)-

toFirst(u).Furthermore,ifX2canalsogoto

,thenaddFirst(X3)-

andsoon,throughallXnuntilthefirstnonnullableone.3.IfX1X2...Xn=>*

,add

tothefirstset.2021/5/958Calculatingfollowsets.Foreachnonterminalinthegrammar,dothefollowing:1.Place#

inFollow(S)whereSisthestartsymboland#

istheinput'srightendmarker.Theendmarkermightbeendoffile,itmightbenewline,itmightbeaspecialsymbol,whateveristheexpectedendofinputindicationforthisgrammar.Wewilltypicallyuse#astheendmarker.2.ForeveryproductionA–>uBvwhereuandv