LL(1)文法

文章目录

• 预测分析法的工作过程
• S_文法（简单的确定性文法）
• 什么时候使用$\epsilon$产生式？
• 非终结符的后继符号集
• 产生式的可选集
• q_文法
• 串首终结符集
• LL(1)文法

预测分析法的工作过程

从文法开始符号触发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定性文法）

特点：

• 每个产生式的右部都以终结符开始。
• 同一非终结符的各个候选式的首终结符都不同。
• S_文法不包含$ϵ$产生式

什么时候使用$ϵ$产生式？

如果当前某非终结符A与当前输入符a不匹配时，若存在$A\to ϵ$，可通过检查a是否可以出现在A的后面，来决定是否使用产生式$A\to ϵ$。（若文法中无$A\to ϵ$，则应报错）。

例：

文法：

1. $S\to aBC$
2. $B\to bC$
3. $B\to dB$
4. $B\to ϵ$
5. $C\to c$
6. $C\to a$
7. $D\to e$

输入：

a d a

推导：

$aBC\Rightarrow adBC\Rightarrow adC\Rightarrow ada$

可以看到在第三步推导中，B转成了空串。而上述文字的意思就是，由于此时输入的字符是a，而B没有候选式能够匹配，因此检查a能否出现在B的后面。换句话说，看看B后面的C能不能匹配a。 如果可以匹配则可以使用B的$ϵ$产生式，没有则报错。

非终结符的后继符号集

可能在某个句型中紧跟在A后边的终结符a的集合，即为FOLLOW(A)， F O L L O W ( A ) = { a ∣ ⇒ ∗ α A a β , a ∈ V T , a , β ∈ ( V T ∪ V N ) ∗ } FOLLOW(A) = \{a | \Rightarrow^*{\alpha A a \beta}, a \in V_T, a,\beta \in (V_T \cup V_N)^*\} FOLLOW(A)={a∣⇒∗αAaβ,a∈VT​,a,β∈(VT​∪VN​)∗}

注：如果A是某个句型的最右符号，则将结束符$添加到FOLLOW(A)中。

例：

1. $S\to aBC$
2. $B\to bC$
3. $B\to dB$
4. $B\to ϵ$
5. $C\to c$
6. $C\to a$

那么 F O L L O W ( B ) = { a , c } FOLLOW(B)= \{a, c\} FOLLOW(B)={a,c}。

换句话说，当输入为b或d时，选择产生式2或3。而当输入为a或c时，选择产生式4。

产生式的可选集

产生式$A\to \beta$的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为$SELECT(A\to \beta )$。也就是说，当遇到可选集中的字符输入时，可以选用可选集对应的产生式。

• $SELECT(A\to a\beta )=a$
• $SELECT(A\to ϵ)$ = $FOLLOW(A)$

q_文法

• 每个产生式的右部或为$ϵ$，或以终结符开始
• 具有相同左部的产生式有不相交的可选集。
• q_文法不含右部以非终结符打头的产生式。

串首终结符集

• 串首终结符：串的第一个符号，并且是终结符。简称首终结符。
• 给定一个文法符号串$\alpha$，$\alpha$的串首终结符集$FIRST(\alpha )$被定义为可以从$\alpha$推导出的所有串首终结符构成的集合。如果$\alpha {\Rightarrow }^{\ast }ϵ$，那么$ϵ$也在$FIRST(\alpha )$中
  • 对于$\forall \alpha \in (V_T\cup V_N{)}^{+}$，$FIRST(\alpha )=a|\alpha {\Rightarrow }^{\ast }a\beta ,a\in V_T,\beta \in (V_T\cup V_N)$
  • 如果$\alpha {\Rightarrow }^{\ast }ϵ$，那么$ϵ\in FIRST(\alpha )$。（$\alpha$中的每一个符号都是非终结符，且每一个非终结符都能推导出空串）
• 产生式$A\to \alpha$的可选集$SELECT$
  • 如果$ϵ\notin FIRST(\alpha )$，那么$SELECT(A\to \alpha )=FIRST(\alpha )$
  • 如果$ϵ\in FIRST(\alpha )$，那么 S E L E C T ( A → α ) = ( F I R S T ( α ) − { ϵ } ) ∪ F O L L O W ( A ) SELECT(A \rightarrow{\alpha}) = (FIRST(\alpha) - \{\epsilon\}) \cup FOLLOW(A) SELECT(A→α)=(FIRST(α)−{ϵ})∪FOLLOW(A)

LL(1)文法

文法G是$LL(1)$的，当且仅当G的任意两个具有相同左部的产生式$A\to \alpha |\beta$满足下面的条件：

• 不存在终结符a使得$\alpha$和$\beta$都能推导出以a开头的串。
• $\alpha$和$\beta$至多有一个能推导出$ϵ$

---

• 如果$\beta {\Rightarrow }^{\ast }ϵ$，则$FIRST(\alpha )\cap FOLLOW(A)=\Phi$
• 如果$\alpha {\Rightarrow }^{\ast }ϵ$，则$FIRST(\beta )\cap FOLLOW(A)=\Phi$

因为如果$\beta {\Rightarrow }^{\ast }ϵ$，那么$SELECT(\beta )$就包含了$FOLLOW(A)$，所以$FIRST(\alpha )$就不能包含$FOLLOW(A)$中元素。不然两个的$SELECT$集将会相交。

• 同一非终结符的各个产生式的可选集互不相交