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

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

5.1確定的自頂向下語法分析思想1.語法分析概念2.自上而下的語法分析的一般過程3.自上而下的語法分析面臨的問題4.開始符號集5.后跟符號集6.select集7.LL(1)文法2021/5/921。語法分析在語言的編譯實現(xiàn)中，把句子分析的過程稱為語法分析，即完成這個任務(wù)的程序稱為語法分析程序或稱為識別程序。分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號，直到分析結(jié)束。2021/5/93（上下文無關(guān)文法）句型的分析句型分析就是識別一個符號串是否為某文法的句型的過程，或者說是某個推導(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分析算法分類分析算法可分為：自上而下分析法：

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

從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。

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

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

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

A→ab

A→a

識別輸入串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

識別輸入串w=cad是否為

該文法的句子1.S

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

cAd

cabd這時

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

cAd

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

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

cAd

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

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

cAd

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

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

宣告分析失敗。（請思考若有

(4)S→cB

(5)B→aa會怎樣?

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

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

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

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

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

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

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

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

xAy

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

xAy

xabyxayxaby

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

xAy

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

pA|qBA→cAd|a

B→dB|c

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

pApcAd

pccAdd

pccadd

試探成功。2021/5/9164。開始符號集---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。后跟符號集--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是LL（1）的，當(dāng)且僅當(dāng)對于G的每一個非終結(jié)符Ａ的任何兩個不同產(chǎn)生式Ａ

α

β，下面的條件成立：

SELECT(Ａ

α)∩SELECT(Ａ

β)=Ф

其中α和β不能同時=>*

ε

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

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

2021/5/9222）。計算FIRST集1.若X

V

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

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

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

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

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

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

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

Y1Y2…YK

是一個產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對于任何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）。計算FOLLOW集1.對于文法的開始符號S,置#于FOLLOW(S)中;2.若Ａ

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

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

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

αBβ是

一個產(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）。計算SELECT集計算產(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消除一般左遞歸對文法要求:

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）化簡由（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ù)下一個(幾個）輸入符號為當(dāng)前要處理的非終結(jié)符選擇產(chǎn)生式要求——文法是LL(1)的第一個L從左到右掃描輸入串第二個L生成的是最左推導(dǎo)

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

1.遞歸（下降）子程序

2.表驅(qū)動分析程序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();//讀入一個單詞}2021/5/941預(yù)測分析程序的實現(xiàn)

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

執(zhí)行第二步

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

FIRST(

)，把Ａ

加

至

[A,a]中，3.若

FIRST(

)，則對任何bFOLLOW(A)

把Ａ

加至

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

[A,a]標(biāo)上“出錯標(biāo)志”。可以證明，一個文法G的預(yù)測分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的2021/5/943

例：表驅(qū)動予測分析程序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ù)測分析表表示狀態(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ù)測分析表2021/5/945表驅(qū)動預(yù)測分析程序分析算法

首先把’#‘然后把文法開始符號推入棧；把第一個輸入符號讀進b;

FLAG：=TRUE；

WHILEFLAGDOBEGIN

把棧頂符號上托出去并放在Ｘ中；

IFX

VtTHENIFX=bTHEN

把下一個輸入符號讀進bELSEERRORELSEIFX=‘#’THENIFb=‘#’THENFLAG:=FALSEELSEERRORELSEIF

[X,b]={X–>

X1X2..XK}THEN把XK，XK-1,..,X1一一推進棧ELSEERRORENDOFWHILE;STOP/*分析成功，過程完畢*／2021/5/946分析輸入串#a+a#的步驟棧內(nèi)容棧頂符號當(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)分析中的一種錯誤處理辦法發(fā)現(xiàn)錯誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的M[A,a]為空“應(yīng)急”恢復(fù)策略跳過輸入串中的一些符號直至遇到“同步符號”為止。同步符號的選擇1把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號加到A的同步符號集，當(dāng)FIRST(A)中的符號在輸入中出現(xiàn)時，可根據(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