Парсер LR для epsilon

Question

Недавно я реализовал парсер LR (1) (без эпсилона), и мне было интересно, как бы я реализовал эпсилон в алгоритме парсинга (примечание: не в алгоритме построения таблицы). Это моя грамматика:

start -> A b
b -> B | \epsilon

Я выполнил перечисленные шаги здесь и получил это в результате моего парсера (таблица):

state 0 on symbol start: 1
state 0 on symbol A: shift and goto state 2
state 1 on symbol $: accept
state 2 on symbol b: 3
state 2 on symbol B: shift and goto state 4
state 2 on symbol $: reduce b → 
state 3 on symbol $: reduce start → A b
state 4 on symbol $: reduce b → B

Приведенная выше таблица верна, но когда я пытаюсь разобрать A, перехода нет:

error: no transition in table for (0, 'b')

Вот как выглядит мой стек:

[0]
[0, 'A', 2]
[0, 'b'] # stack during the error

Теперь я обратите внимание, что наверху нет состояния, что является проблемой, но я понятия не имею, что добавить после него. Мой код сопряжения основан на более здесь .

Answer 1

Этот стек определенно неправильный, и кажется вероятным, что он приводит к ошибке (хотя трудно сказать, не видя кода).

Вот что вы ожидаете:

            LOOK
STACK       AHEAD   ACTION
[0]         A       shift, goto state 2    pushes A (shift) and new state (2)
[0 A 2]     $       reduce b ->            pops 0 pairs, pushes b (reduce) 
[0 A 2 b]           + goto 3               action for b in state 2
[0 A 2 b 3] $       reduce start -> A b    pops 2 pairs, pushes start (reduce)
[0 start]           + goto 1               action for start in state 0
[0 start 1] $       accept                 

Если бы мне пришлось делать предположение, я бы сказал, что вы вставляете один символ для правой части ε. Как я уже упоминал в другом месте (включая ответ, который вы цитируете), ε - это ничто . Это ноль символов, и при его появлении ничего не появляется.