Wie natürlich-sprachliche Deklarationen parsen?

[sma]

Ich möchte über Text-Adventures (http://de.wikipedia.org/wiki/Adventure#Text-Adventures) reden. Dem Spieler wird textbasiert eine Situation beschrieben, er interagiert durch die Eingabe von Befehlen wie "GO NORTH" oder "GET LAMP". Typischerweise gibt es Räume (oder Orte) zwischen denen man wechseln kann und Gegenstände, die man einsammeln, weglegen oder benutzen kann. Vielleicht gibt es auch noch weitere Personen (gerne NSC für Nicht-Spieler-Charaktere genannt), mit denen man reden kann.

Diese Spielwelt lässt sich prima durch die objektorientierte Brille betrachten. Besser noch als "orthodoxe" klassenbasierte Programmiersprachen funktionieren hier prototyp-basierte, die ihre "traits" beliebig zur Laufzeit austauschen können. So etwas könnten wir uns aber schnell auch in Python bauen ().

Klassenbasiert ist aber auch OK: Wir können einen Raum als etwas mit einem Namen und einer Beschreibung definieren, das Gegenstände (und den Spieler) aufnehmen kann und Verbindungen (zu anderen Räumen) hat. Auch ein Gegenstand hat einen Namen und eine Beschreibung und kann optional andere Gegenstände enthalten. Vielleicht kann man Gegenstände nehmen, weglegen, zerbrechen, schieben, auf sie oder in sie klettern, benutzen oder lesen, trinken, usw. Verbindungen haben eine Richtung, vielleicht auch eine Beschreibung und führen schließlich zu anderen Räumen, vielleicht abhängig von einer Bedingung. Um gute Beschreibungen zu erzeugen will man von Gegenständen (und Räumen) wahrscheinlich noch wissen, mit welchem Artikel sie geschrieben und wie dekliniert werden sollen. Und, um nicht laufend "ich verstehe nicht" ausgeben zu müssen, gibt es vielleicht Synonyme und abkürzende Schreibweisen, die man jeweils definieren kann. Das ist aber nicht weiter wichtig.

Ich kann eine Mini-DSL entwickeln, um meine Welt zu beschreiben:

Code: Alles auswählen

    def room(name, desc):
        rooms[name] = Room(name, desc)
    
    def item(name, desc, location, *traits):
        items[name] = Item(name, desc)
        items[name].location = location
        items[name].add_traits(traits)
    
    def connect(dir, room1, room2):
        room1.add_connection(Connection(dir, room1, room2))
        
    room("Kabine", "Kabinen an Bord eines Raumschiffs...")
    room("Bad", "Wie eine Kabine, ist auch das ...")
    item("Broschüre", "Sie beschreibt...", "Kabine")
    item("Bett", "...", "Kabine", fixed, supporter)
    item("Spiegel", "...", "Bad", scenery)
    item("Dusche", "...", "Bad", fixed)

    connect("osten", "Bad", "Kabine")
    connect("westen", "Kabine", "Bad")
    connect("auf/in", "Kabine", "Bett")
    
    items["Bett"].alias = "Möbel"

Doch das wird schnell unübersichtlich. Ich könnte eine externe DSL entwerfen.

Die Programmiersprache "Inform 7" (http://inform7.com/) kann obiges stattdessen quasi natürlich-sprachlich darstellen (allerdings wohl nur auf englisch):

Code: Alles auswählen

    Die Kabine ist ein Raum. "Kabinen an Bord eines Raumschiffs..."
    Das Bad ist östlich von der Kabine. Die Beschreibung ist "Wie eine Kabine, ist auch das Bad..."
    Die Broschüre ist in der Kabine. "Sie beschreibt die Herrlichkeit..."
    Das Bett ist in der Kabine.
    Das Bett ist ein betretbarer Raum.
    Setze "Möbel" mit Bett gleich.
    Der Spiegel ist Kulisse im Bad.
    Die Dusche ist hier. Sie ist unbeweglich.

Wie, und nun komme ich endlich zu meiner Frage, könnte ich so etwas auswerten? Kann ich da ganz naiv mit regulären Ausdrücken und damit mit einer einfachen Mustererkennung herangehen? Kann ich eine "normale" kontextfreie (?) Grammatik definieren? Brauche ich Hilfsmittel aus der Theorie der Sprachverarbeitung, die ich nicht kenne?

Finde ich "(wort+) ist eine? (wort)\.", weiß ich, dass hier ein Ding definiert werden soll. Das erste ist der Name des Dings (und ich kann im Deutschen die schwierige Grammatik angehen und gleich mal das Geschlecht erkennen), das zweite sein Typ. Folgt jetzt ein String, ist das eine Abkürzung und gemeint ist die Beschreibung. Finde ich "(wort+) ist|liegt|(?:befindet sich) (richtung) von (wort+)\." kann ich einen weiteren Raum definieren und mit einem anderen verbinden. Aus "ist in" kann ich schließen, dass ein Gegenstand definiert werden soll. Spannend sind Dinge wie "ist hier". Damit muss man wissen, was gerade der aktuelle Raum ist. Bei "Sie ist" muss ich auch den aktuellen Gegenstand kennen.

Wie würdet ihr das Problem angehen?

[Xynon1]

Ich hatte dazu schonmal was schön ausführliches gelesen, mich aber nie rangesetzt. Ist zwar im Prinzip ein Handbuch für einen Adventure Generator, aber mir gefiehl der Ansatz, der vermittelt(und warscheinlich in dem Generator auch umgesetzt) wurde, sehr gut. Sieh es dir mal an: http://www.martin-oehm.de/tagman/tag.txt
II. 4. - sollte hier für dich Interessant sein.

[deets]

Kam gerade heute oder gestern ueber die PyParsing-ML rein:

https://launchpad.net/myriad-worlds

Koennte interessant sein.

[Hyperion]

Wie würdet ihr das Problem angehen?

Ich sehe im Moment nicht den Vorteil der umgangssprachlichen DSL. Ist das wirklich so viel übersichtlicher, als wenn man eine DSL in JSON / YAML / XML-Syntax umsetzt? Das von deets gepostete Projekt macht das ja wohl in YAML; ich selber hatte mal eines mit JSON angefangen.

Ich schätze mal, dass ab einer gewissen Größe (Anzahl an Räumen, Items, Verbindungen usw) gar nicht mal die Definitionen an sich ein Problem darstellen, sondern eher das Aufspüren / Prüfen von Dead-Locks u.ä. oder gar logischen oder inhaltlichen Fehlern die Hauptschwierigkeiten sind.

Unabhängig davon ist ein solcher Parser sicherlich eine spannende Sache Ich denke ich würde mir wirklich mal ein Mini-Demoadventure ausdenken und damit textuell die Definition aufschreiben. Danach würde ich überlegen, welche Schwierigkeiten es beim Parsen gibt bzw. was ich alles erlauben will. Mir fallen da spontan ein:

- Reihenfolge: Kann / Muss man Bezug an beliebigen Stellen zu früher definierten Objekten nehmen können? Stellt das ggf. ein Problem dar?

Code: Alles auswählen

# in Deinem Bsp:
Das Bett ist in der Kabine.
Das Bett ist ein betretbarer Raum.
# geht auch so was:
Das Bett ist in der Kabine.
...
# ganz viel anderes Zeugs
...
Das Bett ist ein betretbarer Raum.

- Gibt es "Level" oder andere gruppierende Elemente?

Code: Alles auswählen

# "globaler" Abschnitt
Das Meer ist ein Abschnitt.
# Abschnitt im Abschnitt
Das Schiff ist ein Abschnitt und liegt im Meer.
# alles, danach lieht im Schiff
Die Kabine ist ein Raum. "Kabinen an Bord eines Raumschiffs..."
Das Bad ist östlich von der Kabine. Die Beschreibung ist "Wie eine Kabine, ist auch das Bad..."
...
# neuer Abschnitt
Die Insel ist ein Abschnitt
Die Insel liegt im Meer
Der Strand ist ein Raum auf der Insel
Die Hütte liegt neben dem Strand.
# Hui... das hatten wir doch schon mal!
Das Bett ist in der Hütte.

- Sind Elemente in einem Abschnitt einzigartig oder global? Muss man da einen Index einfügen wirds imho genauso hässlich wie in einer Markup-Sprache

Code: Alles auswählen

Das Bett2 ist in der Hütte.

- Sind auch Nebensätze erlaubt?

Na so in der Art etwa. Ich denke anhand solcher Beispiele (und der Idee dahinter) kann man sich ein Bild machen, wie so etwas in dieser natürlichen DSL aussehen kann, welche Probleme man da strukturell erwarten kann und welche Einschränkungen man eben treffen muss. Du als "Gott der Parser" wirst doch da mit regulären Ausdrücken schon weit kommen denke ich mal

[DasIch]

Wenn die Regeln so bleiben dürften es reguläre Ausdrücke tun, ich bezweifle erstmal dass eine kontextfreie Grammatik da sonderlich weiterhilft, es sei den man definiert quasi eine eigene Sprache.

Die Alternative wäre den Text semantisch zu analysieren und Prädikatenlogik zu nutzen um die Regeln zu erfassen. Zumindest bei der semantischen Analyse wird die NLTK sicherlich weiterhelfen können. Letztendlich hast du dann einen Prolog Interpreter für natürliche Sprachen und müsstest damit einen relativ großen Aufwand betreiben.

[sma]

Mich beschäftigen mehrere Dinge und ich habe meine Gedanken noch nicht sortiert.

"Normalen" Programmiersprachen kann ich deren Grammatik quasi ansehen und habe keine größeren Schwierigkeiten, mir vorzustellen, wie ein Parser dafür aussieht. Bei "Inform 7" stehe ich nur staunend vor der Sprache.

Ich fand die Idee von Text-Adventures interessant und habe die Tutorials von TADS 3 und Inform 6 sowie ALAN 3 überflogen (das ist mir alles viel zu umfangreich, um das vollständig zu lesen). Ich ging mit der Idee da ran, dass diese Sprachen eine Vereinfachung "normaler" Programmiersprachen wären. Tatsächlich sind sie wesentlich komplexer, als was so vor 10-15 Jahren üblich war.

Das OO-Paradigma ist in der IF-Gemeinde etabliert, gleichzeitig gibt es (schon viele Jahre lang) die Erkenntnis, dass OO eigentlich gar nicht hilft, sondern größere Spiele zu einem extrem komplexen Wirrwarr an Code macht. Das, so meine Theorie, hat dazu geführt, dass IF eigentlich ausgestorben ist.

Mein einfaches Beispiel, Räume und Gegenstände zu definieren ist typisch OO, bildet jedoch keine Regel ab, wo der Autor von Infom 7 auf ein regelbasiertes System statt prozeduralen Methoden mit Mehrfachvererbung setzt. Ich möchte eigentlich nachvollziehen können, wie man das angeht. Mein erster Schritt war, den Parser zu verstehen.

Ich suche eigentlich nach etwas, das einem "normalen" Menschen erlaubt, eine interaktive Geschichte (mehr in Richtung Rollenspiel denn Puzzle) zu erzählen. TADS 3 oder Inform 6 (ALAN 3 scheint etwas simpler zu sein) kann ich keinem Zumuten. Inform 7 sieht zumindest nett aus. Doch keines dieser System hat weniger als 100 A4-Seiten Beschreibung - nur für die Sprache - die Klassenbibliotheken sind noch mal größer.

Ich gucke seit einiger Zeit Gronkh und Sarazar beim Dragon-Age-2-Spielen zu. Bis auf die Kämpfe und Gronkhs unentschlossenes Sortieren der Ausrüstung finde ich die Gespräche mit den NSCs und allgemein die Tiefe der Hintergrundgeschichte faszinierend. Denkt man sich 80% der Kämpfe, den IMHO unnötigen komplizierten Steigerungs- und Ausrüstungskram sowie die zugegeben tolle Grafik weg, bleibt eigentlich ein Text-Adventure. Und es bleibt etwas, das ich auch bauen könnte. Vielleicht auch für andere, die eher eine Geschichte erzählen wollen, als programmieren.

Es gibt ein umfangreiches Whitepaper vom der Autor von Inform 7, in dem er die Vorteile seiner natürlich-sprachlichen Grammatik darlegt und das (naheliegenden) Argument widerlegt, dass das geschwätziger und umständlicher als eine "orthodoxe" (wie er es so schön nennt) Programmiersprache ist. Durch sehr viele implizite Kontext-Annahmen kann er sehr kompakte Aussagen treffen.

Hinzu kommt, dass er alles deklariert statt (prozedural) konstruiert. Das hat in der Regel eine höhere Abstraktionsstufe, wie spätestens seit SQL jedem Programmierer bekannt sein sollte.

Deutsch ist blöderweise längst nicht so einheitlich wie englisch und macht das ganze noch mal komplizierter. Aber die Zielgruppe, die mir vorschwebt, will eigentlich deutsch. Und ich befürchte, wenn man erst mal mit Englisch anfängt, fehlen einem wichtige Konzepte.

@DasIch Kontextfreie Sprachen werden nicht funktionieren, man will ja Kontext haben. Eigentlich dürften dann auch keine PEG-Parser funktionieren, daher wundert mich, wie man mit PyParsing das angehen können soll (Tipp von @deets, dem ich daher noch nicht nachgegangen bin). Prolog scheint mir aber das richtige Stichwort zu sein.

@Hyperion Zur Zeit glaube ich nur, es ist einfacher verständlich, doch ich werde mal ein paar Leute befragen, die keine Programmiererfahrung haben. Ich glaube, die tuen sich viel, viel schwerer mit jedem sichtbar formalen Format wie XML oder JSON oder YAML, als wir uns das vorstellen können.

Du hast Recht, dass die Definition von Räumen und Gegenständen kein Problem darstellt. Ich nahm das nur als Beispiel, weil man's leicht verstehen kann. Die Probleme beginnen, wenn man Aktionen definiert bzw. Standardaktionen ändern will. TADS 3 bietet z.B. etwa zwei Dutzend (!) Methoden pro Aktion, die in festgelegter Reihenfolge aufgerufen werden und so an diversen Stellen "hooks" bieten, in die man sich hängen kann. Inform 7 sagt (so oder so ähnlich):

Instead of taking the mirror, say "No chance - it is welted into the wall."

After breaking the mirror, say "You immediately regret this decision,
remembering the old saying about 7 years of bad luck."; and
decrement luck of hero by 10.

Das Tutorial von ALAN 3 sagt stattdessen, man soll doch einfach die Standard-Implementation von "take" bzw. "break" aus der Klassenbilothek heraussuchen, dann die passende Methode in das jeweilige Objekt kopieren und entsprechend zusammenstreichen und anpassen.

Ansonsten kann ich leider nicht sagen, was Inform 7 genau kann und was nicht, aber die aufgeworfenen Punkte klingen sinnvoll und es sollte IMHO gehen. Ich weiß, dass man eine Geschichte in Kapitel und Abschnitte zerteilen kann, die dem Parser helfen, Mehrdeutigkeiten aufzulösen, weil er im Zweifel davon ausgeht, dass die Definition aus dem selben Abschnitt gemeint ist. Und statt "Bett2" würde man natürlich eher "Himmelbett" und "gusseisernes Bett" benutzen oder die Objekte sonst wie mit Adjektiven eindeutig machen. Und ja, Nebensätze sind möglich.

@Xynon1: Wow, alles deutsch und schon wieder so viel Text. Schaue ich mir demnächst mal an. Danke für den Tipp. Allerdings sehe ich in Abschnitt II.4 nicht, wie das natürlich-sprachlich ist. Mir scheint das eine "normale" LL(1)-parsbare kontextfreie Grammatik zu sein. Und auch vor 10 Jahren waren Computer schon gut genug, um nicht alles nur mit Abk. zu machen ("Befehl" statt "Bef").

Stefan

[DasIch]

@DasIch Kontextfreie Sprachen werden nicht funktionieren, man will ja Kontext haben. Eigentlich dürften dann auch keine PEG-Parser funktionieren, daher wundert mich, wie man mit PyParsing das angehen können soll (Tipp von @deets, dem ich daher noch nicht nachgegangen bin). Prolog scheint mir aber das richtige Stichwort zu sein.

Mit PyParsing wird es sicherlich nicht gehen mit dem Natural Language Toolkit(NLTK) könnte man aber eine "echte" natürliche Sprache analysieren.

[Hyperion]

@Hyperion Zur Zeit glaube ich nur, es ist einfacher verständlich, doch ich werde mal ein paar Leute befragen, die keine Programmiererfahrung haben. Ich glaube, die tuen sich viel, viel schwerer mit jedem sichtbar formalen Format wie XML oder JSON oder YAML, als wir uns das vorstellen können.

Ok, wenn jemand keine Erfahrung mit formalen Sprachen und exakter Syntax hat, wird es für ihn eher abschreckend sein. Da hat man sicherlich ein Zielgruppenproblem. Ich könnte mir aber vorstellen, dass man da ein GUI basiertes Authoring-Tool entwickeln kann, welches eben die Syntax versteckt. Ist natürlich auch ein Aufwand, wo man abwägen muss, welchen Weg man da einschlagen will.

Bei Warcraft3 kann man mit dem mitgelieferten Editor auch recht Story lastige Szenarien erstellen - allerdings artet auch das in Arbeit aus und ohne Einarbeitung geht da auch nix. Das - mittlerweile eingestellte - Projekt Rastullas Lockenpracht hatte für die Dialogerstellung iirc ein GUI-Tool entwickelt, welches das XML-Format gekapselt hat. Ansonsten fällt mir noch Battle for Wesnoth ein; ok, da liegt der Fokus wirklich nicht auf Story-Telling... aber zumindest kann man da beobachten, dass sich dort auch viele Nicht-Programmierer an die eigene Markup-Sprache (WML) wagen und damit Szenarien und Kampagnen entwickeln.

Ich würde es mal so sagen: Du musst einem Interessierten halt irgend eine Bedienungsanleitung in die Hand geben. Bei einer strikten und ggf. für ihn abstrakt wirkenden Syntax wird es für ihn Frustrationen geben, wenn Syntaxfehler auftreten und inhaltliche Sachen nicht klappen. Bei einer natürlich sprachlichen Markup-Sprache gibt es dann zwar quasi keine Syntaxfehler, dafür kommt da sicherlich auch Frustration auf, wenn etwas nicht klappt, wie es soll. Eine Meldung a la "Ich verstehe den Satz nicht!" vom Parser wird da sicherlich auch frustrieren.

Aus dem Bauch raus könnte ich Dir auch nicht sagen, was für einen unerfahrenen Autoren der sinnvollere Ansatz ist. Allerdings lernt man ja schon in der Schule (und im Studium noch viel mehr), dass man längere Texte gut strukturieren muss, um nicht den Überblick zu verlieren. Schreibt man Satz an Satz, so wird man - ganz unabhängig vom Parsing-Problem - schlicht den Überblick verlieren. ("Wo war gleich die Definition vom dem Raum und dem Gegenstand XYZ da drin, welchen man nur dann hat, wenn man vorher dort und dort war? ...") Insofern würde ich da schon Bedarf sehen, Struktur reinzubringen. Ein wenig mehr Syntax als Satzzeichen und Absätze dürften da schon zu erwarten sein, oder was meinst Du?

Evtl. kann man reStructured Text oder Creole / MarkDown o.ä. für die grobe Form nutzen und damit einen gewissen Rahmen vorgeben. Definiert man dann noch einige Schlüsselwörter (wie z.B. in Sphinx), so beschränkt sich der freie Text ja deutlich in seiner semantischen Komplexität. Das wäre eine Art Kompromiss zwischen extrem striktem Markup a la JSON und komplett freiem Text.

Mir stellt sich da noch eine Frage, die ich mal anhand Deines Beispiels zu erörtern versuche:

After breaking the mirror, say "You immediately regret this decision,
remembering the old saying about 7 years of bad luck."; and
decrement luck of hero by 10.

Im letzten Teil steckt ja einiges an Wissen um die Regelmechanik drin! Das ist ja Arithmetik in Prosa - passt so was wirklich zu jemandem, der eine Geschichte erzählen will? Ich hätte da eher so etwas erwartet:

...; und halbiere / vermindere das Glück des Helden.

Vielleicht irre ich mich, aber ein Erzähler ist da ja eher auf einen spürbaren Effekt aus, als auf einen abstrakten Wert. Ok, vielleicht gibt es da auch Mischformen, die genau das wollen... bei Abenteuern für P&P RPGs werden ja auch idR dem Regelwerk angemessene Werte angegeben und sonst ist es Prosa.

Wie man nun Beziehungen und den Kontext in einem Prosatext parsen kann, wüsste ich aus dem Bauch raus auch nicht! Evtl. hilft es ja doch, sich da kleine Beispiele zu überlegen und anhand derer sich ein Muster dafür auszudenken.

Im Bereich des Semantic Webs wurden einige Sprachen entwickelt, um Ontologien und Abfragesprachen einfach formulierbar zu machen, nämlich z.B. die Turtle-Syntax und die Manchester-Syntax. Dabei basiert das Schema immer auf dem simplen Subjekt - Prädikat - Objekt Prinzip.

In Turtle könnte das so aussehen:

Code: Alles auswählen

Bett ist ein Raum;
      ist verbunden mit Zimmer.

Zimmer ist ein Raum;
      ist verbunden mit Flur,
                               Badezimmer.

Man kann dabei das Subjekt und auch das Prädikat des vorangegangenen Satzes durch das Satzendezeichen in den nächsten übernehmen. Das erspart einem Konjunktionen a la "und". Ob man damit aber auch Bedingungen sinnvoll deklarieren kann, kann ich so nicht sagen.

Solltest Du Leute haben, die das interessiert, so frage diese doch mal, ob sie nicht einfach mal so drauf los schreiben wollen und ein kleines Abenteuer gestalten. Vielleicht hilft Dir das zu erkennen, wie Nicht-Programmierer strukturieren, was diese evtl. "vergessen" oder implizieren.

[Hyperion]

@sma: Bist Du mit dem Problem eigentlich schon weiter gekommen?

[sma]

Ich bin noch dran, aber ich habe erst mal Grundlagenforschung begonnen und mir (wieder) Prolog beigebracht, etwas über DCGs (definite clause grammars a.k.a. unification grammars) gelernt und mir einen Überblick über Inform 6, Inform 7, Tads 3, Alan 3, Hugo und Adrift verschaff.

Nachdem ich mit SICP (wo ich damals den Fehler gemacht hatte, mir die deutsche Version zu kaufen, die völlig bescheuert auch den ganzen Programmtext eingedeutscht hat) und dessen extrem komplizierter Implementierung eines Prolog-artigen Unification Algorithmus gescheitert bin, habe ich mich daran erinnert, dass wahrscheinlich beste Computerlehrbuch zum Thema Lisp und KI zu besitzen und habe in Norvigs Paradigms of Artificial Intelligence Programming geschmökert und einen kleinen Prolog-Interpreter in Python gebaut. Das Buch hat nun auch schon 17 Jahre auf dem Buckel, aber ich kann es gar nicht hoch genug loben. Ich hatte mir letztes Jahr auch "Land of Lisp" schenken lassen und habe gesehen, dass dort auch etwas über Textadventures drin steht. Muss ich auch noch lesen

Danach gibt's dann noch mal ein Update mit weiteren Erkenntnissen.

Stefan

[Hyperion]

Danach gibt's dann noch mal ein Update mit weiteren Erkenntnissen.

Klingt ja alles spannend Bin gespannt.

Hatte mir Alan 3 mal oberflächlich angeguckt und muss gestehen, dass ich den Aufbau ziemlich Pascal artig empfand. So richtig hat das dann imho nichts mehr mit Natürlichsprachlichkeit zu tun und mir würde eine kürzere Syntax dann besser gefallen - aber als Programmierer denkt man da vermutlich auch schon zu stark in Richtung "formal", "einfach" und "kurz".

[cofi]

Ich hatte mir letztes Jahr auch "Land of Lisp" schenken lassen und habe gesehen, dass dort auch etwas über Textadventures drin steht. Muss ich auch noch lesen

Ich hatte schon viel Spass mit LoL, aber die Kapitel ueber Textadventures werden dir bei deinem Problem nicht sonderlich helfen, denn man baut da eine spezielle REPL und hat keine natuerliche Eingabe sondern eben Lisp-Code.

[nezzcarth]

Da du ja gefragt hattest, ob du evtl. irgendwas aus der Sprachverarbeitung brauchst, hier mal ein paar Hinweise, was du dir ansehen könntest; ob dir das hilft, musst du selbst entscheiden:

Für die Beschreibung der beiden Ebenen, die für dich wohl interessant sind, Satz und Text, gibt es einen Haufen Modelle. Zwei von denen ich weiß, dass sie relativ weit verbreitet sind in der Computerlinguistik sind folgende:
http://en.wikipedia.org/wiki/Lexical_Functional_Grammar
http://de.wikipedia.org/wiki/Rhetorical ... ure_Theory
(Insbesondere auch die Links unten ansehen).

Generell ist es halt so, dass gerade die Beschreibung der Syntax natürlichsprachlicher Sätze ein heißes Feld ist, und eine einheitliche Theorie noch weit entfernt ist.
Eine der Richtungen, die für dich als Informatiker (nehme ich mal an), relativ intuitiv zugänglich sein könnte, ist die der generativen Grammatiken (unter die auch das, was ich oben verlinkt habe fällt), denn sie versuchen das Instrumentarium formaler Sprachen aus der theoretischen Informatik für die Beschreibung natürlicher Sprachen zu verwenden; da wundert es nicht, dass Chomsky in beiden Disziplinen bekannt ist.
http://en.wikipedia.org/wiki/Generative_grammar

[pillmuncher]

@sma: Prolog + DCGs könnten dein Problem wohl tatsächlich lösen. Vielleicht könntest du ja entsprechende DCG-Klauseln schreiben, die du dann über den Umweg DCGs --> Prolog --> Yield Prolog nach Python übersetzt?

Unter http://www.python-forum.de/pastebin.php?mode=view&s=186 hab ich ein paar Prolog-Definitionen für einige einfache sinnfreie Sätze wie zB. [die, katzen, jagen, den, hund] oder [einige, maeuse, schlafen] hinterlegt. Immerhin gibt es da Genus-, Numerus- und Kasus-Kongruenz in den np- und vp-Klauseln und die Unterscheidung transitiver und intransitiver Verben. Ich hatte das mal als Test für mein eigenes Spielzeug-Prolog gebaut, deswegen liegen die Definitionen als Prolog-Klauseln vor und nicht als DCG-Klauseln, da mein Prolog die nicht verstand. Derzeit ist es leider out of commission, weil ich es inmitten eines größeren Umbaus einfach im Stich gelassen habe.

Wenn du alle daraus generierbaren Drei-Wort-Sätze ausgeben willst, die von Katzen (im Plural) handeln:

Code: Alles auswählen

?- S = [_,katzen,_], satz(S), writeln(S), fail.

Wie man indexikalische Ausdrücke wie etwa 'hier' verarbeiten kann weiß ich nicht so recht, ich vermute aber, dass man so etwas braucht wie einen situativen Kontext (k.A. ob die Linguisten das so nennen...), auf den bezogen etwas hier oder nicht hier, dh. dort oder östlich von ist. Dieser Kontext müsste dann die global gültigen Regeln (AKA Das Universum) lokal erweitern.

Vielleicht steht ja auch in "Natural Language Processing in Prolog" von Gadzar & Mellish was brauchbares. Und "The Art of Prolog" von Sterling & Shapiro sollte ebenfalls in keinem Informatiker-Haushalt fehlen.

Gruß,
Mick.

[nezzcarth]

Wie man indexikalische Ausdrücke wie etwa 'hier' verarbeiten kann weiß ich nicht so recht, ich vermute aber, dass man so etwas braucht wie einen situativen Kontext (k.A. ob die Linguisten das so nennen...)

Hier, da usw. sind im allgemeinen Deiktika. Im Satzkontext spricht man von Anaphern (Gegenbegriff: Katapher). Sie sind ein Mittel, um Kohäsion herzustellen.

Ein paar Links:
http://de.wikipedia.org/wiki/Deixis
http://de.wikipedia.org/wiki/Anapher_%28Linguistik%29
http://de.wikipedia.org/wiki/Katapher
http://de.wikipedia.org/wiki/Koh%C3%A4s ... guistik%29
http://de.wikipedia.org/wiki/Koh%C3%A4r ... guistik%29
http://de.wikipedia.org/wiki/Textualit% ... d_Dressler

[pillmuncher]

Hier, da usw. sind im allgemeinen Deiktika. Im Satzkontext spricht man von Anaphern (Gegenbegriff: Katapher). Sie sind ein Mittel, um Kohäsion herzustellen.

Ein Bekannter von mir hat darüber promoviert: Anaphernresolution mit beschränkten Parametern.

Gruß,
Mick.

[nezzcarth]

Danke für den Hinweis, das ist doch ganz interessant. Abgesehen davon bestätigt diese Arbeit auch meine These, dass solche stark formalen Theorien - vermutlich eben genau deshalb - für Sprachverarbeitung gerne genommen werden, denn die verwendete HPSG zählt auch zu den generativen Theorien.
Eine weitere mit ähnlichen Eigenschaften, aber aus einem anderen Theorielager ist die http://en.wikipedia.org/wiki/Montague_grammar die man sich mal ansehen kann, wenn man was für Logik übrig hat.

[pillmuncher]

Montague Grammar

Darüber hat eine Freundin von mir ihre Magisterarbeit geschrieben, genauer gesagt über die Generalized Quantifier Theory. Das fand ich recht anregend, habe aber nur ein paar Grundlagen aufgeschnappt. Ich hab's mehr mit der Analytischen Philosophie als mit der reinen Linguistik. Für einen Lisper wie sma wär die GQT vielleicht ganz interessant, weil Generalized Quantifiers ja gut mittels Lambda-Kalkül dargestellt werden können.

[sma]

Es gibt offenbar diverse Ansätze Grammatiken für natürliche Sprachen zu beschreiben. Aber reicht nicht auch ein PEG-Kombinator-Parser mit Backtracking, um Sätze wie "The dark attic is a room. The cellar is below the attic. The tiny red car is in the cellar." zu verstehen?

2008 hatte ich mal den folgenden Kombinator-Parser gepostet:

Code: Alles auswählen

    def empty(ss):
        return ss
    
    def word(pattern):
        pattern = re.compile("\\s*(%s)" % pattern)
        def word_parser(ss):
            r = ()
            for s in ss:
                m = pattern.match(s)
                if m:
                    r += (s[m.end(1):],)
            return r
        return word_parser
    
    def alt(p1, p2):
        def alt_parser(ss):
            return (p1(ss) + p2(ss)) if ss else ()
        return alt_parser
    
    def seq(p1, p2):
        def seq_parser(ss):
            return p2(p1(ss)) if ss else ()
        return seq_parser
    
    def rep(p):
        return alt(empty, lambda ss:rep(p)(p(ss)))
    
    def opt(p):
        return alt(empty, p)

Ein Parser ist hier ein Funktion (die in der Regel von einer anderen Funktion erst erzeugt wird), die eine Liste von Strings mit dem zu verarbeitenden Text übergeben bekommt und eine neue Liste mit derartigen Strings liefert, bei denen der Teil fehlt, den der Parser erkannt hat. Ist in der Ergebnisliste mindestens ein leerer String, konnte die Eingabe erkannt werden:

Code: Alles auswählen

    def parse(p, s):
        for rs in p((s,)):
            if not rs:
                return True

Streng genommen ist das hier kein Parser, sondern nur ein "Recognizer", aber das lässt sich ändern.

Zunächst will ich aber mal annehmen, dass `alt` und `seq` beliebig viele Parameter akzeptieren und wenn ein Parameter ein einfacher String ist, dieser automatisch als `word` aufgefasst wird.

Code: Alles auswählen

    thing = seq("the", rep("\\w+"))
    roomdef = seq(thing, "is", "a", "room", "\\.")
    adjroomdef = seq(thing, "is", alt("above", "below"), thing, "\\.")
    itemdef = seq(thing, "is", alt("in", "inside"), thing, "\\.")
    definitions = rep(alt(roomdef, adjroomdef, itemdef))

Rufe ich jetzt `parse(grammar, "The dark attic...")` auf, sollte `True` gemeldet werden.

Ja, der Parser ist EXTREM ineffizient, weil er eine Tiefensuche statt einer Breitensuche macht, aber das ändert nichts am Prinzip. Dank Backtracking kann ich die drei Definitionen unterscheiden, obwohl sie einen beliebig langen Lookahead benötigen.

Um den Recognizer zu einem Parser zu machen, der eine Art AST liefert, kann ich wie folgt vorgehen:

Statt einer Liste von Strings definiere ich, dass `ss` nun eine Liste von Paaren ist, die aus dem String und einer Liste von Listen bestehen, die ich als Stack auffasse. Ich brauche diese relativ komplexe Struktur, um Wörter einfach zu kombinieren.

So sieht mein Startzustand aus:

Code: Alles auswählen

    ((s, ((),)),)

Dies ist eine Liste mit einem Paar, dessen zweites Element ein Stack mit einer leeren Liste ist.

Statt einfach nur den Reststring dem Ergebnis hinzuzufügen:

Code: Alles auswählen

    r += (s[m.end(1):],)

Baue ich nun ein Tupel, bei dem ich zu der obersten Liste auf dem Stack das erkannte Wort hinzufüge. Weil ich das alles funktional ohne veränderbare Objekte mache, benutze ich für alles Tupel:

Code: Alles auswählen

    r += (s[0][m.end(1):], s[1][:-1] + (s[1][-1] + (m.group(1),),),)

Außerdem führe ich einen neuen Parser `a` ein, der eine Funktion auf dem Ergebnis aufrufen kann:

Code: Alles auswählen

    def a(p, f=lambda x:x):
        def a_parser(ss):
            ss = p(tuple((s[0], s[1][-1] + ()) for s in ss))
            return ((s[0], s[1][:-2] + ((s[1][-2] + f(s[1][-1])),)) for s in ss)
        return a_parser

Hier ist die neue `parse`-Funktion:

Code: Alles auswählen

    def parse(p, s):
        for rs, st in p(((s, ((),)),)):
            if rs == "":
                return st[-1]

Das die verschachtelten Tupel völlig unübersichtlich sind, hier eine `State`-Klasse:

Code: Alles auswählen

    class State:
        def __init__(self, rs, st):
            self.rs, self.st = rs, st
        
        def add(self, rs, w):
            st = list(self.st)
            st[-1] = list(st[-1])
            st[-1].append(w)
            return State(rs, st)
        
        def push(self):
            st = list(self.st)
            st.append([])
            return State(self.rs, st)
        
        def pop(self, f):
            st = list(self.st)
            st[-2].extend(f(st.pop()))
            return State(self.rs, st)

    def word_parser(ss):
        r = []
        for s in ss:
            m = pattern.match(s.rs)
            if m:
                r.extend(s.add(s.rs[m.end(1):], m.group(1)))
        return r
    
    def a_parser(ss):
        return (s.pop(f) for s in p(s.push() for s in ss))

TBC

Stefan