SLR (1) Включены парсер и эпсилон

Question

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

S → X  
X → a | ϵ

Если бы эта грамматика не включала ϵ, я бы построил первое состояние как:

S' → .S
S → .X
X → .a

а как же символ ϵ? Должен ли я включить:

X → .ϵ

тоже

Если так ... при создании следующих состояний ... я должен сделать GOTO(Io,ϵ), являясь Io этим первым состоянием?

Answer 1

Я согласен с Говардом.Ваше состояние в DFA должно содержать элемент: x → . Вот DFA, который я нарисовал для парсера SLR (1), который распознает грамматику, использующую два производства epsilon:

Answer 2

Поскольку ϵ не является терминалом, вы должны удалить его из своего правила, которое дает вам

X → .

Тогда позже у вас не будет странного GOTO с "символом" ϵ но вместо этого ваше состояние

S' → S.

является принимающим состоянием на вашем графике.