Parser-Generator

Parser-Generator

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.

Siehe auch

Compilerbau
lexikalischer Scanner

Weblinks

"LR(k)-Analyse für Pragmatiker"


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • LALR Parser Generator — Infobox Software name = LPG caption = developer = Philippe Charles latest release version = latest release date = latest preview version = latest preview date = operating system = platform = genre = parser/scanner generator license = EPL website …   Wikipedia

  • LL parser — An LL parser is a top down parser for a subset of the context free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser). The class of grammars which are… …   Wikipedia

  • Recursive descent parser — A recursive descent parser is a top down parser built from a set of mutually recursive procedures (or a non recursive equivalent) where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the… …   Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia

  • Simple LR parser — In computer science, a Simple LR parser or SLR parser is created by an SLR parser generator which reads a BNF grammar and constructs an LR(0) state machine and computes the look aheads sets for each reduction in a state by examining the Follow… …   Wikipedia

  • LALR parser — In computer science, a lookahead LR parser or LALR parser is a specialized form of LR parser that can deal with more context free grammars than Simple LR (SLR) parsers. It is a very popular type of parser because it gives a good trade off between …   Wikipedia

  • GLR parser — In computer science, a GLR parser ( Generalized Left to right Rightmost derivation parser ) is an extension of an LR parser algorithm to handle nondeterministic and ambiguous grammars. First described in a 1986 paper by Masaru Tomita, it has also …   Wikipedia

  • Scannerless Boolean Parser — Infobox Software name = SBP developer = Adam Megacz operating system = Java Virtual Machine genre = Parser generator license = BSD license website = [http://research.cs.berkeley.edu/project/sbp/] The Scannerless Boolean Parser is a free software… …   Wikipedia

  • LR parser — In computer science, an LR parser is a parser for context free grammars that reads input from Left to right and produces a Rightmost derivation. The term LR( k ) parser is also used; here the k refers to the number of unconsumed look ahead input… …   Wikipedia

  • Spirit Parser Framework — The Spirit Parser Framework is an object oriented recursive descent parser generator framework implemented using template metaprogramming techniques. Expression templates allow users to approximate the syntax of Extended Backus Naur Form (EBNF)… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”