Skip to content

Instantly share code, notes, and snippets.

@ryandabler
Last active October 18, 2023 11:00
Show Gist options
  • Save ryandabler/5ebe2464d85e4ee39ed411ca7a20609d to your computer and use it in GitHub Desktop.
Save ryandabler/5ebe2464d85e4ee39ed411ca7a20609d to your computer and use it in GitHub Desktop.
Parser/evaluator for equations for this article:
const tokens = [
[/^\s+/, null],
[/^-?\d+(?:\.\d+)?/, 'NUMBER'],
[/^[a-zA-Z]+/, 'IDENT'],
[/^"[^"]+"/, 'STRING'],
[/^\+/, '+'],
[/^-/, '-'],
[/^\*/, '*'],
[/^\^/, '^'],
[/^\//, '/'],
[/^\(/, '('],
[/^\)/, ')'],
[/^,/, ','],
];
class Tokenizer {
// List of tokens recognized by the tokenizer
#tokens;
// Position in the input string from which it will
// read to get the next token
#cursor;
// String to turn into tokens
#string;
constructor(tokens) {
this.#tokens = tokens;
}
read(string) {
this.#cursor = 0;
this.#string = string;
}
next() {
// If at end of input, not more tokens to generate
if (this.#cursor === this.#string.length) {
return undefined;
}
// Find substring beginning at position of cursor
const str = this.#string.slice(this.#cursor);
for (const [pattern, type] of this.#tokens) {
const [match] = pattern.exec(str) || [];
if (!match) {
continue;
}
this.#cursor += match.length;
// Skip tokens with null types
if (type === null) {
return this.next();
}
return { token: match, type };
}
// Could not extract any tokens, so throw error
throw new Error(`Unrecognized input: ${str[0]}`);
}
}
class Parser {
#tokenizer;
#lookahead;
constructor(tokenizer) {
this.#tokenizer = tokenizer;
}
read(string) {
this.#tokenizer.read(string);
this.#lookahead = this.#tokenizer.next();
return this.#EXPRESSION();
}
#eat(...tokenTypes) {
const token = this.#lookahead;
if (!token) {
throw new Error(
`Unexpected end of input; expected ${token.type}`
);
}
if (!tokenTypes.includes(this.#lookahead.type)) {
throw new Error(
`Expected ${tokenType} === ${token.type}`
);
}
this.#lookahead = this.#tokenizer.next();
return token;
}
#is(...tokenTypes) {
return tokenTypes.includes(this.#lookahead?.type);
}
#EXPRESSION() {
return this.#ADDITION();
}
#ADDITION() {
let left = this.#CALL();
while (this.#is('+', '-')) {
left = {
type: 'binary',
left,
op: this.#eat('+', '-').type,
right: this.#CALL(),
};
}
return left;
}
#CALL() {
const maybeCallee = this.#MULTIPLICATION();
if (this.#is('NUMBER', 'IDENT')) {
return {
type: 'call',
fn: maybeCallee.value,
args: [this.#CALL()],
};
}
if (this.#is('(')) {
this.#eat('(');
const args = [this.#EXPRESSION()];
while (this.#is(',')) {
this.#eat(',');
args.push(this.#EXPRESSION());
}
this.#eat(')');
return { type: 'call', fn: maybeCallee.value, args };
}
return maybeCallee;
}
#MULTIPLICATION() {
let left = this.#EXPONENTIATION();
while (this.#is('*', '/')) {
left = {
type: 'binary',
left,
op: this.#eat('*', '/').type,
right: this.#EXPONENTIATION(),
};
}
return left;
}
#EXPONENTIATION() {
let left = this.#BASIC();
while (this.#is('^')) {
left = {
type: 'binary',
left,
op: this.#eat('^').type,
right: this.#BASIC(),
};
}
return left;
}
#BASIC() {
if (this.#is('(')) {
this.#eat('(');
const expr = this.#EXPRESSION();
this.#eat(')');
return expr;
}
if (this.#is('NUMBER')) {
return { type: 'number', value: this.#eat('NUMBER').token };
}
if (this.#is('IDENT')) {
return { type: 'ident', value: this.#eat('IDENT').token };
}
if (this.#is('STRING')) {
// Remove containing quotation marks
const expr = this.#eat('STRING').token.slice(1, -1);
// Test that the sub-expression is in fact a valid expression
new Parser(new Tokenizer(tokens)).read(expr);
return {
type: 'expr',
value: expr,
};
}
throw new Error('Malformed expression');
}
}
class Environment {
#fields;
#parent;
constructor(fields, parent) {
this.#fields = fields;
this.#parent = parent;
}
lookup(ident) {
if (ident in this.#fields) {
return this.#fields[ident];
}
if (this.#parent) {
return this.#parent.lookup(ident);
}
throw new Error(`Unspecified identifier "${ident}"`);
}
}
const binaryEval = (op, left, right) => {
if (op === '+') {
return left + right;
}
if (op === '-') {
return left - right;
}
if (op === '*') {
return left * right;
}
if (op === '/') {
return left / right;
}
if (op === '^') {
return left ** right;
}
}
const evaluate = (node, env) => {
switch (node.type) {
case 'binary': {
const left = evaluate(node.left, env);
const right = evaluate(node.right, env);
return binaryEval(node.op, left, right);
}
case 'call': {
const fn = env.lookup(node.fn);
const args = node.args.map(arg => evaluate(arg, env));
return fn.apply(null, args);
}
case 'ident':
return env.lookup(node.value);
case 'number':
return +node.value;
case 'expr':
return compile(node.value);
}
};
const globalEnv = new Environment({
sin: Math.sin,
cos: Math.cos,
tan: Math.tan,
log: (n, base) => Math.log(n) / Math.log(base),
});
const compile = (string) => {
const parser = new Parser(new Tokenizer(tokens));
const ast = parser.read(string);
return (idents) => evaluate(ast, new Environment(idents, globalEnv));
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment