如何将有限模式扩展为所有可能的匹配？

Question

例如,给定模式

[a-zA-Z]_[0-9]{2}

函数将获取模式并返回包含的数组或列表

a_00, a_01, a_02, ... , a_98, a_99, ... , z_98, z_99

只需扩展数字和字母(及其有限分组).我该怎么做呢？Python或Perl中的示例将是首选.谢谢!

Answer 1

首先,解析表达式并构建一个反映正则表达式的语法结构的树,并包括一个逻辑上出现在末尾的终结符节点.例如,在lisp表示法中,您的示例可能如下所示:

(concat
  (repeat 2
    (concat
      (charset
        (range a z)
        (range A Z))
      (literal _)
      (charset
        (range 0 9))))
  terminator)

接下来,对树进行线程化,以便您可以使用递归来生成组合扩展.到那个,我的意思是比如那个节点a..z在(concat a .. z)所有需要从一个到下一个具有指针,所以a点b,等等,以及concat节点本身指向它的后继者.我们的想法是你可以在扩展中生成当前元素的一个版本,然后递归到下一个元素,当下一个元素返回时,你可以尝试当前元素的下一个版本等,直到所有版本都用完为止,你回到你的来电者(前任或父母).使用堆栈和树的后序遍历最简单地完成此线程.如果在后序遍历期间小心地推送节点,则堆栈的顶部将是序列中的下一个元素.

(线程的替代方法是构造树,以便每个concat节点中的下一个元素是前一个节点的子节点,repeat节点的子节点指向重复节点.)

然后编写一个例程(或使用模式匹配的例程集,或者如果树中的节点是使用面向对象语言中的多态实现的,则为虚拟方法),对于任何给定的节点类型,它会生成正确的输出并递归到下一个节点或儿童以适当的方式.例如,在伪代码中:

if node is of form (repeat n): # non-variable repeat
    for i in 1 to n
        recurse into child
    recurse into threaded successor

if node is of form (concat ...):
    recurse into first element # last element will recurse into successor

if node is of form (literal x):
    emit x
    recurse into successor
    remove x

if node is of form (charset ...):
    for each element in charset:
        emit element
        recurse into successor
        remove element

if node is terminator:
    add string created thus far to final output list

您可以观察到,重复节点的子节点不能递归到节点的后继repeat节点,因此在线程化树时需要考虑这一点.需要采取类似的措施,当到达节点的子节点结束时"当前进度"不会丢失repeat; 或者,子节点的后继者可以指向重复节点本身(即节点图上的真实闭包),但这需要在某处存储计数器.

总而言之,完成此操作可能需要几天时间,具体取决于它需要的灵活性和高性能.另请注意,某些构造(如Kleene星形或闭合(*或+扩展正则表达式))将导致无限列表.支持生成器(例如C#的迭代器语法)或协程/连续(例如Scheme的调用/ cc)或延迟评估(例如Haskell)的语言可以允许迭代列表的前几个元素而无需评估整个列表.或者,选择随机潜在输出而不是穷举迭代对于提供对应于正则表达式的示例可能是优选的.