Parser

Was ist ein Parser?

In der Informatik versteht man unter einem Parser ein Programm, das in der Regel zu einem Compiler geh├Ârt. Der Parser ├╝bersetzt die Eingaben und Anweisungen des Programmierers in eine Maschinensprache, die vom Computer ausgelesen werden kann.

Funktionsweise

Mithilfe einer lexikalischen Analyseschnittstelle, die auch Lexer genannt wird, unterteilt der Parser eine Eingabe. Er zerlegt den Quelltext in sogenannte Token. Innerhalb einer formalen Grammatik repr├Ąsentiert ein Token eine Zeichenkette, die auch als Lexem bezeichnet wird. Ihr wird ein entsprechender Typ zugewiesen. Das Lexem “begin” kann so in der jeweiligen Programmiersprache zum Beispiel als ein Schl├╝sselwort erkannt werden, dem eine bestimmte Ausf├╝hrungsanordnung zugrunde liegt. Diese f├╝hrt dann bereits definierte Aktionen aus, die der Programmiersprache zugeh├Âren. Die Zeichenkette 345 wiederum wird dem Zeichentyp Zahl zugeordnet.

Die Zerlegung der Token unterliegt einer regul├Ąren Grammatik, weshalb die meisten lexikalischen Scanner endliche Automaten sind. Als scannerless Parsers werden diejenigen Parser bezeichnet, die auf die Verwendung eines Lexers verzichten. Nach der Eingabe erfolgt eine syntaktische ├ťberpr├╝fung. Aus den Eingabedaten wird eine Struktur erstellt, die im Deutschen als Ableitungsbaum oder Syntax-Baum und im Englischen als parse tree bezeichnet wird. Anschlie├čend wird der Ableitungsbaum zur Generierung des Codes weiterverwendet.

Letztlich ist der Parser daf├╝r verantwortlich Eingaben auf ihre Richtigkeit zu ├╝berpr├╝fen und diese in eine maschinell auslesbare Sprache umzuwandeln. Bei einer fehlerhaften Eingabe gibt er zum Schluss Warnungen und Fehlermeldungen aus. Syntaxfehlern wird die jeweilige Spalte zugeordnet, sodass der Programmierer die Stelle im Code schnell findet und den Fehler beheben kann. Zuweilen reicht dies allerdings nicht aus, da der Fehler bereits vor der genannten Stelle entstanden sein kann, weshalb Programme einen l├Ąngeren Debugging-Prozess durchlaufen m├╝ssen. Das Debugging erm├Âglicht dem Programmierer Schritt f├╝r Schritt durch den Programmablauf zu gehen, um so die Fehlerquelle ausfindig zu machen.

 

Tipp

Wenn Sie noch Fragen bez├╝glich Debugging haben, dann k├Ânnen Sie gerne den jeweiligen Glossar dazu besuchen und sich ├╝ber das Thema informieren.

 

Parsing-Verfahren

Top Down

Ein Ableitungsbaum kann beim Parsing auf unterschiedliche Weise erstellt werden. Die Bezeichnung richtet sich ganz nach der Reihenfolge, in der der Ableitungsbaum konstruiert wird. Beim Top Down Parsing wird auf der h├Âchsten Ebene mit dem Startsymbol des Codes angefangen. Der Syntax-Baum wird von oben nach unten konstruiert und es wird mit der Wurzel (Top) angefangen. Die Bl├Ątter (Bottom) werden schrittweise ausgef├╝llt. Der Syntax-Baum gliedert sich so immer weiter auf und der Quellcode wird vom Parser in eine formale Grammatik ├╝bertragen.

Bottom Up

Beim Bottom Up Parsing wird sich hingegen in umgekehrter Richtung orientiert. Dieses Parsing-Verfahren f├Ąngt mit der kleinsten vorgefundenen Einheit (Bl├Ąttern) an und arbeitet sich nach und nach zum Startsymbol (Wurzel) des Codes vor. Beide Methoden werden in der Informatik als effizient beschrieben.

Der Vorteil gegen├╝ber dem Top Down Parsing besteht vorwiegend darin, dass der Parser grunds├Ątzlich an jeder beliebigen Stelle des Codes mit der Syntax-Pr├╝fung anfangen kann. Zuweilen kann es beim Top Down Parsing n├Ąmlich dazu kommen, dass der Parser ein Backtracking vornehmen muss. Dies ist etwa der Fall, wenn ein Abzweigeversuch fehlschl├Ągt. Die Syntax-Analyse wird beim Backtracking noch einmal neu gestartet und folgt dann einem alternativen Regelsatz.

Anwendungsbeispiele

  • Jeder Webbrowser verf├╝gt ├╝ber einen eigenen Parser, der den HTML-Code einer Webseite auslesen und in eine neue Datenstruktur ├╝bersetzen kann. Das Aussehen der Seite wird dann ├╝ber CSS definiert.
  • Parsing kommt auch dann zum Einsatz, wenn die Suchmaschinen sich im Netz orientieren, um relevante Textinformationen zu gewinnen.
  • Die im Datenformat XML enthaltenen Informationen werden beim XML-Parsing in eine ├╝bersichtliche Tabellenform ├╝bertragen, die anschlie├čend vom Nutzer bearbeitet werden kann.
  • Text-Adventures benutzen ebenfalls Parsing. Einfache Befehle, wie etwa “├ľffne T├╝r” werden vom Programm ausgelesen und umgesetzt. Die T├╝r wird ge├Âffnet und der Spieler kann den Raum betreten.
  • Programmiersprachen werden beim Parsing ausgelesen und anschlie├čend dem Compiler ├╝bergeben.

Verfeinerte Parsing-Methoden

Top Down und Bottom Up geh├Âren zu den am h├Ąufigsten verwendeten Parsing-Methoden. F├╝r spezielle Probleml├Âsungen bieten sich allerdings noch weitere verfeinerte Methoden zur Klassifizierung an. Eine Methode f├╝r kontextfreie Grammatiken ist zum Beispiel das Chart-Parsing, welches Teilanalysen in einer Tabelle vermerkt. Es bietet sich f├╝r kontextfreie Sprachen an, da es effizienter und schneller in solchen F├Ąllen arbeitet, als die konventionellen Parsing-Verfahren.

Letztlich ist f├╝r die Wahl des Parser-Typs immer entscheidend, welches Ziel erreicht werden soll und welche Methode die besten Ergebnisse liefert. Grunds├Ątzlich stehen dem Anwender so immer Optimierungsm├Âglichkeiten zur Verf├╝gung.

Tipp

Wenn Sie noch Fragen bez├╝glich eines Online Marketing Themas haben, dann k├Ânnen Sie gerne unseren Glossar besuchen und sich ├╝ber das Thema informieren, wo Sie noch speziell Fragen haben.


Sie haben noch Fragen?

Kontaktieren Sie uns

Kostenloser SEO-Check der OSG


Weitere Inhalte