Analyse einer Grammatik durch LR(k)-Parser - Erklärungen gesucht
-
Hallo,
ich hab Interesse daran mir einen Parsergenerator zu schreiben, der mir einen LR(k)-Parser generieren kann. Ich hab das Prinzip wie ein solcher Parser arbeitet und wie die Parsing-Tabelle mit dem Stack zusammenarbeitet, dank den Erklärungen im Drachenbuch, so einigermaßen verstanden.
Was ich aber noch nicht so richtig verstanden habe ist, wie ich eben jetzt einen Generator schreibe, der mir anhand einer Grammatik einen dazugehörigen Parser generiert. Die Analyse der Grammatik wird im Buch zwar auch beschrieben, aber irgendwie sind mir die Erklärungen noch zu hoch.
Kann mir jemand eine Quelle empfehlen, bei der die Analyse der Grammatik nicht als ganz so staubtrockene Theorie behandelt wird oder bei der ein paar (Pseudo-)Code-Beispiele vorhanden sind, die die Erklärungen verdeutlichen?
-
Hallo,
Dir ist schon bewusst, dass kanonische LR(k)-Parser, wie sie im Drachenbuch beschrieben werden, exponentiell in der Größe der Grammatik wachsen? Die Frage ist, ob Du überhaupt praktisch etwas damit anfangen kannst. Entweder ziehst Du Dich, wie yacc und co. auf LALR(1) zurück, oder Du suchst mal nach "On LR(k)-parsers of polynomial size" (wurde auf der ICALP 2010 vorgestellt). Wie der Titel schon sagt, wird in der Arbeit gezeigt, wie man mit wesentlich weniger Platz auskommt.
Gruß
Pauline
-
Hi,
erstmal vielen Dank für deine Antwort. Dass kanonische Parser sehr groß werden können war mir klar - nur nicht wie groß. Das ist für mich momentan auch irrelevant, da ich erst mal verstehen möchte nach welchen Kriterien ein Parsergenerator die Regeln für die Generierung eines Parsers aufstellt. Erst wenn ich das verstanden und umgesetzt habe wollte ich einen Schritt weiter gehen (und da hänge ich nach wie vor fest).
Oder unterscheiden sich die beiden Parserarten so stark voneinander, dass mich das Wissen, das ich beim Entwickeln einer Parserart lerne, bei der anderen Art nicht weiterbringt?
-
Also ich habe dazu nur "Halbwissen", aber im Prinzip generiert ja der kanonische LR(k)-Parser einen Push-Down-Transducer/Push-Down-Automaton, der nur eine Tabelle benötigt, die für jedes Stackelement + Eingabe + Zustand entscheidet, was getan werden muss (jedenfalls im Groben). Die verlinkte Arbeit benutzt eine andere Technik, die auch für allgemeine kontextfreie Grammatiken verwendet kann und dann i.a. es eben nicht erlaubt in linearer Zeit (in Abhängigkeit von der Eingabelänge) zu parsen. Diese Technik wird in der von mir zitierten Arbeit durch die Einschränkung auf LR(k)-Grammatiken so modifiziert, dass man das ganze auf lineare Zeit runter bekommt, ohne Tabellen erzeugen zu müssen, die exponentiell in der Größe der Grammatik groß sind. Im Gegensatz zum kanonischen Parser wird nicht ein Stackinhalt, sondern mehrere Stackinhalte gleichzeitig mittels eines Graphen verwaltet. Das reduziert dann den Speicherbedarf des Parsers selber. Allerdings ist dann der interne Aufbau stark verschieden.
-
Also, ich werde das Dokument mal durcharbeiten. Vllt. ist es ja so gut erklärt, dass ich gleich verstehe wie der Parser funktioniert, dann kann ich ihn umsetzen. Nochmal vielen Dank für deine Hilfe.