Parser

Ein Parser prüft, ob eine Folge von Symbolen von der Grammatik der Quellsprache erzeugt werden kann. Dabei wird von einem Parser erwartet, dass dieser bei Syntaxfehlern aussagekräftige Meldungen liefert. Außerdem sollte ein Parser üblicherweise auftretende Fehler auf eine Art behandeln, die es ihm erlaubt, auch den Rest der Eingabe weiter zu bearbeiten. Die Abbildung verdeutlicht die Rolle des Parsers im Compiler-Modell.


Parser für Grammatiken lassen sich in drei Kategorien einteilen: Universelle Parse-Methoden wie z.B. die Algorithmen von Cocke-Younger-Kasami und Early funktionieren für alle Grammatiken. Für den praktischen Einsatz sind diese Methoden jedoch zu ineffizient. Die in Compilern überwiegend verwendeten Methoden lassen sich als "Top-Down"- oder "Bottom Up"-Methoden klassifizieren. Nach der Graphentheorie beginnt ein Top-Down-Parser die Konstruktion des sogenannten Parse-Baums mit der Wurzel ("Top") und setzt seine Arbeit in Richtung der Blätter ("Bottom") fort, während sich ein Bottom-Up-Parser von den Blättern her zu den Wurzeln hocharbeitet. Beide Parser-Typen lesen die Symbole der Eingabe sukzessive von links nach rechts.

Rolle 
   des Parsers im Compiler-Modell

Rolle des Parsers im Compiler-Modell

Die effizienten Top-Down- und Bottom-Up-Methoden sind auf Teilklassen von Grammatiken beschränkt. Einige dieser Teilklassen, wie z.B. LL- und LR-Grammatiken, sind jedoch mächtig genug, um die meisten syntaktischen Konstrukte in Programmier-sprachen beschreiben zu können. Von Hand geschriebene Parser arbeiten überwiegend mit LL-Grammatiken. Automatisierte Werkzeuge generieren in der Regel Parser für die größere Klasse der LR-Grammatiken.

In der Praxis sind während des Parse-Prozesses eine Reihe weiterer Aufgaben durchzuführen. Zum Beispiel müssen in der Symboltabelle Informationen über die verschiedenen Symbole gesammelt, Typüberprüfungen und andere Aufgaben der semantischen Analyse durchgeführt und Zwischencode generiert werden.

Informationen zum Artikel
Deutsch: Parser
Englisch: parser
Veröffentlicht: 09.04.2012
Wörter: 278
Tags: #Web-Software
Links: Algorithmus, Cat (category), Compiler, Information, Klasse