SLR (1) путаница

Question

S → ( S ) S
|   .

на основании определения 0, 2 и 4 имеют конфликт сдвиг / уменьшение. Следующий набор S - это ")". Для SLR(1) в состоянии 2 "(" не входит в следующий набор S, но почему это SLR (1)? Можете ли вы также объяснить правило конфликта сдвига / уменьшения для slr(1), я мог бы запутался на чем-то.

Answer 1

Давайте начнем с вашей грамматики:

S → (S) S | ε

Чтобы создать синтаксический анализатор SLR(1) для этой грамматики, нам нужно дополнить ее новым правилом запуска:

Старт → S

S → (S) S | ε

Обратите внимание, что FOLLOW(S) содержит ) и $ и никаких других символов.

Теперь мы можем начать строить автомат SLR(1), построив автомат LR(0) и увеличивая каждое производство с помощью набора FOLLOW:

(0)
Start -> .S      [$]
    S -> .(S)S   [$)]
    S -> .       [$)]

(1)
Start -> S.      [$]

(2)
    S -> (.S)S   [$)]
    S -> .(S)S   [$)]
    S -> .       [$)]

(3)
    S -> (S.)S   [$)]

(4)
    S -> (S).S   [$)]
    S -> .(S)S   [$)]
    S -> .       [$)]

(5)
    S -> (S)S.   [$)]

Вы утверждали, что состояния 0, 2 и 4 имеют конфликты сдвиг / уменьшение, но на самом деле я не думаю, что это так. В состоянии (0) у нас есть завершенный элемент S → ., Но ожидаем $ и). Это означает, что мы уменьшаем только на $ а). С другой стороны, единственное действие сдвига здесь происходит на символе (.

Если бы здесь не было заглядываний, у нас был бы конфликт сдвига / уменьшения, но из-за предвидений мы знаем, что сдвигается, если мы видим (и уменьшаем, если видим) или $. Если вы проверите другие помеченные вами состояния, вы увидите, что применяется та же логика.

В результате эта грамматика действительно является SLR(1).