先做 Syntax Analysis 的 Left Recursion，Left Factoring 消除，然后再来做Predictive Parsing

FIRST

**规则如下：**假设需要处理 FIRST(X)

• 如果 X 是 terminal，返回 FIRST(X) = X
• 如果 X 不是 terminal，而是 $X \to Y_1 Y_2\dots Y_n$
  • 先计算所有 $\text{FIRST}(Y_1),\text{FIRST}(Y_2)\dots$
  • 然后从左到右扫，直到遇到第一个 $\text{FIRST}(Y_i)\ne \epsilon$
  • 这个$\text{FIRST}(X) = \text{FIRST}(Y_i)$

FOLLOW

**规则如下：**假设需要处理 FOLLOW(X)

• 如果 X 是 start，我们直接放一个EOF，返回 FOLLOW(X) = {$}
• 如果存在 $X \to \alpha Y \beta$，那么把$\beta$除了$\epsilon$ 的全部FIRST 加入 FOLLOW
  • $\text{FOLLOW}(X)\ \cup \ (\text{FIRST}(\beta) - \epsilon)$
• 如果存在$X \to \alpha Y$… 但$Y$后面没东西了或者可穿透
  • 比如 $X \to \alpha Y$ 或 $X \to \alpha Y\beta$ 但 $\text{FIRST}(\beta)$ 包含 $\epsilon$
  • 那 FOLLOW(X) 全部加入 FOLLOW(Y)
  • 这也就是为什么要自顶向下处理FOLLOW

LL(1) 查询表

**本质：**打表的目的是为了加速 & 确保唯一性。

• 表格内容：给定当前状态 $A$ 以及若干产生式规则 $A\to \alpha_1\mid\alpha_2\mid\dots\mid\alpha_n$
• 如果没有表：得逐一尝试 $A\to\alpha_i$ 试错；如果失败了得回溯 尝试$A\to\alpha_{i+1}$
• 有表格以后：给定当前$A$ 只需要看看下一个输入的字符是谁，然后直接查表

填表逻辑：

• 假设我们有状态 $A_1, A_2, \dots, A_n$，还有token $\alpha_1,\alpha_2,\dots,\alpha_m$
• 一行一行填：假设填写$A_2$ 行，然后$A_2$ 有规则：$A_2 \to \alpha_1\mid \alpha_2$
  • 先看 $A_2\to\alpha_1$：
    • 看看 FIRST($\alpha_1$)，如果不能推成空，直接在 $[A_2,\text{FIRST}(\alpha_1)]$ 几个位置填上 $A_2\to\alpha$
    • 如果 FIRST($\alpha_1$)，如能推成空，那在 $[A_2,\text{FOLLOW}(A_2)]$ 几个位置填上 $A_2\to\alpha$
  • $A_2\to\alpha_2$ 也是同理

直觉理解：

• 我们希望找到 从每一个状态 $A$ 出发，哪些 token是 可以通过 $A$ 的规则一步到达的？
• 其中 能推成 $\epsilon$ （推空）的不算做一步。
• 所以如果我们看到 当前规则分支 FIRST 里不含空，代表这就是一步内能到达的
• 而 如果我们看到 当前规则 FIRST 含空，代表我们需要 跳过当前规则，查询该状态的 FOLLOW