Parsergenerator

Ein Parsergenerator ist ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt.

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:

• LL(k)-Parsing (JavaCC, Coco/R)
• LL(*)-Parsing (ANTLR)
• LALR(1)-Parsing (SableCC, yacc, GNU Bison)

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.

Siehe auch

• Compilerbau
• lexikalischer Scanner

Weblinks

• „LR(k)-Analyse für Pragmatiker“