Как устранить эту левую рекурсию для LL Parser

Question

Как исключить левую рекурсию следующего типа. Кажется, я не могу применить общее правило к этому конкретному.

A -> A | a | b

Используя правило исключения, вы получаете:

A  -> aA' | bA'
A' -> A'  | epsilon

Который еще оставил рекурсию.

Говорит ли это о том, что грамматика является / не является LL(1)?

Спасибо.

Answer 1

Обратите внимание, что правило

A → A

в некотором смысле совершенно бесполезен. Он ничего не делает с деривацией, чтобы применить это правило. В результате мы можем безопасно удалить ее из грамматики, не изменяя ее. Это оставляет

A → a | б

который является LL(1).