TDP v1
2010-06-27 14:30:05

strategy = "FIFO" # LIFO oder FIFO
trace = True

gram1 = {'S':  [['NP', 'VP']],
         'VP': [['V'], ['V', 'NP']],
         'NP': [['Name'], ['DET', 'N']]}

lex1 = {'Sue':   ['Name'],
        'girl':  ['N'],
        'leaves':['N', 'V'],
        'saw':   ['V'],
        'a':     ['DET'],
        'the':   ['DET']}

gram2 = {'S':  [['NP', 'VP']],
         'NP': [['PNAME'], ['NP', 'GEN_S', 'N']],
         'VP': [['V']]}

lex2 = {'John':    ['PNAME'],
        'mother':  ['N'],
        'sister':  ['N'],
        's':       ['GEN_S'],
        'arrived': ['V']}

gram3 = {'S': [['X'], ['Y']],
         'X': [['X'], ['Y'], ['Y', 'X'], ['X', 'Y']],
         'Y': [['X'], ['Y'], ['Y', 'X'], ['X', 'Y']]}

lex3 = {'foo': ['X'],
        'bar': ['Y']}

def tdp(string, (gram, lex)):
   G = (gram, lex)
   wlist = string.split()
   agenda = [(wlist, ['S'], [])]
   (cur_search_state, agenda) = next(agenda)
   while True:
      if accept_state(cur_search_state):
         return "accept"
      else:
         agenda = generate_new_states(cur_search_state, agenda, string, G)
         if trace: print "%s, agenda %s\n" % (cur_search_state, agenda)
         if len(agenda) == 0:
            return "reject"
         else:
            (cur_search_state, agenda) = next(agenda)

def generate_new_states((wlist, goals, visited), agenda, string, (gram,lex)):
   new_states = []
   # terminals
   if len(goals) > 0 and len(wlist) > 0 and wlist[0] in lex:
      if goals[0] in lex[wlist[0]]:
         new_states += [(wlist[1:], goals[1:], [])]
   
   # nonterminals
   if len(goals) > 0 and goals[0] in gram:
      for rhs in gram[goals[0]]:
         if len(rhs + goals[1:]) <= len(wlist): # gegen Links-Rekursion
            if (goals[0], rhs) not in visited:
               new_states += [(wlist, rhs + goals[1:], visited+[(goals[0], rhs)])]
   
   return new_states + agenda

def accept_state((wlist, goals, visited)):
   if wlist == [] and goals == []:
      return True
   else:
      return False

def next(agenda):
   if strategy == "LIFO":
      if len(agenda) > 1:
         return (agenda[0], agenda[1:])
      else:
         return (agenda[0], [])
   elif strategy == "FIFO":
      if len(agenda) > 1:
         return (agenda[-1], agenda[:-1])
      else:
         return (agenda[0], [])

#print tdp("John s mother s sister s sister arrived", (gram2, lex2));
print tdp("John s mother s mother s sister s s sister arrived", (gram2, lex2));
#print tdp("foo bar", (gram3, lex3));