Однозначная грамматика

Question

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

Answer 1

Мне любопытно, потому что это помечено как рекурсивный спуск, что заставляет меня думать LL.

При создании грамматики для анализатора LL запомните эти правила.

Повторение используется для левой ассоциативности:

Foo -> Bar (op Bar)*

Хвостовая рекурсия используется для правильной ассоциативности:

Foo -> Bar (op Foo)?

Теперь у вас нет LL-дружественной грамматики, потому что вы оставили рекурсию:

E -> E+T

С другой стороны, если бы это был LL, ваше возведение в степень использует хвостовую рекурсию, чтобы это работало.

Я предлагаю статьи Википедии, направленные сверху вниз и Левая рекурсия статей (их легче читать, чем статью LL ) И обратите внимание, парсеры LR работают по-разному и приводят к различным грамматикам для левой и правой ассоциативности.

Да, и ваш порядок правил правильный для того, что LL-парсерам нужно для приоритета. Правила оператора с более низким приоритетом стоят первыми в цепочке производственных правил.

Answer 2

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

expr -> term | expr add term
term -> factor | term mult factor
factor -> number | - factor | ( expr )
add -> + | -
mult -> * | /

Этот пример должен быть намного более читабельным, чтобы вы могли применить его к своей домашней работе. Я пропустил оператор ^, но вы сможете понять это из примера. Если вы хотите купить [другой] учебник, Прагматика языка программирования очень поможет.