3 LL(1)文法

现在可以根据 FIRST 和 FOLLOW 集合来方便讨论。

要想不出现回溯，对于文法的任意两个产生式 $A→\alpha|\beta$ 需要满足：

• $FIRST(\alpha)\cap FIRST(\beta)=\varnothing$

这是显然的，因为面对一个输入字符 $a$，需要在 $\alpha$ 和 $\beta$ 中做决定，这个输入字符肯定是某个终结符，如果 $FIRST(\alpha)\cap FIRST(\beta)\not=\varnothing$，说明面对 $a$，不能立即从 $\alpha$ 和 $\beta$ 中做出肯定正确的决定。

• 如果 $\beta\Rightarrow^*\varepsilon$（$\varepsilon$ 在 $FIRST(\beta)$ 中），则 $FIRST(\alpha)\cap FOLLOW(A)=\varnothing$

如果出现这种情况：$\varepsilon\in FIRST(\alpha)$，$a\in FIRST(\beta)$，但是 $a\in FOLLOW(A)$，那么面临 $a$，不能立即从 $\alpha$ 和 $\beta$ 中做出肯定正确的决定。因为如果选择 $\beta$，是自然的；如果选择 $\alpha$，也是有理由的，因为存在 $A\Rightarrow^* ...Aa...$，当前的决定可以是让 $\beta$ 导出空串。

满足这两个条件的文法就称之为 LL(1) 文法，这种文法的语法分析器不需要回溯。

LL(1) 文法还有一些明显的性质：

• 不含左递归
• 没有公共左因子
• 不是二义的

LL(1) 中第一个 L 表示从左向右扫描输入，第二个 L 表示产生最左推导，1 表示每一步中只向前看一个输入符号来决定语法分析动作。

本文阅读量