DFA状态的计算

Question

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

Answer 1

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

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

作为对以下问题的回应:假设DFA已经最小化，那么DFA中的状态数量可以被认为是定义得很好的。然而，转换的数量并不是很好的定义。

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

其次，flex有最小化所有表的总大小的策略。-Cf选项指示它不要这样做。一种这样的优化是找到字符的等价类，并且仅对每个字符类使用转换。输入字符首先被转换为它的类，然后用它来确定转换。因此，转换的数量要少得多，但是需要一个附加表(参见yy_ec)来确定字符类。

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

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

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