konvertieren in LL (k) Grammatik

Question

Ich habe versucht, eine Frage für die Praxis zu lösen, aber ich stieß auf ein Problem, als ich versuchte, die Beispielantwort mit meiner zu vergleichen. Hier ist die Grammatik vor der Konvertierung:

E-> S* 
S-> SD 
S-> D 
D-> [D] 
D-> x 

Das Startsymbol ist E und die andere Nicht-Terminal-Symbole sind S und D.

Meine Antwort ist:

E-> S* 
S-> DS' 
S'-> DS' 
S'-> 
D-> [D] 
D-> x 

In der Probe Antwort, sie S-> DS' nicht haben, und E wird E-> DS'*. Aufgrund der im Buch verwendeten Methoden für die linke Rekursion Entfernen

A -> Aa 
A -> b 

=> A -> bA' 
    A' -> aA' 
    A' -> 

soll es ein S-> DS' sein. Ich bin jetzt verwirrt darüber und vielleicht habe ich diese Methode einfach nicht verstanden. Könnte mir jemand dazu einen Hinweis geben? Und könntest du mir bitte auch die Bedeutung des Sternsymbols * hier mitteilen? Danke vielmals!

Answer 1

Es ist nichts falsch mit Ihrer Antwort. Die Beispielantwort vereinfacht einfach die Grammatik nach der Transformation.

E -> S* 
S -> DS' 

Da Regeln für S' und D und unter der Annahme, dass S und E nicht in anderen Produktionen auftreten, ist dieser Teil der Grammatik entspricht

zu

E -> DS'* 

Die S in der ersten Produktion war einfach ersetzt durch DS', wie in der zweiten abgestreiften Produktion definiert.

Das * Symbol ist möglicherweise ein Kleene star. Es bedeutet, dass S beliebig oft auftreten kann (einschließlich Null). Aber ohne Kontext ist es schwer zu sagen, und es könnte auch etwas anderes bedeuten.