将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中没有递归模式.相反,它为基于堆栈的操作提供了平衡组,以匹配简单的嵌套模式.

是否可以将上述PCRE模式转换为.NET Regex风格？

_{(是的,我知道最好不要使用正则表达式.这只是一个理论问题.)}

参考

• pcre.org - PCRE手册页 - 递归模式
• MSDN - 正则表达式语言元素 - 平衡组定义

Answer 1

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

语法略有不同

• 首先,我们需要语法规则(比如A和Q在这个问题).
• 我们有一个堆栈.堆栈只能包含规则.
• 在每一步中,我们从堆栈中弹出当前状态,匹配我们需要匹配的内容,并将更多规则推送到堆栈中.当我们完成一个州时,我们不会推动任何东西并回到之前的状态.

这种表示法介于CFG和Pushdown自动机之间,我们将规则推送到堆栈.

例:

让我们从一个简单的例子开始:a ⁿ b ⁿ.这种语言通常的语法是:

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从堆栈中弹出s,并为每个匹配一个"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/ caseblock.因此,要检查堆栈当前是否保持状态5:

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

• 再次,(?<=…\A.*)一路走到一切.
• 现在我们推进(?=.{5}…)五个字符......
• 并使用另一个lookbehind,(?<=\A\k<StateId>)检查堆栈是否真的有5个字符.

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

• 无论如何,语言中的短字数是最终的,因此我们可以手动添加它们.
• 使用比单个堆栈更复杂的东西 - 我们可以使用多个堆栈,每个堆栈有零个或一个字符,有效地处理我们的状态(最后有一个例子).

结果

我们的ⁿ b ⁿ模式如下:

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

^{可悲的是,它太长了,无法放入网址,因此没有在线示例.}

如果我们使用带有一个或零个字符的"二进制"堆栈,它将看起来像这样: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上找到

Answer 2

答案是_^(可能)是的.

这种技术比(?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>)?它来检查它是否被捕获.

整个正则表达式应该看起来像这样,但同样,那里的bug也没用.

为什么不工作？

没有同步堆栈的方式:如果我推(?<A>)及(?<B>),我可以按任何顺序弹出他们.这就是为什么这个模式不能区分<z[a;b>]自<z[a;b]>......我们需要对所有一个堆栈.对于简单的情况,
这可以解决,但是在这里我们有更复杂的东西 - 整体Q或者A不仅仅是"<"或"[".