构造正则表达式的最佳NFA算法的选择

How to Choose the Best Algorithms for Translating Regular Expressions into NFA

介绍了工程中广泛应用的四种经典和先进的不确定有限自动机NFA的基本构造方法,它们是位置自动机Apos部分派生自动机Apd,跟随自动机Af,共同跟随集合自动机Acfs。列举大量工程实践中常用和经典的正则表达式,分别用上述自动机算法进行求解实验,对它们的运算尺寸以及与正则表达式尺寸之间的关系,列出表格分别进行比较分析,从中总结出各种自动机的构造特点和最佳应用场合。针对如何根据不同的正则表达式来选择非确定性有限自动机NFA算法提供了重要的参考依据。

This paper first introduces four algorithms for translating regular expressions into NFA： position automata Apos, partial derivative automata Apd, follow automata At, and common follow sets automata Acfs. And then the paper lists some typical regular expressions in practical applications, and uses transition graphs, parameterized methods and tables to analyze and compare the four algorithms based on these regular expressions. And then it concludes which algorithm should be used for what kinds of regular expressions. The conclusions of the paper are important for choosing the best algorithm for translating regular expressions into NFA in practice, especially to reduce the size of NFA.