Definition „Zerteiler“ Was ist ein Parser?

Parser analysieren Zeichenketten und bereiten den Quelltext auf. Auf diese Weise wandeln sie den Code in eine Repräsentation um, mit der andere Programme wie Compiler oder HTML-Renderer arbeiten können.

Anbieter zum Thema

PresseBox - unn | UNITED NEWS NETWORK GmbH

Confluent Germany GmbH

Damit aus Quellcode ein Programm wird, muss es zum Beispiel per Compiler in eine ausführbare Form gebracht werden. Meistens kann der Compiler jedoch nicht direkt verstehen, was im Quellcode steht.

Viele Programmiersprachen, vor allem moderne Hochsprachen, sind so gestaltet, dass sie für Programmierer komfortabel und übersichtlich sind. Der Compiler hat zum Beispiel keine Verwendung für Kommentare oder unsichtbare Symbole wie Leerzeichen. Er benötigt vor allem Informationen wie die verwendeten Schlüsselwörter, Werte oder Operatoren. Außerdem er muss wissen, wie diese zusammenhängen.

Die Informationen aus dem Quelltext müssen also analysiert, aufbereitet und nach einem bestimmten Schema strukturiert werden, um für den Compiler verwertbar zu sein. Diese Aufgabe übernimmt ein Parser. Immer, wenn die Eingabe einer kontextfreien Grammatik folgt, kann sie mit dem passenden Parser maschinell analysiert und aufbereitet werden.

Lexer leisten die Vorarbeit für Parser

Ein Parser kann also Eingaben analysieren und daraus eine hierarchische Repräsentation der Informationen erstellen, die für die weitere Verarbeitung nötig sind. Hierzu müssen die eingelesenen Informationen in die kleinstmöglichen Bestandteile zerlegt werden, die nach den Regeln der jeweiligen Grammatik möglich sind. Dabei wird außerdem analysiert, wie diese Bestandteile logisch zueinander in Beziehung stehen.

Intern wird das Zerlegen von einem lexikalischen Scanner (kurz: Lexer, auch Tokenizer) übernommen. Lexer können zusammengehörende Zeichenketten innerhalb einer Eingabe erkennen und als Token zurückgeben. Token sind logisch zusammenhängende Komponenten, bestehend aus einem Terminal der Grammatik (z. B. Typ) und dem zugeordneten Nichtterminal (z.B. Wert).

Als kleines Beispiel zum besseren Verständnis: Der Ausdruck 4+7 besteht aus den Token „Zahl 4“, „Operator +“ und „Zahl 7“. Der Parser nimmt die so aufbereiteten Informationen Token für Token entgegen und wandelt sie nach und nach in die für die weitere Verarbeitung erforderliche Repräsentation um.

Eingaben werden zu strukturierten Informationen

Mit dem Ergebnis der lexikalischen Analyse führt der Parser eine syntaktische Analyse durch. Sie dient dazu, die Informationen in eine hierarchische Struktur zu bringen. In der Regel wird die Hierarchie mit einem Syntaxbaum (Parsebaum) repräsentiert. Der Syntaxbaum schlüsselt die Eingabe in immer feinere Ausdrücke auf, bis alles auf einzelne Token heruntergebrochen ist.

Die inneren Knoten sind Nichtterminalsymbole (z. B. nicht vollständig zerlegte Ausdrücke, Funktionsaufrufe), die Blätter entsprechen Terminalsymbolen der Grammatik (Token). Der simple Ausdruck 4+7 könnte direkt in drei gleichrangige Blätter „Zahl 4“, „Operator +“ und „Zahl 7“ zerlegt werden, der Ausdruck 4+(3+4) würde zunächst in das Blatt „Zahl 4“ und den inneren Knoten „Ausdruck (3+4)“ abgeleitet und danach weiter aufgeschlüsselt.

Verschiedene Parser-Typen

Man unterscheidet verschiedene Typen von Parsern, darunter vor allem Top-Down-Parser und Bottom-Up-Parser. Diese beiden Typen unterscheiden sich hauptsächlich darin, dass sie unterschiedliche Anfangs- und Endpunkte für den Aufbau des Syntaxbaumes haben.

Top-Down-Parser: Top-Down-Parser (z. B. LL- und LF-Parser) arbeiten sich per Ableitung vom Startsymbol zu den einzelnen Token: Die Analyse läuft vom gesamten Quelltext zu den enthaltenen Funktionen und Ausdrücken und schließlich zu den darin enthaltenen Token.

Bottom-Up-Parser: Beim Bottom-Up-Parser (z. B. verschiedene LR-Parser) beginnt die Verarbeitung mit einem Token, also einem Blatt des Baumes. Er arbeitet sich per Reduktion von einzelnen Token zu größeren Zusammenhängen wie Ausdrücken und Funktionen vor, bis er das Startsymbol erreicht. Beim Bottom-Up-Parser signalisiert das Startsymbol also, dass die Eingabe vollständig analysiert wurde.

Parsergenerator

Mit einem Parsergenerator ist es möglich, automatisch einen effizienten Parser für ein vorgegebenes lexikalisches System zu erstellen. Außerdem gibt es Scannergeneratoren, die aus einer formalen Beschreibung einen lexikalischen Scanner erzeugen. Solche Tools werden zum Beispiel im Compilerbau verwendet - vollwertige Compilergeneratoren sind derzeit noch experimentell.

Parser benötigen korrekt strukturierte Eingaben

Ein Parser ist in der Regel darauf angewiesen, dass die Eingaben eine bestimmte Syntax einhalten. Anweisungen müssen beispielsweise einem standardisierten Format folgen, um korrekt von einem Parser erkannt zu werden.

XML zum Beispiel ist eine weit verbreitete Auszeichnungssprache, mit der Informationen hierarchisch strukturiert werden können. Das Format ist für Menschen direkt und für Maschinen mittels XML-Parser lesbar. Allerdings funktioniert der XML-Parser nur, wenn die Struktur fehlerfrei ist.

Stünde nun ein unerwartetes Zeichen an erster Stelle, könnte im Extremfall die syntaktische Analyse des gesamten Dokuments daran scheitern. Die meisten Parser melden, wenn sie eine fehlerhafte Syntax feststellen. Das hilft nicht nur bei der Fehlersuche, sondern trägt schon während der Entwicklung zur Vermeidung vieler Fehler bei.

(ID:45501105)