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
|
|