зубр сдвиг/свертка проблему перемещения добавить цит в subexpr

Question

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

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

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

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

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

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

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

Answer 1

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

Update (я считаю, что могу доказать свою теорию ... :-):

$ 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: '+' | '-'; 

Answer 2

Проблема заключается в том, что правило

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

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

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

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

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

Также см моего ответа на вопрос this