Bison сдвиг/свертка конфликт A :: = AA правило

Question

Я написал следующие грамматики Bison файла:

%left '+' '-' 
%left '*' '/' 

%token NUMBER 

%% 

expr 
: NUMBER 
| expr '+' expr 
| expr '-' expr 
| expr '*' expr 
| expr '/' expr 
| expr  expr %prec '*' /* implicit multiplication */ 
; 

Теперь bison отчеты конфликта сдвига/о expr : expr expr. Я извлек проблему следующим минимальным набором:

%left OP 

%% 

expr 
: 'a' 
| expr expr %prec OP 
; 

Я не могу почему bison до сих пор жалуется на сдвиг/свёртка конфликт. Я нашел старый архив почты: Re: bison/yacc: shift/reduce conflict using %prec for composition, но я не понимаю объяснений автора.

Может ли кто-нибудь разъяснить, почему эта грамматика неоднозначна и как разрешить конфликт?

EDIT: NUMBER NUMBER Я имею в виду NUMBER * NUMBER, т. Е. Продукт этих двух чисел.

Answer 1

Проблема заключается в том, что токен NUMBER не имеет приоритета. Поэтому, когда есть состояние, которое может либо сдвинуть NUMBER, либо уменьшить правило (независимо от того, имеет ли это правило преимущество), он не может решить, что делать.

Теперь вы можете это исправить для этой грамматики, добавив приоритет для NUMBER (сделать это так же, как *), но он вернется, если добавить любые правила выражения, которые начинаются с любым маркером, кроме NUMBER - для Например, если вы добавите expr: '(' expr ')', вы получите конфликты сдвига/уменьшения на '('.

Еще большая проблема заключается в том, что вы добавляете унарные префиксные операторы, такие как expr: '-' expr. В этом случае вы не столкнетесь с конфликтом, поскольку «-» уже имеет приоритет, но входной код NUMBER - NUMBER будет разобран как NUMBER (- NUMBER), что, вероятно, совсем не то, что вы хотите. Нет хорошего способа справиться с этой проблемой с правилами приоритета.

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

Answer 2

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

State 8 conflicts: 1 shift/reduce 
State 9 conflicts: 1 shift/reduce 
State 10 conflicts: 1 shift/reduce 
State 11 conflicts: 1 shift/reduce 
State 12 conflicts: 1 shift/reduce 

Grammar 

    0 $accept: expr $end 

    1 expr: NUMBER 
    2  | expr '+' expr 
    3  | expr '-' expr 
    4  | expr '*' expr 
    5  | expr '/' expr 
    6  | expr expr 

Таким образом, в грамматике есть 5 сдвигов/уменьшение конфликтов. Это менее серьезный конфликт; вы можете заявить, что вы ожидаете их с помощью %expect 5 в грамматике, если вы уверены, что то, что делает грамматика, является правильным.

state 0 

    0 $accept: . expr $end 

    NUMBER shift, and go to state 1 

    expr go to state 2 

state 1 

    1 expr: NUMBER . 

    $default reduce using rule 1 (expr) 

state 2 

    0 $accept: expr . $end 
    2 expr: expr . '+' expr 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 

    $end shift, and go to state 3 
    '+'  shift, and go to state 4 
    '-'  shift, and go to state 5 
    '*'  shift, and go to state 6 
    '/'  shift, and go to state 7 
    NUMBER shift, and go to state 1 

    expr go to state 8 

state 3 

    0 $accept: expr $end . 

    $default accept 

state 4 

    2 expr: expr '+' . expr 

    NUMBER shift, and go to state 1 

    expr go to state 9 

Государство 5, 6, 7 mimic state 4, но для других операторов. Государство 8 является первым из государств с конфликтом сдвига/сокращения. Помните, что . (точка) в правилах указывает, где находится синтаксический анализатор, когда он достигает этого состояния.

state 8 

    2 expr: expr . '+' expr 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 
    6  | expr expr . 

    NUMBER shift, and go to state 1 

    NUMBER [reduce using rule 6 (expr)] 
    $default reduce using rule 6 (expr) 

    expr go to state 8 

state 9 

    2 expr: expr . '+' expr 
    2  | expr '+' expr . 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 

    '*'  shift, and go to state 6 
    '/'  shift, and go to state 7 
    NUMBER shift, and go to state 1 

    NUMBER [reduce using rule 2 (expr)] 
    $default reduce using rule 2 (expr) 

    expr go to state 8 

Есть различия и сходство между этими двумя состояниями, но утверждает, 10, 11, 12 матча состояния 9 для другой точки неоднозначности исключения.

Проблема в том, что, когда грамматика видит:

NUMBER OP NUMBER NUMBER 

он не может сказать, является ли разобрать, что, как:

(НОМЕР О.П. номером) выражение выраж

или как:

NUMBER OP (NUMBER NUMBER) 
expr OP  expr 

Учитывая, что это смену/сокращение в каждом случае он выбирает сдвиг. Если это то, что вы хотите, добавьте %expect 5 и продолжайте жизнь. Если это не то, что вы хотите, тогда вам нужно переосмыслить свою грамматику. Что указывает пара соседних номеров, и вы уверены, что вам не нужен какой-либо символ оператора (возможно, запятая или двоеточие), чтобы отделить их?

---

Я попытался поднять приоритет пропавшего оператора с помощью:

%left MISSING 

после других деклараций старшинства, а затем с помощью:

expr expr %prec MISSING 

Это ничего не меняет. Также не делает приоритет MISSING очень низким, перечислив его перед другими операторами.

Вы намёк проблем, если вы считаете, как должен быть проанализирован выражение как это:

NUMBER OP NUMBER NUMBER NUMBER OP NUMBER NUMBER OP NUMBER 

Если ОП одинакова в каждом внешнем виде. Моему мозгу больно! Так и есть bison!