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

For a regex pattern, how to determine the length of longest string that matchs the pattern?

本文关键字：模式匹配 字符串 何确定 正则表达式 模式      更新时间：2023-09-26

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 的答案都很好。

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

正则表达式只是树结构的紧凑编码

(类似于数学公式是描述算术的树结构的紧凑编码(。 在每对相邻字符之间都有一个隐式的"跟随"运算符，它对应于一个具有 2 个子节点的节点，一个是其左侧的子正则表达式，另一个是正则表达式的整个其余部分;由|个字符分隔的子正则表达式序列对应于单个"alt"节点，该节点具有与替代项一样多的子节点(即，比|字符的数量多一个(，而其他每个运算符只有一个子项(即它操作的子正则表达式(，并且每个普通字符或字符类根本没有子项。 要计算最大长度匹配字符串，您只需对此树结构进行自下而上的遍历，在每个节点上贪婪地分配与该节点匹配的最长字符串的长度，给定与其子节点匹配的最长字符串的知识。

用于确定与此树中任何给定节点匹配的最长字符串长度的规则如下：

  • follow(x， y( ( xy (： maxlen(x( + maxlen(y(
    • alt(a， b， ...， z( ( a|b|...|z (： max(maxlen(a(， maxlen(
  • b(， ...， maxlen(z((
  • 也许(x( ( x? (： 麦克斯伦(x(
  • rep(x( ( x* ( 或 posrep(x( ( x+ (： 无穷大
  • 任何其他单个字符或字符类 ( [...] (： 1
  • '1 样式反向引用：对应括号表达式的 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; 最顶层的 follow(( 节点的 maxlen， 因此，对于整个正则表达式，是 2 + 1 = 3。

如果你的意思是允许其他 Perl 风格的增强功能的正则表达式，它可能会变得更加复杂，因为局部最优的长度选择可能会导致全局次优的长度选择。 (我曾认为 Perl 风格的扩展甚至有可能使正则表达式图灵完整，这意味着通常不可能确定是否有任何匹配的字符串 - 但这里的讨论似乎表明情况并非如此，除非您当然允许在?{...}结构中。

所以我如何做这个函数是首先创建键值对数据类型。然后用每种类型的正则表达式语法填充数据类型。所以键将是正则表达式语法(例如："*"(。该值将是它将增加多少匹配的字符串的可能长度。因此，键："*"的值为 int.maxvalue。因此，您将遍历列表并搜索传入的任何语法的正则表达式，并将找到的所有值相加并返回。但是，您必须记住，某些语法是转义的，因此您无法计算它们。以及一些语法自动使可能的长度为 int.maxvalue("*"、"+"等(。因此，请先检查这些语法，以便在找到这些类型的正则表达式语法之一后立即自动发回 int.maxvalue。

相关文章：