Преврати грамматику в грамматику LL1

Question

Я готовлюсь к экзамену завтра и собираюсь пройти экзамен за предыдущие годы.

В тесте была грамматика.

Expression -> Foo "+" Bar "end"
Foo -> [a-z0-9]+ | Expression
Bar -> Expression Foo | a*b*c+

Я пытался и часами изучал, как это сделать, но не могу понять.

Я смотрел на замену вещей на epsilion и тому подобное, но не чувствую уверенности.

Я думаю, что мне нужно создать Foo 'и Bar', а затем просто добавить в правила epsilon, но я не уверен.

Может кто-нибудь показать мне (просто) _ как изменить ее на LL (1) способную грамматику

Заранее спасибо

Answer 1

Насколько я помню, LL-1 грамматика смотрит в будущее на 1 символ.Ваша цель устранить двусмысленность и оставить рекурсию.Все что вам нужно - используйте левую факторизацию.Сначала посмотрите .