regex - Perl 中的递归正则表达式

Question

我正在尝试使用它，但无法使其工作。我想检查这样的表达式的语法:(1+2)*(3+4)

我有整数、+、* 和括号。就是这样，但它可以嵌套到任何深度。

在 BNF 语法中，expr 可以这样描述:

expr
<sum>
sum
<product>{+<product>}
product
<atom>{*<atom>}
atom
<number>|(<expr>)
number
<digit>{<digit>}

我尝试将其翻译为 Perl，如下所示:

$number = '\d+';
$atom = "($number|\\((?R)\\))";
$product = "$atom(\\*$atom)*";
$sum = "$product(\\+$product)*";
$expr = $sum;
if ('(1+2)*(3+4)' =~ /^$expr$/)
{
    print "OK";
}

但是不匹配!我做错了什么？

Answer 1

当您递归时，模式开头的 ^ 将无法匹配。

使用(?(DEFINE)...)定义规则，而不是使用(?R)。

'(1+2)*(3+4)' =~ /
   ^ (?&expr) \z

   (?(DEFINE)
      # Rules.
      (?<expr>    (?&sum)                            )
      (?<sum>     (?&product) (?: \+ (?&product) )*+ )
      (?<product> (?&atom)    (?: \* (?&atom)    )*+ )
      (?<atom>    (?&NUMBER) | \( (?&expr) \)        )

      # Tokens.
      (?<NUMBER> \d++ )
   )
/x
   or die("Doesn't match.\n");

简化为

'(1+2)*(3+4)' =~ /
   ^ (?&expr) \z

   (?(DEFINE)
      # Rules.
      (?<expr>      (?&binary_op)                  )
      (?<binary_op> (?&atom) (?: [+*] (?&atom) )*+ )
      (?<atom>      (?&NUMBER) | \( (?&expr) \)    )

      # Tokens.
      (?<NUMBER> \d++ )
   )
/x
   or die("Doesn't match.\n");

假设您只是尝试检查有效性而不是尝试解析字符串。如果需要解析字符串，可以使用 Parse::RecDescent 或 Marpa::R2 构建解析器。