SLR (1) парсер с эпсилон

Question

давайте предположим, что у меня есть следующая грамматика:

E -> ТХ

T -> (E) | int Y

X -> + E | ε

Y -> * T | ε

Построение множества запись я получаю состояние, как это:

T -> Int. Y

Y ->. * T

Y ->.

Это состояние адекватное или нет? То есть, грамматика SLR (1) или нет? Спасибо

Answer 1

Вы должны построить наборы FOLLOW и посмотреть, содержит ли FOLLOW (Y) int или *. если бы это было так, возник бы конфликт смены/сокращения, и грамматика не была бы зеркальной (1). проверьте все состояния, и если ни один из них не имеет конфликтов, грамматика является SLR (1).

Answer 2

Да, данные, указанные вами в государстве, абсолютно правильные.

T->int.Y 
    Y->.*T 
    Y->. 

Это 5-ое состояние в DFA, созданное для парсера SLR (1) для данной грамматики.

Возможно, возникла путаница в Y->Ɛ. Когда вы размещаете точку в расширенных продуктах, например S->A.B, это означает, что A завершен, а B еще не завершен (по завершении здесь означает прогресс в разборе). Точно так же, если вы пишете Y->.Ɛ, это означает, что ɛ пока не будет, но мы также знаем, что ɛ является пустая строка т.е. ничего поэтому Y->.Ɛ интерпретируется как Y->.

Я создал DFA (13 государств) для этой грамматики и обнаружили, что данная грамматика является SLR (1), поскольку нет конфликтов уменьшения-уменьшения или сдвига-уменьшения.