Quelltext der Seite Parsergenerator

Im [[Compilerbau]] ist ein '''Parsergenerator''' ein Computerprogramm, das auf Grundlage einer Spezifikation einen [[Parser]] [[Codegenerator|generiert]].

== Grundlagen ==
Ein Parsergenerator erzeugt [[Unterprogramm]]e 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 [[Erweiterte Backus-Naur-Form|Erweiterter Backus-Naur-Form]] (EBNF).

Viele Parsergeneratoren benötigen einen [[Tokenizer|Scanner]] für die Symbolerkennung. Dieser Scanner wird in der Regel von einem integrierten oder externen [[Lexikalischer Scanner|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 Grammatik|kontextfreie Grammatiken]] zu erzeugen. Folgende Algorithmen werden von gängigen Parsergeneratoren verwendet:
* [[LL-Parser|LL(k)-Parsing]] ([[JavaCC]], [[Coco/R]])
* LL(*)-Parsing ([[ANTLR]])
* [[LALR-Parser|LALR(1)-Parsing]] ([[SableCC]], [[yacc]], [[GNU Bison]], Lemon)

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

== Weblinks ==
* [http://amor.cms.hu-berlin.de/~kunert/papers/lr-analyse/ „LR(k)-Analyse für Pragmatiker“]


[[Kategorie:Compilerbau]]