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

Question

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

A -> A | a | b 

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

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

Который до сих пор леворекурсивные.

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

спасибо.

Answer 1

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

→

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

A → a | b

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