<编译原理>自顶向下语法分析
整理了一些知识点，比较零散，多以例题为主
自顶向下分析方法：
语法分析从顶部(树根、文法的开始符号)到底部(叶子、语言的终结符号)为输入的符号串建立分析树。
主旨：从文法的开始符号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)表为：