使用正则表达式查找匹配的括号

Question

使用正则表达式查找匹配的括号

.netregexparsinggrammarmatching

4

输入是一个表示元素列表的字符串。

列表定义为一个开放的大括号 {，后跟 0 或多个由空格分隔的元素，后跟一个关闭的大括号 }。

元素可以是文字或元素列表。

文字是一系列非空格字符。如果一个元素包含大括号，则必须使用反斜杠进行转义：\{ 和 \}。（或者为简单起见，您可以假设文字中不允许使用大括号）

示例：

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} x\{yz \}foo }"

字面量中不要使用花括号：

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} xyz foo }"

这是一个Tcl列表的简化定义。

我想知道的是：输入内容是否可以使用正则表达式拆分为最外层循环的元素？

期望输出：

abc
{ def ghi }
7
{ 1 {2} {3 4} }
{5 6}
x{yz
}foo

真正的问题是：这能用正则表达式实现吗？

我最感兴趣的是.NET版本，但会接受任何答案。

我将在回答中发布自己的假设，并查看它是否被验证或销毁。

- Cristian Diaconescu

1

为什么 }foo 是一个字面量，但 4} 不是呢？实际上，根据你的定义，}是一个有效的字面量。 - Kobi

@Kobi 你说得对。我试图获得与 Tcl 解释器类似的定义，但它会做一些奇怪的事情。例如，它允许 set a 3{4，但不允许 set a {1 2 3{4 }。封闭花括号也有类似的行为。我会更新问题。 - Cristian Diaconescu

4个回答

3

好的，这个编辑程序可以从记号中去掉大括号并从问题中取出字符串，现在使用 .Net Regexes 的平衡组很容易做到。它只是匹配大括号，这是一个基本示例。
与 KennyTM 的答案类似，如果您不删除顶层大括号，它将无法正常工作，或者它将匹配整个输入。
同样，这更适用于娱乐目的：

(?:                    # try matching...
    (?:\\[{}]|[^\s{}])+\s*? # a literal (allow escaped curly braces)
    |                       # OR
    (?<Curly>{)\s*          # "{" and push to stack
    |                       # OR
    (?<-Curly>})\s*?        # "}", pop from stack and fail if the stack is empty
)+?                    # ...a few times, and stop whenever you can.
(?(Curly)(?!))         # Make sure there aren't any extra open curly braces

更多详细信息请参阅此文章：深入了解正则表达式平衡组

- Kobi

在问题更新之前，我无法让它正常工作。在另一个问题中，我们从头到尾进行验证(^(?:...)+$)，因此引擎必须尝试每种组合。然而，当您为令牌匹配时，引擎可以使用更少的内容来满足要求，这使得设置优先级变得困难。 - Kobi

2

传统观点是坚决不行的。正如我们在编译器课程中所学到的那样，常规语法不能用来描述具有递归定义的语言（即你不能使用有限状态机）。

这里需要的是一个上下文无关解析器，其实现归结为有限状态机+堆栈。
参见ANTLR、bison等。

- Cristian Diaconescu

2

下一次，你可能想在发布答案前提前几分钟离开，因为如果已经有一个受欢迎的帖子，那么其他人很难获得任何投票，这可能会阻止许多其他人发布...甚至查看该问题（如果问题已经被回答，许多人甚至都不会看到它）。我假设您有兴趣收到其他意见，否则您就不会发帖了...对吧？PS：在.NET中，我相信可以使用“常规”表达式来实现此目的，但是您是正确的，不建议使用正则表达式。 - Mark Byers

2

@EJP：这是一个自问自答，严格来说它并不正确，因为在 .NET 中，“正则表达式”实际上根本不是正则的，事实上它可以解析上述内容。但总的来说，这个答案仍然是好的建议。发布自问自答没有问题，这个答案也没有问题，我只是想说，如果他真的想要不同的意见而不仅仅是快速的声望提升（我认为他是），那么他应该等待一下再发布，以避免阻止其他人回答。 - Mark Byers

@mark 我重新阅读了你的评论。你是说这可以在.NET中完成吗？请给我一些证据，你就会得到被接受的答案。 - Cristian Diaconescu

1

@Mark，不仅是.NET，现今几乎所有编程语言中使用的正则表达式实现都不能被称为“正则”。如果一个正则表达式实现支持组和对这些组的反向引用，或者支持环视断言，那么它就不符合更严格的“正则”定义。 - Bart Kiers

1

@Crista Diaconescu：我找到的关于这个主题的最佳资料在这里：https://dev59.com/tXA75IYBdhLWcg3wVneI - Mark Byers

显示剩余3条评论

1

@Cristi关于正则表达式的观点是正确的：使用无栈、有限状态自动机理论上不可能解决递归表达式。然而，解决方案更简单：您只需要保持开放括号数量的计数器，并确保它不会降至0以下。这比维护一个堆栈更节省内存，而且您只需要括号的数量 - 而不是内容。

算法：

counter = 0                        // Number of open parens
For char c in string:              
    print c                        
    if c=='{':                     // Keep track on number of open parens
        counter++
    if c=='}':
        counter--
    if counter==1:                 // New line if we're back to the top level
        print "\n"
    elif counter<1:                // Error if the nesting is malformed
        print "ERROR: parentheses mismatch"
        break

- Adam Matan

真的，但修复很简单。 - Adam Matan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kennytm · Accepted Answer

很遗憾，对于某些正则表达式的变体，例如PCRE和.NET，答案是肯定的，因为它们支持递归模式和类似栈的操作。该语法可以编写为：

ELEMENT  -> (?!\{)\S+ | LIST
LIST     -> '\{\s*' ELEMENT? ('\s+' ELEMENT)* '\s*\}'

因此，在PCRE中，这可以转换为以下模式：

   \{\s*(?0)?(?:\s+(?0))*\s*\}|(?!\{)(?:[^\s}]|\}(?![\s}]))+

#  ---------------------------                   ^^^^^^^^^
#            LIST                    Make sure the } is not closing the group

请参见示例：http://www.ideone.com/SnGsU（为了简单起见，我去掉了顶层的{和}）。

（当然，请勿在工作中尝试：））

（顺便说一下，我不知道如何将此PCRE转换为.NET格式。如果有人知道，请尝试将PCRE递归正则表达式模式转换为.NET平衡组定义）