[ create a new paste ] login | about

Link: http://codepad.org/YrJFOLm2    [ raw code | output | fork ]

aaronla - Python, pasted on May 5:
#
# cpexhaustivetopdown.py
#

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

def empty (input):
  step()
  yield input, None

def fail (input):
  step()
  return []

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

def end (input):
  step()
  if not input:
    yield input, None

def seq (a, b):
  def seq_parse (input):
    step()
    for rest, r1 in a(input):
      for rest2, r2 in b(rest):
        yield rest2, [r1,r2]
  return seq_parse

def alt(a, b):
  def alt_parse (input):
    step()
    for rest, r in a(input):
      yield rest, r
    for rest, r in b(input):
      yield rest, 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

  i = 0
  for _, r in g(input):
    i += 1
    if i < 3:
      print r

  c1 = counter
  print "~", "%s solutions" % i if i else "failed", "%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")


Output:
parsing 1
['1', None]
~ 1 solutions 20 steps
parsing 1+1
[['1', ['+', '1']], None]
~ 1 solutions 40 steps
parsing 1+0-1-0
[['1', ['+', ['0', ['-', ['1', ['-', '0']]]]]], None]
~ 1 solutions 80 steps
parsing 1+(0-1)-((0)+1)
[['1', ['+', [['(', [['0', ['-', '1']], ')']], ['-', ['(', [[['(', ['0', ')']], ['+', '1']], ')']]]]]], None]
~ 1 solutions 308 steps
parsing 
[[None, [None, [None, [None, None]]]], None]
~ 1 solutions 21 steps
parsing a
[['a', [None, [None, [None, None]]]], None]
[[None, ['a', [None, [None, None]]]], None]
~ 5 solutions 62 steps
parsing aa
[['a', ['a', [None, [None, None]]]], None]
[['a', [None, ['a', [None, None]]]], None]
~ 10 solutions 106 steps
parsing aaa
[['a', ['a', ['a', [None, None]]]], None]
[['a', ['a', [None, ['a', None]]]], None]
~ 10 solutions 132 steps


Create a new paste based on this one


Comments: