编译原理 first集

### 编译原理入门教程推荐

对于希望了解编译原理的初学者来说，选择合适的教材和在线资源非常重要。以下是几个值得考虑的学习途径：

#### 推荐书籍
《Compilers: Principles, Techniques, and Tools》通常被称为“龙书”，由Alfred V. Aho等人编写[^2]。这本书全面介绍了编译器设计的核心概念和技术。

#### 在线课程
Coursera平台提供了一门名为“Compiler Construction”的课程，该课程涵盖了从词法分析到优化等多个方面的内容[^3]。这门课适合有一定编程基础的学生学习。

#### 开放教育资源
麻省理工学院(MIT)通过其开放式课程ware项目提供了免费访问的《Introduction to Compiler Design》讲义和视频讲座[^4]。这些材料可以帮助自学者掌握基本理论并实践简单的编译工具开发。

#### 实践练习
为了更好地理解所学知识，建议尝试构建小型编译器项目。可以使用Lex/Yacc组合来实现一个简易的语言解析器作为起点[^5]。

# 安装 Lex 和 Yacc 工具链 (以 Ubuntu 系统为例)
sudo apt-get install flex bison

相关问题

编译原理FIRST 集及 FOLLOW 集

### 编译原理中的FIRST集和FOLLOW集

#### FIRST集的定义与计算方法

对于上下文无关文法 \( G=(V_T,V_N,S,P) \)，\( FIRST(\alpha) \) 表示由字符串 \( \alpha \) 能够推导出的第一个终结符组成的集合。具体来说：

- 如果 \( \alpha \rightarrow a\beta \)，其中 \( a \in V_T \)，那么 \( a \in FIRST(\alpha) \)[^1]。
- 若 \( \alpha \) 可以推导为空串 \( \epsilon \)，即存在 \( \alpha \Rightarrow^{*} \epsilon \)，则规定 \( \epsilon \in FIRST(\alpha) \)。

为了计算某个非终结符 X 的 FIRST 集合，可以按照如下规则迭代处理直到不再发生变化为止：
- 初始化：如果有一个产生式形如 \( A \to a... \)，则将 \( a \) 加入到 \( FIRST(A) \) 中；如果有 \( A \to \epsilon \)，则加入 \( \epsilon \) 到 \( FIRST(A) \) 中[^3]。
- 迭代更新：考虑形式为 \( A \to XYZ...\) 的产生式，
- 将所有属于 \( FIRST(X) \setminus \{\epsilon\} \) 的元素加至 \( FIRST(A) \)；
- 当且仅当 \( \epsilon \in FIRST(X), FIRST(Y)... \)，才把后续符号对应的 FIRST 值（去除 ε）以及最终可能存在的 ε 添加进去。

#### FOLLOW集的定义与计算方法

设 \( S \) 是起始符号，则 \( FOLLOW(S) \) 总包含结束标记 $ 。对于任意其他非终结符 A:

- 对于每条形如 \( A \to ...BX... \) 的规则，应将 \( FIRST(X)\setminus\{\epsilon\}\) 中的所有成员放入 \( FOLLOW(B) \); 并且如果 \( \epsilon \in FIRST(X) \)，还需进一步将整个 \( FOLLOW(A) \) 复制给 \( FOLLOW(B) \)。
- 对于任何直接位于句型末端的非终结符 B (比如 \( A \to ...B$ \))，应该立即将 $ 放入 \( FOLLOW(B) \)。

#### 示例说明

假设给出一个简单的文法：

E -> TE'
E'-> +TE'|ε
T -> FT'
T'-> *FT'|ε
F -> id|(E)

##### 计算 FIRST(E)

由于 E 展开后的首个字符可能是来自 T 或者 E’ 的第一个字符，因此先分别求得这两个部分的第一组：

- \( FIRST(T)=\{id,(,\epsilon\} \)(因为 F 可以展开成 id 或者括号内的表达式，并且 T' 存在一个可选路径允许其生成空串)
- \( FIRST(E')=\{+, \epsilon\} \)

所以 \( FIRST(E)=FIRST(T)∪FIRST(E')-\{\epsilon\}= \{id, (+\} \)

##### 计算 FOLLOW(F)

考虑到 F 出现在两条不同的规则中：

- 在 `T -> FT'` 中，根据上述原则，需要加上 \( FIRST(T')-\{\epsilon\}=\{* ,\epsilon\}-\{\epsilon\}=\{* \}`;
- 同样地，在 `F -> id | (E)` 中，因它处于句柄位置，故还需要增加 \$ 至 \( FOLLOW(F) \);

综上所述，得到 \( FOLLOW(F)=\{$,*\} \)

编译原理 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]。