编译器笔记9-语法分析-LL(1)文法
要想分析器以预测分析法的方式去工作，我们希望文法最好符合S_文法。预测分析法的工作过程：
从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A 和当前输入符号a ，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
S_文法（简单的确定性文法）
- 每个产生式的右部都以终结符开始
- 同一非终结符的各个候选式的首终结符都不相同（S_文法不含ε产生式）
说明：
- 根据上述的文法，当前的输入符号最多能选择一个候选式就不会产生冲突。
- S_文法简单来说就是同一非终结符的各个候选式的首终结符都不同，并且产生式不包含ε。
- 候选式的首终结符不同，保证了选出的候选式都是唯一的。
- 如果S_文法包含ε产生式，那么就保证不了选出的候选式是惟一的。例如a可以匹配以a开头的产生式的右部，也可以匹配右部为ε的产生式。
问题：若S_文法包含ε产生式会产生什么问题？
看以下例子：
例.png
问：什么时候使用ε产生式？
答：如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε，可以通过检查a是否可以出现在A的后面，来决定是否使用产生式A→ε（若文法中无A→ε，则应报错）。
说明:
以上输入ade例子说明空产生式不是什么情况都可以使用的。可见空产生式的使用取决于当前非终结符后面都紧跟哪些终结符。由此我们引入非终结符的后继符号集的概念。
非终结符的后继符号集
非终结符A的后继符号集
可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)
FOLLOW(A)={a|S =>* αAaβ, a∈VT, α,β∈(VT ∪ VN)*}
例.png
说明：
由于B的三个候选式是不相交的，因此可以做出唯一的选择。若当前输入符号为b时选用第二个产生式，若当前输入符号为c时选择第三个产生式，若当前输入为a或c时选择第四个产生式。为了叙述上的方便下面引入产生式的可选集这个概念。
产生式的可选集
产生式A→β的可选集是指可以选用该产生式进行推导时对
应的输入符号的集合，记为SELECT( A→β )
1. SELECT( A → aβ ) = { a }
2. SELECT( A → ε ) = FOLLOW( A )
说明：
- 式1表示只有遇到a终结符时才能选用产生式A→aβ
- 式2表示产生式的右部是空串的话只有遇到A的FOLLOW集的时候才能用产生式A→ε
对于具有相同左部的各个产生式，如果他们的SELECT集互不相交的话我们就可以做出确定的分析。因此我们给出q_文法的定义。
q_ 文法
- 每个产生式的右部为ε或以终结符开始
- 具有相同左部的产生式有不可相交的可选集（q_文法不含右部以非终结符打头的产生式）
ps: q_文法的第二点要注意跟 s_文法的 “同一非终结符的各个候选式的首终结符都不相同” 区分开。举例说明假设存在如下产生式
...
B → {b，c, d}
B → { b }
...
由于产生式的右部允许ε因此产生式对应的终结符集可能包含多个字符，显然B-产生式并不符合q_文法因为这两个具有相同的左部的产生式右部有相交的可选集b,也很显然q_文法的第二点也满足 s_文法的 “同一非终结符的各个候选式的首终结符都不相同” 这个限制。
说明：
q_文法相对于S_文法功能更加强大因为它允许产生式的右部为空串ε，但是q_文法它对产生式的右部限制依然非常严格它不允许产生式的右部以非终结符打头，这限制了它的应用因此我们需要功能更加强大的文法就是接下来要介绍的LL(1)文法。而在LL(1)方法中允许产生式右部以非终结符打头，这就增加了可选集的复杂性，由此我们要引入串首终结符的概念。由此q_文法产生式对可选集的限制比s_文法更强。
串首终结符集
串首终结符：串首第一个符号并且是终结符，简称首终结符。给定一个文法符号串α，α的串首终结符集FIRST(α)被定义为可以从α 推导出的所有串首终结符构成的集合。如果α =>* ε，那么ε也在FIRST(α)中。
对于 ∀α∈(VT∪VN)+, FIRST(α)={a | α =>* aβ，a∈VT，β∈(VT∪VN)*}
如果 α =>* ε ， 那么 ε ∈FIRST(α)
产生式A→α的可选集SELECT
如果ε ∉ FIRST(α), 那么SELECT(A→α) = FIRST(α)
如果ε ∈ FIRST(α), 那么SELECT(A→α) = (FIRST(α)-{ε}) ∪ FOLLOW(A)
例子说明：
若α文法字符串为Ab，假设A-产生式不包含A→ε包含A→eD，A→fD；
那么α =>* eDb，α =>* fD；
那么SELECT(A) = FIRST(A) = {e, f}；
那么FIRST(α) = {e, f}；
PS：
串首终结符的出现是为了让LL(1)文法产生式的右部可以以非终结符打头。
LL(1)文法
文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A→α|β满足下面的条件：
- 如果α和β均不能推导出ε，则FIRST(α)∩FIRST(β) = Φ
- 如果α和β至多有一个能推导出ε
若β =>* ε，则FIRST(α) ∩ FOLLOW(A) = Φ；
若α =>* ε，则FIRST(β) ∩ FOLLOW(A) = Φ；
总结上两条简单的说就是LL(1)文法中具有相同左部的产生式对应的SELECT集不相交。
LL(1)含义：
- 第一个“L” 表示从左向右扫描输入
- 第二个“L” 表示产生最左推导
- “1” 表示在每一步中只需要向前看一个输入符号来决定语法分析动作
概要
需要注意的是，并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求：ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，…ε ∈ FIRST(αn)中至多有一个成立。
