SLR (1) парсер с эпсилон переходами в грамматике

Question

Я пишу SLR (1) парсер из следующей грамматики:

1) S -> aSb 
2) S -> cB 
3) B -> cB 
4) B -> ε 

Прежде всего, я начал с нахождением связанный LR (0) автомат с расширенной грамматикой, добавляющий S' -> S и начинающий вычислять различные состояния. Я нашел следующие состояния:

I0 = {S '-> • S, S-> • aSb, S-> • cB}
(I0, S) = I1; (I0, a) = I2; (I0, c) = I3;
I1 = {S '-> S •}
I2 = {S-> а • Sb, S> • ASB, S> • сВ}
(I2, S) = I4; (I2, a) = I2; (I2, c) = I3
I3 = {S-> c • B, B-> • cB, B-> • ε}
(I3, B) = I5; (I3, ε) = I6; (I3, c) = I7;
I4 = {S-> aS • b}
(I4, b) = I8;
I5 = {S-> сВ •}
I6 = {В->} & epsi; •
I7 = {В-> с • В, В-> • Cb, В-> • е}
(I7 , B) = I9; (I7, ε) = I6; (I7, c) = I7;
I8 = {S-> ASB •}
I9 = {B-> сВ •}

И здесь есть LR (0) автомат:

Automaton Picture

После этого я сделал таблицу анализатора (но я не думаю, что это необходимо для того, чтобы ответить на мой вопрос), поэтому у меня есть сомнения: - это правильный переход эпсилона? Я имею в виду, я относился к нему как к нормальному персонажу, так как в какой-то момент нам нужно уменьшить правило №4. Если я ошибаюсь, как я должен относиться к этому переходу? Спасибо заранее, надеясь, что это полезно и для других людей.

Answer 1

нет, нет необходимости создавать государство I6

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

вы можете использовать JFLAP Software и увидеть это documentation about SLR(1)