3

我需要解析以下形式的表达式：

(S (A (B (D xyz)) (C m)))

( 的数量总是等于 ) 的数量，但是 (S ) 之间可以有任意数量的左括号和右括号对。在这种情况下，我想提取 (A (B (D xyz)) (C m))。文件中可能有任意数量的 (S ) 子句，所以我不能简单地进行 ^(S .* )$ 类型的模式匹配。

如果我知道 (S) 之间潜在的左括号和右括号对的数量，这不会那么困难，但我不确定如何编写一个知道匹配任意数量的 () 的正则表达式。

获得正则表达式模式的任何帮助将不胜感激。提前致谢。

4

3 回答 3

1

使用纯正则表达式不可能匹配任意数字。换句话说，当您生成/编写正则表达式时，您无法匹配一个未知的计数是不可能的。只要您知道生成正则表达式时，匹配n对（无论多么高）都是可能的。nn

于 2012-05-16T16:06:01.760 回答
1

这在理论上是做不到的，只有在预先知道最大嵌套括号数的情况下才能在实践中完成。该解决方案需要一种相当不愉快的表达方式，并且通常被尝试作为一种好奇的家庭作业。这是一个链接，可以更好地解释为什么正则表达式语言不足以解决匹配括号问题。

你需要一个解析器来解决这个问题；一个简单的递归下降就可以了。上面链接中的维基百科文章有一个 C 语言示例实现，您应该能够相对轻松地将其翻译成其他语言。

于 2012-05-16T16:03:01.360 回答
0

可能记录下降解析将是最好的选择。但是，如果您只想找到 (S) 平衡，则可以使用在引擎中进行递归的正则表达式来完成。

它会找到最外在的平衡。如果您正在寻找像 (S(S)) 这样的嵌套，可能涉及递归调用实现正则表达式的函数，传递成功匹配的“核心”。并可能在此过程中创建父子结构。但如果涉及到这个，真正的解析器可能是解决方案。

如何用 Perl 正则表达式解决它 - 

$str = '(some (stuff  (S (A (B (D xyz)) (C m))) the end ) (S extra))';

$regex = qr~
[(]
\s* S \s*
(                   # 1
    (                       # 2
      [(]
      (?:  (?> [^()]+ ) 
        |  (?2)                                         
      )*                                               
      [)]
    )
 |
    [^)]*
)
[)]
~x;

while ($str =~ /$regex/g)
{
    print "found '$1'\n";
}

印刷

found '(A (B (D xyz)) (C m))'
found 'extra'
于 2012-05-16T18:53:59.920 回答