Parsergenerator

Im Compilerbau ist ein Parsergenerator ein Computerprogramm, das auf Grundlage einer Spezifikation einen Parser generiert.

Grundlagen

Ein Parsergenerator erzeugt Unterprogramme für (Programmier-)sprachen, die deren grammatikalische Analyse und Transformation ermöglichen. 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. Die Spezifikation des Parsers erfolgt in der Regel in Backus-Naur-Form (BNF) oder in Erweiterter Backus-Naur-Form (EBNF).

Viele Parsergeneratoren benötigen einen Scanner für die Symbolerkennung. Dieser Scanner wird in der Regel von einem integrierten oder externen Scannergenerator erzeugt.

Die vom Parser erzeugte Repräsentation bildet dann 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 Parsergeneratoren verwendet:

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

Darüber hinaus gibt es weitere Paradigmen (z. B. GLR-Parser), die eine größere Klasse von Grammatiken abdecken, aber weniger gebräuchlich sind.

Weblinks

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