正则表达式到Follow自动机的并行转换算法

"该研究探讨了正则表达式到Follow自动机的并行化构造算法，通过Thompson自动机、Glushkov自动机的转换以及等价状态合并，旨在生成规模更小、效率更高的有限自动机。" 正则表达式在计算机科学中扮演着重要角色，特别是在编译技术与模式匹配中。Thompson自动机、Glushkov自动机和Follow自动机是三种常用的有限自动机，它们在构建正则表达式的非确定性有限自动机（NFA）时各有优势。Thompson自动机以其结构简单和易于并行计算的特点被广泛使用。然而，为了优化性能和节省系统资源，通常需要将正则表达式转换为具有最少状态的NFA。 本研究提出了一个新的并行算法，首先从正则表达式构建Thompson自动机，这一步骤涉及到将正则表达式的结构转化为一种图形表示。Thompson自动机中可能存在ξ边，这些边不改变语言的接受性质，但可能导致状态数量过多。因此，算法的下一步是消除这些ξ边，这一过程有助于简化自动机结构，同时保持语言识别能力不变。此操作实际上实现了从Thompson自动机到Glushkov自动机的转换。Glushkov自动机通常具有更少的状态，但可能不直接支持并行计算。 随后，算法对Glushkov自动机的状态进行等价性检查，并合并等价状态，这一过程可以进一步减少自动机的状态数量。最终的目标是得到一个规模更小的有限自动机，即Follow自动机，它在保持与原正则表达式等价的同时，具有最小化的状态集，从而提高执行效率。 论文中提到了利用位并行算法和倒置自动机的概念来加速这一转换过程。位并行算法是一种利用计算机硬件的位运算能力来提高计算速度的技术，而倒置自动机M_R则用于辅助确定原Thompson自动机M中状态间的关系。通过这样的并行化处理，算法能够更有效地处理大型正则表达式，适用于多处理机环境和并行处理任务。 在实际应用中，这种并行化算法对于提升编译器的性能、优化模式匹配操作以及在资源受限的环境中实现高效计算都具有重要意义。通过实例模拟并行转化过程，作者验证了该方法的有效性和可行性。这一研究不仅丰富了正则表达式转换理论，也为并行编译技术提供了新的思考方向。