Perl兼容正则表达式引擎:如何实现？

Question

perl,python,java和vim等用于实现正则表达式解析的基本方法是什么？

不聪明的形式语言的方法(即NFA,DFA); 也不是解析器组合器(例如14行正则表达式引擎).

我有一个看看源Java的实现Perl的风格的正则表达式,但其sophistcated功能(如,后引用)和效率(例如博耶-穆尔串匹配),使得它很难看到它是如何基本工作原理.

编辑 各种消息来源说:"回溯"参与(如正则表达式匹配可以是简单,快速 ; 形式化方法的课程),但并不清楚在什么是退步的 ...它来评估的方式NFA？它可以直接从正则表达式的AST完成吗？

java/perl/python正则表达式引擎实际上做了什么？

它是这样的:"一种用常规语言生成所有可能单词的方法,但只要它与输入字符串不匹配就放弃一个特定的单词".

Answer 1

正则表达式引擎中有两种常规方法.

• 正则表达式可以转换为有限自动机.这种关系在计算机科学中得到了很好的研究.然后可以有效地执行这些有限自动化,甚至可以向后运行.它们提供了强有力的保证,例如在输入字符串方面以线性时间和恒定空间运行,但是从正则表达式创建有限自动机可能很昂贵.这种方法还将引擎限制为真正的正则表达式,即排除了诸如反向引用或递归之类的高级功能.

• 正则表达式可以由回溯引擎解释.如果模式中的替代方法失败,则可以回溯到最后一个决策点并尝试不同的方法.这非常灵活,并且(具有递归+命名子模式等额外功能)可以解析更大类的正式语言(正式地,类似于LL(*)语法集).这与PEG解析器非常相似.最大的缺点是:由于回溯,运行正则表达式可能需要指数时间 - 即使没有任何额外的高级功能.

最重要的是,正则表达式引擎具有额外的优化功能,例如首先在模式中搜索常量子串,因为这比运行任何类型的正则表达式更有效(任何人甚至可以使用向量化的CPU指令).如果在多个常量字符串之间存在选择点,则可以非常容易地将它们编译成特里数据结构(实际上是简单的有限自动机).这可以减少回溯量.

演示有限自动机和回溯之间差异的正则表达式是a*a*a*a*a*b字符串上的模式aaaaaaaaaaaaaaacb.有限自动机很容易看出这个模式由于c输入中的不匹配.但是回溯引擎现在有许多决策点,它可以为每个a*子模式尝试不同的长度.像Perl这样的正则表达式引擎或rePython中的模块在这种情况下呈指数形式,即需要很长时间才能完成 - a在输入中添加更多s以使其花费更长时间.如果不受信任的用户可以提供任意正则表达式,则允许有趣的拒绝服务攻击.对于不受信任的输入,只应使用基于有限自动机的正则表达式引擎,例如来自Google的RE2.