编译原理LL1文法FIRST 和FOLLOW集

### 编译原理 LL(1) 文法 FIRST 和 FOLLOW 集合 计算 方法

#### 定义与概念

对于给定的上下文无关文法 (CFG)，FIRST和FOLLOW集合用于描述非终结符可能推导出的第一个符号以及紧跟在其后的符号。

- **FIRST集**表示某个符号串能够推导出来的最左边第一个终结符组成的集合。如果该符号串可以推导出ε（空字符串），那么也认为ε属于这个符号串的FIRST集[^3]。

- **FOLLOW集**是指某非终结符A后面可能出现的终结符构成的集合，即在任何可由起始符号S派生出的句型中，在紧接于A之后出现的终结符a所形成的集合；另外还包括当且仅当A能出现在某些句型结尾处时$（代表输入结束标志）也会成为其成员之一。

#### 计算方法

##### FIRST集计算：

1. 对于每一个终结符`a`，有`FIRST(a)`等于{ `a` }；
2. 如果存在产生式`A -> ε`，则将ε加入到`FIRST(A)`中；
3. 若有一个产生式形式为`A → X₁X₂...Xₙ`，
- 初始化临时变量tempSet为空集
- 依次考虑每个Xi(i=1,2,...n)
- 将`FIRST(Xi)\ {ε}`中的所有元素都加到tempSet里
- 如果`ε ∈ FIRST(Xi)`
- 继续处理下一个Xi直到遇到不包含ε的情况为止
- 或者已经遍历完了所有的Xi此时应把ε也放入最终的结果集中
4. 迭代上述过程直至不再发生变化[^5]。

void compute_first_sets() {
    bool changed;
    do {
        changed = false;
        for each non_terminal A in grammar {
            foreach production rule of form A->α {
                set temp_set = {};
                int i = 0;
                while (true){
                    if (first[i][alpha[i]] contains epsilon || i >= length(alpha)){
                        add all elements from first[i][alpha[i]] to temp_set except epsilon;
                        break;
                    }
                    else{
                        add all elements from first[i][alpha[i]] to temp_set;
                        ++i;
                    }
                }
                if (!subset_of(temp_set, first[A])){
                    union(first[A], temp_set);
                    changed |= true;
                }
            }
        }
    }while(changed);
}

##### FOLLOW集计算:

1. 把 `$`(输入结束标记) 加入到开始符号 S 的 FOLLOW(S) 中；
2. 对于每条规则`A→αBβ`：
- 把`FIRST(β)\{ε}`里的所有元素添加至`FOLLOW(B)`内；
- 当`ε∈FIRST(β)`时还需进一步操作如下两种情况：
- 如果 B 是最后一个符号(`A→αB`)，则直接将整个`FOLLOW(A)`复制过来作为新的部分并加入到`FOLLOW(B)`之中；
- 否则继续向右寻找其他可能影响到`FOLLOW(B)`的因素，重复执行此步骤直到无法再找到更多贡献源位置停止。

void compute_follow_sets(){
    follow[start_symbol].insert('$');
    
    bool change_made;
    do {
        change_made = false;

        for each production P : A -> α.Bγ where '.' indicates current position before symbol γ and after sequence α,
          // Case when dot is at the end or next character can derive empty string.
          if(dot_position == last_char_or_next_chars_can_derive_empty_string()){
              extend(follow[B],follow[A]);
              mark_as_visited(P); 
          }

         // For other cases just take first set without considering epsilon transitions.
         else{
             extend(follow[B],first[dot_character]-{'epsilon'});
         }
         
         update_change_flag(change_made);

    }while(has_unvisited_productions());
}