編譯原理（四）

（一）自頂向下分析

從分析樹的頂部（根節點）向底部（葉節點）方向構造分析樹

可以看成是從文法開始符號S推導出詞串w的過程

每一步推導中，都需要做兩個選擇

替換當前句型中的哪個非終結符

用該非終結符的哪個候選式進行替換

1.最左推導

在最左推導中，總是選擇每個句型的最左非終結符進行替換

如果S =>*lm α，則稱α是當前文法的最左句型(left-sentential form)

2.最右推導

在最右推導中，總是選擇每個句型的最右非終結符進行替換

在自底向上的分析中，總是採用最左歸約的方式，因此把最左

歸約稱為規範歸約，而最右推導相應地稱為規範推導

3.自頂向下的語法分析採用最左推導方式

總是選擇每個句型的最左非終結符進行替換

根據輸入流中的下一個終結符，選擇最左非終結符的一個候選式

4.自頂向下語法分析的通用形式

遞歸下降分析(Recursive-Descent Parsing)

由一組過程組成，每個過程對應一個非終結符（也就是說文法中有多少個非終結符，就有多少個過程）

從文法開始符號S對應的過程開始，其中遞歸調用文法中其它非終結符對應的過程。如果S對應的過程體恰好掃描了整個輸入串，則成功完成語法分析

5.預測分析( Predictive Parsing)

預測分析是遞歸下降分析技術的一個特例，通過在輸入中向前看固定個數（通常是一個）符號來選擇正確的A-產生式。

可以對某些文法構造出向前看k個輸入符號的預測分析器，該類文法有時也稱為LL(k) 文法類

預測分析不需要回溯，是一種確定的自頂向下分析方法

（二）文法轉換

(1) 含有A→Aα形式產生式的文法稱為是直接左遞歸的(immediate left recursive)

(2)如果一個文法中有一個非終結符A使得對某個串α存在一個推導A=>+Aα ，那麼這個文法就是左遞歸的

(3)經過兩步或兩步以上推導產生的左遞歸稱為是間接左遞歸的

1.消除直接左遞歸

2.消除間接左遞歸

3.提取左公因子( Left Factoring )

（三）L L ( 1 ) 文法

從文法開始符號出發，在每一步推導過程中根據當前句型的最左非終結符A和當前輸入符號a，選擇正確的A-產生式。為保證分析的確定性，選出的候選式必須是唯一的。

1.非終結符的後繼符號集

可能在某個句型中緊跟在A後邊的終結符a的集合，記為FOLLOW(A)

FOLLOW(A)={a| S =>* αAaβ, a∈Vt，α,β∈(Vt∪Vn)*}

2.產生式的可選集

產生式A→β的可選集是指可以選用該產生式進行推導時對應的輸入符號的集合，記為SELECT( A→β )

例

SELECT( A→aβ ) = { a }

SELECT( A→ε )=FOLLOW( A )

q_文法

每個產生式的右部或為ε ，或以終結符開始

具有相同左部的產生式有不相交的可選集

3.串首終結符集

串首終結符：串首第一個符號，並且是終結符。簡稱首終結符

給定一個文法符號串α， α的串首終結符集FIRST(α)被定義為可以從α推導出的所有串首終結符構成的集合。如果α =>* ε，那麼ε也在FIRST(α)中

產生式A→α的可選集SELECT

如果ε?FIRST(α), 那麼SELECT(A→α)= FIRST(α)

如果ε∈FIRST(α), 那麼SELECT(A→α)=( FIRST(α)-{ε} )∪FOLLOW(A)

4.LL(1)文法

文法G是LL(1)的，當且僅當G的任意兩個具有相同左部的產生式A → α | β 滿足下面的條件：

如果α 和β均不能推導出ε ，則FIRST (α)∩FIRST (β) =Φ

α 和β至多有一個能推導出ε

如果β =>* ε，則FIRST (α)∩FOLLOW(A) =Φ；

如果α =>* ε，則FIRST (β)∩FOLLOW(A) =Φ；

推薦閱讀：