regex - DFA 状态的计算

Question

我想使用 FLEX 计算某个正则表达式的 DFA 状态总数。哪些 C 文件或函数将帮助我使用 FLEX 完成这项任务？

Answer 1

如果您查看由 生成的文件flex，那么yy_accept(和yy_base) 中的条目数可能会很好地指示生成的 DFA 使用的状态数。如果您使用-Cf选项，则yy_nxt包含 DFA 的转换函数，并且表中的行数再次是已使用状态的数量。

您可能有不同版本flex的表名称不同，但它们的名称很可能非常相似。

针对您的以下问题：假设 DFA 已最小化，可以认为 DFA 中的状态数定义得很好。然而，转换的数量没有那么明确。

首先flex，每个输入字符都有一个转换，因为它会转换ECHO任何不属于定义语言的字符。这是由一个新的状态来实现的，以处理这种情况。使用调试器，您可以逆向工程这是哪个状态。但请注意，如果您使用启动条件，您可能必须考虑存在多个此类状态的可能性。如果您想分析许多正则表达式，那么您可能需要研究一些其他工具或获取源代码flex并从那里开始。

其次，flex有策略来最小化所有表的总大小。该-Cf选项指示它不要这样做。一种这样的优化是找到字符的等价类，并且只对每个字符类使用转换。一个输入字符首先被翻译成它的类，然后它被用来确定转换。因此，转换的数量要少得多，但需要一个附加表（请参阅 参考资料yy_ec）来确定字符类别。

因此，转换的数量不是一个定义得很好的概念。如果您对确定扫描仪的内存占用感兴趣，那么我会查看扫描仪数据部分的大小。例如objdump -h在lex.yy.o文件上使用。该.rodata部分的大小将对表格的总大小给出相当准确的估计。

您似乎已经找到了以更详细的形式给出 DFA 中状态数的-v选项。flex在回答为什么"a" {}给出 5 个状态时，您也可以使用该--trace选项，因为它在生成 DFA 时会给出它。显然还有一条End Marker规则，我假设它用于文件结尾。对于每个开始条件，有两种状态，一种在行的开头使用，另一种在行的中间使用。这使得 3 种接受状态（一种为"a"，一种为End Marker，一种为(.|"\n")）加上两种状态用于单一启动条件。

源文件dfa.c不是生成代码的一部分，但是如果您有勇气，当然可以更改源文件flex以进行自己的进一步分析。我快速浏览了一下，似乎代码的生成与转换交织在一起，这使得它不像实验平台所期望的那样模块化。还要注意 K&R 原型，它有效地禁用了对原型的任何类型检查。