Счастлив: уменьшить / уменьшить конфликт

Question

Почему это вызывает предупреждение о сокращении / уменьшении конфликта

root : set1 'X'     
     | set2 'X' 'X' 

set1 : 'A'          
     | 'B'             

set2 : 'B'          
     | 'C'  

но следующий в порядке?

root : 'A' 'X'     
     | 'B' 'X'     
     | 'B' 'X' 'X'  
     | 'C' 'X' 'X' 

Answer 1

Разница заключается в том, что в первом случае парсер должен сделать выбор относительно сокращения, прежде чем он увидит, 'X' или два последуют.

Во втором парсер может использовать одно и то же состояние, назовем его BXкогда это видно B и X- оба сдвинуты, а затем, в зависимости от следующего токена, могут сдвинуться (если X), а затем уменьшите 'B' 'X' 'X' править или иным образом уменьшить 'B' 'X' немедленно.

Обратите внимание, что если у них не было одинаковых токенов, сразу послеset1 'X' но set2 'Y'- тогда не будет никаких проблем, потому что заблаговременно сможет дать понять, какое сокращение предпринять.

Вот соответствующие разделы из вывода из bison -v за разоблачение этой проблемы:

Первый случай

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

Предполагая, что мы получаем 'B'Переходим к состоянию 2:

state 2

set1: 'B' .
set2: 'B' .

'X'       reduce using rule 4 (set1)
'X'       [reduce using rule 5 (set2)]
$default  reduce using rule 4 (set1)

Обратите внимание, что мы можем сделать два возможных сокращения: set1 или же set2оба с одним входным токеном. Следовательно, уменьшить / уменьшить; у нас есть только один токен lookahead, и с этой грамматикой единственным токеном может быть 'X'-в любом случае!

Случай два

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4

Предполагая, что мы получаем 'B'Переходим к состоянию 2:

state 2

root: 'B' . 'X'
    | 'B' . 'X' 'X'

'X'  shift, and go to state 6

Хотя у нас есть только один токен упреждения, генератор парсера может создать состояние, в котором он виден 'B' 'X' из-за размещения структуры входа. Следовательно, мы переходим в состояние 6 в любом случае (или в противном случае ошибка;-)):

состояние 6

root: 'B' 'X' .
    | 'B' 'X' . 'X'

'X'  shift, and go to state 9

$default  reduce using rule 2 (root)

Вот где происходит волшебство: если мы видим 'X', мы сдвигаемся и переходим в состояние 9 (где мы уменьшаем), в противном случае мы уменьшаем 'B' 'X' немедленно.

Для полноты вот состояние 9:

state 9

root: 'B' 'X' 'X' .

$default  reduce using rule 3 (root)

Если бы у нас был знак предвкушения, чтобы устранить неоднозначность

С этим примером грамматики:

root: set1 'X'
    | set2 'Y'

set1: 'A'          
    | 'B'             

set2: 'B'          
    | 'C'

Затем мы начинаем:

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

Мы сдвигаемся 'B' и перейти к состоянию 2:

state 2

set1: 'B' .
set2: 'B' .

'Y'       reduce using rule 5 (set2)
$default  reduce using rule 4 (set1)

Итак, это состояние достигается в обоих правилах для set1 а также set2где у нас есть один 'B' токен в стеке. В этом случае, если мы затем увидим 'Y'сокращаем до set2- или в любом другом случае уменьшите до set1,

Тот факт, что это выбрано set1 сокращение по умолчанию может иметь последствия для обработки ошибок.

Приложение по ГЛР

Счастлив и bison или же yacc) создает парсеры LALR(1) по умолчанию, хотя вы можете создать парсер GLR с --glr (или же %glr-parser в вашем bison файл объявлений). Это может разрешить неоднозначности, одновременно пытаясь использовать обе "возможности"; парсер раскошелится и увидит, как далеко он доберется в любом случае.

Это, вероятно, неразумно, если вам это действительно не нужно, вы знаете, что вам это нужно, и знаете, что может случиться, если что-то пойдет не так. Я не уверен, что произойдет, если обе вилки завершатся успешно; с моим ненаучным тестированием, это всегда заканчивалось тем, что я выбирал более длинный анализ.

Лексер хаки

Если вы не хотите использовать GLR, но не хотите существенно реструктурировать свой синтаксический анализатор, вы можете рассмотреть возможность использования хекса лексера для преодоления этой проблемы.

Прямо сейчас у вас есть это:

root : set1 'X'     
     | set2 'X' 'X' 

Вместо этого вы можете испустить токен для одного 'X' персонаж и другой токен для двоих:

root : set1 ONE_X
     | set2 TWO_XS

Это устраняет неоднозначность в пределах одного токена, и в результате получается однозначная грамматика LALR(1).