EinParser [ˈpɑːʁzɐ] (englischto parse „analysieren“, bzw.lateinischpars „Teil“; im Deutschen gelegentlich auchZerteiler) ist einComputerprogramm, das in derInformatik 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 dieSemantik der Eingabe zu erschließen und daraufhin Aktionen durchzuführen.

Im Vergleich zu einemRecognizer, der die Eingabe analysiert und ausgibt, ob diese im Sinne der Vorgabenrichtig oderfalsch ist, gibt der Parser die Analyse einer Eingabe in einer gewünschten Form aus und erzeugt zusätzlich Strukturbeschreibungen.

Die Syntaxanalyse(Parsing) findet auch außerhalb der Informatik Anwendung, z. B. bei der Untersuchung der Struktur vonnatürlichen Sprachen. In derGrammatik würde die Syntaxanalyse eines Satzes dem Zerlegen des Satzes in seine grammatikalischen Bestandteile (Syntax) entsprechen (siehe dazuLinguistik).

Im Allgemeinen wird ein Parser dazu verwendet, einen Text in eine neue Struktur zu übersetzen, z. B. in einenSyntaxbaum, welcher die Hierarchie zwischen den Elementen ausdrückt.

• HTML-Code besteht aus reinem Text. Der in einemWebbrowser enthaltene Parser erstellt daraus den logischen Aufbau als Datenstruktur. Das Aussehen dieser Elemente wird getrennt viaCSS definiert.
• RSS-Parser wandelnRSS-Feeds in ein anderes Datenformat, beispielsweise für eine HTML-Seite.
• XML-Parser analysierenXML-Dokumente und stellen die darin enthaltenen Informationen (also Elemente, Attribute usw.) für die weitere Verarbeitung zur Verfügung.
• URI-Parser lösen Schemata wieURLs in ihren hierarchischen Aufbau auf (siehe dazu RFC 3986^[1]).
• Logdatei-Parser dienen zum Extrahieren von relevanten Informationen ausWebserver-Protokolldateien, Ereignisprotokollen und anderer in Logdateien gespeicherter Informationen zur automatisierten Analyse.
• Suchmaschinen parsen Webseiten undcrawlen relevante Textpassagen.
• Auslesen einerProgrammiersprache. Aus der erhaltenen Datenstruktur kann einCompiler dann Maschinencode bzw.Bytecode erzeugen.
• EinKommandozeileninterpreter parst Befehle mitsamt deren Parameter für die korrekte Ausführung der Anweisungen des Benutzers (z. B. viaCOMMAND.COM).
• InTextadventures erfolgt die Steuerung der Spielfigur über die Eingabe von Befehlen in natürlicher Sprache, z. B. „Schließe die Haustür mit dem Hausschlüssel auf“. 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.

Zur Analyse des Texts verwenden Parser in der Regel einen separatenLexer (auchlexikalischer Scanner genannt). Dieser zerlegt die (als simpleZeichenkette vorliegenden) Eingabedaten inToken (Eingabesymbole bzw. „Wörter“, die der Parser versteht); weil die Zerlegung in Token einerregulären Grammatik folgt, ist der Scanner meist einendlicher Automat. Diese Token dienen als atomare Eingabezeichen des Parsers. Parser, die keinen separaten Scanner verwenden, werdenScannerless parsers genannt.

Der eigentliche Parser als Implementierung eines abstraktenAutomaten (meist realisiert alsKellerautomat) kümmert sich dagegen um die Grammatik der Eingabe, führt einesyntaktische Überprüfung der Eingangsdaten durch und erstellt in der Regel aus den Daten einenAbleitungsbaum (in Anlehnung an das Englische gelegentlich auch alsParse-Baum bezeichnet). Dieser wird danach zur Weiterverarbeitung der Daten verwendet; typische Anwendungen sind diesemantische Analyse,Codegenerierung in einemCompiler oder Ausführung durch einenInterpreter.

Bei HTML würde ein lexikalischer Scanner die HTML-Datei in HTML-Tags und Fließtext zerlegen und diese Bestandteile an den Parser weiterreichen – d. h. den Scanner „interessiert“ nur das Aussehen der Syntaxelemente („wenn es in spitzen Klammern steht, ist es ein HTML-Tag“). Der Parser dagegen verarbeitet die syntaktischen Zusammenhänge, d. h. untersucht, welche Paare von Tags zusammengehören bzw. wie die Tags ineinander verschachtelt sind; die inhaltliche Bedeutung der Tags interessiert den Parser dagegen nicht, sondern wird erst von der darauf folgenden Weiterverarbeitung berücksichtigt.

Anschaulich dargestellt ist ein Parser diejenige Software, welche die Anweisungen im Quelltext des Anwenders überprüft, weiterverarbeitet und weiterleitet.

Man unterscheidet verschiedene Parse-Verfahren. Dabei wird nach generellerVorgehensweise, also der Unterscheidung nach der Reihenfolge, in der dieKnoten des Ableitungsbaums erstellt werden(top-down, auchtheoriegetriebenes Parsing oderbottom-up, aucheingabegetriebenes Parsing, sowieleft corner), spezifischer Vorgehensweise (LL, LR, SLR, LALR, LC, …) und Implementierungstechnik (rekursiv absteigend, rekursiv aufsteigend oder tabellengesteuert) unterschieden. Weiter wird auch nach Grammatikart unterschieden.

Hier ein paar aufkontextfreien Grammatiken basierende Verfahren:

• Top-Down-Parser
  • LF-Parser
  • LL-Parser
• Bottom-up-Parser
  • LR-Parser
  • SLR-Parser
  • LALR-Parser
• Chart-Parser
• Left-Corner-Parser
  • LC-Parser

• Packrat Parser (Parsing Expression Grammars)

Das Parsen wohldefinierter künstlicher Sprachen (sieheformale Sprachen,Programmiersprachen) ist weniger komplex als das Parsen frei gewachsenernatürlicher Sprachen wie Englisch oder Deutsch, die durch eine Vielzahl vonMehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auchComputerlinguistik.

Hinweis: Der Begriffparsen sollte nicht mit dem Begriffkompilieren verwechselt werden. Letzteres erzeugt einen Zielcode aus einem Quellcode, dabei wird unter anderem auch geparst, darüber hinaus finden aber weitere Aktionen statt.

Parser werden häufig eingesetzt, um aus einer Aneinanderreihung von Symbolen eine Baumstruktur zu machen. Ein typisches Beispiel dafür sind mathematische Ausdrücke wie

${\displaystyle 2+(2+2)-\sin (\pi )}$.

Dieser Ausdruck, so wie er hier steht, besteht erstmal nur aus einer Reihe von Symbolen. Es ist die Aufgabe einesTokenizers als Teil eines Parsers, diese Symbole (zum Beispiel inLeserichtung von links nach rechts) zu identifizieren und einzuordnen. Das Ergebnis ist eineListe, die im Folgenden als Tabelle dargestellt wird und Zeile für Zeile zu lesen ist:

Die (weitere) Aufgabe des Parsers ist nun, die zugrundeliegende Struktur dieser Symbolfolge zu erkennen. Häufig geschieht das in Form einesParsebaums (abstrakter Syntaxbaum), der in diesem Fall so aussehen kann:

Dies ist die Ausgabe eines einfachen Parsers. Diese Ausgabe kann nun durch weitere Programme analysiert werden.

• Compilerbau
• Parsergenerator
• Generative Programmierung

• A. W. Appel:Modern Compiler Implementation in Java. Cambridge 1998.
• Paul Bennett:A Course in Generalized Phrase Structure Grammar. UCL Press, London 1995,ISBN 1-85728-217-5.
• Robert D. Borsley:Syntactic Theory. A unified approach. Edward Arnold, London 1991. 2. überarbeitete Auflage: 1998,ISBN 0-340-70610-4. Deutsche Übersetzung:Syntax-Theorie. Ein zusammengefasster Zugang. Niemeyer Verlag, Tübingen 1997,ISBN 3-484-22055-4.
• Sven Naumann, Hagen Langer:Parsing. Teubner Verlag, 1994.

Wiktionary: Parser – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Mathos Parser – mathematical expression parser in C# (englisch)
• Parsing Techniques – A Practical Guide (englisch)
• Syntaxanalyse (Parsing) (PS)

1. ↑RFC:3986 –Uniform Resource Identifier (URI): Generic Syntax. Januar 2005 (englisch).

• Compilerbau
• Computerlinguistik
• Programmierwerkzeug