Domain Specific Language Parser (DSL-Parser)

Hallo!

Ich versuche gerade, einen allgemeinen Parser für Domain Specific Languages zu schreiben, um somit z.B. grundlegende SQL-Befehle parsen zu können, oder bei Bedarf auch eine eigene kleine Programmiersprache zur Steuerung zu schreiben.

Nun habe ich zunächst angefangen, meine Kenntnisse in diesem Bereich etwas zu erweitern, und möchte hier mal um Rat fragen, ob ich da evtl. etwas falsch verstanden habe.

Zunächst mal zu den Begrifflichkeiten:*Token / Terminalsymbol: Ein eigenständiges Symbol, welches nicht weiter aufgeteilt werden kann. *Identifier / Bezeichner: Ein Name für eine Konstante, Variable oder Funktion. *Keyword: Ein reserviertes Wort der Sprache, welches üblicherweise nicht für Identifier verwendet werden darf. *Operator: Beziehungssymbole vor oder zwischen Identifiern. *Delimiter: Trennzeichen bzw. Gruppierungssymbole für die o.g. Symbole

Am Anfang steht die lexikalische Analyse, dabei werden die Tokens durch einen sog. Lexer erkannt.
Dann folgt die syntaktische Analyse, diese überprüft die Tokens auf korrekte Kombination.
Abschließend erfolgt die semantische Analyse, welche die Tokens verarbeitet und entsprechende Aktionen auslöst.

Einen Lexer zu schreiben, dürfte noch der einfachste Teil sein: Man definiert eine Menge von Symbolen für Keywords, Identifier, Operatoren und Delimiter. Der Lexer setzt die Tokens Zeichen für Zeichen zusammen und prüft die Zugehörigkeit zu einer der o.g. Mengen.
Einziges Problem: Ein im Code definierter Identifier kann vom Lexer so nicht erkannt werden.
Bei der Festlegung einer Syntax habe ich bereits das Problem einer einheitlichen Darstellung (mit welcher Symbolik kann man eine SQL-Syntax ebenso definieren wie eine Java-Syntax).

Bzgl. der Semantik habe ich überlegt, dass vom Parser eine Klasse abgeleitet wird, dessen Methoden per Attribut die Keywords zugeordnet werden. Je nach Keyword wird dann die entsprechende Methode vom Parser aufgerufen. Denkbar wäre dabei noch ein (zusätzlicher) Parameter, welcher benutzerdefinierte Attribute über den bisherigen Verlauf und/oder den aktuellen Kontext enthält.

Ist das gedanklich und begrifflich soweit OK, oder habe ich evtl. irgendwo was falsch verstanden? Oder hat jemand vielleicht eine Idee, wie man den letzten Schritt anstatt mit Attributen evtl. anders eleganter hin bekommt.

EDIT: Nachtrag:
Zum einen habe ich überlegt, ob man nicht die Delimiter weiter aufteilen sollte.
Man hätte dann z.B. zum einen die Formatierungssymbole (Space, Tab, CR), welche nach dem scannen nicht weiter gespeichert werden müssten, und zum anderen die Gruppierungs- und Trennsymbole.

Und eine Syntax könnte man analog zu SELECT Clause (Transact-SQL) oder SELECT (Transact-SQL) definieren, z.B.

RegisterBlock(string name, string blockText);

EDIT: Endlich ist mir der Name wieder eingefallen: Backus-Naur-Form

Hallo tom-essen,

grundsätzlich hast du alles richtig verstanden.

Ich frage mich allerdings, warum du da selber was basteln willst, wo es doch so viele fertige und langjährig gereifte und erprobte Lexer und Parser-Generatoren gibt. Insbesondere, wenn du anscheinend keine Idee hast, wie du die auftretenden Probleme besser lösen kannst als die bestehenden Tools.

Wenn du es wirklich selber machen kannst, würde ich aus dem Quelltext einfach nur einen attribuierten Syntaxbaum erstellen und zur weiteren Verarbeitung dem Benutzercode übergeben. Sonst geht der Zusammenhang zwischen den Syntaxelemente verloren, wie das wohl bei der Idee, für jedes Schlüsselwort eine Methode aufzurufen, der Fall wäre.

herbivore

Hi

Martin Fowler bringt in Kürze ein neues Buch raus: Domain Specific Languages

Schau dir z.B. das an:
http://en.wikipedia.org/wiki/Recursive_descent_parser

Wichtige Begriffe zum googlen: First-Follow Mengen, Normal Formen

Da bekommst du dann z.B. die Grammatik von SQL92: http://vieka.com/esqldoc/sql92bnf.htm

Solche Grammatiken kannst du dann in einen Parser Generator hauen - verwende die nur in Java: http://de.wikipedia.org/wiki/JavaCC

Damit kannst du dann syntaktisch analysieren und sematische Sachen auswerten (anhand von Callbacks)

LG

Hallo!

@herbivore:
Du hast natürlich Recht, es gibt bereits fertige Lösungen. Aber zum einen bin ich zu faul, mich z.B. in Coco/R einzuarbeiten, zum anderen möchte ich auch zum eigenen Verständnis so etwas selbst schreiben.

Edit/Nachtrag: Habe gerade den Tiny Parser Generator entdeckt, den könnte ich mir schonmal anschauen.

@winmike:
Klingt interessant, werde ich mal ausprobieren.

Edit: Bzgl. CoCo/R habe ich gerade ein Tutorial entdeckt: http://www.activevb.de/tutorials/tut_parser/tut_parser_1.html

Auch Microsoft hat was im Angebot: "M".

"M" Overview

Hallo,

hab' mir mittlerweile mal Coco/R angeschaut.
Coco/R erstellt mir zu einer Syntax zwei Dateien:*Parser.cs: Extrahiert die Tokens *Scanner.cs: Scannt die Tokens und ruft dann die noch zu implementierenden Methoden auf, jeweils mit den entsprechenden Parametern.

"Yacc" scheint in etwa dasselbe zu tun, "M" hab' ich mir noch nicht genau angeschaut.

Yacc und Coco/R scheinen aber beide noch ein Problem damit zu haben, korrekte .cs-Dateien zu generieren, da musst ich stark nacharbeiten (hat da jemand andere Erfahrungen gemacht?).

Prinzipiell erstellt ein Scanner demnach im Idealfall einen Syntaxbaum, welcher dann an einen Compiler bzw. eine entsprechende Methode übergeben werden könnte?

Edit: Ich stelle mir dabei einen Baum vor wie im Bild unten

Hallo tom-essen,

nach meinen Verständnis hast du die Begriffe Scanner und Parser vertauscht. Der Scanner (=Lexer) separiert die Token. Der Parser erzeugt den Syntaxbaum.

herbivore

Hallo,

@herbivore:
Stimmt, hab' ich vertauscht, sorry.
Edit: Hab's ja im ersten Beitrag sogar selbst erklärt: Lexer = Lexigrafischer SCANNER (!) 8o

Hallo!

Ich frage mich allerdings, warum du da selber was basteln willst, wo es doch so viele fertige und langjährig gereifte und erprobte Lexer und Parser-Generatoren gibt. Insbesondere, wenn du anscheinend keine Idee hast, wie du die auftretenden Probleme besser lösen kannst als die bestehenden Tools.

Habe ich nun mal mit den am häufigsten genannten versucht.

Die Ergebnisse von Coco/R kann man vergessen (zumindest für C#). Abgesehen davon, dass man erstmal den Code soweit aufbereiten muss, bis alles ohne Fehler compiliert werden kann, funktioniert der parser selbst überhaupt nicht (hab's für C# und SQL ausprobiert).

ANTLR ist sehr unübersichtlich, das Java-Tool kann keinen C#-Code generieren, und die API-Beschreibung auf der Homepage zur Einbindung der .NET-Assemblies in ein eigenes Projekt sind - zumindest für mich - total unverständlich, bzw. ich sehe ausser lauter Klassenbeschreibungen keinen Ansatzpunkt.

Bison kann anscheinend kein C# generieren.

Bin noch auf CSFlex sowie Grammatica gestossen, muss ich mich aber erst mal rein arbeiten.

Bleibt noch Yacc, für den ich aber noch keine lauffähige Version gefunden habe.

Bleibt für mich z.Zt. nur das Fazit, dass die Tools zumindest im C#-Bereich noch experimentell sind, und somit für mich derzeit nicht in Frage kommen.

Im Endeffekt suche ist ja eigentlich nur eine Möglichkeit, SQL-Befehle zu parsen, um diese vor der Ausführung je nach DBMS (MSSQL, Oracle, ...) in die entsprechende Form zu bringen.

Sollte jemand dazu eine Idee haben, oder bereits mit einem Parser-Generator gute Erfahrungen gemacht haben, wäre ich dennoch für eine Antwort dankbar.

Ich werde solange versuchen, einen eigenen Parser zu schreiben.