RegEx引擎如何工作

Question

在学习正则表达式时,我想知道底层引擎是如何工作的.可能更具体地说,我想更多地了解它如何评估,优先考虑和解析表达.我觉得RegEx引擎对我来说是一个黑盒子,我真的很喜欢破译它.

所以我想问一下,在讨论RegEx引擎理论时是否有一些我可以阅读的优秀资源.

*注意:我对构建引擎不感兴趣,只是学习引擎的内部工作原理.

Answer 1

有两种主要的正则表达式引擎.

基于有限状态自动机的那些.这些通常是最快的.它们通过构建状态机并从输入字符串中提供字符来工作.如果不是不可能的话,在这样的引擎中实现一些更高级的功能是很困难的.

基于FSA的引擎示例:
- Posix/GNU ERE/BRE - 用于大多数unix实用程序,例如grep,sed和awk.
- Re2 - 一个相对较新的项目,试图为基于Automata的方法提供更多功能.
那些基于反向跟踪.这些通常将模式编译成字节码,类似于机器指令.然后引擎执行代码,从指令跳转到指令.当指令失败时,它会回溯以找到匹配输入的另一种方式.

基于反向跟踪的引擎示例:
- Perl - 原版.此类型的大多数其他引擎都试图在Perl语言中复制正则表达式的功能.
- PCRE - 最成功的实施.该库是使用最广泛的实现.它具有丰富的功能,其中一些不再被视为"常规".
- Python,Ruby,Java,.NET - 我不打算进一步描述的其他实现.

欲获得更多信息:

如果您希望我扩展某些内容,请发表评论.