Regex/matching 具有完全重叠结果和 "cursor" 操作的引擎

Question

我正在寻找与正则表达式引擎有点相似的东西，但它允许完全重叠的结果并允许在引擎返回匹配项时操纵内部 "cursor"。

正常的正则表达式方式：

假设您有一个带有各种 "alternatives" 的普通正则表达式：item1|item2|item3，并且您使用 findall 或 finditer 来获取所有匹配项。在输入字符串的某个位置，引擎可能会匹配这些备选方案中的任何一个。一旦找到，游标会在匹配结束后立即前进到索引，并继续寻找任何备选方案。即使这些备选方案中的两个或更多可能与初始光标位置处的字符串匹配，也只返回一个：

import re
input_string = 'foobar'
compiled = re.compile('foobar|foo|bar')
compiled.findall(input_string)

# 'foobar'

我想要的(1):

我要他们全部归还。像这样：

import muchneededregexthing
input_string = 'foobar'
compiled = muchneededregexthing.compile('foobar|foo|bar')
searcher = compiled.create_searcher(input_string)
while not searcher.reached_end():
    match = searcher.search() # increments searcher's internal cursor 
                              # to after the end of the match
    print(match.string, match.span())

# foobar (0,6)
# foo (0,3)
# bar (3,6)

我也想要(2):

我希望能够修改搜索器的光标，以便我可以根据运行时发生的情况来操作结果（'foobar' 匹配，'foo' 和 'bar'分开没关系）。

import muchneededregexthing
input_string = 'foobarkitten'
compiled = muchneededregexthing.compile('foobar|foo|bar|kitten')
searcher = compiled.create_searcher(input_string)
while not searcher.reached_end():
    match = searcher.search() # increments searcher's internal cursor 
                              # to after the end of the match
    print(match.string, match.span())
    if match.string == 'foobar':
        searcher.advance_cursor(match.end())

# foobar (0,6)
# kitten (6,12)

我不能使用的（最有可能）：

str.find：我需要用于标记 (markdown/wiki/etc) 解析器的正则表达式。在任何时候，都可能需要寻找许多不同的元素。使用 str.find 我需要使用标记支持的每个元素搜索整个文档。语言太复杂，无法将文档细分为 "header chunk"、"paragraph chunk" 等块
re：除非re神奇地支持我需要的东西，否则我不能使用它，原因如下：正则表达式有限，你不能匹配任何你喜欢的东西。然而，它们的属性对像我这样的案例很有用。我计划分两个阶段进行匹配：正则表达式为元素提供可能的匹配。然后，智能 function/method 会咨询 可能的 匹配是否是 良好的 匹配。如果是这样，很好，前进光标。如果没有，请拧 foobar 并给 foo 和 bar 一个机会。

非常欢迎提出想法。我相当确定我需要上述功能。到目前为止，我最好的想法是编写我自己的 muchneededregexthing 模块，支持 C/C++ 中的大部分正则表达式语法，所以不要担心我会认为你的想法牵强附会。

编辑 1：请求标记示例：

标记元素以及因此需要匹配的标记是通过插件定义和引入的。因此，框架本身不包含任何标记。我可以简单地将插件的令牌与正则表达式匹配并完成它，但我想至少探索这些选项并尝试允许比正则表达式能够支持的标记令牌范围更大的标记令牌。例如，如果他们的关系是数字应该是字符串的某种数字表示，那么如何匹配 string:number？ a:0 是有效标记，但 a:1 不是。然而，b:1 是，bc:28 (1*26 + 2*1).

也是

对于这个例子，插件可以提供一个正则表达式，例如 ([a-z]{1,5})([0-9]{1,5})。然后该算法会将匹配项传递给一个特殊函数，该函数计算第一组的数值并将其与第二组的值进行比较。如果这些值匹配，则插件将处理文档的这一部分。如果没有，它 returns 并尝试让另一个插件处理文档中的这个索引。

Answer 1

如果您保证不会有两个不同的模式在相同的位置匹配相同的长度，您可以使用纯 Python 轻松实现。

如果 pattern 是已编译的正则表达式，则 pattern.search(str, start) 将查找从 start 开始的匹配项，而 pattern.search(str, start, length) 将查找从 start 开始的匹配项长度最多 length.

所以搜索一下。前进到匹配的地方。检查是否需要。如果没有，则决定将其丢弃。使用相同的模式和更短的长度在同一点进行另一次搜索。如果不匹配，或匹配得更远，请将光标前移。

Answer 2

对于那些寻求这个问题答案的未来流浪者：我遇到了 hyperscan recently which does exactly what I was looking for. It's in C, but there is a Python port（我没有测试端口，但原生 C 版本工作得很好）。

虽然大多数正则表达式引擎将仅匹配输入字符串中给定偏移量上的一个子模式，但 Hyperscan 将报告与每个偏移量匹配的所有子模式。另见 hyperscan semantics。

Regex/matching 具有完全重叠结果和 "cursor" 操作的引擎

Regex/matching engine with completely overlapping results and "cursor" manipulation

python

regex

algorithm

markup

parsing