Если вы этого еще не сделали, запустите bison в форме, подобной bison -r all filename.y
, и посмотрите на дополнительный выходной файл filename.output
.В самом верху это дает мне
State 9 conflicts: 2 reduce/reduce
State 10 conflicts: 2 reduce/reduce
State 14 conflicts: 2 reduce/reduce
State 16 conflicts: 2 reduce/reduce
State 35 conflicts: 5 shift/reduce
State 38 conflicts: 8 shift/reduce
...
Следующий экземпляр 'State 9' -
State 9
10 arithmetic_factor: UNSIGNED_TOK . [$end, CPAREN_TOK, PLUS_TOK, MINUS_TOK, MULT_TOK, DIV_TOK, OR_TOK, AND_TOK, EQ_TOK, GEQ_TOK, LEQ_TOK, NEQ_TOK, MORE_TOK, LESS_TOK]
36 bitwise_factor: UNSIGNED_TOK . [$end, CPAREN_TOK, BIT_OR_TOK, BIT_AND_TOK, BIT_XOR_TOK, BIT_LSH_TOK, BIT_RSH_TOK]
$end reduce using rule 10 (arithmetic_factor)
$end [reduce using rule 36 (bitwise_factor)]
CPAREN_TOK reduce using rule 10 (arithmetic_factor)
CPAREN_TOK [reduce using rule 36 (bitwise_factor)]
BIT_OR_TOK reduce using rule 36 (bitwise_factor)
BIT_AND_TOK reduce using rule 36 (bitwise_factor)
BIT_XOR_TOK reduce using rule 36 (bitwise_factor)
BIT_LSH_TOK reduce using rule 36 (bitwise_factor)
BIT_RSH_TOK reduce using rule 36 (bitwise_factor)
$default reduce using rule 10 (arithmetic_factor)
Этот вывод представляет одно возможное "состояние" в машине состояний, реализующей алгоритм синтаксического анализа.
Сначала есть ряд строк, показывающих возможное положение в грамматическом правиле.Точка (.
) всегда показывает текущую позицию в правиле.Когда точка находится в самом конце правила, зубр может следовать за этим со списком в [
квадратных скобках ]
всех терминальных токенов, которые могут быть действительными сразу после нетерминального символа, полученного из правила.
Далее есть таблица действий, которые парсер будет выполнять, учитывая текущее состояние и следующий токен во входном потоке.Конфликты отображаются в виде нескольких записей для одного и того же токена с действиями после первого в [
квадратных скобках ]
(для указания того, что действие будет допустимым с учетом неоднозначной грамматики, но синтаксический анализатор фактически никогда не выполнит это действие).
Таким образом, в выводе State 9 мы видим, что проблема в том, что когда за токеном UNSIGNED_TOK
следует конец ввода парсера или токен CPAREN_TOK
, bison не может определить, является ли числодолжно быть arithmetic_factor
или bitwise_factor
.Что касается конца ввода, возможно, это не имеет большого значения, и проблему можно избежать, если возиться с корневым нетерминалом.Но закрытые скобки - это проблема.Поскольку бизон (по умолчанию) использует грамматику LALR (1) , после обработки первых двух токенов в тексте ( 0u )
, анализатор должен решить, что делать с 0u
, используя только один просмотртокен )
.Но если он решит сделать его arithmetic_factor
и ввести ( 0u ) & 1u
, это неправильно;если он решает сделать его bitwise_factor
, а вводить - ( 0u ) + 1u
, это неправильно.
Чтобы исправить подобные проблемы, часто полезно рассматривать грамматические правила в терминах семантических действий (даже вслучаи, когда грамматика используется только для того, чтобы определить, является ли ввод действительным или нет, и не будет никаких семантических действий).Какое действие должен предпринять переводчик для выражения ( 0u )
?В идеале, вообще ничего: выражение должно иметь то же представление и эффект, что и просто 0u
.Это помещает его в категорию, отличную от составных арифметических выражений и составных побитовых выражений, поскольку они имеют более ограниченное использование (по крайней мере, в показанной грамматике).
Но если мы хотим сказать, например, ( 0u )
НЕ arithmetic_expression
, похоже, мы могли бы пойти к нелепому количеству правил для arithmetic_expression
для перечисления перекрестных произведений всех допустимых типов операндов.Мы можем избежать этого, используя правило для arithmetic_operand
, которое анализатор будет использовать только для подвыражения фактического арифметического оператора (не включая скобки).Чтобы разрешить несколько операторов, любой arithmetic_expression
также может быть использован как arithmetic_operand
.
Итак, вот версия вашей грамматики (после тех же объявлений токенов) без конфликтов приведения-уменьшения:
%%
expression
: int_constant
| float_constant
| bool_constant
| string_constant
| exponent_constant
| symbol_parens
| arithmetic_expression
| boolean_expression
| bitwise_expression
;
compound_symbol
: SYMBOL_TOK
| compound_symbol DOT_TOK SYMBOL_TOK
;
symbol_parens
: compound_symbol
| OPAREN_TOK symbol_parens CPAREN_TOK
;
int_constant
: INTEGER_TOK
| UNSIGNED_TOK
| OPAREN_TOK int_constant CPAREN_TOK
;
float_constant
: FLOAT_TOK
| OPAREN_TOK float_constant CPAREN_TOK
;
bool_constant
: TRUE_TOK
| FALSE_TOK
| OPAREN_TOK bool_constant CPAREN_TOK
;
string_constant
: STRING_TOK
| OPAREN_TOK string_constant CPAREN_TOK
;
exponent_operand
: FLOATING_TOK
| INTEGER_TOK
;
exponent_constant
: exponent_operand CARAT_TOK exponent_operand
| OPAREN_TOK exponent_constant CPAREN_TOK
;
arithmetic_operand
: int_constant
| float_constant
| exponent_constant
| symbol_parens
| arithmetic_expression
;
arithmetic_expression
: arithmetic_operand PLUS_TOK arithmetic_operand
| arithmetic_operand MINUS_TOK arithmetic_operand
| arithmetic_operand MULT_TOK arithmetic_operand
| arithmetic_operand DIV_TOK arithmetic_operand
| MINUS_TOK arithmetic_operand %prec NEGATION
| OPAREN_TOK arithmetic_expression CPAREN_TOK
;
boolean_operand
: bool_constant
| int_constant
| float_constant
| exponent_constant
| string_constant
| symbol_parens
| boolean_expression
;
boolean_expression
: boolean_operand OR_TOK boolean_operand
| boolean_operand AND_TOK boolean_operand
| boolean_operand EQ_TOK boolean_operand
| boolean_operand NEQ_TOK boolean_operand
| boolean_operand LEQ_TOK boolean_operand
| boolean_operand GEQ_TOK boolean_operand
| boolean_operand MORE_TOK boolean_operand
| boolean_operand LESS_TOK boolean_operand
| NOT_TOK boolean_operand
| OPAREN_TOK boolean_expression CPAREN_TOK
;
bitwise_operand
: int_constant
| symbol_parens
| bitwise_expression
;
bitwise_expression
: bitwise_operand BIT_AND_TOK bitwise_operand
| bitwise_operand BIT_OR_TOK bitwise_operand
| bitwise_operand BIT_XOR_TOK bitwise_operand
| bitwise_operand BIT_LSH_TOK bitwise_operand
| bitwise_operand BIT_RSH_TOK bitwise_operand
| BIT_NOT_TOK bitwise_operand
| OPAREN_TOK bitwise_expression CPAREN_TOK
;
%%
102 конфликта сдвига-уменьшения все еще присутствуют, но все они могут быть решены путем указания приоритета и ассоциативности для операторов в правилах boolean_expression
и bitwise_expression
.
Одно замечание:Возможно, это было непреднамеренно, но ваша грамматика не позволяет смешивать операторы из разных «категорий».Например, входные данные (1 + 2 < 4)
и (5 & 6 == 4)
недопустимы.