parsercomb.nim

import strutils

type ParseState = seq[tuple[this, remaining: string]]
type Parser = proc(s: string): ParseState

proc literal(m: string): Parser =
    return proc(s: string): ParseState =
        if s.startsWith(m):
            return @[(m, substr(s, len(m)))]
        else:
            return @[]

proc peek[T](s: seq[T]): T =
    return s[len(s)-1]

proc many1(p: Parser): Parser =
    return proc(s: string): ParseState =
        var pss: seq[ParseState]
        pss.add(p(s))
        while true:
            var ps: ParseState
            for (m, r) in pss.peek():
                for (m1, r1) in p(r):
                    ps.add((m & m1, r1))
            if len(ps) == 0:
                break
            else:
                pss.add(ps)
        var res: ParseState
        for ps in pss:
            for s in ps:
                res.add(s)
        return res

proc then(p1, p2: Parser): Parser =
    return proc(s: string): ParseState =
        var ps = p1(s)
        var ps1: ParseState
        for (m, r) in ps:
            for (m1, r1) in p2(r):
                ps1.add((m&m1, r1))
        return ps1

proc eof(s: string): ParseState =
    if len(s) == 0:
        return @[("", "")]
    else:
        return @[]

var f = many1(literal("a")).then(literal("b")).then(eof)
echo f("aaaaab")