编译原理——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)分析表: