# TODO: examples
# FIXME: error messages
class ParseError(Exception):
def __init__(self, msg=""):
self.msg = msg
def __str__(self):
return self.msg
class Parser:
"""Parser :: (( String -- Input String
, Int -- Cursor position within input
, (a -> Int -> r) -- Success continuation
, (err -> r) -- Failure continuation
) -> r) -> Parser
"""
def __init__(self, go):
self._go = go
def __str__(self):
""" __str__ :: Parser -> String """
return "<Parser>"
def parse(self,inp):
"""parse :: Parser a -> String -> a
Run the given parser for the given input string, returning the given
value or raising `ParseError` on an failing parse.
Arguments:
inp -- the input string
"""
def cont(v,p): return v
def fail(err): raise ParseError(err)
return self._go(inp,0,cont,fail)
def __call__(self,inp):
"""See `parse`"""
return self.parse(inp)
def map(self, f):
"""map :: (a -> b) -> Parser a -> Parser b
Modify the return value of the given parser by applying the given
function
Arguments:
f -- the function to apply
Returns: A parser which returns the modified value when applied
"""
def _go(inp,pos,cont,fail):
def newCont(val,pos):
return cont(f(val),pos)
return self._go(inp,pos,newCont,fail)
return Parser(_go)
def asThough(self,v):
"""as :: b -> Parser a -> Parser b
Override the return value of the given parser to use the given value
instead
"""
return self.map(lambda _:v)
def bind(self, f):
"""bind :: Parser a -> (a -> Parser b) -> Parser b
Construct a parser from a given parser and a function which has access
to it's inner value
Arguments:
f -- the binding function
Returns: The Parser constructed from the binding func.
"""
def _go(inp,pos,cont,fail):
def newCont(val,npos):
return f(val)._go(inp,npos,cont,fail)
return self._go(inp,pos,newCont,fail)
return Parser(_go)
def __rshift__(self, other):
"""See `bind`"""
return self.bind(other)
def then(self,other):
"""Sequence two parsers, ignoring the left result"""
return self.bind(lambda _:lift(other))
def over(self,tail):
"""Sequence two parsers, ignoring the right result"""
return self.bind(lambda v: lift(tail).asThough(v))
def orElse(self, other):
"""orElse :: Parser a -> Parser b -> Parser (Either a b)
Attempt to apply the left parser, and then the right parser if the left
one fails to parse.
Arguments:
other -- A parser to apply if the left parser fails
Returns: A Parser which accepts anything accepted by either left or
right.
"""
def _go(inp,pos,cont,fail):
def leftFail(leftMsg):
def rightFail(rightMsg):
return fail(leftMsg+rightMsg)
return other._go(inp,pos,cont,rightFail)
return self._go(inp,pos,cont,leftFail)
return Parser(_go)
def __or__(self,other):
"""See `orElse`"""
return self.orElse(other)
def desc(self,msg):
"""Attach a message to the given parser to use for descriptive error
messages on failure
"""
def _go(inp,pos,cont,fail):
def newFail(_):
return fail(msg)
return self._go(inp,pos,cont,newFail)
return Parser(_go)
def fail(msg):
"""Return a parser which always fails with the given message"""
def _go(inp,pos,cont,fail):
return fail(msg)
return Parser(_go)
def pure(val):
"""pure :: a -> Parser a
Return a parser which always returns with the given value, consuming no
input
"""
def _go(inp,pos,cont,fail):
return cont(val,pos)
return Parser(_go)
def optional(prs, default=None):
"""optional :: Parser a -> Parser (Maybe a)
Return a parser which attempts to apply the inner parser. On failure,
continue as if no input was consumed with the given default value.
Arguments:
prs -- the parser which may or may not succeed
default -- the value to return if the inner parser fails (default: None)
"""
def _go(inp,pos,cont,fail):
def newFail(_):
return cont(default,pos)
return lift(prs)._go(inp,pos,cont,newFail)
return Parser(_go)
def many(prs):
"""many :: Parser a -> Parser [a]
Construct a parser which applies the given parser as many times as possible
(zero or more), returning collected results in a list.
NB: many(many(whatever)) ==> stack overflow #FIXME
"""
accum = []
def _go(inp,pos,cont,fail):
def newFail(_):
res = accum[:]
accum.clear()
return cont(res, pos)
def newCont(a,pos):
accum.append(a)
return lift(prs)._go(inp,pos,newCont,newFail)
return lift(prs)._go(inp,pos,newCont,newFail)
return Parser(_go)
def many1(prs):
"""As `many` except inner parser is applied at least once, or fail
completely.
"""
return lift(prs).bind(lambda v: many(prs).map(lambda vs : [v]+vs))
def manyTill(prs, end):
"""Repeatedly apply a given parser until a secondary end parser succeeds.
Return values are accumulated and returns as a list
"""
END_PARSER_SENTINEL = object()
def _inBind(v):
if v is END_PARSER_SENTINEL: #not at eol
return lift(prs).bind(lambda val : manyTill(prs, end).map(lambda vs, val=val : [val]+vs))
else: #at eol
return pure([])
return optional(lift(end), default=END_PARSER_SENTINEL).bind(_inBind)
def choice(*prss):
"""Construct a parser by `orElse`ing the given list of parsers together."""
if len(prss) == 1 and type(prss[0]) is list:
prss = prss[0]
p = fail("choice: empty list of choices")
for prs in prss:
p = p.orElse(lift(prs))
return p
def sequence(*prss):
"""Construct a parser by `bind`ing the given list of parsers together. The
results of the inner parsers are returned as an in-order list
"""
if len(prss) == 1 and type(prss[0]) is list:
prss = prss[0]
p = pure([])
for prs in prss:
p = p.bind(lambda l, prs=prs : lift(prs).map(lambda v : l+[v]))
return p
def satisfy(pred,desc=None):
"""satisfy :: (Char -> Bool) -> Parser Char
Construct a parser which succeeds and returns the next char if it satisfies
the given predicate. Otherwise fail.
Arguments:
pred -- a predicate to apply to the next char
desc -- a description of what 'success' looks like (default: None)
"""
def _go(inp,pos,cont,fail):
if pos < len(inp):
c = inp[pos]
if pred(c):
return cont(c, pos+1)
return fail(desc)
return Parser(_go)
def char(c):
"""Construct a parser for the given char"""
assert type(c) is str and len(c) == 1, "char: input must be a single char"
return satisfy(lambda d: d==c, "expected: '"+c+"'")
def string(s):
"""Construct a parser for the given string"""
p = pure([])
for ch in s:
p = p.then(char(ch))
return p.asThough(s)
def lift(p):
"""Convert an argument of arbitrary type to the coresponding parser"""
pType = type(p)
if pType is Parser:
return p
elif pType is str:
return string(p)
elif pType is list:
return sequence(lift(q) for q in p)
elif "__str__" in p:
return lift(str(p))
else:
raise TypeError("lift: can't lift value of type `"+pType+"`")
#------ Examples ------#
anyChar = satisfy(lambda _:True,"any char")
def toNum(s):
s = ''.join(s)
try:
return int(s)
except ValueError:
try:
return float(s)
except ValueError: #Give up; return unchanged
return s
def isDigit(c):
return c.isdigit() or (c in ".+-")
number = many1(satisfy(isDigit, "digit")).map(toNum).desc("number")
EOL = object()
eol = satisfy(lambda c:c == '\n', "EOL").asThough(EOL)
whitespace = many1(satisfy(lambda c:c.isspace())).desc("whitespace")
def token(p):
return optional(whitespace).then(p)
somestring = manyTill(anyChar, whitespace)