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

Question

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中没有递归模式。相反，它提供 balancing groups来进行基于堆栈的操作，以匹配简单的嵌套模式。
是否可以将上述PCRE模式转换为.NET Regex样式？
(是的，我知道最好不要使用正则表达式。这只是一个理论问题。)
引用文献

pcre.org - PCRE man page - Recursive Patterns

MSDN - Regular Expression Language Elements - Balancing Group Definitions

Answer 1

递归模式的.Net替代方案是堆栈。这里的挑战是我们需要表达语法术语栈。
这是一种方法:

语法的符号略有不同

首先，我们需要语法规则(例如问题中的A和Q)。

我们只有一堆。堆栈只能包含规则。

在每一步中，我们从堆栈中 pop 当前状态，匹配我们需要匹配的内容，然后将更多规则 push 堆栈。当我们完成一个状态时，我们什么也不做，就回到原来的状态。

该表示法介于 CFG和 Pushdown automaton之间，我们将规则 push 堆栈。

例:

让我们从一个简单的例子开始:anbn。这种语言的常用语法是:

S -> aSb | ε

我们可以将其改写为适合的符号:

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

换句话说:

我们从堆栈中的S开始。

当我们从堆栈中 pop S时，我们可以:

不匹配，或者...

匹配“a”，但是我们必须将B状态推送到堆栈。这是我们将匹配“b”的 promise 。接下来，我们还推送S，以便在需要时可以保持匹配“a”。

当我们匹配了足够的“a”后，我们便开始从堆栈中 pop B s，并为每个匹配一个“b”。

完成此操作后，我们匹配了偶数个“a”和“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".

在所有情况下，我们都会从堆栈中 pop 当前状态。

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

我们需要以某种方式代表不同的状态。我们不能选择'1''2''3'或'a''b''c'，因为我们的输入字符串中可能没有这些-我们只能匹配字符串中的内容。
一种选择是给我们的州编号(在上面的示例中， S的州编号为0，而 B的州编号为1)。
对于状态S𝒊，我们可以将𝒊个字符压入堆栈。为了方便起见，我们将从字符串的开头开始输入前𝒊个字符。同样，我们不在乎这些字符是多少，而是多少。

推送状态

在.Net中，如果要将字符串的前5个字符压入堆栈，可以编写:

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

这有点令人费解:

(?<=…\A.*)是一个回溯，一直到字符串的开头。

首先，我们要展望一下:(?=…)。这样做是为了使我们可以匹配当前位置以外的位置-如果我们位于位置2，则前面没有5个字符。因此，我们回头期待。

(?<StateId>.{5})将5个字符压入堆栈，表明在某些时候我们需要匹配状态5。

流行状态

根据我们的表示法，我们总是从堆栈中 pop 顶部状态。这很简单: (?<-StateId>)。
但是在我们这样做之前，我们想知道那是什么状态-或捕获了多少个字符。更具体地说，我们需要显式检查每个状态，例如 switch / case块。
因此，要检查堆栈当前是否处于状态5:

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

再次，(?<=…\A.*)从头开始。

现在我们将(?=.{5}…)推进五个字符...

并使用另一个后面的方法(?<=\A\k<StateId>)来检查堆栈中是否确实包含5个字符。

这有一个明显的缺点-当字符串太短时，我们无法表示大状态的数量。此问题有解决方案:

该语言中的简短单词数量是最终的，因此我们可以手动添加它们。

使用比单个堆栈更复杂的东西-我们可以使用几个堆栈，每个堆栈具有零个或一个字符，有效地表示了我们的状态(最后有一个例子)。

结果

我们的abn模式如下所示:

\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)(?!))

Working example on 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上找到用于生成这些模式和所有测试用例的代码