Parsergenerator
Im Compilerbau ist ein Parsergenerator ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt.
[Bearbeiten] 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 Syntax der Sprache, für die er einen Parser erzeugen soll. Bei dieser Sprache kann es sich z.B. um eine Programmiersprache handeln.
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.
[Bearbeiten] Algorithmen
Effiziente Parsergeneratoren beschränken sich darauf, Parser für deterministisch kontextfreie Grammatiken zu erzeugen. Folgende Algorithmen werden von gängigen Parsergeneratoren verwendet:
- LL(k)-Parsing (JavaCC, Coco/R)
- LL(*)-Parsing (ANTLR)
- LALR(1)-Parsing (SableCC, yacc, GNU Bison)
Die Spezifikation des Parsers erfolgt z.B. 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.
