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

Я пытаюсь понять, как работают синтаксические анализаторы 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 принимающим?

Любая помощь будет действительно оценена!


person Chris    schedule 28.01.2009    source источник
comment
Ни за что. Все еще не верю, что нашел этот вопрос в Stack Overflow ;) Итак, в следующий раз, когда вы примените функцию Goto, вы сделаете Goto(Io, \epsilon), где Io это первое состояние?   -  person Oscar Mederos    schedule 28.06.2011


Ответы (2)


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

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

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

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

person jpalecek    schedule 28.01.2009
comment
Вы говорите, что A->.\epsilon нет в I0? - person alhelal; 07.04.2018

Вы можете использовать этот сайт для вычисления этого: https://cyberzhg.github.io/toolbox/lr1

Посмотрите результаты:

введите здесь описание изображения

person Rea Haas    schedule 04.02.2021