Parser

aus Wikipedia, der freien Enzyklopädie

Ein Parser [ˈpɑːɹsɚ] (engl. to parse „analysieren“ bzw. von lateinisch pars „Teil“; weshalb Parser im Deutschen gelegentlich auch als Zerteiler bezeichnet werden; auch Syntaxanalyse) ist ein Computerprogramm^[1], das für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für die Weiterverarbeitung brauchbares Format zuständig ist.^[2]

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

Inhaltsverzeichnis 1 Anwendung 2 Funktionsweise 3 Parser-Typen 3.1 Parser für kontextfreie Grammatiken 3.2 Parser für kontextsensitive Grammatiken 4 Quellen 5 Siehe auch 6 Weblinks 7 Literatur

[Bearbeiten] Anwendung

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.

• HTML-Code ist beispielsweise für einen Computer zunächst einmal nichts anderes als ein Text, also eine Aneinanderreihung von Buchstaben und Zeichen. Der in einem Webbrowser enthaltene Parser analysiert das HTML und erstellt daraus eine Beschreibung der Webseite als Datenstruktur, welche die Grafik-Maschine des Browsers anschließend graphisch auf den Bildschirm überträgt.
• RSS-Parser wandeln RSS-Feeds in einen HTML-Text um. (siehe dazu RSS-Parser)
• XML-Parser analysieren XML-Dokumente und stellen die darin enthaltenen Informationen (also Elemente, Attribute usw.) der weiteren Verarbeitung zur Verfügung.
• URI-Parser lösen beispielsweise Schemata wie http in ihren hierarchischen Aufbau auf (siehe dazu RFC 3986)
• Log Parser dienen zum Extrahieren von Daten aus IIS-Protokolldateien, Ereignisprotokollen und anderer in Logfiles bzw. Protokolldateien gespeicherter Informationen.^[3]
• Suchmaschinen extrahieren (parsen) nach dem Herunterladen und Analysieren (Crawler) die für sie relevanten Textpassagen und bereiten die extrahierten Daten für das Durchsuchen auf (Indexer)
• Parser-Funktionen in der Wikipedia - siehe Vorlagenprogrammierung^[4]
• Text-Parser als Kommunikationsschnittstelle zwischen Spieler und Spiel (vgl. Adventures)
• Auslesen einer höheren Programmiersprache, wie beispielsweise C; Aus der erhaltenen Datenstruktur kann ein Compiler dann Maschinencode erzeugen.^[5]

[Bearbeiten] Funktionsweise

Zur Analyse des Texts verwenden Parser in der Regel einen separaten lexikalischen Scanner (auch Lexer genannt). Dieser zerlegt die (als simple Aneinanderreihung von Zeichen vorliegenden) Eingabedaten in Token (Eingabesymbole bzw. „Wörter“, die der Parser versteht); weil die Zerlegung in Tokens einer regulären Grammatik folgt, ist der Scanner meist ein endlicher Automat. Diese Token dienen als atomare Eingabezeichen des Parsers.

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 (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.

Im obigen HTML-Beispiel 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 zusammen gehö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.

[Bearbeiten] Parser-Typen

Man unterscheidet verschiedene Parse-Verfahren. Dabei wird nach genereller Vorgehensweise^[6] (top-down^[7], bottom-up^[8] oder left corner), spezifischer Vorgehensweise (LL, LR, SLR, LALR, LC, …) und Implementierungstechnik (rekursiv absteigend/„recursive-descent“, rekursiv aufsteigend/„recursive-ascent“, tabellengesteuert) unterschieden. Weiter wird auch nach Grammatikart unterschieden.

[Bearbeiten] Parser für kontextfreie Grammatiken

Hier ein paar auf 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

[Bearbeiten] Parser für kontextsensitive Grammatiken

• Packrat-Parser (Parsing Expression Grammars)

Das Parsen wohldefinierter künstlicher Sprachen (siehe formale Sprachen, Programmiersprachen) ist weniger komplex als das Parsen frei gewachsener natürlicher Sprachen^[9] wie Englisch oder Deutsch, die durch eine Vielzahl von Mehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auch Computerlinguistik.

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

[Bearbeiten] Quellen

1. ↑ Die Syntaxanalyse oder Parsing findet auch außerhalb der Informatik Anwendung, sofern es um Untersuchung der Struktur von Sprachen geht. So beispielsweise auch bei der Syntaxanalyse eines Satzes. - siehe dazu Linguistik
2. ↑ In der Grammatik würde das dem Zerlegen eines Satzes in seine grammatikalischen Bestandteile (Syntax) entsprechen.
3. ↑ vgl. dazu beispielsweise Die Arbeitsweise von Log Parser 2.2
4. ↑ siehe auch ParserFunctions
5. ↑ Heyer, G. - Algorithmen und Datenstrukturen II Kapitel 10 - Syntaxanalyse (Parsing)
6. ↑ Unterscheidung hinsichtlich der Reihenfolge, in der die Kontoen des Derivationsbaums erstellt werden
7. ↑ theoriegetriebenes Parsing
8. ↑ inputgetriebenes Parsing
9. ↑ vergleiche dazu Marcus Parser

[Bearbeiten] Siehe auch

• Recognizer
• Computerlinguistik
• Compiler
• Compilerbau
• Parsergenerator
• Generative Programmierung

[Bearbeiten] Weblinks

• Parsing Techniques – A Practical Guide (englisch)
• Syntaxanalyse (Parsing) (PS)

[Bearbeiten] Literatur

• A. W. Appel: Modern Compiler Implementation in Java. Cambridge, 1998
• Paul Bennett: A Course in Generalized Phrase Structure Grammar. London: UCL Press. 1995. ISBN 1857282175
• Robert D. Borsley: Syntactic Theory. A unified approach. London: Edward Arnold. 1991. (2nd revised edition 1998 ISBN 0340706104. Deutsche Übersetzung: Syntax-Theorie. Ein zusammengefasster Zugang. Tübingen: Niemeyer Verlag. 1997. ISBN 3484220554)
• Sven Naumann, Hagen Langer: Parsing, Teubner Verlag, 1994