Приоритет оператора с парсером LR(0)

Question

Типичная БНФ, определяющая арифметические операции:

E :- E + T
  |  T
T :- T * F
  |  F
F :- ( E )
  | number

Есть ли способ переписать эту грамматику, чтобы она могла быть реализована с помощью синтаксического анализатора LR(0), при этом сохраняя приоритет и левую ассоциативность операторов? Я думаю, что это могло бы быть возможно, введя некие терминалы для устранения неоднозначности, но я не могу понять, как это сделать.

Спасибо!

Answer 1

Язык может иметь грамматику LR(0) только в том случае, если он не содержит префиксов, то есть ни одна строка в языке не является префиксом другой. В этом случае язык, который вы описываете, не имеет префиксов. Например, строка number + number это префикс number + number + number,

Обычный обходной путь для решения этой проблемы состоит в том, чтобы "поставить точку" на вашем языке, требуя, чтобы все сгенерированные строки заканчивались специальным символом "сделано". Например, вы можете потребовать, чтобы все сгенерированные строки заканчивались точкой с запятой. Если вы сделаете это, вы можете создать синтаксический анализатор LR(0) для языка с этой грамматикой:

S → E;

E → E + T | T

T → T * F | F

F → число | (Е)