中山大学数据科学与计算机学院εNDFA确定化实验报告

"16337341+朱志儒+421" 这篇实验报告涉及的主题是编译器构造中的ε-NFA（非确定有限自动机）的确定化。ε-NFA是一种允许存在ε迁移（即无字符输入的迁移）的有限自动机，而确定化的目的是将ε-NFA转换为DFA（确定有限自动机），以简化其状态转移过程，便于后续的编译器分析和优化。 实验目标是设计并实现一个算法，将给定的ε-NFA状态集和映射集转化为确定的FA状态集和映射集。输入包括字母表、ε-NFA的状态信息以及映射信息，输出是相应的确定FA状态集和映射集。 算法描述中提到的关键步骤是“求Ia的方法”，即计算一个状态集I通过读取字符a后所能达到的状态集J，并对J进行ε-闭包操作。ε-闭包是指从一个状态出发，通过一系列ε迁移可以到达的所有状态的集合。造表法是一种用于实现这一过程的策略，它首先填充包含初始状态集S的ε-闭包的第一行，然后逐步计算每个状态集的Ix（读取x后的状态集）和Iy（读取y后的状态集），直到所有可能的组合都已出现在表的第一列中。 程序清单中使用了C++语言编写，包含了`iostream`、`string`、`vector`、`queue`和`algorithm`等库，用于处理输入输出、字符串操作、动态数据结构和算法。主要的数据结构有状态数组`state`、映射数组`mapping`、字符串向量`dfastate`（确定FA状态集）、`ffstate`（最终状态集）以及队列`rstate`（用于状态探索）。`eclosure`函数用于计算ε-闭包。 测试数据部分通常会提供若干输入示例，用于验证算法的正确性。程序清单中可能包含了处理这些输入并生成相应输出的代码，但具体实现细节未完全展示。 这个实验报告的焦点在于理解和实现ε-NFA到DFA的确定化过程，这对于理解编译器如何识别和处理正则表达式至关重要。通过这个实验，学生能够深入理解编译原理中的自动机理论，并锻炼编程实现复杂算法的能力。