Недавно я реализовал синтаксический анализатор 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
Теперь я заметил, что сверху нет состояния, что является проблемой, но я понятия не имею, что добавить после него. Мой код паринга основан на приведенном выше здесь.