/equation.js Secret
Last active
October 18, 2023 11:00
Parser/evaluator for equations for this article:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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