#!/usr/bin/env python

(C) 2005 by Damir Cavar

   This code is free; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

This code is a simple implementation of an agenda-based top-down parser
with backtracking.

In the code you can control the behavior of the parser, i.e. simulate
depth-first or breadth-first by changing the element that is taken from the
agenda, the first or the last one.

import sys, grammar

LIFO = -1
FIFO = 0
strategy = FIFO

def tdparse(input, goal, grammar, agenda):
   """Recursive top-down parse function with weak generative capacity."""

   #print "Got : %s\tinput: %s\nwith agenda:\n%s" % (goal, input, agenda)
   print "Got : %s\tinput: %s" % (goal, input)

   if goal == input == []:
      print "Success"
   elif goal == [] or input == []:
      if agenda == []:
         print "Fail: Agenda empty!"
         entry = agenda.pop(strategy)
         print "Backing up to: %s with %s" % (entry[0], entry[1])
         tdparse(entry[1], entry[0], grammar, agenda)
   else: # there is something in goal and input
      if goal[0] == input[0]: # if initial symbols match, reduce lists, parse
         tdparse(input[1:], goal[1:], grammar, agenda)
         for i in grammar.LHS.get(goal[0], []):
            if [list(i) + goal[1:], input] not in agenda:
               agenda.append([list(i) + goal[1:], input])
         if len(agenda) > 0:
            entry = agenda.pop(strategy)
            tdparse(entry[1], entry[0], grammar, agenda)
            print "Fail: Agenda empty!"

if __name__ == "__main__":
   if len(sys.argv[1:]) > 0:
      myGrammar = grammar.PSG("PSG1.txt")
      print myGrammar
      tdparse(sys.argv[1:], ["S"], grammar.PSG("PSG1.txt"), [])
      print "Example parse:"
      input = ["Mary", "kissed", "John"]
      tdparse(input, ["S"], grammar.PSG("PSG1.txt"), [])