maths_parser.js (117473e) - rtensor · DKL9 GitList

Refactor towards a working QuickJS version

dkl9 commited 117473e at 2023-196 12:46:40

maths_parser.js

Blame History Raw

"use strict";
// maths parser, by dkl9, 2021-05 to 2021-07, used as part of rtensor

import {OPS} from "./rtensor_common.js";
import {AST} from "./maths_ast.js";

// whitespace characters
const WSPACE = [" ", "\t", "\n"];
// characters for starting identifiers
const ISTART = ["_", "'"];
// characters in identifiers after the start
const ICHAR = ["_", "'"];
for (let c = 1; c <= 26; c++) {
    ISTART.push(String.fromCodePoint(c + 64));
    ISTART.push(String.fromCodePoint(c + 96));
    ICHAR.push(String.fromCodePoint(c + 64));
    ICHAR.push(String.fromCodePoint(c + 96));
}
for (let c = 0; c <= 9; c++) {
    ICHAR.push(String.fromCodePoint(c + 48));
}
// characters in numeric literals
const LCHAR = [];
for (let c = 0; c <= 9; c++) {
    LCHAR.push(String.fromCodePoint(c + 48));
}
// precedence of binary operators (greater == lower)
const PREC = [
    4,  4,  3,  3,
    2,  1,  5,  2,
    6,  5,  7,  8,
    4,
];
// associativity of precedence levels (1 == left, 2 == right)
const ASSOC = [0, 0, 2, 2, 1, 1, 1, 1, 2, 2];
// prefix-substrings of operators
const OPB = OPS.flatMap(function(s) {
    const r = [];
    for (let i = 0; i <= s.length; i++) {
        r.push(s.substring(0, i));
    }
    return r;
});
// names of token types
const TTN = [
    "BAD", "identifier", "literal", "boperator",
    "lparen", "rparen", "assign", "lsqbr",
    "rsqbr"
];

/*
operators
+ add or identity
- subtract or negate
* multiply or error
/ divide or reciprocal
^ exponent or power-of-e
\ logarithm or natural logarithm
== equal or equals-zero
-/ nth-root or square root
, vector join or error
< less than or negative
=> anonymous function or error
= assignment or error
.. range/concatenation or encapsulation
*/

// normalise integer literal:
// strip all zeroes from the beginning, unless it is just "0"
const normIntLit = s => (s.replace(/^0+/, "") || "0");

// a token, having a token type (this.tt) and a value (this.v)
// token type may be one of 1 (ident), 2 (int literal), 3 (operator)
// 4 (lparen), 5 (rparen), 6 (assign), 7 (left square bracket),
// 8 (right square bracket)
// value depends on tt: 1 => ident text, 2 => int value, 3 => operator id
// 4, 5, 6, 7, 8 => undefined
export class Token {
    constructor(tt, text) {
        this.tt = tt;
        switch (this.tt) {
            case 1:
                this.v = text;
                break;
            case 2:
                this.v = parseFloat(normIntLit(text));
                break;
            case 3:
                this.v = OPS.indexOf(text);
                break;
            case 4:
            case 5:
            case 6:
            case 7:
            case 8:
                break;
            default:
                dl("error: unrecognised token type " + tt);
        }
    }

// textual representation of the token
    // for debugging purposes -- would not be parsed back into the same token
    toString() {
        return TTN[this.tt] + " " + this.v;
    }
}

// source text surrounded by an interface to provide tokens from it on demand
export class TokenStream {
    constructor(source) {
        this.toks = [];
        this.tind = -1;
        this.src = source;
        this.sind = 0;
    }
    
    // returns boolean indicating if progress through the source text
    // "overran" the source text's length
    orun() {
        return this.sind >= this.src.length;
    }
    
    // get previous token
    prev(n) {
        const tn = n || 1;
        if (this.tind < tn - 1) {
            return null;
        } else {
            this.tind -= tn;
            return this.toks[this.tind];
        }
    }

// get next token, generating the next one if necessary
    next() {
        if (this.tind >= (this.toks.length - 1) && (!this.gen())) {
            return null;
        } else {
            this.tind++;
            return this.toks[this.tind];
        }
    }
    
    // generate next token, returning a boolean indicating success or failure
    gen() {
        // already at the end of the source text? fail
        if (this.orun()) {
            return false;
        }
        // go past any whitespace
        while (WSPACE.includes(this.src[this.sind])) {
            this.sind++;
            if (this.orun()) {
                return false;
            }
        }
        // check if character starts identifier
        if (ISTART.includes(this.src[this.sind])) {
            // collect next characters into identifier token
            let ntok = "";
            while (!this.orun() && ICHAR.includes(this.src[this.sind])) {
                ntok += this.src[this.sind];
                this.sind++;
            }
            this.toks.push(new Token(1, ntok));
        // check if character is in numeric literal
        } else if (LCHAR.includes(this.src[this.sind]) ||
            (this.src[this.sind] == "." && this.src[this.sind + 1] != ".")) {
            // collect next characters into numeric literal token
            let ntok = "";
            let df = false;
            while (!this.orun() && (LCHAR.includes(this.src[this.sind]) || this.src[this.sind] == ".")) {
                if (this.src[this.sind] == ".") {
                    if (df) {
                        break;
                    }
                    df = true;
                }
                ntok += this.src[this.sind];
                this.sind++;
            }
            this.toks.push(new Token(2, ntok));
        // check if character is an operator beginner
        } else if (OPB.includes(this.src[this.sind])) {
            let ntok = "";
            while (!this.orun() && OPB.includes(ntok)) {
                ntok += this.src[this.sind];
                this.sind++;
            }
            ntok = ntok.substring(0, ntok.length - 1);
            this.sind--;
            this.toks.push(new Token(3, ntok));
        /*
        // equal sign of assignment
        } else if (this.src[this.sind] == "=" &&
            this.src[this.sind + 1] != "=" &&
            this.src[this.sind + 1] != ">") {
            this.sind++;
            this.toks.push(new Token(6, "="));
        */
        // left and right square brackets
        } else if (["[", "]"].includes(this.src[this.sind])) {
            const pt = (this.src[this.sind] == "[" ? 7 : 8);
            this.sind++;
            this.toks.push(new Token(pt));
        // left and right parens
        } else if (["(", ")"].includes(this.src[this.sind])) {
            const pt = (this.src[this.sind] == "(" ? 4 : 5);
            this.sind++;
            this.toks.push(new Token(pt));
        // anything else is invalid
        } else {
            throw `invalid character ${this.src[this.sind]}`;
            return false;
        }
        return true;
    }
}

// hopefully, this will be less dumb (than the old Parser class, now deleted)
// each function parses a particular structure,
// returning an AST (with .len, measured in tokens) if successful
// or null if failed
export class NewParser {
    // statement -> expr[9]
    static statement(stream) {
        let tc = 0;
        /*const a = NewParser.lvalue(stream, 9);
        if (a) {
            tc += a.len;
            const b = stream.next() || {};
            tc += !!b.tt;
            if (b.tt == 6) {
                const c = NewParser.expr(stream, 9);
                if (c) {
                    tc += c.len;
                    return new AST(4, true, a, c, tc);
                }
            }
        }
        stream.prev(tc);
        tc = 0;*/
        const d = NewParser.expr(stream, 9);
        if (d) {
            tc += d.len;
            return new AST(4, false, d, undefined, tc);
        }
        return null;
    }

// BAD expr[0] -> lvalue[9]
    // expr[0] -> identifier
    // expr[0] -> literal
    // expr[0] -> lparen expr[9] rparen
    // expr[1] -> expr[0] argSuff*
    // expr[n > 1] -> expr[n - 1] (operator[n - 1] expr[n - 1])*
    // expr[n] -> operator[9] expr[1] argSuff?
    static expr(stream, n) {
        let tc = 0;
        /*if (n == 0) {
            // expr[0] -> lvalue[9]
            const a = NewParser.lvalue(stream, 9);
            if (a) {
                return a;
            }
        }*/
        let b = stream.next() || {};
        tc += !!b.tt;
        if (n == 0) {
            // expr[0] -> identifier
            if (b.tt == 1) {
                return new AST(1, b, undefined, undefined, 1);
            }
            // expr[0] -> literal
            if (b.tt == 2) {
                return new AST(2, b, undefined, undefined, 1);
            }
            // expr[0] -> lparen expr[9] rparen
            if (b.tt == 4) {
                const c = NewParser.expr(stream, 9);
                if (c) {
                    tc += c.len;
                    const d = stream.next() || {};
                    tc += !!d.tt;
                    if (d.tt == 5) {
                        c.len += 2;
                        return c;
                    }
                }
                stream.prev(tc - 1);
            }
            tc = !!b.tt;
        }
        stream.prev();
        tc = 0;
        // expr[1] -> expr[0] argSuff*
        if (n == 1) {
            let c = NewParser.expr(stream, 0);
            if (c) {
                tc += c.len;
                let d;
                while ((d = NewParser.argSuff(stream))) {
                    tc += d.len;
                    c = new AST(8, c, d, d.sqbr, tc);
                }
                return c;
            }
            tc && stream.prev(tc);
            tc = 0;
        }
        // expr[n > 1] -> expr[n - 1] (operator[n - 1] expr[n - 1])*
        if (n > 1) {
            const eol = [NewParser.expr(stream, n - 1)];
            if (!(eol[0])) { return null; }
            tc += eol.len;
            // collect (operator[n - 1] expr[n - 1]) pairs
            while (true) {
                const no = stream.next() || {};
                if (!no.tt) { break; }
                if (no.tt != 3 || PREC[no.v] != n - 1) { stream.prev(); break; }
                const nse = NewParser.expr(stream, n - 1);
                if (!nse) { stream.prev(); break; }
                eol.push(no); eol.push(nse);
                tc += (!!no.tt) + nse.len;
            }
            // collapse expression to tree based on associativity
            let d; let e; let f;
            while (eol.length >= 3) {
                switch (ASSOC[n]) {
                    case 1:
                        d = eol.shift(); e = eol.shift(); f = eol.shift();
                        eol.unshift(new AST(3, d, e, f, d.len + (!!e.tt) + f.len));
                        break;
                    case 2:
                        d = eol.pop(); e = eol.pop(); f = eol.pop();
                        eol.push(new AST(3, f, e, d, f.len + (!!e.tt) + d.len));
                        break;
                    default:
                        dl("error: unreachable");
                        break;
                }
            }
            return eol[0];
        }
        b = stream.next() || {};
        tc += !!b.tt;
        // expr[n] -> operator[9] expr[1]
        if (b.tt == 3) {
            const c = NewParser.expr(stream, 1);
            if (c) {
                tc += c.len;
                return new AST(5, b, c, undefined, tc);
            }
            stream.prev(tc - 1);
        }
        stream.prev();
        tc = 0;
        return null;
    }
    
    // lvalue[0] -> identifier
    // lvalue[1] -> lvalue[0] indSuff?
    // lvalue[2] -> lvalue[1] argSuff?
    // lvalue[n > 2] -> lvalue[n - 1]
    static lvalue(stream, n) {
        // lvalue[0] -> identifier
        if (n == 0) {
            const a = stream.next() || {};
            if (a.tt == 1) {
                return new AST(1, a, undefined, undefined, 1);
            } else {
                a.tt && stream.prev();
                return null;
            }
        }
        let tc = 0;
        // lvalue[1] -> lvalue[0] indSuff?
        if (n == 1) {
            const a = NewParser.lvalue(stream, 0);
            if (a) {
                tc += a.len;
                const b = NewParser.indSuff(stream);
                if (b) {
                    tc += b.len;
                    return new AST(6, a, b, undefined, tc);
                } else {
                    return a;
                }
            } else {
                return null;
            }
        }
        // lvalue[2] -> lvalue[1] argSuff?
        if (n == 2) {
            const a = NewParser.lvalue(stream, 1);
            if (a) {
                tc += a.len;
                const b = NewParser.argSuff(stream);
                if (b) {
                    tc += b.len;
                    return new AST(7, a, b, b.sqbr, tc);
                } else {
                    return a;
                }
            } else {
                return null;
            }
        }
        // lvalue[n > 2] -> lvalue[n - 1]
        if (n > 2) {
            const a = NewParser.lvalue(stream, n - 1);
            if (a) {
                return a;
            } else {
                return null;
            }
        }
        return null;
    }
    
    // indSuff -> lsqbr expr[9] rsqbr
    static indSuff(stream) {
        const lb = stream.next() || {};
        if (!lb.tt) { return null; }
        if (lb.tt != 7) { stream.prev(); return null; }
        const iexc = NewParser.expr(stream, 9);
        if (!iexc) { stream.prev(); return null; }
        const rb = stream.next() || {};
        if (!rb.tt) { stream.prev(1 + iexc.len); return null; }
        if (rb.tt != 8) { stream.prev(1 + iexc.len + 1); return null; }
        iexc.len += 2;
        return iexc;
    }

// will return Array of AST (with properties .len, .sqbr) instead of AST on success
    // precedence rank 6 is used to avoid confusing comma-as-operator
    // with comma-as-argument-separator
    // argSuff -> lparen (expr[6] (comma expr[6])*)? rparen
    // argSuff -> lsqbr (expr[6] (comma expr[6])*)? lsqbr
    static argSuff(stream) {
        const a = stream.next() || {};
        if (a.tt == 4 || a.tt == 7) {
            const rl = [];
            rl.len = 1;
            rl.sqbr = a.tt == 7;
            const b = NewParser.expr(stream, 6);
            if (b) {
                rl.len += b.len;
                rl.push(b);
                let nct; let nae;
                // collect (comma expr[5]) pairs
                while (true) {
                    nct = stream.next() || {};
                    if (nct.tt != 3 || nct.v != 8) {
                        nct.tt && stream.prev();
                        break;
                    }
                    nae = NewParser.expr(stream, 6);
                    if (!nae) {
                        stream.prev();
                    }
                    rl.len += 1 + nae.len;
                    rl.push(nae);
                }
            }
            const c = stream.next() || {};
            rl.len += !!c.tt;
            if (!rl.sqbr && c.tt == 5) {
                return rl;
            }
            if (rl.sqbr && c.tt == 8) {
                return rl;
            }
            stream.prev(rl.len);
        } else if (a.tt) {
            stream.prev();
        }
        return null;
    }
}