Предположим, что у меня есть следующая грамматика:
S → X
X → a | ϵ
Если бы эта грамматика не имела бы ϵ, я бы построил первое состояние, например:
S' → .S
S → .X
X → .a
но как насчет символа ϵ? Должен ли я включать:
X → .ϵ
тоже?
Если это так... при создании следующих состояний... должен ли я сделать GOTO(Io,ϵ), будучи первым в этом состоянии?
Так как ϵ не является терминалом, вы должны удалить его из своего правила, которое дает вам
X → .
Затем у вас не будет странного GOTO с символом ϵ, но вместо этого ваше состояние
S' → S.
является принимающим состоянием на вашем графике.
Я согласен с Говардом. Ваше состояние в DFA должно содержать элемент: x → . Здесь DFA я рисовал для парсера SLR (1), который распознает грамматику, в которой используются две эпсилонские постановки: 