Musterlösung 1.4

fl4$h g0rd0n
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 115
Registriert: 1. Okt 2007 22:20

Musterlösung 1.4

Beitrag von fl4$h g0rd0n »

Hallo,

die Musterlösung kann ich nicht ganz nachvollziehen. Ich bin der Meinung, dass die Bedingungen zur
Prüfung auf LL(1) sich nicht einfach so analog auf LL(2) übertragen lassen.

Wenn man zum Beispiel die Wörter yyx und xyxx betrachtet, dann kann ein deterministischer LL(2)-Parser nicht beide
erkennen. Steigt man rekursiv in eine parseX()-Methode ab, dann ist zunächst in beiden Fällen der
aktuelle Lookahead das Teilwort "yx". Jetzt muss ein Parser daran entscheiden, ob
das Symbol y zu der Produktionsregel mit X (trifft bei xyxx zu) oder S (trifft bei yyx zu) gehört.
Ein deterministischer Parser (für den wir uns in der Praxis interessieren) muss hier immer
die gleiche Entscheidung treffen. Ganz gleich welche Entscheidung getroffen wird, eines
der beiden Wörter wird nicht akzeptiert.

Daher würde ich sagen, dass k = 3 die richtige Antwort ist. Es sei denn, man ist so spitzfindig und lässt auch nichtdeterministische Parser
in der Betrachtung zu :)
"Education is the path from cocky ignorance to miserable uncertainty" -- Mark Twain

Flo S
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 27. Apr 2010 22:50

Re: Musterlösung 1.4

Beitrag von Flo S »

Wäre interessant zu wissen.
Etwas ähnliches haben wir in unserer Abgabe auch geschrieben.
Bei "xyxx" und "yyx" als Wörter lesen wir den ersten Buchstaben ein - "x" bzw "y" und können die S-Produktion entscheiden.
Nun haben wir jedoch für "yxx" und "yx" zwei gleiche Buchstaben. Da der Parser zu diesem Zeitpunkt nicht mehr weiß, ob er davor die S-Produktion S=>xXxx oder S=>yXyx gemacht hat, müssen wir also mindestens 3 Buchstaben einlesen. Wir benötigen also einen LL(3) Parser.

Jens Huthmann
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 192
Registriert: 10. Nov 2011 19:42

Re: Musterlösung 1.4

Beitrag von Jens Huthmann »

Ich werde das nächste Woche überprüfen. DIese habe ich noch Urlaub :roll:

Edit:

Nach ersten Nachforschungen scheint beides ll(2) und ll(3) richtig zu sein.
Die gegeben Grammatik ist ll(2) aber nicht stark ll(2), welches von uns nicht definiert wurde.
Stark bedeutet hier das der Parser sich nicht merkt aus welche Produktion er gekommen ist.

Wir werden das noch genauer untersuchen und Ihnen eine genaue Definition nachliefern.

Jens Huthmann
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 192
Registriert: 10. Nov 2011 19:42

Re: Musterlösung 1.4

Beitrag von Jens Huthmann »

So nach weiterer Überprüfung kann ich sagen das die formale Begründung für ll(2) tatsächlich falsch ist. Man darf die in der Vorlesung angebene Formel nur für k=1 verwenden.

Aber die Grammatik ist tatsächlich mit einem ll(2) Parser zu verarbeiten wenn man die Reihenfolge der Verarbeitung der Produktionen als ein Eingabe einer parse Methode übergibt.

Wenn man einen Parser konstruieren möchte ohne diese Eingabe auskommt, dann benötigt man eine "strong" ll(k) Grammatik. Antlr benötigt solche Grammatiken und auch die Beschreibung in der Vorlesung war auf diese Grammatiken bezogen. Für solche eine Grammatik ist es tatsächlich notwendig eine ll(3) Grammatik zu verwenden.

Da wir selbst auf diesen Unterschied hineingefallen sind werden wir beide Lösungen als korrekt ansehen. Ich versuche noch die tatsächliche formal richtige Bestimmung des k zu beschreiben, was auf jeden Fall wesentlich komplizierter als für k=1 ist.

Die Erweiterung von follow und first auf k Zeichen ist aber korrekt. Nur die Formel welche beides vereinigt darf nicht verallgemeinert verwendet werden.

Antworten

Zurück zu „Archiv“