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

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

1 голос
/ 18 февраля 2010

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

a + b * c + d + e

в 

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

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

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

1 Ответ

3 голосов
/ 03 мая 2010

Следующая грамматика 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

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

HTH.

...