codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# # 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")
Private
[
?
]
Run code
Submit