logo标签列表

将PCRE递归正则表达式模式转换为.NET平衡组定义

.netregexpcrerecursive-regexbalancing-groups
22

PCRE有一个名为递归模式的特性，可以用于匹配嵌套的子组。例如，考虑"语法"

Q -> \w | '[' A ';' Q* ','? Q* ']' | '<' A '>'
A -> (Q | ',')*
// to match ^A$.

可以使用 PCRE 模式来实现

^((?:,|(\w|\[(?1);(?2)*,?(?2)*\]|<(?1)>))*)$

（示例测试用例：http://www.ideone.com/L4lHE）

应该匹配：

abcdefg abc,def,ghi abc,,,def ,,,,,, [abc;] [a,bc;] sss[abc;d] as[abc;d,e] [abc;d,e][fgh;j,k] <abc> [<a>b;<c,d>,<e,f>] <a,b,c> <a,bb,c> <,,,> <> <><> <>,<> a<<<<>>><a>> <<<<<>>>><><<<>>>> <z>[a;b] <z[a;b]> [[;];] [,;,] [;[;]] [<[;]>;<[;][;,<[;,]>]>]

不应匹配：

<a bc> <abc<de> [a<b;c>;d,e] [a] <<<<<>>>><><<<>>>>> <<<<<>>>><><<<>>> [abc;def;] [[;],] [;,,] [abc;d,e,f] [<[;]>;<[;][;,<[;,]>]]> <z[a;b>]

.NET中没有递归模式。相反，它提供了平衡组以进行基于堆栈的操作，以匹配简单的嵌套模式。

是否可能将上述PCRE模式转换为.NET Regex样式？

（是的，我知道最好不要使用正则表达式进行此操作。这只是一个理论问题。）

参考资料

1
不错的问题。我的猜测是“不行”，但我很想看看是否有人能想出一种方法来实现它。 - EMP
1
我认为Perl正在赢得这场战斗。晚上我可能会尝试一下，但对于工作来说太过繁琐了 :P - Kobi
2个回答
13

.Net中替代递归模式的方法是使用栈。挑战在于我们需要用栈来表达语法。
以下是一种实现方式:

语法的稍微不同表示法

  • 首先，我们需要语法规则（例如问题中的A和Q）。
  • 我们有一个栈。该栈只能包含规则。
  • 在每个步骤中，我们从栈中弹出当前状态，匹配所需的内容，并将其他规则推入栈中。当我们完成一个状态时，我们不会推送任何东西，并回到以前的状态。

这种表示法介于上下文无关文法和下推自动机之间，其中我们将规则推送到栈中。

示例:

让我们从一个简单的例子开始：anbn。这种语言通常的语法如下：

S -> aSb | ε

我们可以重新用符号表示：

# Start with <push S>
<pop S> -> "a" <push B> <push S> | ε
<pop B> -> "b"

解释:

  • 我们从栈中开始使用 S。
  • 当我们从栈中弹出 S 时，我们可以选择：
    • 匹配空，或...
    • 匹配 "a"，但是接下来我们必须将状态 B 推到栈中。这是我们会匹配 "b" 的承诺。然后我们还推入 S，这样如果需要，我们就可以继续匹配 "a"。
  • 当我们匹配足够多的 "a" 后，我们开始从栈中弹出 B 并为每个弹出的 B 匹配一个 "b"。
  • 完成此操作后，我们已经匹配了偶数个 "a" 和 "b"。

或者，更松散地说：

当我们处于 S 状态时，匹配 "a" 并推入 B 和 S，或者什么也不匹配。
当我们处于 B 状态时，匹配 "b"。

在所有情况下，我们都从栈中弹出当前状态。

在 .Net 正则表达式中编写模式

我们需要以某种方式表示不同的状态。我们不能选择 '1' '2' '3' 或 'a' 'b' 'c'，因为这些可能不在我们的输入字符串中 - 我们只能匹配存在于字符串中的内容。一种选择是给我们的状态编号（在上面的示例中，S 是状态号 0，而 B 是状态号 1）。对于状态 S，我们可以将字符推入堆栈。为方便起见，我们将从字符串开头推送前几个字符。再次强调，我们并不关心这些字符是什么，只关心它们的数量。

推送状态

在 .Net 中，如果我们想将字符串的前 5 个字符推到堆栈中，我们可以编写：

(?<=(?=(?<StateId>.{5}))\A.*)

这有点复杂：

  • (?<=…\A.*) 是一个回顾，一直到字符串的开头。
  • 当我们到达开头时，有一个向前查找: (?=…)。这样做是为了匹配当前位置之后的内容——如果我们在位置2，我们就没有5个字符在前面。所以我们既要向前，也要向后看。
  • (?<StateId>.{5}) 将5个字符推入堆栈，表示在某个时刻我们需要匹配状态5。

弹出状态

按照我们的记号，我们总是从堆栈中取出顶部状态。这很容易：(?<-StateId>)。
但在那之前，我们想知道那是什么状态——或者它捕获了多少个字符。更具体地说，我们需要显式地检查每个状态，就像switch/case块一样。因此，要检查堆栈当前是否持有状态5：

(?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
  • 再次强调，(?<=…\A.*) 匹配一直到字符串的起始位置。
  • 现在我们将 (?=.{5}…) 往前移动五个字符...
  • 然后使用另一个回顾断言 (?<=\A\k<StateId>) 来检查堆栈是否确实有 5 个字符。

这种方法显然有一个缺点 - 当字符串太短时，无法表示大状态的数量。 解决这个问题的方法有：

  • 语言中短单词的数量是有限的，因此我们可以手动添加它们。
  • 使用比单个堆栈更复杂的东西 - 我们可以使用几个堆栈，每个堆栈都有零个或一个字符，有效地成为我们状态的位（末尾有一个示例）。

结果

我们匹配 anbn 的模式如下：

\A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State B, Index = 1
                (?<=(?=(?<StateId>.{1}))\A.*)
                a
                # Push State A, Index = 0
                (?<StateId>)
                |

            )
        )
        |
        (?:
            # When In State B, Index = 1
            (?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            b
        )
        |\Z
    ){2}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))

Regex Storm上的工作示例

注意事项：

  • 请注意状态周围的量词为 (?:(?:…){2})+ - 也就是说，(状态数量)×(输入长度)。我还添加了一个 \Z 的替代方案。我们不需要深入讨论，但它是 .Net 引擎中的烦人优化的解决方法。
  • 同样可以写成 (?<A>a)+(?<-A>b)+(?(A)(?!)) - 这只是一个练习。

回答问题

问题中的语法可以重写为：

# Start with <push A>
<pop A> -> <push A> ( @"," | <push Q> ) | ε
<pop Q> -> \w
           | "<" <push Q2Close> <push A>
           | "[" <push Q1Close> <push QStar> <push Q1Comma> <push QStar> <push Q1Semicolon> <push A>
<pop Q2Close> -> ">"
<pop QStar> -> <push QStar> <push Q> | ε 
<pop Q1Comma> -> ","?
<pop Q1Semicolon> -> ";"
<pop Q1Close> -> "]"

该模式：

\A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State A, Index = 0
                (?<StateId>)
                (?:
                    ,
                    |
                    # Push State Q, Index = 1
                    (?<=(?=(?<StateId>.{1}))\A.*)
                )
                |

            )
        )
        |
        (?:
            # When In State Q, Index = 1
            (?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                \w
                |
                <
                # Push State Q2Close, Index = 2
                (?<=(?=(?<StateId>.{2}))\A.*)
                # Push State A, Index = 0
                (?<StateId>)
                |
                \[
                # Push State Q1Close, Index = 6
                (?<=(?=(?<StateId>.{6}))\A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q1Comma, Index = 4
                (?<=(?=(?<StateId>.{4}))\A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q1Semicolon, Index = 5
                (?<=(?=(?<StateId>.{5}))\A.*)
                # Push State A, Index = 0
                (?<StateId>)
            )
        )
        |
        (?:
            # When In State Q2Close, Index = 2
            (?<=(?=.{2}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            >
        )
        |
        (?:
            # When In State QStar, Index = 3
            (?<=(?=.{3}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            (?:
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))\A.*)
                # Push State Q, Index = 1
                (?<=(?=(?<StateId>.{1}))\A.*)
                |

            )
        )
        |
        (?:
            # When In State Q1Comma, Index = 4
            (?<=(?=.{4}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            ,?
        )
        |
        (?:
            # When In State Q1Semicolon, Index = 5
            (?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            ;
        )
        |
        (?:
            # When In State Q1Close, Index = 6
            (?<=(?=.{6}(?<=\A\k<StateId>))\A.*)
            (?<-StateId>)
            \]
        )
        |\Z
    ){7}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))

不幸的是，它太长了，无法放入URL中，因此没有在线示例。

如果我们使用只包含一个或零个字符的“二进制”栈，它应该是这样的：https://gist.github.com/kobi/8012361

以下是模式通过所有测试的屏幕截图：http://i.stack.imgur.com/IW2xr.png

额外奖励

.Net引擎不仅可以平衡 - 还可以捕获每个A或Q的实例。这需要对模式进行轻微修改：https://gist.github.com/kobi/8156968。
请注意，我们已向模式添加了组Start、A和Q，但它们对流程没有影响，仅用于捕获。

结果：例如，对于字符串"[<a>b;<c,d>,<e,f>]"，我们可以获得这些Capture：

Group A
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-4) <a>b
    (2-2) a
    (7-9) c,d
    (13-15) e,f
Group Q
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-3) <a>
    (2-2) a
    (4-4) b
    (6-10) <c,d>
    (7-7) c
    (9-9) d
    (12-16) <e,f>
    (13-13) e
    (15-15) f

开放性问题

  • 每个语法都能转换为状态堆栈符号表示法吗？
  • （状态数）×（输入长度）足以匹配所有单词吗？还有哪些公式可以使用？

源代码

用于生成这些模式和所有测试用例的代码可以在https://github.com/kobi/RecreationalRegex上找到。

10

答案是(可能)是的。

这种技术比(?1)递归调用复杂得多，但结果与语法规则几乎一一对应 - 我按照这种系统化的方式工作，可以很容易地看到它如何编写。基本上，你逐块匹配，并使用堆栈来跟踪你所处的位置。这是一个几乎可行的解决方案:

^(?:
    (\w(?<Q>)) # Q1
    |
    (<(?<Angle>))  #Q2 - start <
    |
    (\>(?<-Angle>)(?<-A>)?(?<Q>))  #Q2 - end >, match Q
    |
    (\[(?<Block>))  # Q3 start - [
    |
    (;(?<Semi-Block>)(?<-A>)?)  #Q3 - ; after [
    |
    (\](?<-Semi>)(?<-Q>)*(?<Q>))  #Q3 ] after ;, match Q
    |
    ((,|(?<-Q>))*(?<A>))   #Match an A group
)*$
# Post Conditions
(?(Angle)(?!))
(?(Block)(?!))
(?(Semi)(?!))

在Q->[A;Q*,?Q*]的允许逗号方面存在缺失，出于某种原因允许[A;A]，所以它匹配了[;,,]和[abc;d,e,f]。其余的字符串与测试用例一样匹配。
另一个小问题是使用空捕获时将其推入堆栈的问题——它不会。 A接受Ø，因此我必须使用(?<-A>)?来检查它是否被捕获。

整个正则表达式应该像这样，但是再次强调，由于存在错误，它毫无用处。

为什么不起作用？

没有同步堆栈的方法：如果我推送(?<A>)和(?<B>)，我可以按任意顺序弹出它们。这就是为什么该模式无法区分<z[a;b>]和<z[a;b]>...我们需要一个堆栈来处理所有情况。
对于简单情况，可以解决这个问题，但是在这里我们有更加复杂的情况——一个完整的Q或A，而不仅仅是<或[。

1
顺便说一句，我很惊讶在这个主题上找到的资料如此之少。我是边学边做，花了很多时间。无论如何，如果有人发现我的代码中的缺陷，我会很乐意听取意见。 - Kobi
这个问题仍然困扰着我。我知道我的答案基本上是错误的，因为它没有考虑顺序，类似于http://kobikobi.wordpress.com/2010/12/14/net-regex-matching-mixed-balanced-parentheses/。 - Kobi
1
如果您不介意的话，能否在您的博客中回答这个问题并提供解决方案？https://dev59.com/X4Tba4cB1Zd3GeqP630l - nhahtdh
@nhahtdh - 我目前正在日本度假！随意添加或编辑您的答案。谢谢！ - Kobi
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接