编译原理实验四----NFA确定化（附C++代码）

编译原理实验四----NFA确定化（附C++代码）

• 经验分享
• 算法思路
• • 前述知识点
  • 输入结构体
  • 子集法（确定化）
  • • 代码1：寻找闭包
    • 代码2：自动机运作总流程
    • 代码3：重新命名
  • 最小化
• 代码

1. 编译原理实验一----字符串匹配
2. 编译原理实验二----文法类型的判断
3. 编译原理实验三----词法分析器
4. 编译原理实验四----NFA确定化（附C++代码）
5. 编译原理实验五----LL（1）分析法
6. 编译原理实验六----编译器

经验分享

相信大家在学习此内容的时候都会遇见一个问题，就是课程上学习到的知识只能用来写一些NFA确定化的题目，但是上机实现的时候感觉无从下手。我自己总结的一套经验可以给大家分享分享，这种思路也可以说贯穿了整个项目的设计。
对于算法的设计，在动手之前，我们首先需要思考的问题就是：

1. 我们需要设计什么东西？
2. 我们设计的东西是以什么形式输入？
3. 我们设计的算法是否具有中间状态？
4. 该中间状态是以什么形式出现的？
5. 我们设计的东西是以什么形式输出？

我们下面都是围绕上述问题的过程。

算法思路

前述知识点

我们首先要明确的是:
一个非确定的有穷自动机(NFA)M是一个五元式：

1. M=(K,∑,δ,S,Z)
2. K是一个有限集，它包含所有状态。
3. ∑是一个有穷字母表，它包含所有输入字符
4. δ是包含所有状态转化过程的集合
5. S⊆K,是一个初态集
6. Z⊂ K , 是一个终态集

因此，我们需要使用的数据绝大部分是在δ中，包含转化的状态，输入的字符，以及转化到的状态。K集可以用来判断状态的合法性，∑用来判断输入字符的合法性，S, Z决定起始状态和终止状态，决定转化的起点与终点。

输入结构体

在了解上述情况，其实我们已经可以知道，所需的输入需要哪些数据，比如说下表为需要输入的NFA：(其实输出的DFA也同样是下述的结构)

再根据此表，我们可以定义一个结构体NFAnode，包含转化的状态（唯一），输入的字符（唯一），以及转化到的状态集，如下。

1. state：转化的状态
2. Map<QChar, QSet> nexts：根据上表，我们可知，每一个状态都对应一个输入字符，每一个输入字符都对应一个或者多个转化到的状态，因此，我们可以使用Map类型，前面的char类型表示输入字符，后面的set类型的容器表示转化到的状态集（使用set类型主要目的其实是去重）

注：Map类型和Set类型都是C++的容器，用途效率高，便捷，有需要的可以了解了解C++的STL库，STL库在项目中经常会使用到，推荐大概了解使用的方法
QChar类型和QSet类型以及QString类型是Qt重新封装的类型，与STL库类似，可移植性更强，功能类似

struct NFAnode {                     // 节点结构体
    QString state;                      // 状态
    QMap<QChar, QSet<QChar>> nexts;            // 下一个状态集合
    bool isChange = false ;                     // 是否改变（用于子集法确定化后的DFA重新给状态命名）
};
QVector<NFAnode> nodes;         // 输入节点数组

子集法（确定化）

在完成输入结构体的构建，以及输入对应数据后，我们需要知道的是，怎样把NFA确定化为DFA，最常用的方法就是子集法。子集法的官方描述较为抽象，可以用具体的例子来说明，如下。

1. 在已经了解到非确定的有穷自动机(NFA)是一个五元式M=(K,∑,δ,S,Z)，状态的转化肯定是从起始状态开始，因此可以得出下表，包含起始状态以及起始状态可以转化成的状态集：

2. 我们将整个起始状态可以转化成的状态集合作为一个状态，就可以解决一个输入字符，可以转移多个状态的问题，将NFA转化为DFA，如下表：

3. 继续根据输入五元式M=(K,∑,δ,S,Z)填表：（不含有终结状态黄色标注出来的了）

4. 得到DFA后，可以改写状态名称