三、实验内容
根据文法文件中的产生式输出每一个非终结符的First集。项目类型为Visual C++ Win32 控制台应用程序
四、实验要求：
1、对First()函数的要求
函数的声明要求如下：
set<char>& First(const string& sSymbol, set<char>& setFirst);
第一个参数可以是一个产生式左部的非终结符，如”S”，也可以是右侧的一个候选式，如”TE’”，第二个参数是需要返回的结果集，返回值是求出的First集（即setFirst），包含单个字符的终结符。
2、对文法文件的格式要求
把文法写入wang_mao.txt文件，内容如下：
E->TE'|wang
E'->+TE'|$|mao
T->FT'
T'->*FT'|$
F->(E)|i
文件名用自己的名字全拼命名，如wang_mao.txt，文件中的$表示空串，名字是三个字的第三个字可以写在第三行，如：T->FT'|feng。
3、运行结果的要求
文法文件wang_mao.txt以命令行参数的形式传递给执行程序FirstFollow，如：FirstFollow Wan
### 实验知识点解析
#### 一、实验背景与目的
本次实验主要针对编译原理中的一个关键概念——First集的生成。First集是形式语言理论中的一个重要概念，在编译器设计过程中扮演着至关重要的角色。它主要用于确定词法分析器（如Flex）或语法分析器在遇到某个非终结符时，可能遇到的第一个输入符号是什么。了解并能够正确计算First集对于理解上下文无关文法以及后续的语法分析器设计至关重要。
**实验目的：**
1. **掌握First集的概念及其生成规则：**通过给定的形式文法规则，理解和掌握如何生成每个非终结符的First集。
2. **使用C++实现First集的生成算法：**利用Visual Studio 2015等工具，编写代码实现First集的计算功能。
#### 二、实验环境与工具
- **开发工具：**Visual Studio 2015
- **运行环境：**Windows 10 或 Windows 11
- **项目类型：**Visual C++ Win32 控制台应用程序
#### 三、实验内容详解
**实验内容：**根据给定文法文件中的产生式输出每个非终结符的First集。
**1. First()函数的设计**
函数签名：
```cpp
set<char>& First(const string& sSymbol, set<char>& setFirst);
```
- **sSymbol**：代表一个非终结符或者产生式右侧的一个候选式。
- **setFirst**：用于存储计算得到的First集。
**2. 文法文件格式**
文法文件名为wang_mao.txt，示例如下：
```
E->TE'|wang
E'->+TE'|$|mao
T->FT'
T'->*FT'|$
F->(E)|i
```
- 文件中的`$`表示空串（ε）。
- 如果名字是三个字，则第三个字可以写在第三行，例如：`T->FT'|feng`。
**3. 运行要求**
- 文法文件通过命令行参数传递给执行程序，例如：`FirstFollow Wang_mao.txt`。
- 输出结果类似：
- 每个非终结符的First集。
#### 四、实验算法与核心代码
**First集算法：**
1. 若有产生式 `Aaα`，其中`a∈VT`，则将`a`添加到`First(A)`中；
2. 若有产生式 `Aε`，则将`ε`添加到`First(A)`中；
3. 若有产生式 `AXα`，其中`X∈VN`，则将`First(X)`中非`ε`元素添加到`First(A)`中；
4. 若有产生式 `AX1X2X3...Xkα`，其中`X1X2...Xk∈VN`，则当`X1X2X3...Xi =>ε`（`1≤i≤k`）时，将`First(Xi+1...Xk)`的非`ε`元素添加到`First(A)`中；如果`X1X2X3...Xk=>ε`，则将`First(α)`加入`First(A)`中；
5. 重复执行上述过程，直到`First(A)`不再增大。
**核心代码示例：**
```cpp
set<char>& First(const string& sSymbol, set<char>& setFirst){
if (IsVn(sSymbol[0])) { // 判断是否为非终结符
for (const auto& candidate : g_Production[sSymbol]) { // 遍历所有候选式
size_t i = 0;
while (i < candidate.size()) {
char symbol = candidate[i];
if (IsVt(symbol)) { // 如果是终结符
setFirst.insert(symbol);
break;
} else { // 如果是非终结符
set<char> tempSet;
First(string(1, symbol), tempSet); // 递归调用First函数
if (!tempSet.count('$')) { // 如果当前非终结符的First集中不包含空串
setFirst.insert(tempSet.begin(), tempSet.end());
break;
} else { // 如果当前非终结符的First集中包含空串
setFirst.insert(tempSet.begin(), tempSet.end());
i++; // 移动到下一个符号继续处理
}
}
}
}
} else { // 如果是终结符
setFirst.insert(sSymbol[0]);
}
return setFirst;
}
```
**解释：**
1. **循环遍历每个候选式**：对于每个非终结符的候选式进行遍历。
2. **判断终结符和非终结符**：对于每个符号判断其为终结符还是非终结符。
3. **递归调用First函数**：对于非终结符，递归调用First函数，获取其First集，并根据规则更新当前非终结符的First集。
4. **处理空串情况**：当非终结符的First集中包含空串时，需要继续向右处理下一个符号，直到找到非空串的终结符为止。
通过以上步骤，我们可以有效地计算出每个非终结符的First集。这不仅是编译原理课程中的一个重点内容，也是实现语法分析器的重要基础。
