Vorlesung: Praxis der Funktionalen Programmierung | Index

Ausblick zu Parsern

Parser-Kombinatoren sind ein eindrucksvoller Beweis für die programmiertechnische Effizient von Monaden.

In imperativen Sprachen schreibt man entweder einen Parser mit Rekursivem Abstieg von Hand (wenn man viel Zeit hat) (der GNU Ada Compiler) (das gibt schöne Fehlermeldungen) (aber der Programmtext ist ewig lang) - oder einen bottom-up-Parser (d. h. einen Kellerautomaten) mit einem Parsergenerator (bison). Das ist seit 30 Jahren Standard, und deswegen auch hoch optimiert.

Die monadischen Parser in der vorgestellten Form benötigen einige Umbauten, um vergleichbare Effizienz zu erreichen. Eine Änderung haben wir schon gesehen (Nichtdeterminismus beschränken). Was braucht man noch? Man unterscheidet wenigstens zwei Arten von Fehlern: solche, die auftreten, weil wir im falschen Zweig einer Alternative waren, und solche, die aus einer wirklich inkorrekten Eingabe entstehen. Im letzten Fall sollten wir sofort abbrechen, im ersten Fall müssen wir die weiteren Alternativen testen.

Für informativere Fehlermeldungen möchten wir ausgeben, was der Parser als nächstes Zeichen (Token) erwartete (aber nicht bekommen hat). Man braucht also Parser, die in jedem Schritt auch die Liste der möglichen nächsten Zeichen mitführen, und dann danach verzweigen.

Das ist alles implementiert in der Parser-Kombinator-Bibliothek Parsec, jetzt offizieller Bestandteil der ghc-Bibliothek, und läuft auch inter hugs. Habe ich im Sequencer benutzt (Quelltext) War ganz einfach (180 Zeilen für alles).

Pretty-Printer

Das Gegenteil vom Parsen ist Drucken. Wir haben das hier ignoriert, und die Syntaxbäume grafisch ausgegeben. Ein Compiler muß aber (spätestens bei Fehlermeldungen) auch mal Teile von (eventuell transformierten) Syntaxbäumen wieder in ASCII-Text wandeln. Dieser soll menschen-lesbar sein, also vernünftig umgebrochen und eingerückt.

Auch dazu gibt es Layout-Kombinator-Bibliotheken. Bestandteil von ghc ist diese Bibliothek. Läuft auch inter hugs. Habe ich im Sequencer benutzt. (Quelltext) War ebenfalls ganz einfach (90 Zeilen für alles).


best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de