跳转至

4 自顶向下的语法分析

需要说明一下，编译原理的笔记中涉及到文法的部分，所有小写字母（$a,b$ 等）一律为终结符，所有大写字母（$A,B$ 等）一律为非终结符，所有小写希腊字母（$\alpha,\beta$ 等）一律是属于 $V^*$ 的串（可以为空）。

两个集合——First 集合和 Follow 集合

First 集合的定义和求解

  First 的定义是： $$\operatorname{FIRST}(\alpha)=\lbrace\alpha\stackrel{*}{\Rightarrow}a\beta,a\in V _ T,\alpha,\beta\in V^*\rbrace\tag{4.1}$$

这个用大白话说，$\operatorname{FIRST}(\alpha)$ 就是符号串 $\alpha$ 所推导出的所有终结符串中的第一个终结符的集合。上面的定义 $(4.1)$ 尚不完善，还需要加上这一点：如果 $\alpha$ 能推出空串，那么 $\varepsilon$ 就也在 $\operatorname{FIRST}(\alpha)$ 里面。
  求 First 集合的大致步骤如下，假设要求 First 集的符号串是 $\alpha$。实际上，有两种情况很快出答案：

  • $\alpha=\varepsilon$，即这个 $\alpha$ 本身就是空串。那么 $\operatorname{FIRST}(\alpha)=\lbrace\varepsilon\rbrace$。
  • $\alpha=a\beta$，即 $\alpha$ 以一个终结符开头。那么 $\operatorname{FIRST}(\alpha)=\lbrace a\rbrace$。

接下来是比较复杂的 $\alpha=A\beta$，即以一个非终结符开头（注意我们这里的 $\beta$ 和上面的 $\beta$ 都可以是空串）。这个时候又要分两种情况：

  • $A$ 不可以推导出空串。显然这个时候 First 集合就与 $\beta$ 无缘了，因为 $A$ 再怎么推导也总归落到一个非终结符。因此有 $\operatorname{FIRST}(\alpha)=\operatorname{FIRST}(A)$。
  • $A$ 可以推导出空串。这个时候注意 $A$ 可能还有一些产生式推不出空串，因此有 $\operatorname{FIRST}(\alpha)=\operatorname{FIRST}(\beta)\cup(\operatorname{FIRST}(A)-\lbrace\varepsilon\rbrace)$。

这里其实又涉及到一个问题，怎么判断一个非终结符 $A$ 能不能推出空串？这个算法也是很简单，不再赘述。

Follow 集合的定义和求解

  Follow 的定义是： $$\operatorname{FOLLOW}(A)=\lbrace a|S\stackrel{*}{\Rightarrow}\alpha A\beta,a\in V _ T,a\in\operatorname{FIRST}(\beta),\alpha,\beta\in V^*\rbrace\tag{4.2}$$

这个定义还是太抽象了，写的稍微人性化一点就是：

$$\operatorname{FOLLOW}(A)=\lbrace a|S\stackrel{*}{\Rightarrow}\cdots Aa\cdots,a\in V _ T\rbrace\tag{4.3}$$

也就是从起始符号 $S$ 开始，通过推导能够出的所有含 $A$ 的句型中 $A$ 后面的那个终结符的所有可能结果。上面两个定义都不完善，还需要加上一点，即如果 $S\stackrel{*}{\Rightarrow}\cdots A$，那么也应有 $ \# \in\operatorname{FOLLOW}(A)$，这里的 $\#$ 被称为句末符。

$\operatorname{FIRST}$ 和 $\operatorname{FOLLOW}$ 运算的区别

应该能看出这两个运算除了概念之外，还有一些不同。

  • 定义域：$\operatorname{FIRST}$ 的定义域是所有符号串 $\alpha$，而 $\operatorname{FOLLOW}$ 的定义域仅仅是非终结符 $A$。因此前者的定义域包含后者的定义域。
  • 值域：$\operatorname{FIRST}$ 的值域是 $V _ T\cup\lbrace\varepsilon\rbrace$，而 $\operatorname{FOLLOW}$ 的值域是 $V _ T\cup\lbrace\#\rbrace$。

  求 Follow 集合的算法在此也可以描述一下。首先，对于每一个非终结符 $A\in V _ N-\lbrace S\rbrace$，都有一个集合 $F _ A=\varnothing$；特别地，有 $F _ S=\lbrace\#\rbrace$。然后不断地遍历所有产生式，对于不同的产生式，执行不同的操作：

  • 如果产生式是 $B\stackrel{*}{\Rightarrow}\cdots A$ 类型的，令 $F _ A\leftarrow F _ A\cup F _ B$。
  • 如果产生式是 $B\stackrel{*}{\Rightarrow}\cdots A\beta$ 类型的：
    • 若 $\beta$ 不可推导出空串，则令 $F _ A\leftarrow F _ A\cup \operatorname{FIRST}(\beta)$。
    • 若 $\beta$ 可以推导出空串，则令 $F _ A\leftarrow F _ A\cup(\operatorname{FIRST}(\beta)-\lbrace\varepsilon\rbrace)\cup F _ B$。

一直重复上面的操作，直到某次遍历结束时，发现对于任意的非终结符 $A$，$F _ A$ 都没有发生更新。此时 $F _ A=\operatorname{FOLLOW}(A)$。

上面提到符号串 $\beta$ 能否推导出空串的问题。$\beta$ 能推导出空串，当且仅当 $\beta\in V _ N^*$ 且 $\beta$ 中所有的非终结符都能推导出空串。

Select 集合与 LL（1）文法

  Select 的定义是： $$\operatorname{SELECT}(A\to\alpha)=\begin{cases}\operatorname{FIRST}(\alpha),&\alpha\stackrel{*}{\nRightarrow}\varepsilon\\ \left(\operatorname{FIRST}(\alpha)-\lbrace\varepsilon\rbrace\right)\cup\operatorname{FOLLOW}(A),&\alpha\stackrel{*}{\Rightarrow}\varepsilon\end{cases}\tag{4.4}$$

可以看出，该运算的定义域是产生式。
  Select 集合的发明主要是为了帮助 LL（1） 文法(1)的自顶向下分析过程。在推导过程中，当前句型最左旁边的非终结符为 $A$，将句型和我们最终需要得到的句子对比，发现句子中对应的位置应该是 $a$。那么此时选择的产生式 $A\to\alpha$ 应当满足 $a\in\operatorname{SELECT}(A\to\alpha)$。
  显然，对于左部为 $A$ 的 $k$ 个产生式 $A\to \alpha _ i(i=1,2,\cdots,k)$，最多有一个 $i$ 满足 $a\in\operatorname{SELECT}(A\to \alpha _ i)$，否则就不知道要选择哪一个产生式。实际上满足这样的条件的文法就是 LL（1）文法。该条件以数学语言描述就是

  1. LL（1）文法的含义：
    • 第一个 L（Left to right parsing）指的是从左向右分析 token。
    • 第二个 L（Left-most derivation）指的是最左推导。
    • 1 指的是只需向右看 1 个符号即可确定选择哪个产生式进行推导。这里构造非终结符的 Follow 集合，实际上就体现了这一点。

$$\forall i,j(i\neq j\to\operatorname{SELECT}(A\to \alpha _ i)\cap\operatorname{SELECT}(A\to \alpha _ j)=\varnothing)\tag{4.5}$$

LL（1）文法一定是无二义性的文法。因此，如果证明了一个文法的二义性（即找到一个句型的多个不同语法树），就可以断定该文法一定不是 LL（1）文法。

  判别一个文法是不是 LL（1）文法，其一般性步骤就是求 Select 集合，然后看是否满足式 $(4.5)$ 的条件。但是很多时候，特别是当一个文法不是 LL（1）文法的时候，我们不用求完整的 Select 集合，通过一个反例一眼就可以看出来(1)，这种时候就不要再傻傻地求 SELECT 集合了。

  1. 这里举一个例子：$$\begin{aligned}S&\to AB|bC\\ A&\to b|\varepsilon\\ B&\to aD|\varepsilon\\ C&\to AD|b\\ D&\to aS|c\end{aligned}$$ 这里实际上一眼可以看出 $b\in\operatorname{SELECT}(C\to b)$。并且因为 $A\to b$，所以 $b\in\operatorname{SELECT}(C\to AD)$。因此不是 LL（1）文法。