#
# cpsimpletopdown.py
#

counter = 0
def step ():
  global counter;
  counter+=1

def empty (input):
  step()
  return input, True

def fail (input):
  step()
  pass

def lit (s):
  def parse (input):
    step()
    if input and input[0] == s:
      return input[1:], input[0]
    else:
      return input, False
  return parse

def end (input):
  step()
  if not input:
    return input, True
  else:
    return input, False

def seq (a, b):
  def seq_parse (input):
    step()
    input, r1 = a(input)
    if r1:
      input, r2 = b(input)
      if r2:
        return input, [r1,r2]
    return input, None
  return seq_parse

def alt(a, b):
  def alt_parse (input):
    step()
    #which?
    input, r = a(input)
    if not r:
      input, r = b(input)
    return input, r
  return alt_parse

def lazy (thunk):
  def parse (input):
    step()
    return thunk()(input)
  return parse

def tryit (g, input):
  c0 = counter
  print "parsing", input

  _, r = g(input)
  c1 = counter
  if r: print r
  print "~", "%s steps" % (c1-c0)

number = alt(alt(lit('0'), lit('1')),
             seq(lit('('), seq(lazy(lambda:arithmetic), lit(')'))))
operator = alt(lit('+'), lit('-'))
arithmetic = alt(
  number, 
  seq(number, seq(operator, lazy(lambda:arithmetic))))
start = seq(arithmetic, end)

tryit(start, "1")
tryit(start, "1+1")
tryit(start, "1+0-1-0")
tryit(start, "1+(0-1)-((0)+1)")

aamb = alt(lit('a'), empty)
aambn = seq(seq(aamb, seq(aamb, seq(aamb, seq(aamb, aamb)))), end)

tryit(aambn, "")
tryit(aambn, "a")
tryit(aambn, "aa")
tryit(aambn, "aaa")

parsing 1
['1', True]
~ 7 steps
parsing 1+1
~ 7 steps
parsing 1+0-1-0
~ 7 steps
parsing 1+(0-1)-((0)+1)
~ 7 steps
parsing 
[[True, [True, [True, [True, True]]]], True]
~ 21 steps
parsing a
[['a', [True, [True, [True, True]]]], True]
~ 20 steps
parsing aa
[['a', ['a', [True, [True, True]]]], True]
~ 19 steps
parsing aaa
[['a', ['a', ['a', [True, True]]]], True]
~ 18 steps