Конфликт сдвига / уменьшения бизонов в правиле A :: = AA

Question

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

%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: сдвинуть / уменьшить конфликт, используя% prec для композиции , но я также не понимаю объяснения автора.

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

РЕДАКТИРОВАТЬ: под 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 имитируют состояние 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

он не может определить, нужно ли анализировать это как:

(НОМЕР ОП НОМЕР) НОМЕР expr expr

или как:

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 s!