ParserTypen

Parsertypen bezeichnen Kategorien von Parsern, die in der Softwareentwicklung eingesetzt werden, um Eingaben gemäß einer Grammatik zu analysieren. Typischerweise unterscheiden sie sich nach der Parsing-Strategie (Top-down vs. Bottom-up) und nach dem formalen Parsing-Formalismus (zum Beispiel LL-, LR- oder Parsing-Expression Grammars). Die Wahl hängt von der Komplexität der Grammatik, dem gewünschten Fehlermeldungsgrad und der Performance ab.

Top-down-Parser arbeiten rekursiv von der Startregel aus nach unten. Dazu gehören rekursiv-abstiegende Parser und LL(k)-Parser. Sie sind oft einfach zu implementieren und eignen sich gut für handgeschriebene Parser oder Sprachen mit einfachen Grammatikstrukturen. Sie benötigen jedoch grammatische Einschränkungen, wie das Eliminieren linker Rekursion, damit der Parser deterministisch arbeitet.

Bottom-up-Parser bauen die Struktur schrittweise von Blättern zur Startregel auf. Typische Vertreter sind Shift-Reduktions-Parser wie LR(0), SLR, LALR und Canonical LR. Sie können eine größere Klasse kontextfreier Sprachen akzeptieren als Top-down-Parser, sind aber meist komplexer zu implementieren oder über Parsergeneratoren nutzbar. Sie liefern oft robuste Fehlermeldungen und sind gut geeignet für Programmiersprachen-Grammatiken.

Parsing-Expression Grammars (PEGs) liefern deterministische Parser durch eine feste Reihenfolge der Wahlmöglichkeiten und vermeiden Mehrdeutigkeiten auf formaler Ebene. Weitere Ansätze wie Chart-Parsing oder Earley-Parser werden vor allem in der Verarbeitung natürlicher Sprache eingesetzt, wo Ambiguität häufig vorkommt.

In der Praxis finden Parsertypen Anwendung in Compliers, Interpretern, Datenextraktion, Formatkonvertierung und API-Parsing. Parsergeneratoren wie Bison, Yacc, ANTLR oder Lemon ermöglichen die automatische Erstellung von Parsern für bestimmte Typen von Grammatiken. Die Wahl eines Parsertyps hängt von Grammatik, Fehlertoleranz, Wartbarkeit und Performance ab.