Почему эта грамматика не имеет конфликта сокращения/сокращения?

Рассмотрим следующую (по общему признанию бессмысленную — она была значительно упрощена, чтобы проиллюстрировать суть) грамматику:

negationExpression
    : TOK_MINUS constantExpression %prec UNARYOP
    | testRule
    ;

constantExpression
    : TOK_INTEGER_CONSTANT
    | TOK_FLOAT_CONSTANT
    ;

testRule
    : negationExpression constantExpression  // call this Rule 1
    | constantExpression   // Rule 2
    ;

Bison не жалуется на конфликт редукции/редукции при работе с этой грамматикой, но мне кажется, что он есть. Предположим, мы проанализировали negationExpression и constantExpression; мне кажется, что парсер теперь может делать две вещи, основываясь на приведенном выше определении:

  1. Сократите последовательность до testRule, используя Правило 1 выше.
  2. Сократите constantExpression до testRule, используя Правило 2 выше (в этом случае negationExpression останется нетронутым, поэтому стек синтаксического анализа будет выглядеть так: negationExpression testRule)

Однако никаких предупреждений не выдается, и когда я смотрю на файл .output, который генерирует Bison, кажется, что нет никакой двусмысленности:

state 5

    6 testRule: constantExpression .

    $default  reduce using rule 6 (testRule)
...
state 9

    5 testRule: negationExpression constantExpression .

    $default  reduce using rule 5 (testRule)

Согласно документам Bison:

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

Здесь точно не так?


parsing bison reduce-reduce-conflict
person user4520    schedule 10.04.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Нет, сюда не относится.

«Последовательность ввода» — неудачная формулировка; на самом деле имеется в виду «тот же ввод» или, возможно, более явно, «та же подпоследовательность префикса действительного ввода». Другими словами, если есть два или более правил, которые могут применяться ко всему вводу, вплоть до текущей точки чтения (и с учетом просмотра вперед).

В вашей грамматике testRule никогда ничему не следует. Его (и negationExpression ) можно сократить только в самом начале некоторого вывода. Таким образом, если (частично сокращенный) ввод заканчивается на negationExpression constantExpression, невозможно уменьшить constantExpression до testRule, потому что ни один вывод начального символа не может включать testRule в неначальной позиции.

person rici    schedule 10.04.2017