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

Question

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

a + b * c + d + e

как

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

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

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

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

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

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

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

http://img340.imageshack.us/img340/6793/53395907.png

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

НТН.