Tomita-Parser

Ein Tomita-Parser (nach Masaru Tomita) ist ein Parsverfahren für kontextfreie Grammatiken, das eine Verallgemeinerung des LR(k)-Verfahrens ist. Das Verfahren wird deshalb auch GLR(k)-Verfahren (für Generalized LR(k)) genannt.

Ausgangspunkt des Tomita-Parsers ist der Tabellenerstellungsvorgang des LR(k)-Verfahrens. Bei Grammatiken, die nicht die LR(k)-Eigenschaft haben (u. a., aber nicht nur, ambige Grammatiken), führt dieser Vorgang zu Mehrfacheinträgen, sog. Konflikten:

• Shift-Reduce-Konflikt: es besteht die Möglichkeit, das nächste Eingabesymbol auf den Stapel des Parsers zu legen oder eine erkannte rechte Seite einer Produktionsregel durch die linke Regelseite zu ersetzen.
• Reduce-Reduce-Konflikt: es gibt mindestens zwei Produktionsregeln, mit deren Hilfe eine Reduktion erfolgen kann.

Der Algorithmus des Tomita-Parsers verfolgt diese Konflikte pseudo-parallel weiter. Als Datenstruktur wird ein sog. Graphstapel (graph structured stack) – ein gerichteter azyklischer Graph – verwendet, der alle bereits vollzogenen Parsoperationen repräsentiert.