Парсер LR1 и Эпсилон

Question

Я пытаюсь понять, как работают парсеры LR1, но у меня возникла странная проблема: что если грамматика содержит эпсилоны? Например: если у меня есть грамматика:

S -> A
A -> a A | B
B -> a

Понятно, с чего начать:

S -> .A
A -> .a A 
A -> .B

... и т. Д.

но я не знаю, как это сделать для такой грамматики:

S -> A
A -> a A a | \epsilon

Правильно ли делать:

S -> .A
A -> .a A a
( A -> .\epsilon )

А затем сделать это государство в DFA принятия?

Любая помощь будет принята с благодарностью!

Answer 1

Да, именно так (представьте, что эпсилон - это пустое пространство, в котором нет двух точек для точки по бокам).

В автомате LR (0) вы могли бы принять состояние и уменьшить его до A. Однако из-за производства A->a A a возник бы конфликт сдвига / уменьшения.

В автомате LR (1) вы определяете, сдвигать или уменьшать, используя прогноз (a -> shift, что-нибудь в FOLLOW(A) -> уменьшение)

См. Статью Википедии