В интересах любого, кто читает этот вопрос и ответ, возможно, полезно знать, что токен + в вопросе предназначен для оператора предварительного увеличения ++. Согласно комментарию, изменение было внесено во избежание необходимости введения декларации токена. Ниже я позволил себе сменить '+' на синтаксис Bison "++", потому что я думаю, что это менее запутанно использовать обычное написание предполагаемого оператора. Я также использовал расширение цитируемых токенов Bison, потому что оно более читабельно. (Но это тривиально, чтобы удалить.)
Конфликт возникает потому, что на самом деле существует действительный синтаксический анализ, который использует rvalue: lvalue продукцию. В частности, вход
++ x [ x ]
может быть проанализирован вашей грамматикой двумя способами:
rvalue rvalue
/ \ |
"++" lvalue lvalue
/--------------\ /------------------\
rvalue '[' rvalue ']' rvalue '[' rvalue ']'
| | / \ |
lvalue lvalue "++" lvalue lvalue
| | | |
'x' 'x' 'x' 'x'
Обратите внимание, что первым является требуемый анализ; индексный оператор связывается более тесно, чем префиксный оператор приращения, так что ++x[x] правильно анализируется как ++ (x[x]). Довольно хорошо все языки обрабатывают постфиксные операторы таким образом, что соответствует ожидаемому поведению. (Подавляющее большинство программистов ожидают, что -x[3] сначала извлечет элемент 3 массива x, а затем отрицает его. Привязка -x сначала не имеет никакого смысла. Это не менее верно для ++; если x - это массив, ++x имеет такой же смысл, как и -x.)
Это противоречит вашему утверждению о том, что следует выбирать «уменьшить 1»; правильный анализ требует, чтобы было взято «уменьшить 2». Эта ошибка также отражена в вашем объявлении о приоритете, которое логически должно давать приоритет справа-ассоциативно постфиксным операторам:
%right "++" '['
(Технически префиксные операторы связываются менее плотно, чем постфиксные операторы. Но для них нормально разделять уровень приоритета из-за правильной ассоциативности.)
Но нет никакого смысла вносить это изменение, потому что объявления приоритетов не могут разрешать конфликты уменьшения / уменьшения, потому что разрешение по приоритету всегда включает сравнение между приоритетом production , который может быть уменьшен, и приоритетом Смотритель токен , который может быть сдвинут. (Другими словами, типы сравниваемых вещей разные.)
В состоянии 6 (воспроизведено в вопросе) синтаксический анализатор сместил "++", а затем 'x' и затем принудительно уменьшил 'x' до lvalue. Таким образом, стек синтаксического анализатора равен ... "++" lvalue, а токен предпросмотра - [. Если грамматика не пыталась разделить lvalue и rvalues (так, чтобы вершина стека была просто value вместо lvalue), то варианты, доступные для синтаксического анализатора, должны были бы уменьшить "++" value до value, или сдвинуть [ при подготовке к правой стороне value '[' value ']'. С указанным выше объявлением уровня приоритета сдвиг выиграет из-за правой ассоциативности, поэтому появится правильный анализ.
Но грамматика пытается различить lvalue и rvalues, и это делает невозможным сдвиг парсера [; чтобы [ был действительным, он должен сначала уменьшить lvalue до rvalue. Решения о приоритете, однако, всегда являются немедленными; синтаксический анализатор на самом деле не видит сокращение rvalue: lvalue как прелюдию к сдвигу [. То, что он видит, - это два конкурирующих действия по сокращению, и приоритет не относится к таким конфликтам.
Поскольку объявления приоритетов не помогут в этом конкретном конфликте, проще всего не пытаться использовать их для унарных операторов, зарезервировав их использование для бинарных операторов. (Также было бы возможно вообще их не использовать, но они удобны для выражения двоичного приоритета.) Справочное руководство B [Примечание 1] поясняет, что описательный текст, а не включенная грамматика, это то, что точно определяет приоритет оператора и ассоциативность, и повествовательный текст включает в себя две синтаксические категории: Первичные выражения и Унарные выражения , которые не появляются в грамматике, но на самом деле синтаксически необходимо.
Легко написать грамматику, используя эти нетерминалы, если мы игнорируем различие lvalue / rvalue, так что это хорошее место для начала. (Примечание: я переместил операторы пост-инкремента / декремента в primary, чтобы не полагаться на объявления приоритетов.)
%token NAME CONSTANT
%token INC "++" DEC "--"
%left '+' '-'
%left '*' '/' '%'
%start value
%%
primary : NAME
| primary '[' value ']'
| CONSTANT
| '(' value ')'
| primary "++"
| primary "--"
unary : primary
| '*' unary
| '-' unary
| '&' unary
| "++" unary
| "--" unary
value : unary
| value '+' value
| value '-' value
| value '*' value
| value '/' value
| value '%' value
Теперь мы можем видеть, что есть два разных нетерминала, которые нужно разделить на варианты l и r , так как и primary, и unary могут выдавать lvalue , (x[x] и *x, соответственно.) Однако это не так просто, как просто разделить оба этих нетерминала на две категории из-за каскада:
value : unary
unary : primary
в сочетании с желаемым неявным приведением lvalues к rvalue.
Нашей первой мыслью может быть просто разделить нетерминалы, позволяя каскаду проходить через rvalue: lvalue постановки:
value : runary
runary : lunary
| rprimary
lunary : lprimary
rprimary: lprimary
К сожалению, это приводит к двум различным путям достижения lprimary:
value -> runary -> lunary -> lprimary
value -> runary -> rprimary -> lprimary
Так как каскадные производства не имеют связанного действия, и преобразование lvalue в rvalue (операция разыменования) одинаково для обоих экземпляров, для нас фактически не имеет значения, какой из этих путей выбран. Но парсер будет заботиться, поэтому мы должны устранить один из них. Вот одно из возможных решений:
%token NAME CONSTANT
%token INC "++" DEC "--"
%left '+' '-'
%left '*' '/' '%'
%start value
%%
lprimary: NAME
| primary '[' value ']'
primary : lprimary
| rprimary
rprimary: CONSTANT
| '(' value ')'
| lprimary "++"
| lprimary "--"
lunary : lprimary
| '*' runary
runary : lunary
| rprimary
| '-' runary
| '&' runary
| "++" lunary
| "--" lunary
value : runary
| value '+' value
| value '-' value
| value '*' value
| value '/' value
| value '%' value