tabnas

Parse expressions with precedence

Add infix, prefix, suffix and ternary operators to a grammar, with a binding-power scale you control.

@tabnas/expr

Precedence is the one part of parsing that rule tables are bad at. Expressing 1+2*3 as nested rules means one rule per precedence level, and adding a level means rewriting the chain. @tabnas/expr does it with a Pratt parser instead: every operator carries two numbers, and precedence falls out of comparing them.

Register it on a grammar that already defines values, and values become expressions:

import { Tabnas } from '@tabnas/parser'
import { jsonic } from '@tabnas/jsonic'
import { Expr } from '@tabnas/expr'

const tn = new Tabnas().use(jsonic).use(Expr)

tn.parse('1+2*3')

What comes back

An S-expression: an array whose first element is the operator and whose remaining elements are the terms. The operator is an Op object — it carries the source text, the binding powers, and which fixity matched — so printing a tree usually means replacing it with op.src first:

// Replace each Op with its source text, for display.
const S = (x) =>
  Array.isArray(x) && x.length
    ? [x[0].src || x[0].osrc || S(x[0]), ...x.slice(1).map(S)]
    : x

S(tn.parse('1+2*3'))     // => [ '+', 1, [ '*', 2, 3 ] ]
S(tn.parse('-1+2'))      // => [ '+', [ '-', 1 ], 2 ]
S(tn.parse('2+3+4'))     // => [ '+', [ '+', 2, 3 ], 4 ]
S(tn.parse('(1+2)*3'))   // => [ '*', [ '(', [ '+', 1, 2 ] ], 3 ]

Two things worth noticing. 2+3+4 groups to the left, because addition’s binding powers say so. And the parenthesis is kept in the tree as an operator of its own rather than dissolved — the tree records that the source was written with brackets, which matters if you are formatting it back out.

Expressions live wherever values live, so this needs nothing extra:

S(tn.parse('[1+2, 3*4]'))
// => [ [ '+', 1, 2 ], [ '*', 3, 4 ] ]

The binding-power scale

Each operator gets a left and a right number. When two operators compete for a term, the larger binding power wins. The default table is spaced in millions so there is room to insert between levels:

Operatorleftright
+ - prefix—4000000
* / %30000003100000
+ - infix20000002100000

Associativity is the relationship between the two numbers on one operator. left < right binds to the left, which is what you want for arithmetic. left > right binds to the right, which is what you want for exponentiation and assignment.

Adding operators

op is a map of definitions merged over the defaults, so you only name what you are adding:

const tn = new Tabnas().use(jsonic).use(Expr, {
  op: {
    exponent:  { infix: true,  left: 5000000, right: 4900000, src: '**' },
    lt:        { infix: true,  left: 1400000, right: 1500000, src: '<' },
    and:       { infix: true,  left: 1000000, right: 1100000, src: '&&' },
    factorial: { suffix: true, left: 6000000,                 src: '!' },
  },
})

S(tn.parse('2**3**2'))     // => [ '**', 2, [ '**', 3, 2 ] ]
S(tn.parse('1<2 && 3<4'))  // => [ '&&', [ '<', 1, 2 ], [ '<', 3, 4 ] ]
S(tn.parse('3! + 1'))      // => [ '+', [ '!', 3 ], 1 ]

** binds right (left > right), so 2**3**2 is 2**(3**2). && sits below comparison, so comparisons bind tighter and become its operands. ! is a suffix at the top of the scale, so it takes 3 before + sees it.

Setting an operator to null removes it. Be aware of what that means: the symbol is no longer an operator, but it is still lexable text, so in a relaxed grammar like jsonic 1 % 2 becomes the implicit list [1, '%', 2] rather than a syntax error. Removing an operator is not the same as forbidding it.

Function-call and index syntax

A paren operator with a preval takes the value written immediately before it as its first term. That is all a function call is:

const tn = new Tabnas().use(jsonic).use(Expr, {
  op: {
    call:  { paren: true, osrc: '(', csrc: ')', preval: { active: true } },
    index: { paren: true, osrc: '[', csrc: ']', preval: { required: true } },
  },
})

S(tn.parse('max(1,2)'))   // => [ '(', 'max', [ 1, 2 ] ]
S(tn.parse('f(1)'))       // => [ '(', 'f', 1 ]
S(tn.parse('a[1]'))       // => [ '[', 'a', 1 ]

active means the preceding value is used if present, so (1+2) still groups. required means the operator only matches with one, which is what keeps [ working as a list bracket everywhere else.

Ternaries are declared with a two-element src:

const tn = new Tabnas().use(jsonic).use(Expr, {
  op: { ternary: { ternary: true, src: ['?', ':'], left: 1500000, right: 1400000 } },
})

S(tn.parse('a ? b : c'))   // => [ '?', 'a', 'b', 'c' ]

Computing a value instead

Pass evaluate and the plugin reduces each node as it closes, so parse returns the answer rather than the tree:

const math = (rule, ctx, op, terms) => {
  if (op.paren) return terms[0]
  if (op.prefix) return '-' === op.src ? -terms[0] : +terms[0]
  switch (op.src) {
    case '+': return terms[0] + terms[1]
    case '-': return terms[0] - terms[1]
    case '*': return terms[0] * terms[1]
    case '/': return terms[0] / terms[1]
    default:  return NaN
  }
}

const tn = new Tabnas().use(jsonic).use(Expr, { evaluate: math })

tn.parse('1+2*3')            // => 7
tn.parse('-(1+2)*3')         // => -9
tn.parse('a: 2*(3+4), b: 1') // => { a: 14, b: 1 }

Check op.prefix before switching on op.src: - is both a prefix and an infix operator and they arrive at the same callback with a different number of terms.

Evaluating during the parse is a choice, not the default. It is the right one for a configuration language, where the result is a value. It is the wrong one for anything that wants to inspect, rewrite or re-emit the source — keep the tree and walk it afterwards.

What this costs

The expression grammar is not a small addition. It brings its own rules, counters and edge cases around implicit lists and maps, and it changes what some inputs mean. On plain jsonic, a: 1-2 parses to the string '1-2'; install Expr and it is a subtraction. That is usually the point, but it is a behaviour change to existing input, so install it on a derived instance (base.make().use(Expr)) if other code depends on the original.

See also