正则表达式优化 - C枚举typedef

Question

我有一个项目需要从一个.h文件中解析枚举类型的定义。比如我们来看一个简单的例子：

typedef enum
{
    data1, /*aaagege*/
    data2,

    data3
}ESample;

这是一个非常简单的声明（没有赋值或者其他复杂的东西），但是我写的正则表达式在性能上似乎很差。我的表达式是：

typedef\s+enum\s*\{(?:\s+(\w+)[^\n]*)+\s*\}(\w+)\s*;

我在我的一个文件上测试了这个表达式（大约有2000行代码），结果花了很长时间……

我尝试的第一件事就是让所有可能的部分都变得不贪婪，像这样：

typedef\s+?enum\s*?\{(?:\s+?(\w+?)[^\n]*?)+?\s*?\}(\w+?)\s*?;

但是这样反而让情况更糟了。

有没有什么建议可以让我提高性能？如果你能解释一下你建议的解决方案以及为什么比我的好，那对我会有很大帮助。

提前谢谢你，
Kfir

Answer 1

我尝试做的第一件事就是让一切尽量不贪心……但这只让事情变得更糟。

当然会这样！怎么可能不会呢？看看这个正则表达式：

\w+\s

它会（贪心地）吃掉所有的单词字符，当这些字符用完后，它会寻找一个空格字符。现在考虑一下：

\w+?\s

这个表达式会吃掉一个单词字符，然后检查是否有空格。如果没有，它会再吃掉一个单词字符，然后再检查空格。它会检查每一个单词字符，看看是不是空格。

一般来说，不贪心的方式比贪心的方式慢，因为它需要检查同样的字符两次。有时候，不贪心的方式会产生不同的结果，但如果没有，总是使用贪心的方式。实际上，Perl有占有型量词：

\w++\s

这意味着“要贪心，如果匹配失败，就别想把任何字符还回来，因为你太贪心了。”上面的例子运行得很好，可能还可以优化，但你可以通过这个更好地理解：

\w++h

这个例子总是会失败，因为任何单词末尾的“h”字符会被\w++永久吃掉，而如果只是\w+，它会被吃掉，但在匹配失败后会被还回来，看看是否能成功。

不幸的是，按我所知，Python没有占有型的形式（不过在评论中，@tchrist建议了一个替代的Python正则表达式库），所以第一个例子大概是你能得到的最快的速度。你也可以通过搜索字符串“enum”的出现次数来加速，而不是使用一个巨大的正则表达式去搜索整个文件。

Answer 2

你不能用正则表达式来解析C语言：

// w00t /* "testing */ "strings n comments \"here"//
printf("/* haha gotcha\" epic stuff") /* "more text // */;

/* typedef test {
     val,
     "string",
*/ typedef test ??<
     val,
     "commentstring/*\"//",
??>

不过，如果你只是想快速处理一下所有的类型定义：

typedef\s+enum\s*{[^}]*}[^;]+;

Answer 3

慢的原因是因为你使用了嵌套的重复（用^标记的部分）：

(?:\s+(\w+)[^\n]*)+
                ^ ^

这会导致嵌套的回溯，从而使运行时间呈指数级增长。

但是你还有一个更大的问题，就是把一个组放在重复里面，这样只会保留这个组的最后一次匹配结果：

>>> print m.groups()
('data3', 'ESample')