Eigener (kleiner) SQL-Parser

[BillieJoe90]

Hallo,
ich würde gerne für ein Projekt in der Schule eine "Ersatz-Datenbank" für Delphi schreiben, die zwar im Hintergrund alles in Records und Dateien speichert, jedoch mit SQL-Querys angesprochen werden kann. Natürlich wäre dafür ein SQL-Parser von Nöten, der sich zunächst erstmal auf SELECT, INSERT INTO, DELETE, UPDATE, WHERE, GROUP BY, und ORDER BY beschränken und auch sehr einfach gehalten sein sollte!
Kennt jemand irgendein Tutorial zu so etwas? Oder einen Grundeinstieg, damit ich weiß, wie man einen String "parst"? Weil auf Anhieb hätte ich jetzt keine Idee, wie ich jede Möglichkeit von Eingabe "abfangen" und erkennen könnte.

Danke schonmal!

Johannes

PS: Bitte schreibt keine Antworten zu dem Sinn des Projekts. Es ist rein für den Informatik-Unterricht und ich möchte damit mal einen Einblick in das Parsen bekommen.

[Der_Unwissende]

Hi,
das erste was Du eigentlich machen solltest ist nach diesem Stichwort (Parsen) googlen oder halt woanders suchen. Deswegen an dieser Stelle die Frage: Hast Du das denn schon gemacht? Was hat deine Suche so ergeben und wo kommst Du da nicht weiter?

An sich solltest Du hier ordentlich viel finden. Für ein Schulprojekt steht dann natürlich etwas mehr Information zur Verfügung als Du letztlich brauchst, aber das sollte weniger stören (frag hier nach oder geh zu einer anderen Quelle, wenn es zu kompliziert wird).

An sich wird beim Parsen eine einfache Syntax-Analyse durchgeführt. Ein Parser bekommt eine Liste von Token, prüft diese auf ihre Korrektheit (was die Anordnung angeht) und überführt sie i.d.R. in einen Syntaxbaum.
Die weiteren Arbeiten finden dann auf Basis dieses Syntaxbaums statt.

Am Anfang des gesamten Vorgangs steht immer eine Eingabe (z.B. eine Datei oder hier auch ein String). Eine solche Eingabe zerlegt man erstmal in ihre einzelnen Bestandteile. Dazu kann ein Screener (ein Sieb) eingesetzt werden. Als Trennung in Bestandteile kannst Du dabei das Zerlegen anhand von Leerzeichen verstehen. Dabei muss jede Form von Leerzeichen (ein oder mehrere Space, Tabulatoren, Linefeeds oder Zeilenumbrüche) berücksichtigt werden. Zudem kannst Du hier (soweit vorhanden) auch gleich alle Kommentare entfernen. Was Du also bekommst ist eine Liste von Strings. Aus dem String "Dies ist ein Satz //mit Kommentar" würde dann etwas wie ['Dies', 'ist', 'ein', 'Satz'].

Mit dieser Liste geht es dann zum Scanner. Dieser führt eine lexikalische Analyse durch. Hier wird also in einer Art Lexikon nachgeschaut, ob ein Schlüsselwort erkannt wird. Jeder String wird anhand solcher Schlüsselworte einfach qualifiziert. Was Du dabei rausbekommst sind die bereits erwähnten Token. Ein Token besteht immer aus dem Typ und (meistens) noch einem Wert. Etwas deutlicher wird das, was ich meine, wenn wir es an einem Beispiel betrachten. Sei die Eingabe:
"SELECT X FROM Y WHERE"
ist hier natürlich nicht vollständig, aber es zeigt das Prinzip. Nach dem Screener erhälst Du ['SELECT', 'X', 'FROM', 'Y', 'WHERE']. Jetzt bildest Du aus jedem String das Tupel (TYP, WERT), aus dieser Liste wird also [(SELECT, _), (BEZEICHNER, 'X'), (FROM, _), (BEZEICHNER, Y), (WHERE, _)].
Der Unterstrich steht hier für nichts, da z.B. ein Select keinen Wert benötigt, ein Bezeichner hingegen schon. Was Du hier siehst ist die Qualifizierung. Du weißt bei jedem Token um was für einen Typen es sich handelt.

Zu guter Letzt kommt jetzt diese Liste von Token zum eigentlichen Parser. Dieser prüft nun, ob die Anordnung der Token korrekt ist. Diese Prüfung wird anhand einer Grammatik durchgeführt. Eine Grammatik legt dabei Ableitungen fest. Such einfach mal im Kontext der Informatik nach Grammatiken. Insbesondere sollten hier kontextfreie Grammatiken sowie die (E)BNF.
Für eine SQL-Abfrage könnte z.B. eine erlaubte Syntax die Form haben, dass eine Anweisung aus einem SELECT BEZEICHNER FROM BEZEICHNER [WHERE] besteht.

Wichtig wäre hier jetzt die letzte eckige Klammer mit dem WHERE. Diese Bedingung ist optional (an die Notation der EBNF angelehnt). Dein Parser muss hier also sowohl die Liste mit als auch ohne ein WHERE am Ende akzeptieren. Der Parser kennt eben eine Grammatik und kann für eine Liste von Token prüfen, ob diese der Grammatik genügt. Ist dies der Fall, lag die Eingabe in syntaktisch korrekter Form vor. Natürlich muss sich nicht jede Eingabe in korrekter Form befinden, wird also eine ungültige Tokenfolge gefunden z.B. [(SELECT,_), (FROM, _)], dann würde hier ein Syntaktischer Fehler erkannt (und gemeldet) werden. Nach der obigen Regel muss dem (SELECT,_) ein Bezeichner folgen.

Für den erfolgreichen Fall, baut man einfach einen Syntaxbaum zusammen. Dies hat den Vorteil, dass man hier die Trennung zwischen dem Parser und der weiteren Verarbeitung vornehmen kann. Ist der Baum (seine mögliche Zusammensetzung) bekannt, kann mit diesem gearbeitet werden. Alle Schichten oberhalb des Parsers werden nur einen solchen Baum benötigen. Ein solcher Baum befindet sich immer in einer Form, die leicht verarbeitet kann (diese Form wird eben durch den Baum festgelegt). Zudem befindet sich ein solcher Baum natürlich (durch die vorgegebene Form) immer in korrekter Syntax. Der Parser, der diesen Baum erzeugt ist austauschbar, ohne dass dies einen Einfluss auf die aufsetzenden Schichten hat (diese wollen wie gesagt nur einen solchen Baum).
Man spricht hier auch von Back- und Front-End (beim Compilerbau).
An dieser Stelle ist das aber auch egal.

Du musst Dir an dieser Stelle nur überlegen, was für einen Baum Du erstellen möchtest und wie dieser abgearbeitet werden kann. In deinem Fall kannst Du dann einfach den Baum traversieren und die gefundenen Elemente interpretieren.

Ich hoffe, dass ich grob die Arbeitsweise eines Parsers erklären konnte. Wie gesagt, an sich solltest Du viel zu dem Thema durch Suchen finden. Eine wichtige Bemerkung zu dem Thema (und dem theoretischen Nutzen) hätte ich aber auch noch. So finde ich es natürlich nicht schlecht, dass Du Dich für die prinzipielle Arbeitsweise interessierst! Hier sei Dir übrigens das Drachenbuch empfohlen.
Der Bau eines Parsers hat aber ein paar wichtige Eigenschaften:

• Er ist fehleranfällig
• Er ist mühsam
• Er ist fast immer gleich (unterschiede liegen nur in der Grammatik)

Deshalb wurden Parser-Generatoren geschaffen. Diese erstellen aus einer Beschreibung der Grammatik einen Parser. Da diese Generatoren feste Algorithmen für die Generierung eines Parsers einsetzen sinkt natürlich die fehleranfälligkeit und der Aufwand immens. Die meisten Parsergeneratoren sind natürlich erbrobt und man kann somit von einer Fehlerfreiheit ausgehen. Genauso wichtig ist dann auch die Tatsache, dass man von allen Optimierungen profitiert, die der Generator berücksichtigt. Häufig hängen diese direkt von der eingesetzten Grammatik ab (auch hier sei auf die Suche nach LL, LR, .. verwiesen). Letztlich heißt das, dass man eben nicht das Rad neu erfinden muss und von allen Erkenntnissen und Mühen profitiert, die andere hier schon geleistet haben.
Natürlich ist es trotzdem nicht falsch sich mit dem Aufbau/der Arbeitsweise eines Parsers beschäftigt und ich rate Dir davon auch nicht ab, aber wie gesagt, in der Praxis würdest Du deutlich von einem Generator profitieren und es wäre dumm auf solche Vorteile zu verzichten.

Gruß Der Unwissende

[alzaimar]

Also, einen 'Screener' kenne ich nicht. Ein 'Sieb' wäre auch ein 'Sieve'.

So, Wortklauberei vorbei.

SQL ist eine Sprache und jede Sprache besteht aus Sätzen, Wörtern und Satzzeichen. Der Scanner zerlegt die Eingabezeichenkette (Satz) erstmal in einzelne 'Wörter' und Satzzeichen. Das macht es dem Parser viel leichter, den Satz zu erkennen.

Nochmal: Der Scanner zerlegt die Zeichenkette in Wörter und der Parser baut diesen Syntaxbaum auf.

Dem Unwissenden würde ich bei der Beurteilung der Parser und Parsergeneratoren widersprechen:
1. Ein selbstgebastelter Parser ist unermesslich wertvoll: Denn er vermittelt dir Kenntnisse, die Du in 20 Jahren Programmierung nicht erhalten wirst. Also: Bau Dir einen!
2. Selbstgebastelte Parser sind, wenn man die Technik kapiert hat, immer unterschiedlich. Es gibt simple precedence und LL(1) Parser, sowie Stackmaschinen, NDE-Automaten etc.
3. Mühsam sind sie, das stimmt.

Ansonsten hat der 'Unwissende, der seinen Namen zu Unrecht trägt', Dir alles wichtige erzählt: Wer gute Parser/Compiler bauen will, der mussdie Theorie beherrschen.

Übrigens gibt es eine sehr schöne Komponente TJanSQL, die SQL auf Textdateien abbildet. Da solltest du fündig werden.

[Dax]

Zitat von alzaimar:

Ein selbstgebastelter Parser ist unermesslich wertvoll: Denn er vermittelt dir Kenntnisse, die Du in 20 Jahren Programmierung nicht erhalten wirst. Also: Bau Dir einen!

Dem kann ich nur zustimmen. Mir hat eben diese Meinung, die ich auch teile, gewissermaßen die letzten beiden Informatikarbeiten gerettet, wenn nicht sogar geschenkt. Aber ein selbstgebauter Parser trägt nicht nur zum Verständnis der Theorie hinter all dem bei, sondern ist auch weiter nützlich - zum Beispiel, um Parsergeneratoren und ihre Eingaben besser zu verstehen.

Also: es lohnt sich