<aside> 💡 Key Points

自顶向下的、 递归下降的、 基于预测分析表的、

适用于LL(1) 文法的、 LL(1) 语法分析器

</aside>

Top-Down Parsing

自顶向下构建语法分析树

• 根节点是文法的起始符号 $S$
• 叶节点是词法单元流 $w\$$
  • 仅包含终结符号与特殊的文件结束符 $\$$ (EOF)
• 每个中间节点表示对某个非终结符应用某个产生式进行推导

<aside> 💡 LL 的核心问题：选择哪个 non-terminal? 选择哪个 production?

</aside>

Recursive-Descent Parsing

为每个非终结符写一个递归函数，

内部按需调用其它非终结符对应的递归函数, 下降一层。

$\tt{void~A()}~\{$

$\textrm{Choose an $A$-production, where }A\rightarrow X_1,X_2,…,X_n$

$\tt for~(i=1~to~k)~\{$

$\tt if~(X_i.isNonTerminal())$

$\tt call~X_i()$

$\tt else~if~(X_i\text{ equals to the current symbol }a)$

$\textrm{Read the next input}$

$\tt else$

$\tt throw~UnexpectedLexicalUnitException()$

$\}$

$\}$

Predictive Parsing

指明了每个非终结符在面对不同的词法单元或文件结束符时：

• 该选择哪个产生式 (按编号进行索引)
• 或者报错 (空单元格)

<aside> 💡 $LL(1)$ Grammars

如果文法 G 的预测分析表是无冲突的, 则 G 是 $LL(1)$ 文法。

• 无冲突: 每个单元格里只有一个生成式 (编号) </aside>

递归下降的、预测分析实现方法：