转换PCRE递归正则表达式到.NET均衡组定义 [英] Converting PCRE recursive regex pattern to .NET balancing groups definition

问题描述

PCRE有一个称为递归模式的功能，它可以被用来匹配嵌套子组。例如，请考虑语法

PCRE has a feature called recursive pattern, which can be used to match nested subgroups. For example, consider the "grammar"

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

它可以在PCRE进行与模式

It can be done in PCRE with the pattern

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

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

ABCDEFG ABC，DEF，GHI ABC ,,, DEF ,,,,,, [ABC] [A，BC; ] SSS [ABC; D]。 为[ABC; D，E] [ABC; D，E] [FGH; J，K] ＆LT; ABC＆GT; [＆LT; A＆GT; b，c为C，D＆GT;，＆LT; E，F＆GT;] ＆LT; A，B，C＆GT; ＆LT; A，BB，C＆GT; ＆LT ; ,,,＆GT; ＆LT;＆GT; ＆LT;＆GT;＆LT;＆GT; ＆LT;＆GT;，＆LT;＆GT; A＆LT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆LT; A＆GT;＆GT; ＆LT;＆LT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆GT;＆LT;＆GT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆GT; ＆LT; Z＆GT; A; B] ＆LT; Z [A; B] GT; [[]] [，;，] [[]] [＆LT; [;]取代;＆LT; [;] [;，＆LT;;，]＆GT;] GT;]

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]> [[;];] [,;,] [;[;]] [<[;]>;<[;][;,<[;,]>]>]

＆LT; A BC＆GT; ＆LT; ABC＆LT;德＆GT; [A＆LT; B; C取代; D，E] [A] ＆LT;＆LT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆GT;＆LT;＆GT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆GT;＆GT; ＆LT;＆LT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;＆GT;＆LT;＆GT;＆LT;＆LT;＆LT;＆GT;＆GT;＆GT; [ABC ;高清] [;]，] [; ,,] [ABC; D，E，F] [＆LT; [;]取代;＆LT; [;] [;，＆LT;;，]＆GT;]]＆GT; ＆LT; Z [A; B＆GT;]

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

目前在.NET中没有递归模式。相反，它提供均衡组了解基于堆栈的操纵匹配简单的嵌套模式。

There is no recursive pattern in .NET. Instead, it provides balancing groups for stack-based manipulation for matching simple nested patterns.

是否有可能转换成上述PCRE模式进入.NET的正则表达式的风格呢？

Is it possible to convert the above PCRE pattern into .NET Regex style?

<子>（是的，我知道这是最好不要使用正则表达式在这一点。这只是一个理论问题。）

• pcre.org - PCRE手册页 - 递归模式
• MSDN - 普通防爆pression语言元素 - 平衡组定义

• pcre.org - PCRE man page - Recursive Patterns
• MSDN - Regular Expression Language Elements - Balancing Group Definitions

推荐答案

在.NET替代递归模式是一个堆栈。这里的挑战是，我们需要EX preSS语法这方面堆栈。
下面是这样做的一种方式：

The .Net alternative to recursive pattern is a stack. The challenge here is that we need to express the grammar it terms of stacks.
Here's one way of doing that:

• 首先，我们需要语法规则（如 A 和问：中的问题）。
• 我们有一个堆栈。堆栈只能包含规则。
• 在弹出我们目前的状态从堆栈的每一步，符合我们所需要的匹配，并推动进一步的规则入堆栈。当我们有一个国家做到不推任何东西，返回到previous状态。

• First, we need grammar rules (like A and Q in the question).
• We have one stack. The stack can only contain rules.
• At each step we pop the current state from the stack, match what we need to match, and push further rules into the stack. When we're done with a state we don't push anything and get back to the previous state.

这个符号是介于 CFG 和的下推自动，我们推规则堆栈。

This notation is somewhere between CFG and Pushdown automaton, where we push rules to the stack.

让我们从一个简单的例子：一个 ^N B ^N 。通常的语法这种语言是：

Let's start with a simple example: aⁿbⁿ. The usual grammar for this language is:

S -> aSb | ε

我们可以另一种方式是，以适应符号：

We can rephrase that to fit the notation:

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

在的话：

• 我们在堆栈中以取值。
• 当我们跳出取值从堆栈中我们可以：
  • 匹配什么都没有，或者...
  • 匹配一个，但我们必须将状态 B 推到堆栈中。这是一个承诺，我们将匹配B。接下来，我们也推取值让我们可以保持匹配一个S如果我们想。
  • We start with S in the stack.
  • When we pop S from the stack we can either:
    • Match nothing, or...
    • match "a", but then we have to push the state B to the stack. This is a promise we will match "b". Next we also push S so we can keep matching "a"s if we want to.

    或更宽松：

    当我们在情况下S，匹配a和推B，然后S，或搭配什么都没有。
      当我们在情况B，匹配B。

    When we're in case S, match "a" and push B and then S, or match nothing.
    When we're in case B, match "b".

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

    In all cases, we pop the current state from the stack.

    这篇关于转换PCRE递归正则表达式到.NET均衡组定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！