parser.py

def split(list):
    "[a] -> (a, [a])"
    return [list[0], list[1:]]

def reduce(list, zero, add):
    "([a], b, (b, a) -> b) -> b"
    for i in range(0, len(list)):
        zero = add(zero, list[i])

    return zero

def pack(charlist):
    "[char] -> string"
    return reduce(charlist, "", lambda x, xs: x + xs)

####

# type parser a = ((a, stream) -> ignored, (e, stream) -> ignored, stream) -> ignored
# Parser receives 3 params:
#  - ok:   function, which takes parsing result and remaining string;
#  - fail: function, which takes error message and its location;
#  - stream to be parsed.
# Then it performs some actions on stream and calls either "ok" or "fail".
# Parser is not supposed to return.

def just(x):
    "a -> parser a"
    return lambda ok, fail, stream: (
        ok(x, stream)
    )

def fail(m):
    "e -> parser anything"
    return lambda ok, fail, stream: (
        fail(m, stream)
    )

def string(s):
    "string -> parser string"
    def it(ok, fail, stream):
        if stream.startswith(s):
            ok(s, stream[len(s):])
        else:
            fail(s, stream)
    return it

def spaces(ok, fail, stream):
    "parser NoneType"
    i = 0
    for i in range(0, len(stream)):
        if stream[i] != ' ':
            break

    ok(None, stream[i:])

####

def match(p, cont):
    "(parser a, (a -> parser b)) -> parser b"
    "supply 'cont' with result of parser 'p'"
    def it(ok, fail, stream):
        def proceed(x, stream):
            cont(x)(ok, fail, stream)

        p(proceed, fail, stream)
    
    return it

def after(p, p1):
    "(parser _, parser b) -> parser b"
    return match(p, lambda _: p1)

def any(description, parsers):
    "(string, [parser a]) -> parser a"
    def it(ok, fail, stream):
        if parsers == []:
            fail(description, stream)
        else:
            first, rest = split(parsers)

            def proceed(_1, _2):
                any(description, rest) (ok, fail, stream)

            first(ok, proceed, stream)

    return it

def many(p):
    "parser a -> [parser a]"
    return any("-", [many1(p), just([])])

def many1(p):
    "parser a -> [parser a]"
    return (
        match(     p,  lambda x:  (
        match(many(p), lambda xs: (
        just([x] + xs)))))
    )

####

def token(p):
    "parser a -> parser a"
    return match(p, lambda s: (
           after(spaces, 
           just (s))))

def oneOf(list):
    "[a] -> parser a"
    def it(ok, fail, stream):
        try:
            list.index(stream[0])
            ok(stream[0], stream[1:])

        except e:
            fail(list, stream)

    return it

def satisfying(pred):
    "(a -> bool) -> parser a"
    def it(ok, fail, stream):
        try:
            c, rest = split(stream)
            (ok(c, rest) if pred(c) else fail("-", stream))
        except:
            fail("-", stream)

    return it

def decorate(message, parser):
    "(string, parser a) -> parser a"
    "changes error message to 'message'"
    return any(message, [parser])

####

"too lazy to 'import re[gexp]'"
identifier = decorate("identifier",
    match(     satisfying(lambda c: c.isalpha()),                 lambda head: (
    match(many(satisfying(lambda c: c.isalpha() or c.isdigit())), lambda rest: (
          just(pack([head] + rest))))))
)

####

def trace(p, s):
    "trace the run of the parser"
    print("parsing <" + s + "> with " + str(p))
    ok   = lambda x, at: print("parsed "   + str(x) + ", remains <" + at + ">")
    fail = lambda x, at: print("expected " + str(x) + " at <" + at + ">")
    p(ok, fail, s)

name = token(identifier)

trace(many(name), "as1 a1d 1fg")
trace(after(name, name), "as1 1ad 1fg")