codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# simplified monadic (PEG) parser. no memoization, some backtracking. # parser :: str -> maybe (value, str) def ret (value): return lambda s: (value, s) def bind (p, *fs): def parse (s): res = p(s) for f in fs: res = res and f(res[0])(res[1]) return res return parse never = lambda s: False def alt (*ps): def parse (s): for p in ps: res = p(s) if res: return res return False return parse empty = ret(None) def then (p, *ps): return bind(p, lambda x: bind(then(*ps), lambda rest: ret([x]+rest)) if ps else ret([x])) def repeat (p, res=[]): return alt( bind(p, lambda v: repeat(p, res+[v])), ret(res) ) def repeat1 (p): return bind(p, lambda v: repeat(p, [v])) def pred (f): def parse (s): if s and f(s[0]): return (s[0], s[1:]) else: return False return parse def char (ch): return pred(lambda c: c==ch) def literal (s): return then(*(char(c) for c in s)) def delay (fn): return bind(empty, lambda _:fn()) def option (p): return alt(p, empty) def repn (p, n): return then(*([p]*n)) end = lambda s: False if s else (None, s) # try out some parsing def tryit (lang, inp): print "parsing", repr(inp), "with", lang print " ==>", then(eval(lang), end)(inp) parens = alt( then( char('('), delay(lambda:parens), char(')') ), empty ) tryit('parens', '()') tryit('parens', '((()))') tryit('parens', '(()') term = alt( repeat1(pred(str.isdigit)), then(char('('), delay(lambda:expr), char(')'))) arith = then(term, repeat(then(alt(char('*'), char('/')), delay(lambda:term)))) expr = then(arith, repeat(then(alt(char('+'), char('-')), delay(lambda:arith)))) tryit('expr', '1') tryit('expr', '1+2') tryit('expr', '1+2*3+(4+5)*6') name = repeat1(pred(str.isalpha)) opentag = bind(char('<'), lambda _: name, lambda n: bind(char('>'), lambda _: ret(''.join(n)))) def closetag(n): return then(literal('</'), literal(n), char('>')) xmls = repeat(delay(lambda:xml)) xml = bind(opentag, lambda n: then(xmls, closetag(n))) tryit('xml', '<a></a>') tryit('xml', '<a><b><c></c><d></d></b></a>')
Private
[
?
]
Run code
Submit