Parsergenerator
Ein Parsergenerator ist ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt.
Inhaltsverzeichnis |
Grundlagen
Ein Parsergenerator erzeugt für (Programmier-)Sprachen Unterprogramme zu deren grammatikalischer Analyse und Transformation. Die erzeugten Unterprogramme werden Parser genannt. Als Eingabe erhält ein Parsergenerator die Sprachsyntax für die er einen Parser erzeugen soll. Zum Beispiel werden Quellprogramme von Programmiersprachen durch einen Parser in eine Baumstruktur überführt.
Viele Parsergeneratoren benötigen einen Scanner für die Symbolerkennung. Dieser Scanner wird in der Regel von einem externen oder einem integrierten Scannergenerator erzeugt.
Die vom Parser erzeugte Repräsentation bildet die Grundlage für einen Compiler oder Interpreter.
Der Aufwand zum Erzeugen eines leistungsfähigen und korrekten Compilers wird durch Parsergeneratoren deutlich reduziert.
Algorithmen
Effiziente Parsergeneratoren beschränken sich darauf, Parser für deterministisch kontextfreie Grammatiken zu erzeugen. Folgende Algorithmen werden von gängigen Parser-Generatoren verwendet:
Die Spezifikation des Parsers erfolgt in Backus-Naur-Form (BNF) oder Erweiterter Backus-Naur-Form (EBNF).
Darüber hinaus gibt es weitere Paradigmen (z.B. GLR-Parser), die eine größere Klasse von Grammatiken abdecken, aber weniger gebräuchlich sind, da der Gewinn an Flexibilität in keinem Verhältnis zum Verlust an Effizienz steht.
