Wie Parser Sätze analysieren

Beim Parsing in der Computerlinguistik untersucht ein Programm, wie ein Satz grammatisch aufgebaut ist. Ein Parser nutzt grammatische Regeln oder ein trainiertes Sprachmodell, um zu bestimmen, welche Wörter zusammengehören und welche grammatischen Rollen sie haben. So erkennt er zum Beispiel eine Nominalgruppe, also eine Wortgruppe um ein Nomen, oder das Subjekt eines Verbs.

Manche Parser beginnen mit einer erwarteten Satzstruktur und prüfen, ob die Wörter dazu passen. Andere setzen bei den Wörtern an und bauen daraus eine Struktur auf. Es gibt auch Parser, die Zwischenergebnisse speichern oder direkt Beziehungen zwischen einzelnen Wörtern bestimmen.

Ein Satz wird zum Baum

Ein einfacher Parser könnte den Satz „Der Hund jagt die Katze“ mit diesen Regeln analysieren:

S  → NP VP
NP → Det N
VP → V NP

S steht für Satz, NP für Nominalgruppe, VP für Verbgruppe, Det für Artikel, N für Nomen und V für Verb. Die erste Regel besagt: Ein Satz besteht hier aus einer Nominalgruppe und einer Verbgruppe. Die weiteren Regeln beschreiben, wie diese Gruppen aufgebaut sind.

Der Parser ordnet „Der Hund“ als Nominalgruppe ein und „jagt die Katze“ als Verbgruppe. Daraus entsteht ein Baum, der zeigt, wie die Wörter zu Satzteilen gruppiert sind. Er heißt Phrasenstrukturbaum:

S
├── NP: Der Hund
└── VP
    ├── V: jagt
    └── NP: die Katze

Der Baum zeigt, welche Wörter zusammengehören und wie die Satzteile aufgebaut sind. Die Regeln sind hier vereinfacht. Eine vollständige Grammatik des Deutschen müsste auch weitere Wortformen und Satzbauvarianten abdecken.

Vier Parsing-Verfahren

Beim Top-down-Verfahren setzt der Parser beim vollständigen Satz an und zerlegt ihn mithilfe der Grammatik in erwartete Bestandteile. Bei der Regel S → NP VP sucht er also zuerst eine Nominalgruppe und eine Verbgruppe und prüft dann, ob die Wörter dazu passen.

Ein Bottom-up-Verfahren beginnt bei den Wörtern und verbindet sie Schritt für Schritt zu größeren Einheiten. Bei Shift-Reduce nimmt der Parser zunächst das nächste Wort in einen Arbeitsspeicher auf. Das heißt Shift. Sobald gespeicherte Wörter oder Gruppen zu einer Grammatikregel passen, fasst er sie zu einer größeren Einheit zusammen. Das heißt Reduce. So kann er aus „Der“ und „Hund“ eine Nominalgruppe bilden.

Ein Chart-Parser speichert bereits gefundene oder mögliche Teile einer Satzanalyse in einer Tabelle, dem sogenannten Chart. Wenn mehrere Analysen dieselbe Wortfolge enthalten, kann der Parser ein gespeichertes Ergebnis wiederverwenden, statt es erneut zu berechnen. Zu solchen Verfahren zählen CYK und Earley. Das klassische CYK-Verfahren setzt eine passend umgeformte Grammatik voraus.

Beim Dependency Parsing gibt der Parser die Struktur anders aus: Er verbindet einzelne Wörter durch Beziehungen. So kann „Hund“ als Subjekt mit „jagt“ verbunden werden und „Katze“ als Objekt. Das Ergebnis ist ein Abhängigkeitsbaum statt eines Baums aus Satzteilen wie Nominal- und Verbgruppen. Manche Dependency-Parser verarbeiten die Wörter schrittweise und fügen dabei Beziehungen hinzu.

Wie Parser Regeln und Beispiele nutzen

Ein regelbasierter Parser nutzt eine Grammatik, in der Regeln ausdrücklich festgelegt sind. Er prüft, welche Satzstrukturen sich damit bilden lassen. Ein Parser kann auch aus Beispielsätzen lernen, in denen Satzteile oder Beziehungen zwischen Wörtern markiert sind. Solche Markierungen heißen Annotationen. Das gelernte Modell nutzt die Beispiele, um neue Sätze zu analysieren.

Regeln oder gelernte Entscheidungen legen nicht immer eine einzige Struktur fest. Im Satz „Ich sah den Mann mit dem Fernglas“ kann „mit dem Fernglas“ beschreiben, womit ich sah, oder den Mann näher bestimmen. Ein Parser kann beide Analysen ausgeben. Ein Wahrscheinlichkeitsmodell kann eine davon bevorzugen, doch die wahrscheinlichste Analyse beweist nicht automatisch, was die sprechende Person gemeint hat. Dafür zählt auch der Gesprächszusammenhang.

Was Parsing nicht leistet

Parsing beschreibt die Syntax, also den grammatischen Aufbau eines Satzes. Daraus ergibt sich nicht automatisch die vollständige Bedeutung. Ein Parser kann etwa Subjekt und Objekt erkennen, ohne alle Absichten oder den Kontext der Aussage zu erfassen.

Der Parser gibt unterschiedliche Ergebnisse aus, je nachdem, was er darstellen soll. Ein Phrasenstrukturbaum gruppiert Wörter zu Satzteilen. Ein Abhängigkeitsbaum zeigt Beziehungen zwischen Wörtern. Beide beschreiben syntaktische Zusammenhänge, aber auf unterschiedliche Weise. Ein Programm, das nur entscheidet, ob ein Satz nach einer Grammatik zulässig ist, ohne eine Struktur auszugeben, heißt Erkenner.