Parse::RecDescent: Разбор вложенного арифметического выражения?

Question

В настоящее время я использую это для анализа арифметических выражений:

expr  : '(' expr ')' 
      | number op expr 
      | variable op expr 
      | number
      | variable
      | <error>

Он работает для простых выражений, но не может обрабатывать вложенные выражения в скобках. Любая идея, как расширить / изменить его, чтобы он мог обрабатывать вложенные выражения.

Например это работает:

5 + 12
33 - $var
13 + 2 * $v
( 44 + 98 )

но это не работает

( 44 + 98 ) / 2
( 44 + 98 ) / ( 5 + $var2 )
( 11 + 5 ) * ( 3 + ( $v * 2 ) )

Answer 1

У вашей цепочки приоритетов есть проблема. 1 + (2 + 3) можно разобрать как number op exprс expr на правом существе '(' expr ')', но (1 + 2) + 3 не могу, потому что expr не может появиться слева от op, Конечно, вы не можете добавить его туда напрямую, потому что левая рекурсия запрещена. Что вам нужно сделать, это разбить его как:

expr: term '+' expr
    | term '-' expr
    | term

term: factor '*' term
      | factor '/' term
      | factor

factor: '(' expr ')'
    | number
    | variable
    | <error>

Да, в конце цепочки круглые скобки находятся полностью внизу, что может показаться странным, но в них говорится, что выражение в скобках может появляться везде, где может существовать фактор, и будет оцениваться до того, как оно всплывет. Теперь легко понять, что, поскольку все относится к factorвыражение в скобках может появляться где угодно.

Answer 2

Добавьте правило, чтобы объединить выражение в квадратных скобках с другим выражением, используя инфиксный оператор:

| '(' expr ')' op expr

Между прочим, исходная грамматика не имеет вложенных выражений, а содержит инфиксные выражения, начинающиеся с термина в скобках.

В общем случае решение с помощью пользовательских хоббсов является стандартным подходом к работе с выражениями с инфиксными операторами различного предпочтения. Дополнительным преимуществом является то, что правильный порядок вычисления подвыражений обеспечивается самой грамматикой и не требует обработки дополнительным кодом.

Оставайтесь с этим решением, только если вам не нужен полноценный оценщик выражений (вы наверняка обнаружите, что он вам нужен...).