資源描述：
《自頂向下語法分析方法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第5章自頂向下語法分析方法確定的自頂向下分析思想LL(1)文法的判別某些非LL(1)文法到LL(1)文法的等價變換不確定的自頂向下分析思想確定的自頂向下分析方法返回目錄確定的自頂向下分析思想文法G1[S]:S→pAS→qBA→cAdA→a B→dB B→bW=pccadd自頂向下的推導過程：S?pA?pcAd?pccAdd?pccadd語法樹：SpASpAcAdSpAcAdcAdSpAcAdcAda這個文法的特點：每個產(chǎn)生式的右部都由終結符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結符開始。文法G1[S]:S→p
2、AS→qBA→cAdA→a B→dB B→b文法G2[S]:S→ApS→BqA→aA→cAB→b B→dBW=ccap自頂向下的推導過程：S?Ap?cAp?ccAp?ccap語法樹：SApSApcASApcAcASApcAcAa這個文法的特點：每個產(chǎn)生式的右部不全是由終結符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結符或非終結符開始。文法中無空產(chǎn)生式。文法G1[S]:S→ApS→BqA→aA→cAB→b B→dB定義：設G=(VT,VN,S,P)是上下文無關文法，F(xiàn)IRST(α)={a
3、αaβ,a∈VT,α∈V+
4、,β∈V*,}若αε，則規(guī)定ε∈FIRST(α)*?*?調用返回FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:S→ApS→BqA→aA→cAB→b B→dB文法G3[S]:S→aAS→dA→bASA→εW=abd試圖推導的過程：S?aA?abAS?abS?abd定義：設G=(VT,VN,S,P)是上下文無關文法，A∈VN,S是開始符號。FOLLOW(A)={a
5、S?A?且a∈FRIST(?),?∈VT*,?∈V+}若S?A?,且?ε，則規(guī)定#∈FOLLOW(A)即：FOLLOW(A)={a
6、S…Aa…
7、,a∈VT}若S…A，則規(guī)定#∈FOLLOW(A)#作為輸入串的結束符，或稱為句子括號，如： #輸入串#*?*?*?*?*?調用返回對A→α，A→β其中A∈VN,α,β∈VN*，當α和β不同時推導出空時（設α不推導出空，β推導出空），則當FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ時，對于非終結符A的替換仍可唯一地確定候選。定義：給定上下文無關文法的產(chǎn)生式A→α，A∈VN,α∈V*，若αε，則SELECT(A→α)=FIRST(α)如果αε，則SELECT(A→α)=FIRST(α)∪FOLLOW(A)*?*?調
8、用返回定義：一個上下文無關文法是LL(1)文法的充要條件是： 對每個非終結符A的兩個不同產(chǎn)生式A→α和A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ其中α,β不同時能ε。*?LL(1)文法的含義：第一個L表示：自頂向下分析是從左向右掃描輸入串。第二個L表示：分析過程中將用最左推導。1表示：只需向右看一個符號便可決定如何推導（即選擇哪個產(chǎn)生式進行推導）。類似也可以有LL(K)文法：需向前查看K個符號才可確定選用哪個產(chǎn)生式。文法G[S]是否是LL(1)文法:S→aAS→dA→bASA→εSELECT(S→aA)={a}
9、 SELECT(S→d)=daizoyzSELECT(A→bAS)= SELECT(A→ε)={a,d,#,ε}SELECT(S→aA)∩SELECT(S→d)={a}∩onefd20=ΦSELECT(A→bAS)∩SELECT(A→ε)=∩{a,d,#,ε}=Φ所以該文法是LL(1)文法。設文法G[S]為:S→aASS→bA→bAA→εSELECT(S→aAS)={a} SELECT(S→b)=SELECT(A→bA)= SELECT(A→ε)={a,b,ε}SELECT(S→aAS)∩SELECT(S→b)={a}∩{
10、b}=ΦSELECT(A→bA)∩SELECT(A→ε)=∩{a,b,ε}≠Φ所以該文法不是LL(1)文法。G[S]:S→aASS→bA→bAA→ε對輸入串W=ab進行推導：S?aAS?abAS?abS出錯S?aAS?aS?abLL(1)文法的判別求出能推出ε的非終結符計算FIRST集計算FOLLOW集計算SELECT集判別是否是LL(1)文法例：設文法G[S]為:S→ABS→bCA→εA→b B→εB→aDC→ADC→bD→aSD→c判斷它是否是LL(1)文法。1.求出能推出ε的非終結符S→ABS→bCA→εA→bB→εB
11、→aDC→ADC→bD→aSD→c非終結符SABCD初值未定未定未定未定未定第一次掃描是是否第二次掃描是否2.計算FIRST集1.若X?V?,則FIRST(X)={X}2.若X?VN,且有產(chǎn)生式X?a…，則a∈FIRST(X); 若X??也是一條產(chǎn)
