How to Build a Custom Arithmetic Parser with AST and Vector Extensions in JavaScript

4 Parser (Syntax Analysis)

After lexical analysis splits the input string into tokens, the parser assembles these tokens into an abstract syntax tree (AST) using a stack. Each node in the AST is a simple JavaScript object with type, children, and maxChildren properties.

4.1 Defining AST Nodes

An AST is a tree composed of nodes and literals. The root node is created by RootNode() and pushed onto the stack.

interface Node {
  type: string,
  children: [], // can contain Node or Literal
  maxChildren: number,
}

4.2 Stack and Root Node

Each incoming token is pushed onto the stack. The first step pushes the root node:

function RootNode(){
  return {
    type: "ROOT",
    children: [],
    maxChildren: 0,
  }
}
const stack = [RootNode()];

4.3 General Node Rules

No‑children node: maxChildren === 0 Not‑full node: maxChildren > 0 && children.length < maxChildren Full node:

maxChildren > 0 && children.length >= maxChildren

function isFullNode(node){
  if (isNoChildrenNode(node)) return false;
  return node && node.children && node.children.length >= node.maxChildren;
}
function isNotFullNode(node){
  if (isNoChildrenNode(node)) return false;
  return node && node.children && node.children.length < node.maxChildren;
}
function isNoChildrenNode(node){
  return node.maxChildren === 0;
}

4.4 Number Node

function NumberNode(){
  return {
    type: "NUMBER",
    children: [...arguments],
    maxChildren: 1,
  }
}

When a NUMBER token arrives, the parser checks the stack top: if it is not full, the number is pushed as a child; otherwise a new node is pushed.

const top = stack[stack.length - 1];
if (token.type === "NUMBER") {
  if (isFullNode(top)) throw new Error("Previous node is full");
  const number = CreateTypeNode(token.type)(token.value);
  if (isNotFullNode(top)) {
    return topChildPush(number);
  } else {
    return stackPush(number);
  }
}

4.5 Operator Nodes (+, -, *, /)

function AddNode(){ return {type:"+", children:[...arguments], maxChildren:2}; }
function SubNode(){ return {type:"-", children:[...arguments], maxChildren:2}; }
function MulNode(){ return {type:"*", children:[...arguments], maxChildren:2}; }
function DivNode(){ return {type:"/", children:[...arguments], maxChildren:2}; }

Operator precedence is stored in operatorValue and used to decide whether to rob (higher precedence steals a child) or retire (current node is closed).

const operatorValue = {
  "ROOT": 0,
  "+": 1,
  "-": 1,
  "*": 2,
  "/": 2,
  "NUMBER": 3,
};

4.6 Retire and Rob Operations

const retire = (type) => {
  stack.push(CreateTypeNode(type)(stack.pop()));
};
const rob = (type, children) => {
  const child = children.pop();
  stack.push(CreateTypeNode(type)(child));
};

The parser compares the precedence of the incoming operator with the stack top. If the top has higher or equal precedence, retire is performed; otherwise rob moves a child to the new operator.

4.7 Link Operation

Before retiring, link collapses full nodes that appear before the new operator, ensuring left‑to‑right evaluation for operators with equal precedence.

const link = (type) => {
  const value = operatorValue[type];
  while (
    isFullNode(stack[stack.length-1]) &&
    isNotFullNode(stack[stack.length-2]) &&
    (value <= typeValue(stack[stack.length-1])) &&
    (value <= typeValue(stack[stack.length-2]))
  ) {
    stack[stack.length-2].children.push(stack.pop());
  }
};

4.8 Handling Parentheses

Parentheses are treated as barrier nodes with maxChildren: 0. When a closing ) token is seen, remove("(") links the inner nodes, converts the opening node to a closing node, and marks it as full.

function ParNode(){ return {type:"(", children:[], maxChildren:0}; }
if (token.value === ")") {
  return remove("(");
}
const remove = (type) => {
  link(type);
  while (stack.length && !(stack[stack.length-1].type===type && !stack[stack.length-1].children)) {
    tempStack.push(stack.pop());
  }
  const top = stack[stack.length-1];
  if (top.type===type){
    top.type = opposite[type]; // '(' => ')'
    top.children = [];
    while (tempStack.length){ top.children.push(tempStack.pop()); }
    top.maxChildren = top.children.length;
  }
};

4.9 Negative Numbers

The minus sign can be a prefix (negation) or infix (subtraction). If the stack top is a no‑children or not‑full node, the parser treats - as a prefix and creates a NEGATE node.

function NegNode(){ return {type:"NEGATE", children:[...arguments], maxChildren:1}; }
if (token.type === "SIGN") {
  if (isFullNode(top)) {
    // infix subtraction handled earlier
  } else {
    if (token.value === "-") return stackPush(CreateTypeNode("NEGATE")());
    if (token.value === "+") return; // unary plus ignored
    throw new Error(token.value + " cannot be used as prefix");
  }
}

4.10 Extending to Vectors

Square brackets [ ] denote a 2‑D vector. A comma separates the two components. The parser adds [, ], and , as sign tokens and defines VecNode and WallNode (the comma).

function VecNode(){ return {type:"[", children:[], maxChildren:0}; }
function WallNode(){ return {type:",", children:[], maxChildren:0}; }
if (token.value === "[") { return stack.push(CreateTypeNode("[")()); }
if (token.value === ",") { link("["); return stack.push(CreateTypeNode(",")()); }
if (token.value === "]") { return remove("["); }

4.11 Custom Operators (@rot, @dot, @deg)

Custom symbols start with @. The lexer collects characters after @ into a single token. Nodes for rotation, dot product, and degree‑to‑radian conversion are added, with precedence higher than arithmetic operators.

function DegNode(){ return {type:"@deg", children:[...arguments], maxChildren:1}; }
function DotNode(){ return {type:"@dot", children:[...arguments], maxChildren:2}; }
function RotNode(){ return {type:"@rot", children:[...arguments], maxChildren:2}; }
const operatorValue = {
  "ROOT":0, "(":1, "[":1, "@dot":2,
  "<":3, ">":3, "+":4, "-":4,
  "*":5, "/":5, "@rot":5,
  "NEGATE":6, "@deg":7, "NUMBER":8,
  ")":9, "]":9, "ROOT_END":10,
};

5 Evaluation

After the EOF token, the AST is complete. A recursive evaluate function walks the tree and computes the result. It handles numbers, the four arithmetic operators, parentheses, vectors, and the custom operators.

function evaluate(node){
  const {type, children} = node;
  if (type === "NUMBER") return Number(children[0]);
  if (type === "+") {
    const a = evaluate(children[0]);
    const b = evaluate(children[1]);
    return Vector2d.is(a) && Vector2d.is(b) ? Vector2d.add(a,b) : a + b;
  }
  if (type === "-") {
    const a = evaluate(children[0]);
    const b = evaluate(children[1]);
    return Vector2d.is(a) && Vector2d.is(b) ? Vector2d.sub(a,b) : a - b;
  }
  if (type === "*" || type === "/") {
    const a = evaluate(children[0]);
    const b = evaluate(children[1]);
    if (typeof a === "number" && typeof b === "number") {
      return type === "*" ? a * b : a / b;
    }
    if (Vector2d.is(a) && typeof b === "number") {
      return type === "*" ? Vector2d.scale(a,b) : Vector2d.scale(a,1/b);
    }
    if (Vector2d.is(b) && typeof a === "number") {
      return type === "*" ? Vector2d.scale(b,a) : Vector2d.scale(b,1/a);
    }
    throw new Error("Invalid multiplication/division of vectors");
  }
  if (type === "NEGATE") {
    const a = evaluate(children[0]);
    return Vector2d.is(a) ? Vector2d.scale(a,-1) : a * -1;
  }
  if (type === "]") {
    const comps = children.filter(c=>c.type !== ",");
    const a = evaluate(comps[0]);
    const b = evaluate(comps[1]);
    if (typeof a === "number" && typeof b === "number") return new Vector2d(a,b);
    throw new Error("Vector requires two numbers");
  }
  if (type === "@dot") {
    const a = evaluate(children[0]);
    const b = evaluate(children[1]);
    if (Vector2d.is(a) && Vector2d.is(b)) return Vector2d.dot(a,b);
    throw new Error("Dot product requires two vectors");
  }
  if (type === "@rot") {
    const a = evaluate(children[0]);
    const b = evaluate(children[1]);
    if (Vector2d.is(a) && typeof b === "number") return Vector2d.rotate(a,b);
    if (Vector2d.is(b) && typeof a === "number") return Vector2d.rotate(b,a);
    throw new Error("Rotation needs a vector and an angle");
  }
  if (type === "@deg") {
    const a = evaluate(children[0]);
    if (typeof a === "number") return a / 180 * Math.PI;
    throw new Error("@deg expects a number");
  }
  if (type === "ROOT_END") return evaluate(children[0]);
}
console.log(evaluate(ast)); // example output

6 Summary

The article demonstrates a complete pipeline: lexical analysis (lexer) → syntax analysis (parser) → AST construction → recursive evaluation. It shows how to extend the parser with custom tokens for vectors, parentheses, negative numbers, and user‑defined operators, and provides a Vue demo for visualizing the AST.

7 Demo

A live Vue demo ( http://rococolate.github.io/blog/ast/index.html ) visualizes the token‑to‑AST conversion, and the source code is available on GitHub ( https://github.com/Rococolate/ast_demo ).