Parser-Generator

Ein Parser-Generator ist ein Computerprogramm, das Unterprogramme zur lexikalischen und grammatikalischen Analyse eines Quelltextes für einen Interpreter oder Compiler erzeugt.

Compiler und Interpreter bestehen in der Regel aus drei Stufen:

• 1. einer lexikalischen Analyse (Analysator)
• 2. einer grammatikalischen Analyse (Parser)
• 3. und entweder einem
• • 1. Codegenerator, so dass ein ausführbares Programm (oder ein Unterprogramm) entsteht, oder
  • 2. einem Auswerter, so dass ein Interpreter entsteht.

Der lexikalische Analysator erkennt dabei Zeichenketten wie "Hello World", Bezeichner, Zahlen, Kommentare und Schlüsselworte wie FOR, ELSE oder CALL. Der Parser vergleicht die vom Analysator gelieferten Resultate mit der Syntax der zu übersetzenden Programmiersprache und steuert die dritte Stufe. Beim Interpreter werden dort die Ausdrücke ausgewertet und die Anweisungen durchgeführt. Beim Compiler wird der Maschinencode erstellt.

Sowohl der lexikalische Analysator wie auch der Parser lassen sich effizient mit endlichen Automaten realisieren, die die Analyse einer Symbolkette tabellengesteuert vornehmen. Sie sind weitgehend maschinenunabhängig. Die Erzeugung der erforderlichen Tabellen von Hand ist jedoch aufwändig und fehleranfällig.

Hierfür existieren Parser-Generatoren, unter Unix zum Beispiel lex (Lexical Analyser) und sein GNU-Pendant flex für die lexikalische Analyse und yacc (Yet Another Compiler Compiler) oder Bison für den Parser. Der Maschinencode-Generator muss zusätzlich für jede Maschine codiert werden.

Als Eingabe wird bei lex eine Datei mit den lexikalischen Elementen und den Aktionen benötigt. yacc verarbeitet eine Datei mit der Sprachsyntax in einem der Backus-Naur-Form ähnlichen Format. Als Ausgabe erhält man die erforderlichen Unterprogramme und Tabellen in der Programmiersprache C, die dann von einem Compiler übersetzt werden.

Die automatisch erzeugten Prozeduren kann man dann mit den restlichen, von Hand codierten Teilen ergänzen, das sind im Wesentlichen das Hauptprogramm und der Aufruft des Codegenerators bzw. Auswerters. Der Aufwand zum Erzeugen eines leistungsfähigen Analysators und Parsers wird durch Parser-Generatoren auf ein Minimum reduziert.