Recursive Decent Parser: Rekursionsanker?

[freakC++]

Oh! Das wusste ich gar nicht. Dann hoffe ich mal, dass die Konvertierung nicht kompliziert ist. Ich habe da bereits etwas gefunden.

Viele Grüße und danke
freakC++

[freakC++]

Hallo,

da bin ich noch einmal. Ich die Grammatik in eine rechtsrekursive unmgeschrieben und sie nun nach obigem Schema implementiert. Ich gehe den in der lexikalischen Analyse erstellten Tokenstream von links nach rechts durch.

Nun habe ich folgendes Problem. Mein Parser funktioniert einwandfrei, solange nur ein abzuleitender Ausdruck eingegeben wurde.

Seien a und b in meiner Grammatik ableitbar und auch a & b. Dann gibt mein Parser jedoch nach der erfolgreichen Prüfung von a grünes Licht. Er schaut sich also b gar nicht mehr an. Stellt man sich das alles als Baum vor, so wird nur ein Teilbaum geprüft.

Kann mir jemand sagen, wie man dieses Problem beheben kann? Mir fällt da auf Anhieb nichts Schlaues ein.

Wie kann ich den ganzen Ausdruck parsen und nicht nur einen Teilbaum?

Vielen Dank
LG, freakC++

[Gast]

Nehmen wir mal eine einfache Grammatik für Deine Teilsprache:
A -> A & A
A -> id

A ist ein Nichtterminal. & Dein "Und"-Symbol und id ein Identifier (a oder b zum Beispiel).

Problem: Nicht eindeutig.

Lösung:
A -> A & B | B
B -> id

Damit sind die Parsebäume eindeutig.

Aber Problem: Linksrekursiv -> Nicht geeignet für LL(1)-Parser.

Lösung, Linksrekursion Eliminieren.

Für eine allgemeine Linksrekursive Grammatik der Form
A -> A alpha | beta

(mit irgendwelchen Symbolketten alpha und beta)

ist die eliminierte Form:
A -> beta C
C -> alpha C | epsilon

In Deinem Beispiel ist
alpha identisch mit & B
und
beta identisch mit B

Das gibt
A -> B C
C -> & B C | epsilon
B -> id
für ein neu einzuführendes Nichtterminal C

Dein Parser bricht also nach einem ersten Symbol ab.
Das kann aber garnicht vorkommen, wenn du die Eliminierung korrekt vorgenommen und den Parser richtig gebaut hast.
Warum? Schau wie ein id & id abgeleitet wird:

A => B C => id C

An dieser Stelle könnte C nur dann zu Epsilon abgeleitet werden, wenn kein Token mehr im Eingabestrom ist. Aber da ist definitiv noch ein &.
Deshalb geht die Ableitung weiter mit:
=> id & B C => id & id C => id & id

Anmerkung: Eine derart umgebaute Grammatik macht den Aufbau eines Syntaxbaumes etwas Schwieriger. Ein weiterer Grund warum Du Dir bei Gelegenheit mal LR-Parser anschauen solltest
Nochwas: Die eingeführte Linksrekursion (um die Grammatik eingeutig zu machen)deshalb, weil man häufig linksassoziative Operatoren will und ständig auf dieses Problem stößt.

[freakC++]

Hallo µ,

danke für deine ausführliche Antwort.

µ schrieb:

Dein Parser bricht also nach einem ersten Symbol ab.
Das kann aber garnicht vorkommen, wenn du die Eliminierung korrekt vorgenommen und den Parser richtig gebaut hast.

Daraus schließe ich, dass ich schlichtweg einen Fehler in meiner Grammatik habe. Meine Vorgehensweise passt jedoch zu deiner und daher würde ich freuen, wenn ihr euch mal meine Eleminierung anschaut:

Ein Teil der Ursprungsgrammatik lautet:

A → A | B
A → B
B → B & E
B → E

Dabei sind A, B und C Nichtterminale. Durch die Eleminierung der Linkrekursion habe ich zuerst Epsilon-Produktionen erzeugt, die ich dann jedoch ebenfalls wieder elemeniert habe. Ich komme auf folgende Grammatik:

A -> B A
A -> B
B -> E D
B -> E

C -> | and_term C
C -> | and_term

D -> & E D
D -> & E

Damit erhalte ich jedoch das oben angesprochene Problem. Ich sehe hier nicht den Unterschied zu deiner Grammatikanpassung.

Kannst Du mir helfen?

[freakC++]

oder gibt es da etwa noch ein Problem mit der Eindeutigkeit?

[freakC++]

Ich muss noch anmerken, dass das "|" Symbol nichts mit der Backus-Naur-Form zu tun hat, sondern ein Terminalsysmbol ist.

µ schrieb:

Nehmen wir mal eine einfache Grammatik für Deine Teilsprache:
A -> A & A
A -> id

A ist ein Nichtterminal. & Dein "Und"-Symbol und id ein Identifier (a oder b zum Beispiel).

Problem: Nicht eindeutig.

Lösung:
A -> A & B | B
B -> id

Damit sind die Parsebäume eindeutig.

Ich vermute also sehr stark, dass meine Grammatik zwar nicht mehr linksrekursiv ist, aber dafür nicht eindeutig. Doch leider weiß ich nicht, wie ich meine Grammatik in eine eindeutige umwandeln soll. Warum ist deine zweite eindeutig?

Ich nehme jetzt mal an, dass bei dir "|" zur Backus-Naur-Form gehört. Deine zweite, eindeutige Grammatik lautet also:

A -> A & B
A -> B
B -> id

Warum ist die eindeutig und die erste nicht?

Vielen Dank
LG, freakC++ :xmas1:

[ipsec]

freakC++ schrieb:

Warum ist die eindeutig und die erste nicht?

Folgendes Wort: id & id & id
kann bei der ersten Grammatik auf zwei Arten geparst werden.
1. A(A(A(id) & A(id)) & A(id))
2. A(A(id) & A(A(id) & A(id)))
(wird hoffentlich deutlich)

Mit der zweiten Grammatik gibt es nur eine Möglichkeit:
A(A(A(B(id)) & B(id)) & B(id))

[pumuckl]

Wie viele Symbole peekst du? Bei

A -> B A
A -> B
B -> E D
B -> E

musst du wenn du B gematcht hast schauen ob danach noch ein A kommt oder ob es nur das B war. Sonst wird dein Parser beispielsweise die zweite Produktion für B matchen und ein D was evtl. noch dahinter im Stream liegt verhungert.

[Bashar]

pumuckl, das Problem kann man durch Linksfaktorisierung lösen, man muss nicht das Lookahead erhöhen:

A -> B A?
A? -> A
A? -> ε
B -> E D?
B? -> E
B? -> ε

[freakC++]

Das von pumuckl angesprochene Problem könnte (hoffentlich) die Lösung zu meinem Problem sein. Laut Bashar kann dieses durch Linksfaktorisierung behoben werden. Dabei kommen jedoch epsilon-Produktionen wieder in die Grammatik, die ich allesamt bei Behebung der Linksrekursion eleminiert habe.

Sind epsilon-Produktionen schlecht? Eigentlich handelt es sich dabei ja nur um eine Funktion, die true zurückgibt. Man könnte sie bei der Implementierung also einfach weglassen?!

LG, freakC++

[pumuckl]

Weglassen nicht ganz, der Unterschied mit/ohne Epsilon ist im Grunde folgender:

gegeben:
X -> Y
P -> Q
P -> ε

(pseudocode)

X: match Y else false
P: match Q else true

[freakC++]

Ok, alles klar! Nachdem ich also nun Linksrekursion entfernt und die damit entsehenden epsilon-Produktionen entfernt und schließlich noch wie Bashar gezeigt hat, linksfakotrisiert habe (damit kamen jedoch wieder epsilon-Produktionen rein), konnte ich noch keinen befriedigenden Status erreichen.

Daher schaue ich mir die aktuelle Tokenposition an und machte folgende interessante Beobachtung.

Meine Grammatik akzeptiere wieder a & b, wobei bereits sowohl a als auch b akzeptiert werden. Ich prüfe nun den Ausdruck a & b.

- Falls in a ein syntaktischer Fehler vorhanden ist, so reicht meine Grammatik nach dem anfangs geposteten Muster false durch und ich fange den Fehler erfolgreich ab.

- Falls in b ein Fehler ist, reicht meine Grammatik leider ein true durch, sodass ich dadurch nicht den Syntaxfehler merke. Mein aktuelles Token bleibt jedoch am Ende von a stehen.

Ich könnte also einfach abfragen, ob die aktuelle Tokenposition am Ende der Eingabe liegt. Doch das wäre irgendwie geschummelt.

Wisst ihr, warum kein false zurückgegeben wird?

Vielen Dank
LG, freakC++

edit: Ich habe mir jetzt in jedem Rekursionsschritt die aktuelle Tokenposition angeschaut. Dabei fällt auf, dass diese bei einem syntaktisch korrektem Ausdruck bis ans Ende des Tokenstreams geht, dann wieder auf 0 und noch einmal wieder ans Ende...

[Gast]

freakC++ schrieb:

Dabei kommen jedoch epsilon-Produktionen wieder in die Grammatik, die ich allesamt bei Behebung der Linksrekursion eleminiert habe.

Sind epsilon-Produktionen schlecht? Eigentlich handelt es sich dabei ja nur um eine Funktion, die true zurückgibt. Man könnte sie bei der Implementierung also einfach weglassen?!

Moment mal. Durch Eliminierung der Linksrekursion (nach dem oben von mir geposteten Schema) wird sogar eine Epsilon-Produktion eingeführt. Es ist nicht Sinn der Eliminierung, irgendwelche Epsilon-Produktionen zu entfernen.
Und Epsilon-Produktionen sind natürlich nichts "Schlechtes". Du darfst sie nicht einfach weglassen, ohne die Sprache der Grammatik zu ändern.
Schau nochmal oben wie ich den Term abgeleitet hatte, die letzten Schritte:
id & id C => id & id
Ohne die Produktion C -> Epsilon wäre das garnicht möglich.

[freakC++]

aber durch Epsilon-Produktionen, die durch die Eleminierung einer Linksrekursion entstehen, können versteckte Linksrekursionen wieder hinzukommen. Deswegen habe ich sie eliminiert.

siehe hier:

tagh.de/tom/wp-content/uploads/Linkrekursion.pdf

Ist es denn legitim, einfach zu prüfen, ob die aktuelle Tokenposition auf das Ende des Tokenstreams zeigt?

Vielen Dank
LG, freakC++

[Gast]

freakC++ schrieb:

aber durch Epsilon-Produktionen, die durch die Eleminierung einer Linksrekursion entstehen, können versteckte Linksrekursionen wieder hinzukommen. Deswegen habe ich sie eliminiert.

Die Epsilons die durch das Ersetzungsschema eingeführt werden, führen ihrerseits natürlich keine erneute Linksrekursion ein. Sonst wäre das ja komplett sinnlos.

freakC++ schrieb:

Ist es denn legitim, einfach zu prüfen, ob die aktuelle Tokenposition auf das Ende des Tokenstreams zeigt?

Nein! Es kann natürlich vorkommen, dass eine Produktion der Form C->Eps irgendwo in der Mitte einer Ableitung angewendet werden muss. Wenn Du Epsilonproduktionen einfach ignorierst, veränderst Du die Sprache. Das obige Schema erhält die Sprache. Du darfst nicht einfach Produktionen streichen.

[freakC++]

Da die Linksfaktorierung nichts gebracht hat, arbeite ich nun mit der Grammatik ohne Epsilon-Produktionen. Damit müsste es dann aber legitim sein, zu prüfen, ob man am Ende des Tokenstreams angekommen ist. Alle Tests funktionieren jedenfalls sehr gut. Aus irgendeinem (traurigen) Grund funktioniert das Durchreichen eines false-Wertes ja nicht, sobald b des Ausdruckes a & b syntaktisch falsch ist und a und b selbst akzeptiert werden.

µ schrieb:

Sonst wäre das ja komplett sinnlos.

Was sagst Du denn zu dieser Grammatik, deren Linksrekursion entfernt wurde? Durch die Epsilon-Produktion kann diese versteckt auftreten, sodass Epsilon-Produktionen entfernt werden müssen.

A -> BAbb | a
B -> epsilon

Vielen Dank für deine Hilfe!!
LG, freakC++

[pumuckl]

freakC++ schrieb:

Was sagst Du denn zu dieser Grammatik, deren Linksrekursion entfernt wurde? Durch die Epsilon-Produktion kann diese versteckt auftreten, sodass Epsilon-Produktionen entfernt werden müssen.

A -> BAbb | a
B -> epsilon

Bei der Grammatik ist B ja nunmal völlig überflüssig, da es nur die Epsilon-Produktion ist. Damit kannst du B komplett rausnehmen und hast wieder eine linksrekursive Grammatik.

Zeig uns am Besten immer die vollständigen Produktionen, sonst kann man nur schwer verlässliche Aussagen treffen.

[Gast]

freakC++ schrieb:

Was sagst Du denn zu dieser Grammatik, deren Linksrekursion entfernt wurde? Durch die Epsilon-Produktion kann diese versteckt auftreten, sodass Epsilon-Produktionen entfernt werden müssen.

A -> BAbb | a
B -> epsilon

Das ist ein konstruiertes Beispiel, indem die Rekursion eben nicht entfernt wurde. Du hast gesagt: Durch die Eliminierung werden neue Linksrekursionen eingeführt. Das ist aber nicht wahr. Durch das Schema oben wurde ein neues Terminal C und eine Epsilonproduktion C->eps eingeführt. Das kann aber nicht zu einer neuen versteckten Rekursion führen, da C vorher noch nicht in der Grammatik aufgetaucht ist. Dieses Beispiel aus der PDF besagt viel eher, dass man vorsichtig sein sollte, wenn die Grammatik vorher bereits epsilons enthält. Denn dann könnten versteckte Linksrekursionen enthalten sein, die das Eliminierungsschema nicht auf rein mechanische Weise auffinden und beseitigen würde.

Würde auch sagen: Zeige uns Deine Grammatik. Am besten die Ausgangsform, also eine die durchaus noch Mehrdeutig sein kann. Dann können wir das eindeutig machen, Rekursionen entfernen und Faktorisieren.