Adriane Boyd WS 2001-2002 Parsing PT-2 Implementierung (Top-down parser with parallel processing) Verwendung: parser grammatikdatei.txt lexikondatei.txt g1.txt und l1.txt sind Beispieldateien. Das PT-2 Parserprogramm zwei Dateien: eine Lexikondatei und eine Grammatikdatei. In der Lexikondatei ist jede Zeile ein Eintrag, der aus einem Wort, einem Leerzeichnen, und der lexikalische Kategorie besteht. Weil das Programm Terminal- und Nicht-Terminalsymbole durch Großschreibung unterscheidet, sollen die Wortarten in der Lexikondatei klein geschrieben werden. In der Grammatikdatei soll auch ein Eintrag auf jeder Zeile stehen: das erste Symbol ist das Symbol auf der linken Seite der Regel und die folgenden Symbole sind die auf der rechten Seite. Ein Leerzeichnen kann die Symbole trennen. Nicht-Terminalsymbole sind definiert als Symbole, die wenigstens einen Großbuchstaben enthalten. Das Parserprogramm liest diese zwei Dateien am Anfang ein und fragt dann den Benutzer nach einem Satz. Im eingegebenen Satz wird Zeichensetzung und Klein/Großschreibung ignoriert. Nur die echten Buchstaben werden erkannt, also sind aus der Sicht des Parsers die Sätze "Many tourists sleep." und "MANy,,, TourisTS SLEEP..." gleich. Mit dem im Skript erklärten Algorithmus wird der Satz bearbeitet: die lexikalischen Einträge für die Wörter werden gefunden, alle mögliche Reihenfolgen von Regelexpansionen werden generiert, bis terminale Symbole in der ersten Position stehen, und die Reihenfolgen, die dem Wort in der jetzigen Position entsprechen, werden erkannt. Die Position wird dann erhöht und der Prozess wird wiederholt werden, bis der ganze Satz durch gearbeitet ist. Nach jedem Schritt werden die Zwischenergebnisse ausgedruckt. Am Ende werden die Reihenfolgen akzeptiert, die leere Derivationen haben. Wenn der Satz akzeptiert ist, wird "Guter Satz" und eine Liste von Regelnreihenfolgen von Parsen ausgedruckt. Die Reihenfolgen von Regelnummern entsprechen der Folge von Regeln in der Grammatikdatei (die erste Regel ist Regel 0). Wenn der Satz nicht akzeptiert ist, druckt das Programm "Schlechter Satz" aus. Der Benutzer wird dann nach einem neuen Satz gefragt. Wenn der Benutzer einen leeren Satz eingibt, endet das Programm. Über das Programm: Das Lexikon und die Grammatik sind beide Arrays von den Einträgen, aber die Lexikonelemente sind einfache Tokens und die Grammatikelemente sind verkettete Listen von denselben Tokens. Ich habe eine beschränkte "verkettete Liste" Klasse geschrieben, die in den Grammatik- und Parserklassen benutzt wird. Die Derivationstabelle und Regelreihenfolgetabelle sind Arrays von verketteten Listen, die immer parallel geändert werden. Für jedes Wort im Satz nimmt die Expand-Funktion die Listen in der Derivationstabelle und erweitert sie, bis das erste Symbol terminal oder nicht weiter expandierbar ist. Dann geht die Reduce-Funktion durch die Tabelle und erhält nur die Listen, die das gleiche erste Symbol als das lexikalische Eintrag in der jetzigen Position haben. Die ersten Elemente in den gebliebenden Listen sind gelöscht und die Position erhöht. (Bemerkung: Das Element "term" in dem Token wird in der Grammatik als terminale/nicht-terminale Flag benutzt und auch in den Regelreihenfolgen als die Regelnummer. Ich brauchte eine int Variable, um die Regelreihenfolge zu speichern und "term" war schon da. Es ist ein bisschen unklar, weil dieses "term" in zwei verschiedenen Weisen benutzt ist. Vielleicht wäre es besser, wenn es eine besondere "verkettete Liste" Klasse für die Derivationstabelle und Regelreihenfolgetabelle zusammen geben würde.) Begrenzungen: -Der erste Eintrag im Lekixon für ein Wort wird immer benutzt, also ist lexikalische Ambiguität unmöglich. -Die Größen des Lexikons und der Grammatik sind auf 100 Einträge begrenzt. -Die Größen der Derivation- und Regelreihenfolgenarrays sind auf 100 Einträge begrenzt. -Dieses Programm ist nur für Spielgrammatiken und Spiellexika geeignet, weil ihre Größen begrenzt sind, aber auch weil die Einträge nicht sortiert werden. Die Suchmethoden sind deswegen äußerst ineffizient.