javascript - 对于正则表达式模式，如何确定与模式匹配的最长字符串的长度？

Question

有了 Regex 模式 regexPattern，我如何确定与 regexPattern 匹配的最长字符串的长度。

虚构的 int LongestLength(string pattern) 应该像这样工作:

Assert.Equals(LongestLength("[abc]"), 1);
Assert.Equals(LongestLength("(a|b)c?"), 2);

Assert.Equals(LongestLength("d*"), int.MaxValue); // Or throws NoLongestLengthException

虽然题目是 C#，但 C# 和 JavaScript 的答案都很好。

Answer 1

这对于 proper regex 来说非常简单仅使用运算符 ?、* 和 + 和 |，加上括号、字符类，当然还有普通字符.事实上，即使是 \1 风格的反向引用(它不是正则表达式的正式定义的一部分，并且确实使一些关于正则表达式的问题复杂化)也可以毫无问题地处理。

正则表达式只是树结构的紧凑编码(类似于数学公式是描述算术的树结构的紧凑编码)。在每对相邻的字符之间有一个隐含的“跟随”运算符，它对应于一个有 2 个子节点的节点，一个是它左边的子正则表达式，另一个是正则表达式的整个其余部分；由 | 字符分隔的一系列子正则表达式对应于单个“alt”节点，其子节点的数量与备选方案的数量一样多(即，比 | 字符的数量多一个) ，而每个其他运算符只有一个 child (即它所操作的子正则表达式)，而每个普通字符或字符类根本没有 child 。要计算最大长度匹配字符串，您可以对该树结构进行自下而上的遍历，在每个节点贪婪地分配将匹配该节点的最长字符串的长度，给定与其匹配的最长字符串的知识 children 。

确定与这棵树中任何给定节点匹配的最长字符串长度的规则是:

• 遵循(x, y) (xy): maxlen(x) + maxlen(y)
• alt(a, b, ..., z) (a|b|...|z): max(maxlen(a), maxlen(b), ...,最大长度(z))
• 也许(x) (x?): maxlen(x)
• rep(x) (x*) 或 posrep(x) (x+):无穷大
• 任何其他单个字符或字符类([...]):1
• \1-style backreferences: 相应括号表达式的 maxlen

一个结果是 * 或 + 出现在任何地方(除非转义或字符类的一部分，显然)将导致无限向上传播直到它击中根源。

例子

Regex: abcd
"Function call syntax": follows(a, follows(b, follows(c, d)))
As a tree:

follows
 /  \
a  follows
    /  \
   b  follows
       /  \
      c    d

第二个例子:

Regex: (a|b|de)c?
"Function call" syntax: follows(alt(a, b, follows(d, e)), maybe(c))
As a tree:

     follows
     /     \
   alt     maybe
  / | \        \
 a  b follows   c
       /  \
      d    e

对于第二个正则表达式/树，自下而上的遍历将为叶节点 a、b、d、e 和 c 分配 maxlen 为 1；那么底部 follows() 节点的 maxlen 是 1 + 1 = 2；那么 alt() 节点的 maxlen 是 max(1, 1, 2) = 2；可能节点的 maxlen 为 1；最顶层的 follows() 节点的 maxlen，因此对于整个正则表达式，是 2 + 1 = 3。

如果您指的是允许其他 Perl 风格增强功能的正则表达式，它可能会变得更加复杂，因为局部最佳长度选择可能会导致全局次优选择。 (我原以为 Perl 风格的扩展甚至有可能使正则表达式图灵完备，这意味着通常不可能确定是否有 any 匹配的字符串——但 the discussion here 似乎表明情况并非如此，除非您当然允许 ?{...} 构造。)