сдвиг / уменьшение проблемы перемещения бизонов - PullRequest
Новая
       57

сдвиг / уменьшение проблемы перемещения бизонов

3 голосов
/ 03 октября 2009

Первоначально в примере было это 

expr:
        INTEGER
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        ;

Я хотел, чтобы это было «более просто», поэтому я написал это (я понимаю, что это будет делать «+» как для сложения, так и для вычитания. Но это пример) 

expr:
        INTEGER
        | expr addOp expr           { $$ = $1 + $3; }
        ;

addOp:
          '+' { $$ = $1; }
        | '-' { $$ = $1; }
        ;

Теперь я получаю ошибку сдвига / уменьшения. Это должно быть точно так же -_- (для меня). Что мне нужно сделать, чтобы это исправить?

изменить: чтобы все было понятно. У первого НЕТ предупреждения / ошибки. Я использую% left, чтобы установить приоритет (и я буду использовать% right для = и других правых операций). Однако, похоже, это не относится к подвыражениям.

Ответы [ 2 ]

1 голос
/ 06 октября 2009

Проблема в том, что правило 

expr: expr addOp expr { ..action.. }

не имеет приоритета. Обычно правила получают приоритет первого токена в RHS, но это правило не имеет токенов в своей RHS. Вам нужно добавить директиву% prec к ней: 

expr: expr addOp expr %prec '+' { ..action.. }

, чтобы явно дать правилу приоритет.

Обратите внимание, что это не избавит от конфликта сдвига / уменьшения, который присутствовал в вашей исходной грамматике. Он просто разрешает его в соответствии с указанными вами правилами приоритета, что означает, что бизон не сообщит вам об этом. В целом, использование приоритета для разрешения конфликтов может быть непростым делом, поскольку оно может скрывать конфликты, которые вы, возможно, хотели бы решить по-другому, или они могут быть неразрешимыми в вашей грамматике, как написано.

Также см. Мой ответ на этот вопрос

1 голос
/ 04 октября 2009

Вы уверены, что конфликты включают только эти два правила? Первый должен иметь больше конфликтов, чем второй. По крайней мере, с одним символом прогнозирования решение перейти в состояние со стеком addOp проще во второй раз.

Обновление (Полагаю, я могу доказать свою теорию ...: -): 

$ cat q2.y
%% expr: '1' | expr '+' expr | expr '-' expr;
$ cat q3.y
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';
$ yacc q2.y
conflicts: 4 shift/reduce
$ yacc q3.y
conflicts: 2 shift/reduce

Сказав все это, для грамматик yacc нормально иметь неоднозначности, и любая реальная система, вероятно, будет иметь не только несколько, но буквально десятков конфликтов сдвига / уменьшения. По определению, этот конфликт возникает, когда имеется совершенно корректный доступный сдвиг, поэтому, если вы не возражаете, парсер принимает этот сдвиг, тогда не беспокойтесь об этом.

Теперь, в yacc вы должны предпочесть леворекурсивные правила. Вы можете добиться того, чтобы и избавились от неоднозначности грамматики с помощью: 

$ cat q4.y
%% expr: expr addOp '1' | '1';
  addOp: '+' | '-';
$ yacc q4.y
$

Примечание: в приведенном выше примере нет конфликтов. Если вам нравится ваша грамматика такой, какая она есть, просто сделайте: 

 %expect 2
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';
...