带句点“.”的弹性规则没有编译

Question

我在使用 flex

编译此正则表达式时遇到问题

"on"[ \t\r]*[.\n]{0,300}"."[ \t\r]*[.\n]{0,300}"from"    {counter++;}

我在 flex 规范文件的规则部分有 100 百条规则。我试着编译它 flex -Ce -Ca rule.flex 我等了 10 个小时仍然没有完成所以我杀了它。我开始寻找问题并将问题缩小到这条规则。如果我从 100 条规则中删除这条规则，将它编译成 C 代码需要 21 秒。

如果我用其他字符替换句点，它会成功编译。例如

"on"[ \t\r]*[.\n]{0,300}"A"[ \t\r]*[.\n]{0,300}"from"    {counter++;}

立即编译。即使是 space 字符的句点 followed/preceded 也可以快速编译

"on"[ \t\r]*[.\n]{0,300}" ."[ \t\r]*[.\n]{0,300}"from"    {counter++;}

我可以从 flex manual 中看出“.”匹配文字“.”

我的规则有什么问题？

Answer 1

简单的回答是 [.\n] 可能并不像您认为的那样。在字符 class 中，大多数元字符都失去了它们的特殊含义，因此字符 class 只包含两个字符：文字 . 和换行符。你应该使用 (.|\n).

但这并不能解决问题。

根本原因是使用了固定的重复计数。如果匹配区域的末尾不明确，大（甚至不是那么大）的重复计数可能导致状态机的指数爆炸。

随着 [.\n] 的重复，除非正则表达式的其余部分可以以点或换行符开头，否则重复的匹配项具有明确的终止符。所以 "." 会触发问题，但 "A" 不会。如果您更正重复以匹配任何字符，那么任何后续字符都会触发指数爆炸。因此，如果您进行上述建议的更改，正则表达式将继续无法编译。

将重复计数更改为无限重复（星号运算符）可避免此问题。

为了说明问题，我使用了-v选项来检查具有不同重复计数的状态数。这清楚地显示了状态计数的指数增长，而且很明显，重复 14 次以上是不可能的。（我没有显示时间消耗；只要说 flex 的算法在 DFA 的大小上不是线性的就足够了，所以虽然每次额外的重复都会使状态数量加倍，但它大致使时间消耗增加四倍; 在 16 个状态下，flex 花费了 45 秒，因此假设它需要大约一周的时间来重复 23 次是合理的，前提是它需要的 6GB RAM 可用而无需太多交换。我没有尝试这个实验.)

$ cat badre.l
%%
"on"[ \t\r]*[.\n]{0,XXX}"."[ \t\r]*[.\n]{0,XXX}"from"
$ for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14; do
>   printf '{0,%d}:\t%24s\n' $i \
>      "$(flex -v -o /dev/null <( sed "s/XXX/$i/g" badre.l) |&
>         grep -o '.*DFA states')"
> done
{0,1}:        17/1000 DFA states
{0,2}:        25/1000 DFA states
{0,3}:        41/1000 DFA states
{0,4}:        73/1000 DFA states
{0,5}:       137/1000 DFA states
{0,6}:       265/1000 DFA states
{0,7}:       521/1000 DFA states
{0,8}:      1033/2000 DFA states
{0,9}:      2057/3000 DFA states
{0,10}:     4105/6000 DFA states
{0,11}:    8201/11000 DFA states
{0,12}:   16393/21000 DFA states
{0,13}:   32777/41000 DFA states
{0,14}:   65545/82000 DFA states

将正则表达式更改为对两次重复都使用 (.|\n) 大致使状态数增加三倍，因为随着该更改 both 重复变得不明确（并且两者之间存在相互作用他们两个）。

带句点“.”的弹性规则没有编译

Flex rule with a period "." is not compiling

regex

flex-lexer

lex