Проблема в том, что вы игнорируете конфликт сдвига / уменьшения, который вы получаете от генератора парсера.В то время как yacc / bison (и предположительно PLY) исправит ошибки за вас, это разрешение может не выполнять то, что вы хотите, и может привести к синтаксическому анализу, который анализирует язык, отличный от того, который вы пытаетесь проанализировать.
Всякий раз, когда вы получаете сдвиг / уменьшение (или уменьшение / уменьшение) конфликт от генератора синтаксического анализатора LR, вам действительно нужно понимать, что такое конфликт (и почему он возникает), чтобы знать, можете ли вы его игнорировать или нужно ли его исправлять,Итак, давайте исправим вашу грамматику, избавившись от «хака» (что явно неправильно, а не того, что вы хотите проанализировать), а также от бесполезного «пустого» правила (которое просто смущает вещи):
%token FILE NUMBER
%%
algebraic_notation : piece start_position capture end_position promotion
piece : 'K' | 'Q' | 'B' | 'N' | 'R' | /*pawn*/
start_position : FILE | NUMBER | FILE NUMBER | /*empty*/
end_position : FILE NUMBER
capture : 'x' | /*empty*/
promotion : '=' 'Q' | '=' 'R' | '=' 'N' | '=' 'B' | /*empty*/
Теперь, когда вы запустите это через 'bison -v' (ВСЕГДА используйте -v для получения подробного выходного файла - я не уверен, что эквивалентен PLY), вы получите сообщение о конфликте сдвига / уменьшения, и есливы смотрите в файле .output
и видите, что это такое:
state 7
1 algebraic_notation: piece . start_position capture end_position promotion
FILE shift, and go to state 9
NUMBER shift, and go to state 10
FILE [reduce using rule 11 (start_position)]
$default reduce using rule 11 (start_position)
start_position go to state 11
Это говорит о том, что после просмотра piece
, когда следующий токен - FILE
, он не знаетдолжен ли он сдвигаться (трактовать FILE
как (часть) start_position
) или уменьшать (давая пустое start_position
).Это потому, что ему нужно больше внимания, чтобы увидеть, есть ли вторая позиция для использования в качестве end_position
, чтобы знать, что делать, поэтому простое игнорирование конфликта приведет к парсеру, который не сможет проанализировать множество допустимых вещей (в основном, что-либо сempty start_position
и capture
).
Лучший способ решить связанный с упреждением конфликт с уменьшением смещения, включающий пустое производство, подобное этому (или практически любой конфликт, связанный с пустым производством, на самом деле), заключается вразобрать грамматику - избавиться от пустого правила и продублировать любое правило, которое использует нетерминал как с таковым, так и без него.В вашем случае это дает вам правила:
algebraic_notation : piece capture end_position promotion
algebraic_notation : piece start_position capture end_position promotion
start_position : FILE | NUMBER | FILE NUMBER
(другие правила не изменены). При этом у вас все еще есть конфликт с уменьшением смены:
state 7
1 algebraic_notation: piece . capture end_position promotion
2 | piece . start_position capture end_position promotion
FILE shift, and go to state 9
NUMBER shift, and go to state 10
'x' shift, and go to state 11
FILE [reduce using rule 14 (capture)]
start_position go to state 12
capture go to state 13
По сути, мыМы только что переместили конфликт на один шаг и теперь имеем проблему с пустым правилом capture
.Таким образом, мы также разглашаем это:
algebraic_notation : piece end_position promotion
algebraic_notation : piece capture end_position promotion
algebraic_notation : piece start_position end_position promotion
algebraic_notation : piece start_position capture end_position promotion
capture : 'x'
, и теперь бизоны не сообщают больше о конфликтах, поэтому мы можем быть достаточно уверены, что они будут анализироваться так, как мы хотим.Вы можете немного упростить его, избавившись от правила capture
и используя литерал 'x'
в правиле algebraic_notation
.Лично я предпочитаю это, так как думаю, что яснее избежать ненужной косвенности:
%token FILE NUMBER
%%
algebraic_notation : piece end_position promotion
algebraic_notation : piece 'x' end_position promotion
algebraic_notation : piece start_position end_position promotion
algebraic_notation : piece start_position 'x' end_position promotion
piece : 'K' | 'Q' | 'B' | 'N' | 'R' | /*pawn*/
start_position : FILE | NUMBER | FILE NUMBER
end_position : FILE NUMBER
promotion : '=' 'Q' | '=' 'R' | '=' 'N' | '=' 'B' | /*empty*/