Анализатор LR1 и Epsilon

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) вы бы определили, следует ли сдвигать или уменьшать, используя lookahead (a -> сдвиг, что-нибудь в FOLLOW(A) -> уменьшить)

Смотрите на Статья в Википедии