Parser

Ein Parser (englisch: to parse - analysieren, deutsch: Zerteiler) ist ein Programm, das meist Teil eines Compilers ist. Der Compiler sorgt dafür, dass der Programmcode korrekt in eine maschinell ausführbare Maschinensprache übersetzt wird. Die Aufgabe des Parsers ist hierbei die Zerlegung und Umwandlung des Inputs in ein brauchbares Format für die Weiterverarbeitung. Es wird also zum Beispiel eine in Programmiersprache formulierte Befehlskette syntaktisch analysiert und dann in die einzelnen Bestandteile aufgegliedert.

Funktionsweise

Um einen gegebenen Text zu analysieren, verwenden Parser meistens einen separaten lexikalischen Scanner (genannt Lexer), welcher die Eingabedaten in Token (Eingabesymbole, z.B. Wörter) zerlegt. Bei dem Lexer handelt es sich meist um einen endlichen Automaten, welcher einer regulären Grammatik folgt und somit eine korrekte Zerlegung garantiert. Die erhaltenen Token dienen daraufhin als Eingabezeichen für den Parser.

Der eigentliche Parser kümmert sich um die Grammatik der Eingabe, führt eine syntaktische Analyse der Inputdaten durch und erstellt in der Regel einen Syntaxbaum (Parse-Baum). Dieser kann für die Weiterverarbeitung der Daten verwendet werden, z.B. zur Codegenerierung durch einen Compiler oder Ausführung durch einen Interpreter (Übersetzer). Somit ist der Parser diejenige Software, welche die Anweisungen im Quelltext überprüft, weiterverarbeitet und weiterleitet.

Beispiel für einen Parsebaum

Typen von Parsern

Grundsätzlich gibt es zwei verschiedene Parse-Verfahren, das Top-Down-Parsing und das Bottom-Up-Parsing. Diese unterscheiden sich generell in der Reihenfolge, in welcher die Knoten des Syntaxbaums erstellt werden.

  • Top-down: Bei der Top-Down-Methode arbeitet der Parser zielorientiert, das bedeutet er sucht beginnend bei dem Startsymbol der Syntax nach einer passenden, syntaktischen Ableitung. So entwickelt sich der Parse-Baum von oben nach unten in Richtung einer immer detaillierteren Aufgliederung.
  • Bottom-up: Der Bottom-Up-Parser geht von den Token des Eingabesatzes aus und versucht schrittweise größere syntaktische Zusammenhänge aufzubauen. Dies erfolgt solange, bis das Startsymbol der Grammatik erreicht ist.

Anwendungen

Oftmals wird ein Parser dazu verwendet, einen Text in eine neue Struktur zu überführen, z.B. in einen Syntaxbaum, welcher die hierarchische Anordnung der Elemente ausdrückt. In folgenden Anwendungsbereichen ist die Benutzung eines Parsers meist unerlässlich:

  • Das Auslesen einer Programmiersprache erfolgt durch einen Parser, welcher dem Compiler daraufhin eine Datenstruktur zur Verfügung stellt, mit deren Hilfe der Maschinencode bzw. Bytecode erzeugt werden kann.
  • HTML-Code ist für einen Computer zunächst nur eine Aneinanderreihung von Zeichen, welche durch den im Webbrowser enthaltenen Parser analysiert werden muss. Dieser liefert eine Beschreibung der Webseite als Datenstruktur, welche daraufhin von einem Layout-Engine auf den Bildschirm projeziert werden kann.
  • Spezielle XML-Parser sind für die Analyse von XML-Dokumenten zuständig und stellen die darin enthaltenen Informationen für die weitere Verwendung zur Verfügung.
  • URI-Parser lösen komplexe Schemata wie z.B. URLs in ihren hierarchischen Aufbau auf.
  • Suchmaschinen wie z.B. Google extrahieren (parsen) von den heruntergeladenen Webseiten mit Crawlern die für sie relevanten Textbereiche. Diese werden aufbereitet und die geparsten Daten können für das Durchsuchen verwendet werden.

Fazit

Neben der groben Unterteilung in Top-Down- und Bottom-Up-Parsing sind noch feinere Klassifizierungen von Parsertypen möglich. Bezogen auf die zu analysierende Grammatik können mit dem passenden Parser bessere Crawls auf Webseiten durchgeführt werden. Suchmaschinen werden stets das Ziel verfolgen, diesen Vorgang der effizienten Webseitenanalyse zu optimieren, um dem User schnelle und informationsreiche Suchergebnisse zur Verfügung zu stellen.

Weblinks

Kategorie

Verwandte Artikel