javascript - 使用 Javascript 正则表达式避免回溯

Question

我正在使用 JavaScript 开发函数解析器，它大致要求满足以下条件才能将文本序列视为函数:

• 包含驼峰命名(以非数字的小写字符开头)
• 可以有参数(如果没有参数，括号是可选的)
• 参数名称需要与函数名称具有相同的属性，并且可以有多个参数，以逗号分隔
• 返回变量名称是可选的，可以在函数定义后用“->”指定(即 someFunc(var1)->retVal 或 someFunc->retVal。它们需要具有与函数名称相同的属性。<

现在假设我得到一个包含函数定义的文本字符串(一些有效，一些无效)，如下所示:

somefunc(var1,var2),SomeFunc,somefunc()->RetVal,somefunc()->retVal,somefunc->retVal

这可以使用以下正则表达式进行解析:

((?:\b[a-z]\w*)\(?(?:[a-z]\w*,?)*\)?(?:->[a-z]\w*)?(?=,|$))+

将从中提取以下函数定义:

• somefunc(var1,var2)
• somefunc()->retVal
• somefunc->retVal

现在，即使我的正则表达式工作正常，我相信我可能会遇到一些基于使用 this 进行调试的回溯问题。正则表达式测试网站。例如，我相信当正则表达式命中上面字符串中的 SomeFunc 时，会发生大量回溯。

有什么方法可以优化这个正则表达式吗？如果是这样，我将来是否可以将任何准则应用于我的正则表达式，以提高它们的效率？

Answer 1

用 RegEx 解析通常不是一个好主意。RegEx 不是为解析而生的，它是为搜索和匹配而生的。因此，它的解析非常糟糕(而且效率低下)。

看起来您正在尝试生成文档？您是否考虑过使用 JSDoc ？这是一种编写 JS 注释的方式，可以为您生成文档。也有代码编辑器 (WebStorm) 可以为您生成实际注释。

抱歉，如果这不是您想听到的，但当我尝试做同样的事情时，它帮助了我。 :)

---

编辑:对于 Google 员工，这里有一些关于防止回溯的建议:

How do I prevent backtracking from happening?

Do not use nested constructs that have + or *! For example, ([a-z]+)* is a badly-written construct that could be rewritten as [a-z]* without changing the logic.

Applying this to our example above means the regex ^([a-zA-Z0-9]+\s?)$ should be changed to ^([a-zA-Z0-9]+\s)[a-zA-Z0-9]+$ to avoid a nested hierarchy. This adjustment means it only takes around 132 iterations for a string of length 30 instead of 1 billion! Sounds much better, right?

更多信息和示例可在来源处获得:https://community.appway.com/screen/kb/article/checking-strings-avoiding-catastrophic-backtracking-1482810891360