Eigener Parser

[BillieJoe90]

Hallo,
meine Frage passt vielleicht nicht ganz in diesen Bereich, aber egal...

Ich würde gerne einen eigenen XML-Parser schreiben. Nicht des Nutzen wegen (wozu das Rad neu erfinden?), sondern zur Übung bzw. zum Verständnis. Nun bin ich auf der Suche nach einem Tutorial, wie man einen Parser programmiert. Am besten wäre natürlich eines für eine SGML-Sprache wie HTML oder XML. Leider habe ich im Internet bis jetzt nur unpassende Tutorials gefunden.
Kennt jemand eines/welche? Sprache ist egal, englisch oder deutsch halt...

Danke schonmal!

Johannes

[Der_Unwissende]

Hi,
an sich musst Du beim Parser-Bau wirklich nur nach dem allgemeinen Stichwort Parser suchen. Die Sprache ist tatsächlich egal.
Die Arbeitsweise ist fast immer die gleiche, Du arbeitest in grob 4 Schritten:

1. Screener - Zerlegen der Eingabe in einzelne Worte (entfernen von Leerzeichen und Kommentaren)
2. Scanner - Erkennen von Schlüsselworten, Umwandlung von Worten in Token
3. Parser - Syntaktische Analyse, prüft ob die Token in dieser Kombination gültig ist
4. Syntaxbaum - Wird vom Parser erstellt, kann aber z.B. auch durch das Erbauer-Muster realisiert werden

Das sind keine scharf getrennten Schritte. Häufig wird der Scanner schon den Screener beinhalten und auch der Parser kann alles auf einmal machen. Trotzdem hat es sich durchgesetzt, dass man wenigstens den Scanner/Lexer von dem Parser trennt. Insbesondere ist es aber eher unüblich, dass man den kompletten Parser selbst erstellt, da es hier einige Fehlermöglichkeiten gibt. Sehr viel häufiger wird man eher zu einem Parsergenerator greifen. Diesen gibt man eine Grammatikdatei mit, die die Syntax (häufig als BNF) enthält. Daraus erstellt der Parsergenerator dann einen Parser in der Zielsprache.
Das hat durchaus viele Vorteile, da sich so deutlich bessere (und fehlerfreiere) Parser erstellen lassen, die zudem immer vom Stand der Technik des Generators profitieren können.

An sich kannst Du aber einfach nach dem Begriff Parser suchen, da solltest Du eigentlich einiges finden (z.B. bei Wikipedia). Dinge wie Bottom-Up, Top-Down, LR, Shift-Reduce, LL, ... sollten Dir bei deiner Suche begegnen. Als Lektüre kann ich Dir sonst Aho, Stein, Ullmann - Compilerbau (das Drachenbuch) empfehlen . Hier dürfte der erste Teil schon alles zum Thema Parser abdecken, im Gesamten geht das Buch (wie der Titel ja verrät) über den Bau eines Parsers hinaus!

Gruß Der Unwissende

[BillieJoe90]

Vielen Dank für deine ausführliche Antwort, hat mir sehr geholfen!

[QuickAndDirty]

nehme einfach
YACC

Yet Another Compiler Compiler