parser.js

// 111.11
// 'hello '' world'

class Parser {
    static of(parser) {
        return new Parser(parser)
    }

    constructor(runParser) {
        this.runParser = runParser
    }
    
    then(amb) {
        return Parser.of(stream => 
            this.runParser(stream).then(res => 
                ( res.ok
                ? amb(res.value).runParser(res.stream)
                : res
                )
            )
        )
    }
    
    map(f) {
        return this.then(x => Parser.return(f(x)))
    }
    
    catch(emb) {
        return Parser.of(stream => 
            this.runParser(stream).then(res =>
                ( res.ok
                ? res
                : res.stream.beyond(stream)
                  ? res
                  : emb(res.error).runParser(stream)
                )
            )
        )
    }
    
    or(other) {
        return this.catch(_ => other)
    }
    
    orJust(x) {
        return this.catch(_ => Parser.return(x))
    }
    
    _and(other) {
        return this.then(_ => other)
    }
    
    and_(other) {
        return this.then(x => other.then(_ => Parser.return(x)))
    }
    
    some() {
        return this.productive().then(x  => 
               this.many()      .then(xs => {
                    xs.unshift(x)
                    return Parser.return (xs)
               }))
    }
    
    productive() {
        return Parser.of(stream =>
            this.runParser(stream).then(res =>
                !res.ok
                    ? res
                    : !res.stream.beyond(stream)
                        ? (() => { throw new Error("not productive at <" + stream.text.slice(stream.offset)) + ">" })()
                        : res
            )
        )
    }
    
    many() {
        var prod = this.productive()
        var acc = []
        function loop() {
            return prod.then(x => {
                acc.push(x)
                return loop(this)
            }).orJust(acc)
        }
        return loop(this)
    }
    
    ignore() {
        return this.map(_ => undefined)
    }
    
    describe(error) {
        return this.catch(_ => Parser.fail(error))
    }
    
    try() {
        return Parser.of(stream =>
            this.runParser(stream).then(res =>
                res.ok
                    ? res
                    : res.stream.beyond(stream)
                        ? {error: res.error, stream: stream}
                        : res
            )
        )
    }
    
    static guard(bool) {
        return bool? Parser.return() : Parser.fail("Parser.guard")
    }
    
    join(sep) {
        return this.map(it => it.join(sep || ""))
    }
    
    asToken(mark) {
        return Parser.getPosition.then(pos   =>
               this              .then(value =>
               Parser.return({pos, value, mark})))
    }
}

Parser.regex = (str) => {
    var reg = new RegExp(str, 'y')
    return Parser.of(stream => stream.regex(reg))
}

Parser.return = (value) =>
    Parser.of(stream =>
        Promise.resolve({ok: true, value, stream})
    )

Parser.fail = (error) =>
    Parser.of(stream =>
        Promise.resolve({error, stream})
    )

Parser.string = (str) => Parser.of(stream => {
    return stream.take(str.length).then(res => {
        var {ok, value, stream: rest} = res
        var out = ok && value === str
            ? {ok, value, stream: rest}
            : {error: "expected `" + str + "`", stream}
        return Promise.resolve(out)
    })
})

Parser.sequence = (list) => {
    var [elem, ...rest] = list
    return elem
        ? elem                 .then(x  =>
          Parser.sequence(rest).then(xs =>
          Parser.return([x].concat(xs))))
        : Parser.return([])
}

Parser.for = (list, f) => {
    return Parser.sequence(list).map(f)
}

Parser.significant = (list) =>
    Parser.for(list, list => list.filter(x => x !== undefined))

Parser.first = (list) =>
    Parser.for(list, list => list.filter(x => x !== undefined)[0])

Parser.that = (pred) =>
    Parser.of(stream =>
        stream.uncons().then(res =>
            res.ok && pred(res.value) ? res : {error: "Parser.that", stream}
        )
    )

Parser.manyThat = (pred) =>
    Parser.of(stream => stream.takeWhile(pred))
    
Parser.someThat = (pred) =>
    Parser.that    (pred).then(x  =>
    Parser.manyThat(pred).then(xs =>
    Parser.return(x + xs)))

Parser.getPosition = Parser.of(stream => stream.position())

class CharStream {
    static of(text) {
        return new CharStream(text, 0)
    }
    
    static file(filename) {
        return CharStream.of(require('fs').readFileSync(filename).toString())
    }
    
    constructor(text, offset) {
        this.text   = text
        this.offset = offset
    }
    
    uncons() {
        return this.take(1)
    }
    
    take(n) {
        var {text, offset} = this
        if (text.length >= offset + n) {
            return Promise.resolve({ok: true, value: text.substr(offset, n), stream: new CharStream(text, offset + n)})
        } else {
            return Promise.resolve({error: "EOF", stream: this})
        }
    }
    
    takeWhile(pred) {
        var {text, offset} = this
        for (var i = offset; i < text.length; i++) {
            if (!pred(text[i])) {
                return Promise.resolve({
                    ok: true,
                    value: text.slice(offset, i),
                    stream: new CharStream(text, i)
                })
            }
        }
        return Promise.resolve({
            ok: true,
            value: text.slice(offset, i),
            stream: new CharStream(text, offset + i)
        })
    }
    
    beyond(other) {
        return this.offset > other.offset
    }
    
    position() {
        return Promise.resolve({ok: true, value: this.offset, stream: this})
    }
}

module.exports = { Parser, CharStream }

syntax.js

var { Parser, CharStream } = require('./parser.js')

var set = (items) => {
    var arr = Array.prototype.slice.apply(items)
    var carrier = {}
    arr.forEach(x => { carrier[x] = true })
    return (x) => carrier[x]
}

var reservedWords = set("module object end => let in \\ open ---".split(" "))
var notReserved = (w) => !reservedWords(w)
var isReserved  = (w) => reservedWords(w)

var spaces = set(" \n\t")
var punctuations = set("(;,.:)")
var numbers = set("0123456789")
var nonName = set("'")

var digits  = Parser.someThat(numbers)
var mdigits = Parser.manyThat(numbers)
var dot     = Parser.string(".")

var int =
    Parser.for([ 
        digits,
        dot._and(mdigits).orJust(""),
    ], ([a, c]) => Number(a + (c ? "." + c : "")))
    .describe("int constant")
    .asToken("const")
       
var quote = Parser.string("'")
var notQuotes = Parser.manyThat(c => c != "'")
        
var string =
    Parser.first([
        quote.ignore(),
        notQuotes,
        quote.ignore(),
    ]).some()
    .join("'")
    .describe("string constant")
    .asToken("const")

var nameStarter = (c) => !spaces(c)
                      && !punctuations(c)
                      && !numbers(c)
                      && !nonName(c)

var nameChar = (c) => !spaces(c)
                   && !punctuations(c)
                   && !nonName(c)

var firstChar = Parser.that(nameStarter)
var latterChars = Parser.manyThat(nameChar)

var identifier = 
    firstChar.then(n =>
    latterChars.map(ame => n + ame))
    .describe("identifier")

var name =
    identifier.then(name =>
        Parser.guard(notReserved(name))
            .describe("not reserved")
            ._and(Parser.return(name))).try()
    .asToken("name")

var comment =
    Parser.string("---")._and(Parser.manyThat(c => c != "\n"))
    .asToken("comment")

var space = Parser.manyThat(spaces)
    .asToken("space")

var punctuation = Parser.that(punctuations)
    .asToken("punct")

var reserved =
    identifier.then(name =>
        Parser.guard(isReserved(name))
            .describe("reserved")
            ._and(Parser.return(name))).try()
    .asToken("name")

var s = CharStream.file("parser.js")

var token =
    name.or(reserved).or(comment).or(string).or(int).or(punctuation).and_(space)

var tokens = space._and(token.many())

var before = Date.now()

tokens.runParser(s).then(res => {
    var d = Date.now() - before
    if (res.value && res.value.forEach)
        res.value.forEach(({pos, value, mark}) => {
            console.log(pos + "\t" + mark + "\t" + value)
        })
    else
        console.log(res)
    console.log({bps: s.text.length / d * 1000})
})