parser.js

var {tokenize, tokens, stdConf} = require('./tokenizer.js');

var run = (parser, text) => parser(tokenize(text, stdConf))

var ok  = (x, s) => ({stream: s, good: true, value: x})
var err = (x, s) => ({stream: s, message: x})

var pure = (x) => (s) => ok(x, s)
var fail = (x) => (s) => err(x, s)

var apply = (fn, ...parsers) => (s) => {
    var accum = []
    for (var i = 0; i < parsers.length; i++) {
        var res = parsers[i](s)
        if (res.good) {
            s = res.stream
            accum.push(res.value);
        } else {
            return res
        }
    }
    return ok(fn.apply(null, accum), s)
}

var getPosition = s => ok(s, s)

var produce = (...args) => {
    var significant = (f) => (...args) => {
        var argz = []
        for (var i = 0; i < args.length; i++)
            if (args[i])
                argz.push(args[i])
        return f.apply(null, argz)
    }
    var argz = [significant(args[args.length - 1])]
    for (var i = 0; i < args.length - 1; i++)
        argz.push(args[i])
    return apply.apply(null, argz)
}

var any = (msg, ...parsers) => (s) => {
    for (var i = 0; i < parsers.length; i++) {
        var res = parsers[i](s)
        if (res.good || s.char > res.stream.char)
            return res
    }
    return err(msg, s)
}

var lookahead = (parser) => (s) => {
    var res = parser(s)
    if (!res.good)
        res.stream = s
    return res
}

var many = (p) => (s) => {
    var acc = []
    for (;;) {
        var res = p(s)
        if (res.good && res.stream.char == s.char)
            throw new Error({
                message: "many(p): p succeed, nothing consumed",
            })

        if (!res.good)
            return ok(acc, s)

        acc.push(res.value)
        s = res.stream
    }
}

var some = (p) => apply((x, xs) => {xs.unshift(x); return xs}, p, many(p))

var satisfies = (msg, p) => (s) => {
    if (s && p(s.text)) {
        return ok(s.text, s.next)
    }
    return err(msg, s)
}

var silently = (p) => produce(p, x => null)

var onDemand = (lp) => {
    var p = null
    return (s) => {
        p = p || lp()
        return p(s)
    }
}

var fs = require("fs")

var parseFile = (p, file) => {
    var text = fs.readFileSync(file).toString()
    return run(p, text)
}

module.exports = (
    { run
    , parseFile
    , silently
    , onDemand
    , pure
    , fail
    , apply
    , produce
    , many
    , some
    , any
    , lookahead
    , satisfies
    , getPosition
    }
)

syntax.js

"use strict";

var { run
    , parseFile
    , silently
    , onDemand
    , pure
    , fail
    , apply
    , produce
    , many
    , some
    , any
    , lookahead
    , satisfies
    , getPosition
    } = require('./parser.js')

var tell = (at, x) => {
    // console.log({at, produced: x});
    return x
}

var reservedNames = ["let", "in", ";", "=", "\\", "->", '', '<EOS>', "{", "}"]

var isReservedName  = (tok) => reservedNames.find(x => x == tok) == tok
var isStringLiteral = (tok) => tok.startsWith('"') || tok.startsWith("'")
var isNumberLiteral = (tok) => "0123456789".includes(tok[0])

var layouted = (p) => (
    produce
      ( token("{")
      , optional(token(";"))
      , sepBy(token(";"), p)
      , token("}")
      , xs => xs
      )
)

var sepBy = (sep, p) => (
    produce
      ( p
      , many(produce(sep, p, x => x))
      , (x, xs) => [x].concat(xs)
      )
)

var optional = (p) => (
    any ( "optional"
        , p
        , silently(pure(1))
        )
)

var name = satisfies("name", (tok) => !
    (  isReservedName(tok)
    || isStringLiteral(tok)
    || isNumberLiteral(tok)
    )
)

var token = (tok) => silently(satisfies("== " + tok, (curr) => curr == tok))

var string = satisfies("string literal", isStringLiteral)
var number = satisfies("number literal", isNumberLiteral)

var expr = onDemand(() => (produce
    ( some(terminal)
    , (values) => tell("app", {type: "app", values})
    )
))

var commented = (p) => any("comment or doc"
    , produce
        ( token("comment")
        , string
        , p
        , (comment, value) => Object.assign({}, value, {comment})
        )
    , produce
        ( token("doc")
        , string
        , p
        , (comment, value) => Object.assign({}, value, {doc})
        )
    , p
)

var binding = commented(produce
    ( name
    , many(name)
    , token('=')
    , expr
    , (name, args, body) => tell("binding", {type: "binding", name, args, body})
    )
)

var letExpr = (produce
    ( token("let")
    , layouted(binding)
    , token("in")
    , expr
    , (bindings, expr) => tell("letExpr", {type: "let", bindings, expr})
    )
)

var lambda = (produce
    ( token("\\")
    , some(name)
    , token("->")
    , expr
    , (args, body) => tell("lambda", {type: "lambda", args, body})
))

var terminal = commented(any("terminal"
    , string
    , number
    , produce(token("("), expr, token(")"), (e) => tell("braced terminal", e))
    , letExpr
    , lambda
    , name
))

var prettifyParseResult = (res) => {
    if (res.value)
        return res.value
    return "Expected "
         + res.message
         + ", but found "
         + res.stream.text
         + " at "
         + JSON.stringify({col: res.stream.col, line: res.stream.line})
}

try {
    console.log(prettifyParseResult(parseFile(expr, "test.lc")));
} catch (e) {
    console.log(e.stack);
} finally {

}

test.lc

let
  y = 1
  z h x = 2
in
  \x -> x

tokenizer.js

"use strict";

module.exports.tokenize = (text, conf) =>
    conf ? asList(applyLayout(module.exports.tokens(text), conf))
         : asList(module.exports.tokens(text))

module.exports.tokens = (stream) => {
    var accum = []
    var pos = {line: 1, col: 1, char: 0}
    var isSingle = (c) =>
        (  c == "="
        || c == "("
        || c == ")"
        || c == "{"
        || c == "}"
        || c == ";"
        || c == "\\"
        )
    var isSpace  = (c) => c == " " || c == "\n"
    var countChar = (pos, char) => char == '\n'
        ? {line: pos.line + 1, col:           1, char: pos.char + 1}
        : {line: pos.line,     col: pos.col + 1, char: pos.char + 1}

    var end =           () => pos.char >= stream.length
    var spaceHere =     () => isSpace(stream[pos.char])
    var singleHere =    () => isSingle(stream[pos.char])
    var seekWordStart = () => !end(pos) && spaceHere(pos)
    var count =         () => { pos = countChar(pos, stream[pos.char]) }
    var seekWordEnd =   () => !end(pos) && !spaceHere(pos) && !singleHere(pos)
    var token = (begin, end) => stream.slice(begin.char, end.char)

    var fromTo = (open, close) => {
        if (stream.slice(pos.char, pos.char + open.length) == open) {
            var begin = copy(pos)

            for (var i = 0; i < open.length; i++)
                count()

            while (!end()
                && stream.slice(pos.char, pos.char + close.length) != close
            ) {
                count()
            }

            for (var i = 0; i < close.length; i++)
                count()

            var finish = copy(pos)

            accum.push(copy(begin, {text: token(begin, finish)}))
            return true
        }
    }

    while (!end()) {
        while (seekWordStart())
            count();

        var begin = copy(pos);

        if (fromTo('"""', '"""')) continue;
        if (fromTo('"', '"')) continue;
        if (fromTo("'", "'")) continue;

        if (singleHere())
            count()
        else do {
            count()
        } while (seekWordEnd())

        var finish = copy(pos)

        accum.push(copy(begin, {text: token(begin, finish)}))
    }

    accum.push(copy(pos, {text: "<EOS>"}))

    return accum
}

Array.prototype.flatMap = function (f) {
    var acc = []
    this.map(x => acc.push(f(x)))
    return acc
}

Array.prototype.last = function () {
    return this[this.length - 1]
}

var set = (o, things) => Object.assign({}, o, things)

var applyLayout = (tokenArray, conf) => {
    var acc = []
    var starters = []
    var nextStarts = false
    tokenArray.forEach(token => {
        var last = starters.last()
        if (last && token.col == last.col && token.text != conf.semicolon)
            acc.push(set(token, {text: conf.semicolon}))

        if (token.text == conf.closeBracet) {
            starters.pop()
        }

        if (last && token.col < last.col && token.text != conf.closeBracet) {
            acc.push(set(token, {text: conf.closeBracet}))
            starters.pop()
        }

        if (nextStarts && token.text != conf.openBracet) {
            starters.push({col: token.col})
            acc.push(set(token, {text: conf.openBracet}))
            nextStarts = false
        }

        acc.push(token)

        if (conf.isStarter(token))
            nextStarts = true;

        if (token.text == conf.openBracet) {
            nextStarts = false
        }
    })
    return acc
}

var asList = (accum) => accum.reduceRight((list, elem) => {
    elem.next = list;
    return elem
})

var copy = (...obj) => Object.assign({}, ...obj)

module.exports.stdConf = {
    semicolon: ";",
    openBracet: "{",
    closeBracet: "}",
    isStarter: x => x.text == "let"
                 || x.text == "list"
                 || x.text == "where"
}