45. Ableitungen

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 aⁱbaⁱ-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))