parser combinators in python

parser.py

from collections import namedtuple

Lazy = namedtuple('Lazy', 'force')


def parseConst(a):
  """
  >>> parseConst(1)('')
  [(1, '')]
  """
  return lambda s: [(a, s)]


def parseNothing(s):
  return []


def parseString(target):
  """
  >>> parseString('foo')('foobar')
  [('foo', 'bar')]
  """
  def p(s):
    if s.startswith(target):
      return [(target, s[len(target):])]
    else:
      return []
  return p


def parseEither(p1, p2):
  """
  >>> list(parseEither(parseString('foo'), parseString('bar'))('bar'))
  [('bar', '')]
  """
  def p(s):
    for r in p1(s):
      yield r
    for r in p2(s):
      yield r
  return p


def parseBoth(p1, p2):
  """
  >>> list(parseBoth(parseString('foo'), parseString('bar'))('foobar'))
  [(('foo', 'bar'), '')]
  >>> list(parseBoth(Lazy(lambda: parseString('foo')), Lazy(lambda: parseString('bar')))('foobar'))
  [(('foo', 'bar'), '')]
  """
  if not isinstance(p1, Lazy):
    actualp1 = p1
    p1 = Lazy(lambda: actualp1)
  if not isinstance(p2, Lazy):
    actualp2 = p2
    p2 = Lazy(lambda: actualp2)

  def p(s):
    return (((a, b), s2) for (a, s1) in p1.force()(s) for (b, s2) in p2.force()(s1))
  return p


def mapParser(f, p):
  """
  >>> list(mapParser(lambda x: x+1, parseConst(2))('bla'))
  [(3, 'bla')]
  """
  def q(s):
    return ((f(a), s1) for (a, s1) in p(s))
  return q


def runParser(p, s):
  """
  >>> runParser(parseString('foo'), 'foo')
  'foo'
  >>> runParser(parseString('foo'), 'foobar')
  >>> runParser(parseString('foo'), 'bar')
  """
  complete = (a for (a, s1) in p(s) if s1 == '')
  try:
    return complete.next()
  except:
    return None


def star(p):
  """
  >>> list(star(parseString('x'))('xxx'))
  [(['x', 'x', 'x'], ''), (['x', 'x'], 'x'), (['x'], 'xx'), ([], 'xxx')]
  """
  cons = mapParser(lambda (h, t): [h] + t, parseBoth(p, Lazy(lambda: star(p))))
  nil = parseConst([])
  return parseEither(cons, nil)


def plus(p):
  """
  >>> list(plus(parseString('x'))('xxx'))
  [(['x', 'x', 'x'], ''), (['x', 'x'], 'x'), (['x'], 'xx')]
  """
  return mapParser(lambda (h, t): [h] + t, parseBoth(p, star(p)))


def parseAny(ps):
  """
  >>> list(parseAny(map(parseConst, ['a', 'b', 'c']))(''))
  [('a', ''), ('b', ''), ('c', '')]
  """
  return reduce(parseEither, ps, parseNothing)


###############################################################################

Number = namedtuple('Number', ['n'])
Sum = namedtuple('Sum', ['n', 'm'])
Product = namedtuple('Product', ['n', 'm'])


def evalExpr(e):
  """
  >>> evalExpr(Sum(Number(1), Product(Number(2), Number(3))))
  7
  """
  if isinstance(e, Number):
    return e.n
  elif isinstance(e, Sum):
    return evalExpr(e.n) + evalExpr(e.m)
  elif isinstance(e, Product):
    return evalExpr(e.n) * evalExpr(e.m)
  else:
    raise ValueError(
        '{}:{} must be a Number|Sum|Product tree'.format(e, type(e))
    )

parseDigit = parseAny(map(parseString, ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']))
parseDigit.__doc__ = """
>>> list(parseDigit('7'))
[('7', '')]
>>> list(parseDigit('x'))
[]
"""

parseNumber = mapParser(lambda ds: Number(int(''.join(ds))), plus(parseDigit))
parseNumber.__doc__ = """
>>> list(parseNumber("123x"))
[(Number(n=123), 'x'), (Number(n=12), '3x'), (Number(n=1), '23x')]
"""


def parseBinary(op, f, base):
  single = base
  multiple = mapParser(
      lambda ((a, _), b): f(a, b),
      parseBoth(
          parseBoth(single, parseString(op)),
          Lazy(lambda: parseBinary(op, f, base))
      )
  )
  return parseEither(multiple, single)

parseProduct = parseBinary('*', Product, parseNumber)
parseProduct.__doc__ = """
>>> list(parseProduct('2*3'))
[(Product(n=Number(n=2), m=Number(n=3)), ''), (Number(n=2), '*3')]
"""

parseSum = parseBinary('+', Sum, parseProduct)
parseSum.__doc__ = """
>>> list(parseSum('2+3'))
[(Sum(n=Number(n=2), m=Number(n=3)), ''), (Number(n=2), '+3')]
>>> runParser(parseSum, '1+2*3')
Sum(n=Number(n=1), m=Product(n=Number(n=2), m=Number(n=3)))
"""


def main():
  while True:
    print "Enter an expression to evaluate or q to quit"
    print "> ",
    raw = raw_input()
    if raw == 'q':
      break
    trees = list(parseSum(raw))
    if not trees:
      print "Could not parse the expression"
      continue
    print evalExpr(trees[0][0])


if __name__ == '__main__':
  import doctest
  doctest.testmod()
  main()