编译原理中first集的求法

在编译原理中，first集是常见的一类集合，表示一些符号串所能够产生的最左终结符集合。针对这种集合的求法，我们可以从多个角度进行分析。

一、基本概念

在介绍first集的求法之前，我们先来了解一下first集的基本概念。假设给定一个文法G=(V, T, P, S)，其中V表示非终结符集，T表示终结符集，P表示产生式集，S表示文法的开始符号。

对于一个符号串X，如果X能够推导出一个终结符号a，且a不等于空串，则称a是X的first符号。如果X能够推导出一个空串，则称空串是X的一个first符号。然后，first(X)表示所有X的first符号组成的集合。注意，对于任意的非终结符号X和Y，如果存在一条产生式X->Y1Y2...Yk，那么可以将first(Y1)中不包含空串的符号和first(Y2)、first(Y3)……first(Yk)合并后得到first(X)。

二、求法

1. 直接推导法

直接推导法是求解first集最简单的方法，也是最朴素的方法。它的基本思路是对于每个产生式逐一考虑，并用归纳法的思想来进行求解。

首先，对于任意的终结符号a，first(a) = {a}。其次，对于任意的非终结符号X，如果存在一条产生式X->aα，其中a为终结符号，那么可以得到first(X) = {a}。对于这种情况，我们可以快速计算出first集，因为只有这种情况的first集一定是一个单独的终结符号。

最后，考虑对于任意的非终结符号X，如果存在一条产生式X->Y1Y2...Yk，则可以将first(Y1)中不含空串的符号添加到first(X)里面。如果first(Y1)里面仍然包含空串，则可以将first(Y2)中不含空串的符号添加到first(X)里面。按照这样的方式进行递归计算，直到添加新的符号为止。

2. 公共前缀法

除了直接推导法，还有一种比较常见的方法是公共前缀法。这种方法的基本思想是：对于所有产生式左部相同的情况，它们的first集合具有相同的前缀序列。因此，只需分析这些产生式的右部，找出它们的首符号集合，并将它们合并成为一个集合，那么这个集合就是左部的first集合。

3. 预测分析法

另外一种常见的方法是预测分析法。这种方法最初被用于LL分析器中，但是也可以用于求解first集。其基本思想是：对于任意两个产生式，如果它们的左部相同，但是右部的首符号集合不同，那么这些非终结符号的first集合也不同。

具体地，如果存在一条产生式X->αβ，其中α *ε，那么first(X)包含了first(α)和first(β)。如果first(α)包含了空串，那么需要将first(β)中不包括空串的符号加入到first(X)中。然后将first(α)从first(X)中删除，重复以上步骤，直到first(α)不再包含空串为止。

三、总结

编译原理中first集的求法，可以从多个角度进行分析。直接推导法是最朴素的方法，公共前缀法则是针对一类产生式集合的特殊情形。预测分析法则是一种基于非终结符右部首符号集合的递归求解方法。不同方法适用于不同的情况，我们需要根据实际应用场景进行选择和应用。