Ein Parser, von „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler genannt, ist ein Computerprogramm, dass in der Informatik für die Zerlegung und Umwandlung einer Eingabe in ein für die Weiterverarbeitung geeigneteres Format zuständig ist. Häufig werden Parser eingesetzt, um im Anschluss an den Analysevorgang die Semantik der Eingabe zu erschließen, um im Anschluss Aktionen auszuführen.

Im Vergleich zu einem Recognizer, der die Eingabe analysiert und ausgibt, ob diese im Sinne der Vorgaben richtig oder falsch ist, gibt der Parser die Analyse einer Eingabe in einer gewünschten Form aus und erzeugt zusätzlich Strukturbeschreibungen.

Wie funktioniert ein Parser?

Zur Analyse des Texts verwenden Parser in der Regel einen separaten Lexer. Dieser zerlegt die als Zeichenkette vorliegenden Eingabedaten in Token (Eingabesymbole bzw. „Wörter“, die es versteht). Weil die Zerlegung in Token einer regulären Grammatik folgt, ist der Scanner meist ein endlicher Automat. Token dienen als atomare Eingabezeichen des Parsers. Parser, die keinen separaten Scanner verwenden, nennt man Scannerless Parser.

Der eigentliche Parser als Implementierung eines abstrakten Automaten, meist realisiert als Kellerautomat, kümmert sich dagegen um die Grammatik der Eingabe, führt eine syntaktische Überprüfung der Eingangsdaten durch und erstellt in der Regel aus den Daten einen Ableitungsbaum, den man im Anschluss zur Weiterverarbeitung der Daten verwendet. Typische Anwendungen sind die semantische Analyse, Codegenerierung in einem Compiler oder die Ausführung durch einen Interpreter.

Bei HTML zerlegt ein lexikalischer Scanner beispielsweise die HTML-Datei in HTML-Tags und Fließtext. Diese Bestandteile reicht es dann an den Parser weiter. Der Scanner ist also ausschließlich auf das Aussehen der Syntaxelemente aus. Spitze Klammern = HTML-Tag 😉 Siehe auch meinen Beitrag über HTML.

Der Parser übernimmt die übernimmt die Verarbeitung der syntaktischen Zusammenhänge, untersucht, welche Paare von Tags zusammengehören bzw. wie die Tags ineinander verschachtelt sind. Die inhaltliche Bedeutung der Tags interessiert den Parser dagegen nicht. Die Berücksichtigung findet erst in der darauffolgenden Weiterverarbeitung statt.

Veranschaulicht, ist ein Parser die Software, welche die Anweisungen im Quelltext des Users überprüft, weiterverarbeitet und weiterleitet.

Welche Typen von Parsern gibt es?

Man unterscheidet bei der allgemeinen Vorgehensweise verschiedene Parse-Verfahren. Folglich erfolgt die Unterscheidung nach der Reihenfolge, in der die Knoten des Ableitungsbaums erstellt sind. Beispiele hierfür sind: Top-Down, auch theoriegetriebenes Parsing; Bottom-Up, auch eingabegetriebenes Parsing; Left Corner, spezifischer Vorgehensweise (LL, LR, SLR, LALR, LC, …) und Implementierungstechnik (rekursiv absteigend, rekursiv aufsteigend oder tabellengesteuert) unterschieden. Weiter erfolgt die Unterscheidung auch, wie bereits erwähnt, nach der Grammatikart.

Parser für kontextsensitive Grammatiken

Das Parsen wohldefinierter künstlicher Sprachen, hierbei ist natürlich die Rede von Programmiersprachen, ist weniger komplex als das Parsen frei gewachsener natürlicher Sprachen wie Englisch, Deutsch oder einer anderen Sprache, die durch eine Vielzahl von Mehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Wobei man hierüber mehr in der Computerlinguistik erfährt, über die ich in einem zukünftigen Beitrag schreiben werde.

Fallbeispiel

Man setzt Parser häufig ein, um eine Aneinanderreihung von Symbolen zu einer Baumstruktur zu adaptieren. Dies kann bei einem mathematischen Ausdruck folgenderweise aussehen:

7+(7+7)-sin(π) 

Symbol	Kategorie	Erläuterung
7	Zahl
+	Rechenzeichen
(	Klammer auf
7	Zahl
+	Rechenzeichen
7	Zahl
)	Klammer zu
–	Rechenzeichen
sin	Symbolname	(hier: die Sinus-Funktion)
(	Klammer auf
π	Symbolname	(hier: die Kreiszahl π)
)	Klammer zu

Die weitere Aufgabe des Parsers ist nun, die zugrundeliegende Struktur dieser Symbolfolge zu erkennen. Häufig geschieht dies in Form eines Parsebaums (abstrakter Syntaxbaum), der in diesem Fall folgendermaßen aussehen kann:

Wo finden Parser Anwendung

• HTML-Code besteht aus reinem Text. Der in einem Webbrowser standardmäßig enthaltene Parser erstellt daraus den logischen Aufbau als Datenstruktur. Das Aussehen dieser Elemente wird getrennt via CSS definiert.
• XML-Parser analysieren XML-Dokumente und stellen die darin enthaltenen Informationen für die weitere Verarbeitung zur Verfügung.
• RSS-Parser wandeln RSS-Feeds in ein passendes Datenformat um. Beispielsweise für eine HTML-Seite.
• URI-Parser lösen Schemata wie URLs in ihren hierarchischen Aufbau auf.
• Logdatei-Parser dienen zum Extrahieren von relevanten Informationen aus Webserver-Protokolldateien, Ereignisprotokollen und anderer in Logdateien gespeicherter Informationen zur automatisierten Analyse.
• Suchmaschinen parsen Webseiten und crawlen relevante Textpassagen.
• Auslesen einer Programmiersprache. Aus der erhaltenen Datenstruktur kann ein Compiler dann Maschinencode bzw. Bytecode erzeugen.
• Ein Kommandozeileninterpreter parst Befehle mitsamt deren Parameter für die korrekte Ausführung der Anweisungen des Benutzers. Das ältere Publikum, die mit DOS vertraut sind, kennen dies vielleicht noch aus der command.com Datei 😉
• In Textadventures wie erfolgt die Steuerung der Spielfigur über die Eingabe von Befehlen in natürlicher Sprache, z. B. „Gehe in den Raum“, „Öffne Tür“ usw. Der Parser greift auf eine Datenbank aller manipulierbarer Objekte im Spiel zu und analysiert, welche Interaktion mit welchen Objekten der Spielwelt der Spieler mit seiner Befehlseingabe meinte.

Fazit

Es gibt verschiedene Parser. Je nach der zu analysierenden Grammatik sucht man sich den passenden Parser aus. Durch die richtige Wahl resultieren bessere und akkuratere Ergebnisse. Durch den Einsatz von diversen Parsern ist es auch möglich, sich relevante Informationen aus den verschiedensten Quellen heranzuziehen. Angefangen von Börsen Daten, über Wetterinformationen und bis hin zu allem, was das Herz begehrt. Sowohl die Anwendungsentwicklung, als auch das Web ist heute ohne einen Parser kaum mehr vorstellbar.