Сдвинуть/уменьшить конфликты в грамматике арифметических выражений с n-арными суммами/произведениями

Question

Разбирать двоичные суммы/продукты легко, но у меня возникли проблемы с определением грамматики, которая анализирует

a + b * c + d + e

как

sum(a, prod(b, c), d, e)

Моя первоначальная (наивная) попытка привела к 61 конфликту сдвига/сокращения.

Я использую чашку Java (но я полагаю, что решение для любого другого генератора синтаксического анализатора будет легко переведено).

Answer 1

Следующая грамматика ANTLR:

parse
  :  exp EOF
  ;

exp
  :  add_exp
  ;

add_exp
  :  mul_exp ('+' mul_exp)* 
  ;

mul_exp
  :  atom ('*' atom)* 
  ;

atom
  :  Number
  |  '(' exp ')'
  ;

Number
  :  'a'..'z'
  ;

анализирует ввод a + b * c + d + e как:

альтернативный текст http://img266.imageshack.us/img266/7099/17212574.png

Как вы можете видеть, mul_exp находится дальше всего в дереве и (с использованием соответствующего «прохода» по дереву) будет оцениваться в первую очередь.

и ввод a + b * (c + d) + e анализируется как:

альтернативный текст http://img688.imageshack.us/img688/2207/89332200.png

Изображения были созданы с помощью ANTLRРаботает.

РЕДАКТИРОВАТЬ:

Такой инструмент, как ANTLRРаботает упрощает отладку грамматики!Например, если я нажму на atom Правило в приведенной выше грамматике автоматически генерируется и отображается в нижней части экрана:

альтернативный текст http://img340.imageshack.us/img340/6793/53395907.png

Конечно, это правило совсем не сложное, но когда вы начинаете работать с более сложными правилами, визуализировать их таким образом довольно легко.

ХТХ.