Зубр уменьшить / уменьшить

Question

Я новичок в разборе Bison и не могу понять, как это работает.У меня есть следующая грамматика, где я сохранил минимум для выделения проблемы.

%left '~'
%left '+' 
%token T_VARIABLE
%% 
start: expr;
expr: composite_expr | variable_expr;
variable_expr: T_VARIABLE;
composite_expr:   
     expr '+' expr      
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

%%

Как видите, я хочу применить различные функции к оператору '~' в зависимости от типа выражениячто следует.Однако это приводит к двум конфликтам уменьшения / уменьшения.

Конечно, если я переписываю правило Composite_expr, как это ...

composite_expr:   
     expr '+' expr      
   | '~' expr           { /* ??? */ }
;

... тогда никаких конфликтов нет, но сейчасЯ не могу позвонить либо do_something_1(), либо do_something_2(), потому что больше не могу сказать, является ли expr variable_expr или composite_expr.

Есть ли другой способ, которым я могу это сделать?Кто-нибудь может объяснить, почему там, где в первую очередь уменьшают / уменьшают конфликты?

Имейте в виду, что это урезанная версия, и на самом деле правило composite_expr очень длинное.Так что дублировать это не может быть и речи.

Answer 1

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

В этом случае вы увидите что-то вроде:

state 8

    3 expr: variable_expr .
    6 composite_expr: '~' variable_expr .

    $end      reduce using rule 6 (composite_expr)
    '+'       reduce using rule 3 (expr)
    '+'       [reduce using rule 6 (composite_expr)]
    $default  reduce using rule 3 (expr)

, который говорит вам, что не знает, какое правило уменьшить при прогнозе +. Теперь, очевидно, из ваших правил приоритета вы хотите правило 6 (так как ~ имеет более высокий приоритет, чем +), но правила устранения неоднозначности приоритетов в бизоне - это своего рода хак и не могут с этим справиться - оно не понимает что уменьшение правила 3 ​​приведет к смещению + перед уменьшением правила, которое будет использовать ~.

Так что вы можете с этим поделать? Вы можете принять существование конфликта и упорядочить свои правила, чтобы все происходило правильно. В этом случае вам нужно переместить правило expr: composite_expr | variable_expr в конец (по крайней мере, после правил composite_expr). Это некрасиво, трудно понять и еще труднее поддерживать.

С другой стороны, вы можете разобраться с вещами, чтобы избавиться от единых правил (правила с одним нетерминалом и ничем иным справа - это правила, которые имеют тенденцию вызывать проблемы уменьшения / уменьшения). Что-то вроде:

composite_expr:   
     composite_expr '+' composite_expr
   | composite_expr '+' variable_expr
   | variable_expr '+' composite_expr
   | variable_expr '+' variable_expr
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

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

Лучшая альтернатива, скорее всего, заключается в том, чтобы вообще не делать этого в грамматике, а вместо этого делать выбор на основе ваших семантических правил. Что-то вроде:

expr:   
     expr '+' expr      { $$.isComposite = true; }
   | '~' expr           { if ($2.isComposite)
                              do_something_2();
                          else
                              do_something_1();
                          $$.isComposite = true; }
   | T_VARIABLE         { $$.isComposite = false; }
;

и вы устанавливаете %type для expr как структуру с дополнительным полем bool isComposite вместе со всем, для чего вы его использовали.