БНФ-грамматика для левых -ассоциативных операторов

У меня есть следующая EBNF грамматика для простых арифметических выражений с левыми -ассоциативными операторами:

expression:
    term {+ term}

term:
    factor {* factor}

factor:
    number
    ( expression )

Как я могу преобразовать это в грамматику BNF без изменения ассоциативности оператора? Следующая БНФ-грамматика у меня не работает, потому что теперь операторы стали право-ассоциативными:

expression:
    term
    term + expression

term:
    factor
    factor * term

factor:
    number
    ( expression )

Википедия говорит:

Several solutions are:

  1. rewrite the grammar to be left recursive, or
  2. rewrite the grammar with more nonterminals to force the correct precedence/associativity, or
  3. if using YACC or Bison, there are operator declarations, %left, %right and %nonassoc, which tell the parser generator which associativity to force.

Но там не сказано, как переписать грамматику, и я не использую никаких инструментов синтаксического анализа, таких как YACC или Bison, только простой рекурсивный спуск. Возможно ли то, о чем я прошу?

7
задан fredoverflow 11 July 2012 в 12:50
поделиться