Wie natürlich-sprachliche Deklarationen parsen?

[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