Comment éliminer cette récursion gauche pour LL Parser

Question

Comment éliminer une récursion gauche du type suivant. Je n'arrive pas à appliquer la règle générale à ce sujet particulier.

A -> A | a | b 

En utilisant la règle d'élimination vous obtenez:

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

qui a encore laissé récursivité.

Est-ce que cela dit quelque chose à propos de la grammaire étant/n'étant pas LL (1)?

Merci.

Answer 1

Notez que la règle

A → A

est, dans un sens, tout à fait inutile. Il ne fait rien à une dérivation pour appliquer cette règle. En conséquence, nous pouvons l'enlever en toute sécurité de la grammaire sans changer ce que la grammaire produit. Cela laisse

A → a | b

qui est LL (1).