Recursive Decent Parser: Rekursionsanker?

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...

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++

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.

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.