<編譯原理>自頂向下文法分析

整理了一些知識點，比較零散，多以例題為主

自頂向下分析方法：

文法分析從頂部(樹根、文法的開始符号)到底部(葉子、語言的終結符号)為輸入的符号串建立分析樹。

主旨：從文法的開始符号S出發，反複使用各種産生式，尋找”比對”于輸入符号串的推導（從S（根）出發，向下逐漸建立文法樹，最終：為輸入串尋找一個最左推導）

自上而下分析面臨的主要問題

   1） 如何選擇候選式：如果對文法不做任何限制，對候選式的選擇成為無根據的，隻好一一試探所有候選式，直至成功或失敗。不斷地回溯，大大影響速度。

   2）左遞歸文法将使自上而下分析陷入無限循環.

是以，我們需要：

   1）對文法加以一定的限制，使每次對候選式的選擇是唯一的，進而進行确定的自上而下分析。

   2）将左遞歸變為右遞歸（或疊代）

消除直接左遞歸方法：

A->Aα|β, α,β ∈ (VN∪VT)*, A ∈ VN, β不以A開頭

則：A -> βA′       

       A ′->αA ′|ε

[例]   文法   E->E+T | T   

                   T->T*F | F    

                   F->(E) | a 

          消除左遞歸，得

                  E->TE’

                  E’->+TE’ | ε

                  T->FT’

                  T’->*FT’ |ε

                  F->(E) | a

消除間接左遞歸：

[例]  G[S]： S ->Qc | c

                        Q ->Rb | b

                        R ->Sa | a

因     S ->Qc->Rbc->Sabc, 是左遞歸文法

代入法：                       S->(Rb | b)c | c

                                      S->Rbc | bc | c

                                      S->(Sa | a)bc | bc | c

是以                               S->Sabc | abc | bc | c

消除左遞歸，得

                                      S->abcS’ | bcS’ | cS’

                                      S’->abcS’ | ε 

LL(1)文法定義：

一個文法G是LL(1)文法，當且僅當對文法中形如 A->α1 | α2 | …| αn都滿足LL(1)條件，即

(1) First(αi) ∩First(αj)=Φ, i≠j；

      且如果αi ->* ε,則

(2) First(αj) ∩Follow(A)=Φ, i≠j

[例]： 給定文法 S→0S|1S|ε是否為 LL(1) 文法？

解：構造LL(1)分析表: 

        0              1             #

S     S->0S      S->1S      S->ε

因為表中無多重定義， 是以該文法是 LL(1) 文法。

[例]左遞歸文法是LL(1)文法嗎？

解： 因為左遞歸文法意味着有隐含的左公共因子，是以左遞歸文法不是LL(1)文法。

        例如： A->Aa|b

        因為：First(Aa}={b}， First(b)={b}，

        是以：First(Aa} -> First(b)= {b}

FOLLOW集的計算：

 (1) 設S為G中開始符号，則#∈FOLLOW(S)

(2) 若A ->αBβ是一産生式，則把FIRST(β)的非空元素加入到FOLLOW(B)中。

    如果β ->* ε，即有： A ->αB

    則把FOLLOW(A)也加入到FOLLOW(B)中

(3) 反複使用(2)，直到每個VN的FOLLOW集不再增大為止。

SELECT集的計算：

當α不能推出ε時： select( A→α) =First(α)

當α ->* ε時： select( A→α) =Follow(A) ∪ (First(α) –{ε})

[例] 判斷G是否是LL(1)文法，如果是，構造LL(1)分析表G[S]

1.  S ->AB|bC

2.  A ->ε|b

3.  B ->ε|aD

4.  C ->AD|b

5.  D ->aS|c

求First集、 Follow集:

          FIRST        FOLLOW

S b,a,ε           # FOLLOW(S)={#} ∪ FOLLOW(D)

A b,ε              #,a,c FOLLOW(A)=(FIRST(B)-{ε})∪ FOLLOW(S)∪ FIRST(D)

B a,ε              # FOLLOW(B)=FOLLOW(S)

C b,a,c          # FOLLOW(C)=FOLLOW(S)

D a,c             #  FOLLOW(D)=FOLLOW(B)∪FOLLOW(C)

select(S ->AB)={b,a,#}

select(S ->bC)={b}            

select(A -> ε)=Follow(A)={#, a, c}

select(B -> ε) =Follow(B) ={#}

select(C ->AD)=First(AD)={b,a,c}

select(C ->b)={b}

故LL(1)表為：