编译原理——FIRST集、FOLLOW集、SELECT集与LL(1)分析方法

梳理一下 LL(1)分析表的构造方法 以及与之相关的 FIRST集 和 FOLLOW集 的构造方法。

1.  FIRST集的构造方法
   • 以个人的理解，求FIRST集一句话概括即：推导时，每个 非终结符 的第一个 终结符 的集合。实际上，理解了这句话大可不必记公式。
   • 在求FIRST集的过程中，重点观察产生式右部的第一个字符。
   •  如果给定一个文法，它的文法形式可能有以下三种（大写字母为非终结符，小写字母为终结符，ε为空串）：
     1. A -> a
        • 开头直接就是终结符的情况，直接把此非终结符加入FIRST(A)。
     2. A -> ε
        • 空串开头的情况，直接把空串加入FIRST(A)。
     3. A -> B···
        • 以非终结符开头，后面存在 终结符或者非终结符 的情况，需要先将非终结符B的FIRST集求出来，然后由FIRST(B)分为包含或不包含空串ε的两种情况讨论：
          1. 若FIRST(B)中不包含空串ε，则将FIRST(B)的所有元素加入FIRST(A)，不考察接下来的非终结符和终结符。
          2. 若FIRST(B)包含空串ε，则将FIRST(B)除ε外的所有元素加入FIRST(A)，接着求FIRST(C)、FIRST(D)……并将其FIRST集除ε外的元素加入FIRST(A)，直到接下来的非终结符的FIRST集不包含ε。如果推到最后一位为终结符，则将终结符加入FIRST集。
        • 这种情况很好理解，因为如果将A推导为B，那么B推导出的第一个字母即为A的第一个字母。但是假如B可以推导为空串ε，那么就需要后面的非终结符提供终结符（产生A的第一个终结符的重任就交给了B后面的非终结符），所以要考察后继非终结符的FIRST集。
   •  如果把构造FIRST集的过程写成递归函数，其回溯条件即：
     • if ( ‘ε’ not in FIRST(非终结符)  || this is a 终结符 ) return;
2. FOLLOW集的构造方法
   • 以个人理解，求FOLLOW集即：推导时，每个 非终结符 的后一个 终结符 的集合。
   • 构造FOLLOW集的过程中，需要用到FIRST集（因此先求FIRST再求FOLLOW）。需要重点关注产生式右部中对应的非终结符的后一个字符。
   • 构造过程开始前，要首先将 ‘#’后随符 加入开始符号的FOLLOW集中，这是规定。
   • 同样的，FOLLOW集也分以下几种情况（求B的FOLLOW集）：
     1. A -> Ba
        • 这种情况最简单，由于B后面紧跟的是终结符，所以直接将a加入FOLLOW(B)。
     2. A -> …BC…
        • B后紧跟非终结符C，这种情况下，将C的FIRST集中除ε外的元素加入FOLLOW(B)。
        • 这种情况很好理解，要求B后的一个字符，就是求C的第一个字符，即C的FIRST集。但若C是空串，即B后没有字符，所以去掉FIRST(C)中的空串ε。
     3. A  -> …B 或 A -> …BC
        • 求B的FOLLOW集
          1. B是最后一位。
             • 只需把FOLLOW(A)加入FOLLOW(B)即可。
          2. B后只有一个非终结符C并且FIRST(C)中有空串ε。
             • 这时除了将FIRST(C)除ε外的元素加入FOLLOW(B)外，还需将FOLLOW(A)加入FOLLOW(B)
        • 这种情况下，如果B结尾，那么B的FOLLOW集和A的FOLLOW集其实是等价的，所以将FOLLOW(A)加入FOLLOW(B)；如果B后还存在一个C，C还可以推为空串，那么可以看作C不存在，结果还是与B结尾相同的。
3. LL(1)分析表的构造
   • LL(1)分析表的列标题为终结符（即一个终结符为一列），行标题为非终结符（即一个非终结符为一行），内容为文法的产生式。
   • 按照FIRST、FOLLOW集，将产生式入表，具体方法为：
     • 确定一个非终结符
     • 在该非终结符的FIRST集中拿出一个终结符
     • 找到该终结符在文法中出现的产生式
     • 以选中的非终结符为行，选中的终结符为列，将该产生式填入表格
   • 如果遇到FIRST集中存在空串ε，那么：
     • 确定出现空串的非终结符
     • 考察此非终结符的FOLLOW集
     • 对于FOLLOW集中的每个元素，以元素为列，此非终结符为行，填入形如【非终结符 -> ε】的产生式
4. SELECT集的构造方法
   • 上述LL(1)分析表的构造过程, 实际上就是SELECT集的求法, 即:
     • 如果FIRST(X)中不存在空串ε, 则SELECT(X) = FIRST(X)
     • 如果FISRT(X)中存在空串ε, 则SELECT(X) = { FIRST(X) – ε } ∪ FOLLOW(Χ)

以书中的题为例：

• 文法，FIRST集和FOLLOW集：

• LL(1)分析表：