Expression Parser

A no-dependency, easy-to-extend interpreter for parsing and evaluating expressions.

This project is just a single file, aiming to be easy to understand, extend, and build upon.

Install

npm install expressionparser

Built-in Languages

A built-in language called "formula" is provided as the default.

Evaluating an expression:

import { init, formula } from 'expressionparser'

const parser = init(formula, (term: string) => {
if (term === "MY_VARIABLE") {
return 42;
} else {
throw new Error(Invalid term: ${term});
}
});

parser.expressionToValue("(1 + 1) + 40 = MY_VARIABLE"); // true

Custom Language

Parse simple expressions, in a language of your own description, such as:

(A AND B) OR NOT (C OR D)

or

1 + 1 * 2 - (10 / 2) + SQRT 16

The latter language can be configured as follows:

const arithmeticLanguage = {
INFIX_OPS: {
'+': function(args) {
const [a, b] = args();
return a() + b();
},
'-': function(args) {
const [a, b] = args();
return a() - b();
},
'*': function(args) {
const [a, b] = args();
return a() * b();
},
'/': function(args) {
const [a, b] = args();
return a() / b();
},
',': function(args) {
const [a, b] = args();
return [a()] + b();
}
},
PREFIX_OPS: {
'SQRT': function(arg) {
const val = arg()
return Math.sqrt(val);
},
'POW': function(args) {
const [a, b] = args();
return Math.pow(a(), b());
}
},
PRECEDENCE: [['SQRT', 'POW'], ['*', '/'], ['+', '-'], [',']],
GROUP_OPEN: '(',
GROUP_CLOSE: ')',
SEPARATORS: [','],
WHITESPACE_CHARS: [" "],
SYMBOLS: ['(', ')', '+', '-', '*', '/', ','],

termDelegate: function(term) {
return parseInt(term);
}
};

and evaluated as:
const expr = 'pow(1 + 1 \* 2 - (10 / 2) + sqrt(16), 2)'.toUpperCase();
const result = new ExpressionParser(arithmeticLanguage).expressionToValue(expr);

(which will result in 4)

Note: the unpackArgs helper function can be used to avoid doing const [a, b] = args(); in every function. This also checks for the correct number of arguments. See the implementation in "formula.ts".

e.g.

const arithmeticLanguage = {
INFIX_OPS: {
'+': unpackArgs(function(a, b) {
return a() + b();
}),
// ...etc.
}
}

Tokeniser

This uses the built-in tokeniser (which is very simple), but you can write your own tokeniser and pass the tokens into:

const result = new ExpressionParser(arithmeticLanguage).evaluateTokens(['1', '+', '1']);

(which will also result in 2)

If you get fancy, you can specify INFIX_OPS and PREFIX_OPS as functions (of key to value) instead of objects.

RPN

This parser will also convert between an expression and a Reverse Polish Notation (RPN) list:

const parser = new ExpressionParser();

parser.expressionToRpn(expr); // returns RPN list
parser.tokensToRpn(exprTokenList); // returns RPN list
parser.rpnToExpression(rpnList); // returns expression string
parser.rpnToTokens(rpnList); // returns expression token list

Further configuration

The SEPARATORS, WHITESPACE_CHARS, and SYMBOLS options are to assist the built-in tokeniser and expression string builder.

There are 3 types of token:

- By default tokens are made up of any contiguous string of characters separated by any member of WHITESPACE_CHARS.
- Characters in SYMBOLS will be collected as a separate category to other characters, so they can exist adjacent to other characters but be separated into another token.
- SEPARATORS are put into a single-character token of their own.

e.g. assuming ' ' in WHITESPACE_CHARS:

- If there are no SYMBOLS or SEPARATORS: "!! A" will be tokenized as ["!!", "A"], but "!!A" will be tokenized as ["!!A"]
- If '!' is in SYMBOLS: "!! A" and "!!A" will both be tokenized as ["!!", "A"]
- If '!' is instead in SEPARATORS: "!! A" and "!!A" will both be tokenized as ["!", "!", "A"]

The termDelegate option is used to evaluate the terminal symbols in the parse tree (i.e. the values).