imported>Aka: /* Parser für kontextfreie Grammatiken */ doppelten Link entfernt

2026-04-28T19:55:24Z

Parser für kontextfreie Grammatiken: doppelten Link entfernt

Neue Seite

Ein '''Parser''' [{{IPA|ˈpɑːʁzɐ}}] ({{enS|to parse}} „analysieren“, bzw. {{laS|pars}} „Teil“; im Deutschen gelegentlich auch '''Zerteiler''') ist ein [[Computerprogramm]], das 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 [[Formale Semantik|Semantik]] der Eingabe zu erschließen und daraufhin Aktionen durchzufü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.

Die Syntaxanalyse ''(Parsing)'' findet auch außerhalb der Informatik Anwendung, z. B. bei der Untersuchung der Struktur von [[Natürliche Sprache|natürlichen Sprachen]]. In der [[Grammatik]] würde die Syntaxanalyse eines Satzes dem Zerlegen des Satzes in seine grammatikalischen Bestandteile ([[Syntax]]) entsprechen (siehe dazu [[Linguistik]]).

== Anwendung und Beispiele ==
Im Allgemeinen wird ein Parser dazu verwendet, einen Text in eine neue Struktur zu übersetzen, z. B. in einen [[Syntaxbaum]], welcher die Hierarchie zwischen den Elementen ausdrückt.

* [[Hypertext Markup Language|HTML]]-Code besteht aus reinem Text. Der in einem [[Webbrowser]] enthaltene Parser erstellt daraus den logischen Aufbau als Datenstruktur. Das Aussehen dieser Elemente wird getrennt via [[Cascading Style Sheets|CSS]] definiert.
* [[RSS-Parser]] wandeln [[RSS (Web-Feed)|RSS]]-Feeds in ein anderes Datenformat, beispielsweise für eine HTML-Seite.
* [[XML-Parser]] analysieren [[Extensible Markup Language|XML]]-Dokumente und stellen die darin enthaltenen Informationen (also Elemente, Attribute usw.) für die weitere Verarbeitung zur Verfügung.
* [[Uniform Resource Identifier|URI]]-Parser lösen Schemata wie [[Uniform Resource Locator|URLs]] in ihren hierarchischen Aufbau auf (siehe dazu <nowiki>RFC 3986</nowiki><ref>{{RFC-Internet |RFC=3986 |Titel=Uniform Resource Identifier (URI): Generic Syntax |Datum=2005-01}}</ref>).
* [[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 [[Webcrawler|crawlen]] relevante Textpassagen.
* Auslesen einer [[Programmiersprache]]. Aus der erhaltenen Datenstruktur kann ein [[Compiler]] dann Maschinencode bzw. [[Bytecode]] erzeugen.
* Ein [[Kommandozeileninterpreter]] parst Befehle mitsamt ihren Parametern für die korrekte Ausführung der Anweisungen des Benutzers (z. B. via [[COMMAND.COM]]).
* In [[Textadventure]]s 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.

== Funktionsweise ==
Zur Analyse des Texts verwenden Parser in der Regel einen separaten [[Lexikalische Analyse|Lexer]] (auch ''lexikalischer Scanner'' genannt). Dieser zerlegt die (als simple [[Zeichenkette]] vorliegenden) Eingabedaten in [[Token (Übersetzerbau)|Token]] (Eingabesymbole bzw. „Wörter“, die der Parser versteht); weil die Zerlegung in Token einer [[Reguläre Grammatik|regulären Grammatik]] folgt, ist der Scanner meist ein [[endlicher Automat]]. Diese Token dienen als atomare Eingabezeichen des Parsers. Parser, die keinen separaten Scanner verwenden, werden ''Scannerless parsers'' genannt.

Der eigentliche Parser als [[Implementierung]] eines abstrakten [[Automat (Informatik)|Automaten]] (meist realisiert als [[Kellerautomat]]) kümmert sich dagegen um die Grammatik der Eingabe, führt eine [[Syntax|syntaktische]] Überprüfung der Eingangsdaten durch und erstellt in der Regel aus den Daten einen [[Ableitungsbaum]] (in Anlehnung an das Englische gelegentlich auch als ''Parse-Baum'' bezeichnet). Dieser wird danach zur Weiterverarbeitung der Daten verwendet; typische Anwendungen sind die [[semantische Analyse]], [[Codegenerierung]] in einem [[Compiler]] oder Ausführung durch einen [[Interpreter]].

Bei HTML würde ein lexikalischer Scanner die HTML-Datei in [[Tag (Informatik)|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.

== Parser-Typen ==
Man unterscheidet verschiedene Parse-Verfahren. Dabei wird nach genereller
Vorgehensweise, also der Unterscheidung nach der Reihenfolge, in der die
Knoten des Ableitungsbaums erstellt werden
([[Top-down und Bottom-up|top-down]], auch ''theoriegetriebenes Parsing'' oder
[[Top-down und Bottom-up|bottom-up]], auch ''eingabegetriebenes Parsing,'' sowie ''left corner''), spezifischer Vorgehensweise (LL, LR, SLR, LALR, LC, …) und Implementierungstechnik ([[Rekursiver Abstieg|rekursiv absteigend]], rekursiv aufsteigend oder tabellengesteuert) unterschieden. Weiter wird auch nach Grammatikart unterschieden.

=== Parser für kontextfreie Grammatiken ===
Hier ein paar auf [[Kontextfreie Grammatik|kontextfreien 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]]
Ein [[Top-Down-Parser]] generiert mithilfe von Regeln einer [[Formale Grammatik|formalen Grammatik]] und der Expansion der Nichtterminale einen [[Syntaxbaum]] für eine gegebene [[Zeichenkette]]. Er beginnt beim Startsymbol und arbeitet sich zu den Terminalen vor. Dabei verwendet er die Linksableitung. Es gibt zwei Typen von Top-Down-Parsern: Rekursive Abstiegsparser und nicht-rekursive Abstiegsparser. Der rekursive Abstiegsparser wird auch als ''Brute-Force-Parser'' oder ''Backtracking-Parser'' bezeichnet. Er generiert den Syntaxbaum mithilfe von Brute-Force- und Backtracking-Techniken. Der nicht-rekursive Abstiegsparser wird auch als ''[[LL-Parser]]'', ''prädiktiver Parser'', ''Parser ohne Backtracking'' oder ''dynamischer Parser'' bezeichnet. Er verwendet eine Syntaxtabelle anstelle von Backtracking, um den Syntaxbaum zu generieren.

Ein [[Bottom-up-Parser]] generiert den [[Syntaxbaum]] für eine gegebene Eingabezeichenkette mithilfe von Regeln einer [[Formale Grammatik|formalen Grammatik]], indem er die Terminalsymbole komprimiert. Er beginnt mit den Terminalsymbolen und endet mit dem Startsymbol. Dabei verwendet er die Rechtsableitung in umgekehrter Reihenfolge. Bottom-up-Parser werden in zwei Typen unterteilt: [[LR-Parser]] und Operatorpräzedenzparser. Der LR-Parser generiert den Syntaxbaum für die gegebene [[Zeichenkette]] mithilfe einer eindeutigen Grammatik. Er folgt der umgekehrten Rechtsableitung. Der Operatorpräzedenzparser generiert den Syntaxbaum aus der gegebenen Grammatik und Zeichenkette, wobei die Bedingung gilt, dass zwei aufeinanderfolgende Nichtterminalsymbole und das Epsilon niemals auf der rechten Seite einer Regel stehen dürfen.<ref>{{Internetquelle |url=https://www.geeksforgeeks.org/compiler-design/types-of-parsers-in-compiler-design/ |titel=Types of Parsers in Compiler Design |werk=GeeksforGeeks |datum=2019-07-26 |sprache= |abruf=2026-04-28}}</ref>

=== Parser für kontextsensitive Grammatiken ===
* [[Packrat Parser]] (Parsing Expression Grammars)

Das Parsen wohldefinierter künstlicher Sprachen (siehe [[formale Sprache]]n, [[Programmiersprache]]n) ist weniger komplex als das Parsen frei gewachsener [[Natürliche Sprache|natürlicher Sprachen]] wie Englisch oder Deutsch, die durch eine Vielzahl von [[Mehrdeutigkeit]]en, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auch [[Computerlinguistik]] und [[Dependenzparsing]].

''Hinweis:'' Der Begriff ''parsen'' sollte nicht mit dem Begriff ''[[Kompilierung|kompilieren]]'' verwechselt werden. Letzteres erzeugt einen Zielcode aus einem Quellcode, dabei wird unter anderem auch geparst, darüber hinaus finden aber weitere Aktionen statt.

== Beispiel ==

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
: <math>2 + (2 + 2) - \sin(\pi)</math>.
Dieser Ausdruck, so wie er hier steht, besteht erstmal nur aus einer Reihe von Symbolen. Es ist die Aufgabe eines [[Tokenizer]]s als Teil eines Parsers, diese Symbole (zum Beispiel in [[Leserichtung]] von links nach rechts) zu identifizieren und einzuordnen. Das Ergebnis ist eine [[Liste (Datenstruktur)|Liste]], die im Folgenden als Tabelle dargestellt wird und Zeile für Zeile zu lesen ist:

{| class="wikitable"
|- class="hintergrundfarbe5"
! Symbol !! Kategorie !! Erläuterung
|-
| 2 || Zahl ||
|-
| + || Rechenzeichen ||
|-
| ( || Klammer auf ||
|-
| 2 || Zahl ||
|-
| + || Rechenzeichen ||
|-
| 2 || 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 das in Form eines [[Parsebaum]]s (''abstrakter Syntaxbaum''), der in diesem Fall so aussehen kann:


[[Datei:Parser-Organigram.svg|800px]]

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

== Siehe auch ==
* [[Compilerbau]]
* [[Parsergenerator]]
* [[Generative Programmierung]]

== Literatur ==
* 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.

== Weblinks ==
{{Wiktionary}}
* [https://github.com/MathosProject/Mathos-Parser Mathos Parser] – mathematical expression parser in C# (englisch)
* [https://www.dickgrune.com/Books/PTAPG_1st_Edition/ Parsing Techniques – A Practical Guide] (englisch)
* [https://www.cis.lmu.de/~leiss/parsing-06-07/parsingfolien.pdf Syntaxanalyse (Parsing)] ([[PostScript|PS]])

== Einzelnachweise ==
<references />

[[Kategorie:Compilerbau]]
[[Kategorie:Computerlinguistik]]
[[Kategorie:Programmierwerkzeug]]

Parser - Versionsgeschichte

imported>Aka: /* Parser für kontextfreie Grammatiken */ doppelten Link entfernt