#!/usr/bin/env python

"""
BUAParser.py
(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 is an implementation of a simple agenda-based buttom-up parser with
backtracking.

You can change the behavior of the parser by setting the value in the code
line:

strategy = FIFO

to the LIFO or FIFO. This simulates breadth first or depth first, respectively.
"""

import sys, grammar

LIFO = -1
FIFO = 0
strategy = LIFO

def parse(input, grammar, rootsymbol):
   """Simple non-recursive bottom up parser."""
   agenda = []
   while True:
      print "Input: %s" % (input,)
      if input == rootsymbol:
         print "Success!"
         break
      else:
         for i in range(1, len(input) + 1):     # window
            for j in range(len(input) - i + 1): # movement
               for lhs in grammar.RHS.get(tuple(input[j:i + j]), []):
                  newhyp = input[:j] + [lhs] + input[i + j:]
                  if newhyp not in agenda:
                     agenda.append(newhyp)
         if len(agenda) > 0:
            input = agenda.pop(strategy)
            print "Backing up to: ", input
         else:
            if input == rootsymbol:
               print "Success!"
            else:
               print "Failure! No more backtracking!"
            break


if __name__ == "__main__":
   if len(sys.argv[1:]) > 0:
      parse(sys.argv[1:], grammar.PSG("PSG1.txt"), ['S'])
   else:
      print "Example parse:"
      input=["the", "cat", "chases", "a", "mouse"]
      parse(input, grammar.PSG("PSG1.txt"), ['S'])