Die Infrastruktur, die wir uns gebaut haben, erlaubt auch, relativ einfach einen schlichten Parser zu implementieren.
Ein Parser ist dabei ein Programm, das die syntaktischen Beziehungen, die zunächst in der Sequenz von Symbolen versteckt sind, in eine zur Darstellung dieser Beziehungen geeignete Struktur überführt. In dem Satz “Der Mann beißt den roten Hund” könnte man beispielsweise sagen, dass er aus einer Nominalphrase (“Der Mann”) und einer Verbphrase besteht (“beißt den roten Hund”). Letztere besteht dann aus einem transitiven Verb (“beißt”) und einer weiteren Nominalphrase – und so fort, bis man bei den einzelnen “Wörtern” (die Anführungszeichen sollen andeuten, dass hier die Alltagsbedeutung von Wort gemeint ist) angelangt ist.
Für die kontextfreien Grammatiken, die wir hier behandelt haben, ist die geeignete Struktur ein Baum. Zu diesen wird später noch mehr zu sagen sein, vorerst reicht es, sich vorzustellen, dass ein Baum die im letzten Absatz dargestellte Verschachtelung, bei der ein paar Konstituenten Kinder einer anderen sind, darstellt.
Genau genommen taugt übrigens die letzte Fassung des Generierungsprogramms auch schon als (sehr ineffizienter) Parser – aber dabei gibts dann ein paar Probleme, deren Diskussion hier zu weit führt.
Eine einfacher rekursiver top-down-Parser sieht so aus:
class TopDownParser: def __init__(self, grammar): self.grammar = grammar def parse(self, wordToParse, curParse=None): if curParse is None: curParse = word.Word(str( self.grammar.getStartSymbol())) if wordToParse==curParse: return [] leftmostNonTerm = curParse.getLeftmostNonTerm() if not leftmostNonTerm or len(curParse)>len(wordToParse): return for rule, deriv in self.grammar.deriveLeft( leftmostNonTerm, curParse, yieldRules=1): rulesApplied = self.parse(wordToParse, deriv) if rulesApplied is not None: return [rule]+rulesApplied
Im Wesentlichen generieren wir und hören auf, wenn wir das richtige Wort gefunden haben. Wenn das so ist, geben wir die Folge der Regeln, deren (Links-) Anwendung zum gesuchten Wort führt, zurück.
So, wie das geschrieben ist, ist das Verhalten für ambige Grammatiken (also solche, in denen verschiedene Regelfolgen zu einen gegebenen Wort führen können) nicht sinnvoll – der Parser gibt eben nur eine Regelfolge (einen “Parse”) zurück. Außerdem geben wir den Versuch, das Wort zu parsen, auf, wenn curParse länger als wordToParse wird. Das wiederum funktioniert nur, wenn die Wörter während einer Ableitung nie kürzer werden können. Tatsächlich ist das aber keine wesentliche Beschränkung, da man zeigen kann, dass man kontextfreie Grammatiken (fast) immer so umformen kann, dass die diese Bedingung erfüllen (man spricht da von ϵ-Freiheit).
Die Klasse, die wir hier definiert haben, wirkt ein wenig albern, weil es nur eine wirklich nützliche Methode gibt. Allerdings gibt es mehr als nur einen Parse-Algorithmus, und vielleicht wollen wir ja später mal einen anderen einsetzen. Durch die Verkapselung in eine Klasse ist die Wahrscheinlichkeit größer, dass wir bei einem Wechsel des Algorithmus die Schnittstelle beibehalten können.
Mit einer Grammatik wie
S -> NP VP S -> NP VP PP VP -> "vi" VP -> "vt" NP VP -> "vt" NP PP NP -> "n" NP -> "det" "n" NP -> "det" "adj" n PP -> "prep" NP
gibt der Parser für das Wort
word.Word('"det" "n" "vt" "n" "prep" "n"')
folgenden Parsebaum:
+-S +-NP | +-"det" | +-"n" +-VP +-"vt" +-NP | +-"n" +-PP +-"prep" +-NP +-"n"
Die oben angegebene Grammatik könnte schon für eine simple natürliche Sprache gut sein. Dabei sind die Terminale dieser Grammatik so genannte Präterminale, die grammatischen Kategorien entsprechen. Das n steht etwa für ein Nomen, das vi für ein intransitives Verb. In der Regel werden solche “Tags” (die aber in der Realität weit komplexer sein können, etwa “Nomen im Nominativ Singular”) von einem dem Parser vorgeschalteten Programm, einem Tagger, vergeben. Der Vorteil dieser Vorgehensweise ist, dass Lexikon und Grammatik getrennt bleiben können.
Im an diese Seite angehängten Code ist eine Funktion enthalten, die aus der Folge von Regeln, die parse zurückgibt, einen Baum in geeigneter Darstellung erzeugt, und eine weitere Funktion, die diesen Baum in der gezeigten Weise ausgibt. Wer Lust hat, kann diese Funktionen studieren.