在golang中使用嵌套组的regexp问题

Question

考虑以下玩具示例.我想在Go中使用正则表达式匹配,其中名称是a由单个分隔的字母序列#,因此a#a#aaa是有效的,但是a#或a##a不是.我可以通过以下两种方式编写正则表达式:

r1 := regexp.MustCompile(`^a+(#a+)*$`)
r2 := regexp.MustCompile(`^(a+#)*a+$`)

这两项都有效.现在考虑更复杂的匹配由单斜杠分隔的名称序列的任务.如上所述,我可以用两种方式编写代码:

^N+(/N+)*$
^(N+/)*N+$

其中N是带有^和$ stripped的名称的正则表达式.由于我有两个N的情况,所以现在我可以有4个正则表达式:

    ^a+(#a+)*(/a+(#a+)*)*$
    ^(a+#)*a+(/a+(#a+)*)*$
    ^((a+#)*a+/)*a+(#a+)*$
    ^((a+#)*a+/)*(a+#)*a+$

问题是为什么当匹配字符串时"aa#a#a/a#a/a"第一个失败而其余3个案例按预期工作？是什么导致第一个正则表达式不匹配？完整的代码是:

package main

import (
    "fmt"
    "regexp"
)

func main() {
    str := "aa#a#a/a#a/a"
    regs := []string {
        `^a+(#a+)*(/a+(#a+)*)*$`,
        `^(a+#)*a+(/a+(#a+)*)*$`,
        `^((a+#)*a+/)*a+(#a+)*$`,
        `^((a+#)*a+/)*(a+#)*a+$`,
    }    
    for _, r := range(regs) {
        fmt.Println(regexp.MustCompile(r).MatchString(str))
    } 
}

令人惊讶的是它打印 false true true true

Answer 1

您可以尝试减轻量词的原子子嵌套。
如果没有锚点，
如果使用像这样的嵌套可选量词，
当找不到直接解决方案时，表达式可能会在回溯中爆炸。

Go 可能对此犹豫不决，迫使它彻底失败，而不是
大规模回溯，但不确定。

尝试这样的事情，看看它是否有效。

 # ^a+(#?a)*(/a+(#?a)*)*$

 ^ 
 a+
 (                    # (1 start)
      \#?
      a 
 )*                   # (1 end)
 (                    # (2 start)
      /
      a+
      (                    # (3 start)
           \#?
           a 
      )*                   # (3 end)
 )*                   # (2 end)
 $

编辑：（从评论转过来）如果复杂性太高，有些引擎甚至不会编译它，有些引擎会在运行时默默地失败，有些引擎会锁定在回溯循环中。

这个细微的差别就是问题所在

坏：太复杂(#?a+)*
好：没有嵌套、开放式量词(#?a)*

如果您遇到此问题，请去掉嵌套，通常可以解决
回溯问题。

eit2：如果您需要分隔符并希望确保分隔符仅位于中间并被a' 包围，您可以尝试此操作

https://play.golang.org/p/oM6B6H3Kdx

 #  ^a+[#/](a[#/]?)*a+$

 ^ 
 a+
 [\#/] 
 (                             # (1 start)
      a
      [\#/]? 

 )*                            # (1 end)
 a+
 $ 

或这个

https://play.golang.org/p/WihqSjH_dI

 # ^a+(?:[#/]a+)+$

 ^ 
 a+ 
 (?:
      [\#/] 
      a+
 )+
 $