Wie diese Linke Rekursion für LL Parser zu beseitigen ist

Question

Wie Sie eine linke Rekursion des folgenden Typs beseitigen. Ich kann nicht scheinen, die allgemeine Regel auf diesem besonderen anwenden zu können.

A -> A | a | b 

Durch die Beseitigung Regel erhalten Sie:

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

Welche Rekursion noch verlassen hat.

Sagt dies irgendetwas über die Grammatik, die LL (1) ist/ist?

Vielen Dank.

Answer 1

Beachten Sie, dass die Regel

A → A

ist, in gewissem Sinne völlig nutzlos. Es führt zu keiner Ableitung, um diese Regel anzuwenden. Als Ergebnis können wir es sicher aus der Grammatik entfernen, ohne zu ändern, was die Grammatik produziert. Diese Blätter

A → a | b

was ist LL (1).