Unser Programm läuft jetzt. Enthalte small.gr folgende Grammatik:
S -> NP VP OP -> det no NP -> det n vt -> "bites" det -> "a" vt -> "eats" det -> "the" no -> "man" VP -> vt OP n -> "dog"
Dann:
examples> gener-with-classes.py small.gr 5 a dog bites a man a dog bites the man a dog eats a man a dog eats the man the dog bites a man the dog bites the man the dog eats a man the dog eats the man
Jetzt wollen wir noch die Ableitungen sehen. Dafür bauen wir generate so um, dass in seenDict jetzt immer drinsteht, aus welchem Wort das augenblickliche Wort abgeleitet ist. Außerdem drucken wir die Ableitungen nicht mehr, sondern hängen sie in eine (vorerst globale) Liste.
Das sieht dann so aus:
def generate(curWord, grammar, maxLen, sourceWord, seenWords={}): if seenWords.has_key(curWord): return else: if sourceWord: seenWords[curWord] = sourceWord if len(curWord)>maxLen: return if curWord.isAllTerminal(): allDerivations.append(curWord) for deriv in deriveLeft(curWord, grammar): generate(deriv, grammar, maxLen, curWord, seenWords)
Damit das Sinn hat, ändern wir noch:
if __name__=="__main__": allDerivations = [] grammar = Grammar.Grammar(sys.argv[1]) derivDict = {} generate(word.Word(str( grammar.getStartSymbol())), grammar, int(sys.argv[2]), None, derivDict) for d in allDerivations: printDerivation(d, derivDict)
Das seenWords-Dictionary könnte dann für unsere aibai-Grammatik so aussehen:
{Word('b'): Word('S'), Word('a a a S a a a'): Word('a a S a a'), Word('a b a'): Word('a S a'), Word('a a S a a'): Word('a S a'), Word('a a b a a'): Word('a a S a a'), Word('a S a'): Word('S')}
Diese Datenstruktur enthält alles, was wir brauchen, um eine komplette Ableitung zu rekonstruieren. Wir müssen nur beim fertigen Wort anfangen, im Dictionary nachsehen, was der Vorgänger war und dann nach dessen Vorgänger sehen. Als Pseudocode:
Eingabe: Ein abgeleitetes Wort w, ein Dictionary, das Ableitungen auf ihre Vorgänger abbildet d
Setze ableitung auf die Liste, in der nur w enhalten ist
Solange am Ende von w einen Vorgänger hat:
Setze w auf den Vorgänger von w
Hänge w an ableitung an
Rückgabe: Die Umkehrung von ableitung
Das lädt zu einer while-Schleife ein:
def printDerivation(word, derivDict): derivList = [word] while derivDict.has_key(word): derivList.append(derivDict[word]) word = derivDict[word] if len(derivList)>1: derivList.reverse() print " -> ".join(map(str, derivList))
Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen
(1)
Die globale Variable allDerivations macht natürlich so in etwa alles falsch, was man (stilistisch) falsch machen kann: Sie ist nicht nur global, sie wird auch noch in tief in rekursiven Funktionen verändert.
Welche Alternativen kennt ihr, um damit besser umzugehen?