combinator-parser.py

def fail():
  "Returns a parser that fails on every input."
  return lambda s: None
 
def char(c):
  "Returns a parser that matches 'c' and fails otherwise."
  return lambda s: (s[1:], c) if s and s[0] == c else None
 
def alt(p1, p2):
  "Returns a parser that applies either parser 'p1' or 'p2'."
  return lambda s: p1(s) or p2(s)
 
def digit():
  "Returns a parser that matches '0'..'9'."
  return reduce(lambda p, c: alt(p, char(c)), "0123456789", fail())

def rep(p):
  "Returns a parser that applies 'p' as often as possible."
  def _(s):
    def a(s, l):
      r = p(s)
      if r:
        return a(r[0], l + [r[1]])
      return s, l
    return a(s, [])
  return _
 
def seq(p1, p2):
  "Returns a parser that applies 'p1' and, if that didn't fail, 'p2'."
  def _(s):
    r1 = p1(s);
    if r1:
      r2 = p2(r1[0])
      if r2:
        return r2[0], [r1[1], r2[1]]
  return _
 
def a(p, f):
  "Returns a parser that applies 'f' to a successful parsing result."
  def _(s):
    r = p(s)
    if r:
      return r[0], f(r[1])
  return _
 
def digits():
  "Returns a parser that matches one or more digits."
  return a(seq(digit(), rep(digit())), lambda v: "".join([v[0]] + v[1]))
 
def Lit(v): return lambda x: v
def X(): return lambda x: x
def Op(op): return lambda l, r: lambda x: op(l(x), r(x))
Mul = Op(int.__mul__)
Add = Op(int.__add__)
Sub = Op(int.__sub__)
 
def const():
  "Returns a parser that parses a number into a 'Lit' object."
  return a(digits(), lambda v: Lit(int(v)))
 
def x():
  "Returns a parser that parses an 'x' into an 'X' object."
  return a(char('x'), lambda v: X())
 
def mult():
  "Returns a parser that parses a number followed by x into a 'Mul(Lit, X)' object."
  return a(seq(const(), x()), lambda v: Mul(*v))
 
def factor():
  "Returns a parser that parses <num>x or x."
  return alt(mult(), alt(const(), x()))
 
def add():
  "Returns a parser that parses +<factor> into a reducable function."
  return a(seq(char('+'), factor()), lambda v: lambda l: Add(l, v[1]))
 
def sub():
  "Returns a parser that parses -<factor> into a reducable function."
  return a(seq(char('-'), factor()), lambda v: lambda l: Sub(l, v[1]))
 
def term():
  "Returns a parser that parses additions, subtractions factors."
  return a(seq(factor(), rep(alt(add(), sub()))),
    lambda v: reduce(lambda x, f: f(x), v[1], v[0]))
 
# examples
print term()("2x")[1](21)
print term()("124x+9x-17x+10-6x")[1](10)