Parser

Funktionsweise

Mithilfe einer lexikalischen Analyseschnittstelle, die auch Lexer genannt wird, unterteilt der Parser eine Eingabe. Er zerlegt den Quelltext in sogenannte Token. Innerhalb einer formalen Grammatik repräsentiert ein Token eine Zeichenkette, die auch als Lexem bezeichnet wird. Ihr wird ein entsprechender Typ zugewiesen.

Das Lexem “begin” kann so in der jeweiligen Programmiersprache zum Beispiel als ein Schlüsselwort erkannt werden, dem eine bestimmte Ausführungsanordnung zugrunde liegt. Diese führt dann bereits definierte Aktionen aus, die der Programmiersprache zugehören. Die Zeichenkette 345 wiederum wird dem Zeichentyp Zahl zugeordnet.

Die Zerlegung der Token unterliegt einer regulären Grammatik, weshalb die meisten lexikalischen Scanner endliche Automaten sind. Als scannerless Parsers werden diejenigen Parser bezeichnet, die auf die Verwendung eines Lexers verzichten.

Nach der Eingabe erfolgt eine syntaktische Überprüfung. Aus den Eingabedaten wird eine Struktur erstellt, die im Deutschen als Ableitungsbaum oder Syntax-Baum und im Englischen als parse tree bezeichnet wird. Anschließend wird der Ableitungsbaum zur Generierung des Codes weiterverwendet.

Letztlich ist der Parser dafür verantwortlich Eingaben auf ihre Richtigkeit zu überprüfen und diese in eine maschinell auslesbare Sprache umzuwandeln. Bei einer fehlerhaften Eingabe gibt er zum Schluss Warnungen und Fehlermeldungen aus. Syntaxfehlern wird die jeweilige Spalte zugeordnet, sodass der Programmierer die Stelle im Code schnell findet und den Fehler beheben kann.

Zuweilen reicht dies allerdings nicht aus, da der Fehler bereits vor der genannten Stelle entstanden sein kann, weshalb Programme einen längeren Debugging-Prozess durchlaufen müssen. Das Debugging ermöglicht dem Programmierer Schritt für Schritt durch den Programmablauf zu gehen, um so die Fehlerquelle ausfindig zu machen.

Parsing-Verfahren

Top Down

Ein Ableitungsbaum kann beim Parsing auf unterschiedliche Weise erstellt werden. Die Bezeichnung richtet sich ganz nach der Reihenfolge, in der der Ableitungsbaum konstruiert wird. Beim Top Down Parsing wird auf der höchsten Ebene mit dem Startsymbol des Codes angefangen.

Der Syntax-Baum wird von oben nach unten konstruiert und es wird mit der Wurzel (Top) angefangen. Die Blätter (Bottom) werden schrittweise ausgefüllt. Der Syntax-Baum gliedert sich so immer weiter auf und der Quellcode wird vom Parser in eine formale Grammatik übertragen.

Bottom Up

Beim Bottom Up Parsing wird sich hingegen in umgekehrter Richtung orientiert. Dieses Parsing-Verfahren fängt mit der kleinsten vorgefundenen Einheit (Blättern) an und arbeitet sich nach und nach zum Startsymbol (Wurzel) des Codes vor. Beide Methoden werden in der Informatik als effizient beschrieben.

Der Vorteil gegenüber dem Top Down Parsing besteht vorwiegend darin, dass der Parser grundsätzlich an jeder beliebigen Stelle des Codes mit der Syntax-Prüfung anfangen kann. Zuweilen kann es beim Top Down Parsing nämlich dazu kommen, dass der Parser ein Backtracking vornehmen muss. Dies ist etwa der Fall, wenn ein Abzweigeversuch fehlschlägt. Die Syntax-Analyse wird beim Backtracking noch einmal neu gestartet und folgt dann einem alternativen Regelsatz.

Anwendungsbeispiele

• Jeder Webbrowser verfügt über einen eigenen Parser, der den HTML-Code einer Webseite auslesen und in eine neue Datenstruktur übersetzen kann. Das Aussehen der Seite wird dann über CSS definiert.
• Parsing kommt auch dann zum Einsatz, wenn die Suchmaschinen sich im Netz orientieren, um relevante Textinformationen zu gewinnen.
• Die im Datenformat XML enthaltenen Informationen werden beim XML-Parsing in eine übersichtliche Tabellenform übertragen, die anschließend vom Nutzer bearbeitet werden kann.
• Text-Adventures benutzen ebenfalls Parsing. Einfache Befehle, wie etwa “Öffne Tür” werden vom Programm ausgelesen und umgesetzt. Die Tür wird geöffnet und der Spieler kann den Raum betreten.
• Programmiersprachen werden beim Parsing ausgelesen und anschließend dem Compiler übergeben.

Verfeinerte Parsing-Methoden

Top Down und Bottom Up gehören zu den am häufigsten verwendeten Parsing-Methoden. Für spezielle Problemlösungen bieten sich allerdings noch weitere verfeinerte Methoden zur Klassifizierung an.

Eine Methode für kontextfreie Grammatiken ist zum Beispiel das Chart-Parsing, welches Teilanalysen in einer Tabelle vermerkt. Es bietet sich für kontextfreie Sprachen an, da es effizienter und schneller in solchen Fällen arbeitet, als die konventionellen Parsing-Verfahren.

Letztlich ist für die Wahl des Parser-Typs immer entscheidend, welches Ziel erreicht werden soll und welche Methode die besten Ergebnisse liefert. Grundsätzlich stehen dem Anwender so immer Optimierungsmöglichkeiten zur Verfügung.