регулярное выражение с рекурсией в Perl

Question

Я пытаюсь использовать это, но не могу заставить его работать. Я хочу проверить синтаксис выражений, таких как: (1 + 2) * (3 + 4)

У меня есть целые числа, +, * и скобки. Это все, но оно может быть вложено на любую глубину.

В синтаксисе BNF выражение может быть описано следующим образом:

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.

Answer 2

Обходное решение ikegami выше с DEFINE прекрасно, но оно не отвечает на вопрос, как это сделать по-моему. Минимальное изменение моего кода, чтобы заставить его работать? Икегами прав, причина несоответствия - ^ in / ^ $ expr $ /. Когда синтаксический анализатор повторно вводит регулярное выражение рекурсивно, он снова проверяет начало строки, что завершается ошибкой. Так что я не могу иметь ^ и $ в регулярном выражении, кажется. Без них мои строки совпадают. Но тогда некоторые недопустимые строки также совпадают, например, A (1 + 2) * (3 + 4) B. В отсутствие ^ и $ это не обязательно соответствует всей строке. Проблема.

Икегами предложил решение этой проблемы в комментарии выше. Я просто напишу это. Я проверил это, и оно работает:

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

Обратите внимание, что теперь у меня есть (? 1) вместо (? R) и что я заключил $ expr в скобки. (? 1) относится к первой группе захвата, которая ($ expr). Таким образом, рекурсия возвращается в этот подэкс вместо всего регулярного выражения. ^ не встретил снова. Это решает это.