编译原理 First集的实现

### 编译原理中First集合的实现方法

在编译器设计领域，`FIRST`集合用于描述给定文法符号串可能开始的终结符。如果该符号串可以推出空字符串，则`ε`也属于其`FIRST`集合。

#### 定义与性质
对于任一非终结符A，定义`FIRST(A)`为所有可以从A推导出来的最左端首个字符组成的集合（当能推导出空字时含`ε`）。此概念适用于预测分析表构建等场景[^1]。

#### 计算过程概述
为了获得某个特定非终结符X的`FIRST(X)`：

- 如果X是一个终端符号，则`FIRST(X)`仅包含自身；
- 若X是非终端且存在规则形如`X → Y...Z`，那么依次考察Y至Z各元素对应的`FIRST(Y)...FIRST(Z)`直到遇到不含`ε`的结果为止；若全含则最终还需加入`ε`到`FIRST(X)`里[^3]。

#### C++代码实例展示
下面给出一段基于上述原则编写用来计算并打印指定上下文无关文法规则集中各个非终态所对应`FIRST`集合作品质保证措施之一——测试用例验证环节不可或缺的部分程序片段:

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;

// 假设已知文法结构体Grammar及其成员函数getProductions()
struct Grammar {
    unordered_map<char,vector<string>> productions;
    
    const vector<string>& getProductions(char nonterminal){
        return productions.at(nonterminal);
    }
};

void compute_first_sets(const Grammar &grammar, unordered_map<char,set<char>>& firstSets);

int main(){
    // 初始化文法对象...
}

void compute_first_sets(const Grammar &grammar, unordered_map<char,set<char>>& firstSets) {
    bool changed = true;
    while(changed){
        changed=false;
        for(auto &[nonterm,rules]: grammar.productions){
            set<char> newFirsts;
            for(const auto& rule : rules){
                size_t i=0;
                do{
                    char symbol = rule[i];
                    if(islower(symbol)){ // 终结符处理逻辑简化表示
                        newFirsts.insert(symbol);
                        break;
                    }else{               // 对于非终结符查找已有first集合并考虑epsilon情况
                        for(auto elem:firstSets[symbol]){
                            if(elem!='\0')
                                newFirsts.insert(elem);
                        }
                        if(firstSets[symbol].find('\0')==firstSets[symbol].end())
                            break;
                    }
                }while(++i<rule.size());
                
                if(i==rule.size())       // 当前产生式全部由可选为空者构成
                    newFirsts.insert('\0');
            }

            if(newFirsts!=firstSets[nonterm]){ // 更新first集合并标记变更状态以便继续迭代直至稳定
                firstSets[nonterm]=newFirsts;
                changed=true;
            }
        }
    }
}

这段代码实现了对输入CFG（Context-Free Grammar）进行遍历，并通过固定点算法逐步填充每个非终结符关联的第一跟随项列表(`firstSets`)。这里采用了一个简单的do-while循环来模拟逐个检查产生式右侧符号的过程，同时利用了C++标准库中的容器类完成数据存储和操作[^2]。