Published
Edited
Dec 25, 2020
parser('(x+y)*(x-y)')
parser = {
const tokenizer = str => {
const lex = [
[/^(\s+)(.*)/, "Space"],
[/^(\d+)(.*)/, "Integer"],
[/^(\w+)(.*)/, "Literal"],
[/^(\+)(.*)/, "Plus"],
[/^(\-)(.*)/, "Minus"],
[/^(\*)(.*)/, "Times"],
[/^(\/)(.*)/, "Divide"],
[/^(\^)(.*)/, "Power"],
[/^(\()(.*)/, "Left"],
[/^(\))(.*)/, "Right"]
];
let s = str;
const r = [];
while (s) {
for (let i = 0; i < lex.length; ++i) {
let m = s.match(lex[i][0]);
if (m) {
const l = lex[i][1];
if (l !== 'Space') r.push([l, m[1]]);
s = m[2];
break;
}
}
}
r.push(["End", ""]);
return r;
};
const parser = str => {
const l = tokenizer(str);
let it = 0;
const next = () => l[it][0];
const value = () => l[it][1];
const consume = () => (it = it + 1);
const expect = tok => {
if (next() === tok) consume();
else throw 'error';
};
let Eparser, Exp, P;
const isBinary = tok => {
return (
tok === 'Plus' ||
tok === 'Minus' ||
tok === 'Times' ||
tok === 'Divide' ||
tok === 'Power'
);
};
const isTerminal = tok => {
return tok === 'Integer' || tok === 'Literal';
};
const binary = tok => {
return tok;
};
const isUnary = tok => {
return tok === 'Minus';
};
const unary = tok => {
return 'Unary' + tok;
};
const associativity = op => {
if (op === 'Power') return 'Right';
else return 'Left';
};
const prec = op => {
switch (op) {
case 'UnaryMinus':
return 2;
case 'Plus':
return 1;
case 'Minus':
return 1;
case 'Times':
return 3;
case 'Divide':
return 3;
case 'Power':
return 4;
}
};
Eparser = () => {
const t = Exp(0);
expect('End');
return t;
};
Exp = p => {
let t = P();
while (isBinary(next()) && prec(binary(next())) >= p) {
const op = binary(next());
consume();
const q = prec(op) + (associativity(op) === 'Right' ? 0 : 1);
const t1 = Exp(q);
t = { node: op, child: [t, t1] };
}
return t;
};
P = () => {
if (isUnary(next())) {
const op = unary(next());
consume();
const q = prec(op);
const t = Exp(q);
return { node: op, child: [t] };
} else if (next() === 'Left') {
consume();
const t = Exp(0);
expect('Right');
return t;
} else if (isTerminal(next())) {
const t = value();
consume();
return t;
} else throw 'error';
};
return Eparser();
};
return parser;
}
parserWithForms('(x+f(y+1,-3*z^2))*(x-y)')
parserWithForms = {
const tokenizer = str => {
const lex = [
[/^(\s+)(.*)/, "Space"],
[/^(\w+)\((.*)/, 'Form'],
[/^(\d+)(.*)/, "Integer"],
[/^(\w+)(.*)/, "Literal"],
[/^(\+)(.*)/, "Plus"],
[/^(\-)(.*)/, "Minus"],
[/^(\*)(.*)/, "Times"],
[/^(\/)(.*)/, "Divide"],
[/^(\^)(.*)/, "Power"],
[/^(\()(.*)/, "Left"],
[/^(\))(.*)/, "Right"],
[/^(,)(.*)/, 'Comma']
];
let s = str;
const r = [];
while (s) {
for (let i = 0; i < lex.length; ++i) {
let m = s.match(lex[i][0]);
if (m) {
const l = lex[i][1];
if (l !== 'Space') r.push([l, m[1]]);
s = m[2];
break;
}
}
}
r.push(["End", ""]);
return r;
};
const parser = str => {
const l = tokenizer(str);
let it = 0;
const next = () => l[it][0];
const value = () => l[it][1];
const consume = () => (it = it + 1);
const expect = tok => {
if (next() === tok) consume();
else throw `next = ${next()}, ${tok} expected.`;
};
let Eparser, Exp, P;
const isBinary = tok => {
return (
tok === 'Plus' ||
tok === 'Minus' ||
tok === 'Times' ||
tok === 'Divide' ||
tok === 'Power'
);
};
const isTerminal = tok => {
return tok === 'Integer' || tok === 'Literal';
};
const binary = tok => {
return tok;
};
const isUnary = tok => {
return tok === 'Minus';
};
const unary = tok => {
return 'Unary' + tok;
};
const associativity = op => {
if (op === 'Power') return 'Right';
else return 'Left';
};
const prec = op => {
switch (op) {
case 'UnaryMinus':
return 2;
case 'Plus':
return 1;
case 'Minus':
return 1;
case 'Times':
return 3;
case 'Divide':
return 3;
case 'Power':
return 4;
}
};
Eparser = () => {
const t = Exp(0);
expect('End');
return t;
};
Exp = p => {
let t = P();
while (isBinary(next()) && prec(binary(next())) >= p) {
const op = binary(next());
consume();
const q = prec(op) + (associativity(op) === 'Right' ? 0 : 1);
const t1 = Exp(q);
t = { node: op, child: [t, t1] };
}
return t;
};
P = () => {
if (isUnary(next())) {
const op = unary(next());
consume();
const q = prec(op);
const t = Exp(q);
return { node: op, child: [t] };
} else if (next() === 'Left') {
consume();
const t = Exp(0);
expect('Right');
return t;
} else if (next() === 'Form') {
const op = value();
let ch = [];
do {
consume();
ch.push(Exp(0));
} while (next() === 'Comma');
expect('Right');
return { node: op, child: ch };
} else if (isTerminal(next())) {
const t = value();
consume();
return t;
} else throw 'error';
};
return Eparser();
};
return parser;
}
parser2 = {
const symbolTable = {};
const lookup = (name, attr = {}) => {
const s = symbolTable[name];
if (s) return s;
else {
const s = { name: name, attr: attr };
symbolTable[name] = s;
return s;
}
};
lookup('Plus', { flat: true });
lookup('Times', { flat: true });
lookup('Do', { flat: true });
const flatten = e => {
if (e.tail) {
if (!e.head.atom) {
e.head = flatten(e.head);
}
let t = [];
for (let i = 0; i < e.tail.length; ++i) {
e.tail[i] = flatten(e.tail[i]);
if (
e.head.atom &&
e.head.atom.attr.flat &&
e.tail[i].head &&
e.tail[i].head.atom &&
e.tail[i].head.atom === e.head.atom
) {
t.push(...e.tail[i].tail);
} else t.push(e.tail[i]);
}
e.tail = t;
}
return e;
};
const tokenizer = str => {
const lex = [
[/^(\s+)(.*)/, "Space"],
[/^(\d+)(.*)/, "Integer"],
[/^(;)(.*)/, "Do"],
[/^(=>)(.*)/, "Lambda"],
[/^(\w+)(.*)/, "Literal"],
[/^(\+)(.*)/, "Plus"],
[/^(\-)(.*)/, "Minus"],
[/^(\*)(.*)/, "Times"],
[/^(\/)(.*)/, "Divide"],
[/^(\^)(.*)/, "Power"],
[/^(\()(.*)/, "Left"],
[/^(\))(.*)/, "Right"],
[/^(\[)(.*)/, "LeftBra"],
[/^(\])(.*)/, "RightBra"],
[/^({)(.*)/, "LeftCurly"],
[/^(})(.*)/, "RightCurly"],
[/^(,)(.*)/, "Comma"]
];
let s = str;
const r = [];
while (s) {
for (let i = 0; i < lex.length; ++i) {
let m = s.match(lex[i][0]);
if (m) {
const l = lex[i][1];
if (l !== 'Space') r.push([l, m[1]]);
s = m[2];
break;
}
}
}
r.push(["End", ""]);
return r;
};
const parser = str => {
const l = tokenizer(str);
let it = 0;
const next = () => l[it][0];
const nextnext = () => l[it + 1][0];
const value = () => l[it][1];
const consume = () => (it = it + 1);
const expect = tok => {
if (next() === tok) consume();
else throw `next = ${next()}, ${tok} expected.`;
};
let Eparser, Exp, P;
const isBinary = tok => {
return (
tok === 'Do' ||
tok === 'Lambda' ||
tok === 'Plus' ||
tok === 'Minus' ||
tok === 'Times' ||
tok === 'Divide' ||
tok === 'Power'
);
};
const isTerminal = tok => {
return tok === 'Integer' || tok === 'Literal';
};
const binary = tok => {
return tok;
};
const isUnary = tok => {
return tok === 'Minus';
};
const unary = tok => {
return 'Unary' + tok;
};
const associativity = op => {
if (op === 'Power' || op === 'Lambda') return 'Right';
else return 'Left';
};
const prec = op => {
switch (op) {
case 'UnaryMinus':
return 20;
case 'Do':
return 0;
case 'Lambda':
return 5;
case 'Plus':
return 10;
case 'Minus':
return 10;
case 'Times':
return 30;
case 'Divide':
return 30;
case 'Power':
return 40;
}
};
Eparser = () => {
const t = Exp(0);
expect('End');
return t;
};
Exp = p => {
let t = P();
while (next() === 'LeftBra') {
let ch = [];
if (nextnext() === 'RightBra') {
consume();
} else {
do {
consume();
ch.push(Exp(0));
} while (next() === 'Comma');
}
expect('RightBra');
t = { head: t, tail: ch };
}
while (isBinary(next()) && prec(binary(next())) >= p) {
const op = binary(next());
consume();
const q = prec(op) + (associativity(op) === 'Right' ? 0 : 1);
const t1 = Exp(q);
t = { head: { atom: lookup(op), type: 'Symbol' }, tail: [t, t1] };
}
return t;
};
P = () => {
if (isUnary(next())) {
const op = unary(next());
consume();
const q = prec(op);
const t = Exp(q);
return { head: { atom: lookup(op), type: 'Symbol' }, tail: [t] };
} else if (next() === 'Left') {
consume();
const t = Exp(0);
expect('Right');
return t;
} else if (next() === 'LeftCurly') {
let ch = [];
if (nextnext() === 'RightCurly') {
consume();
} else {
do {
consume();
ch.push(Exp(0));
} while (next() === 'Comma');
}
expect('RightCurly');
return { head: { atom: lookup('List'), type: 'Symbol' }, tail: ch };
} else if (isTerminal(next())) {
if (next() == 'Integer') {
const t = { atom: Number(value()), type: 'Integer' };
consume();
return t;
} else if (next() == 'Literal') {
const t = { atom: lookup(value()), type: 'Symbol' };
consume();
return t;
}
} else throw 'error';
};
return flatten(Eparser());
};
return parser;
}
function lispPrint(e) {
if (e.atom) {
switch (e.type) {
case 'Integer':
return e.atom;
case 'Symbol':
return e.atom.name;
}
}
let s = '(';
s += lispPrint(e.head);
for (let i = 0; i < e.tail.length; ++i) s += ' ' + lispPrint(e.tail[i]);
s += ')';
return s;
}
lispPrint(parser2('x+y+z+4;x+y;3*z'))
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.