进行自上而下的语法分析，基于文法是 LL(1) 文法。分为递归下降的预测分析和非递归下降的预测分析。
#提取左公因子
对产生式组 $$A \rightarrow \alpha | \alpha b_1 | \alpha b_2 | \ldots | \alpha b_m | \gamma_1 | \gamma_2 | \ldots | \gamma_p$$
用如下产生式组替换：
$$A \rightarrow \alpha A ^ { \prime } \left| \gamma _ { 1 } \right| \gamma _ { 2 } | \ldots | \gamma _ { p }$$
$$A ^ { \prime } \rightarrow \varepsilon | b _ 1| b _ 2 | \dots | b _ { \mathrm { m } }$$
#消除左递归
对产生式组
$$A \rightarrow A \alpha _ { 1 } | A \alpha _ { 2 } | \cdots | A \alpha _ { n } | \beta _ { 1 } | \beta _ { 2 } | \ldots | \beta _ { m }$$
用如下产生式组替换：
$$A \rightarrow \beta _ { 1 } A ^ { \prime } | \beta _ { 2 } A ^ { \prime } | \ldots | \beta _ { m } A ^ { \prime }$$
$$A ^ { \prime } \rightarrow \alpha _ { 1 } \mathrm { A ^ { \prime } } | \alpha _ { 2 } \mathrm { A ^ { \prime } } |\ldots | \alpha _ { \mathrm { n } } \mathrm { A ^ { \prime } } | \varepsilon$$
Tips: 消除左递归并非一定产生等价的 LL(1)文法。
🌰$S\rightarrow Aa \mid b, A\rightarrow SB, B\rightarrow ab$
- 如果把A的产生式代入S的产生式得到等价文法是LL(1)的。
- 如果把S的产生式代入A的产生式得到等价文法不是LL(1)的。
#LL(1)文法
第一个 L 代表从左到右扫描输入串，第二个 L 代表最左推导，1 表示分析的每一步只需向前查看一个符号。
LL(1) 文法具有无二义性、无左公因子、无左递归的性质。对于文法的任何非终结符，使用它匹配输入串时，能够根据所面临的输入符号准确的选择产生式，如果该产生式匹配成功，那么这个匹配不是虚假匹配，如果该产生式匹配不成功，则用其他的产生式也一定不会匹配成功。
#判断一个文法是否是 LL(1) 文法
对于文法中的任何两个产生式 $A\rightarrow\alpha\mid\beta$，满足：
- $FISRT(\alpha) \bigcap FISRT(\beta) = \varnothing$
- 如果 $\beta\Rightarrow^*\varepsilon$，那么 $FISRT(\alpha)\bigcap FOLLOW(\beta)=\varnothing$
#非递归分析预测分析表的构建
- 对文法的每个产生式 $A\rightarrow\alpha$，执行第二步和第三步。
- 对 FIRST($\alpha$) 的每个终结符 a，把 $A\rightarrow\alpha$ 加入 M[A, a]（即加入表中 A 行 a 列）。
- 如果 $\varepsilon$ 在 FIRST($\alpha$) 中，对 FOLLOW(A) 的每个终结符 b（包括💲）, 把 $A\rightarrow\alpha$ 加入 M[A, b]。
- M的其它没有定义的条目都是 error。