Emoji AST Interpreter Parser Stage - Part 2

Tokens on their own are just a flat shopping list, they show an apple came before a plus, but they say nothing about grouping, and grouping is exactly what decides whether multiply happens before add, so this part turns that flat list into a tree.

Reading the token stream produced back in Part 1, the parser builds an abstract syntax tree, a nested shape where every node knows its own operator and its children, and that tree is the real backbone every later stage in this series will lean on.

Keeping the parser small but honest about one hard truth, operator precedence, because multiply before add is never optional.

Shaping the AST Node

Now that the project spans more than one file, a small folder layout keeps things tidy, the lexer from Part 1 lives on its own, the token types it shares sit in a dedicated types file, and this part adds a parser file plus the node shapes it produces, so every stage stays firmly in its own lane and imports only what it genuinely needs from its immediate neighbors.

emoji-compiler/
├── src/
│   ├── types.ts      # shared Token and Node shapes
│   ├── lexer.ts      # Part 1: string  → tokens
│   └── parser.ts     # Part 2: tokens  → AST
└── main.ts           # wires stages together

An abstract syntax tree is built from nodes, and the language needs just two node shapes to start, a number node that wraps a single fruit, and a binary node that holds an operator together with a left and a right child that are themselves nodes.

This recursive definition, a node whose children are also nodes, is exactly what lets a flat expression fold into a deep tree.

// src/types.ts
export type TokenKind = 'number' | 'operator' | 'eof'

export interface Token {
  kind: TokenKind
  value: string
}

export type Node =
  | { type: 'number'; value: string }
  | { type: 'binary'; op: string; left: Node; right: Node }

Parsing With Precedence

Its trick for precedence is a technique often called precedence climbing, and the idea is easier than the name suggests, a left operand gets parsed first, then the next operator is peeked at, and each operator keeps binding into the current expression while its precedence stays high enough, and the moment a weaker operator appears the loop stops and hands control back up.

Each operator gets a number, multiply and divide sit higher than plus and minus, and when the parser sees a stronger operator ahead it recurses to build that subtree first, so an apple plus a banana times a cherry groups the banana with the cherry.

Alongside that, the parser also tracks a simple cursor into the token array, consuming each token one by one as it moves forward.

// src/parser.ts
import type { Node, Token } from './types.ts'

const PRECEDENCE: Record<string, number> = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2
}

export function parse(tokens: Token[]): Node {
  let pos = 0
  const peek = (): Token => tokens[pos]
  const next = (): Token => tokens[pos++]

  function parsePrimary(): Node {
    const token = next()
    if (token.kind === 'number') {
      return { type: 'number', value: token.value }
    }
    if (token.value === '(') {
      const inner = parseExpression(0)
      next() // consume the matching ')'
      return inner
    }
    throw new SyntaxError(`Unexpected token: ${token.value}`)
  }

  function parseExpression(minPrec: number): Node {
    let left = parsePrimary()
    while (
      peek().kind === 'operator' &&
      PRECEDENCE[peek().value] >= minPrec &&
      PRECEDENCE[peek().value] !== undefined
    ) {
      const op = next().value
      const right = parseExpression(PRECEDENCE[op] + 1)
      left = { type: 'binary', op, left, right }
    }
    return left
  }

  return parseExpression(0)
}

Reading the Resulting Tree

Feeding the tokens for an apple plus a banana times a cherry into the parser returns a single binary node at the root whose operator is plus, whose left child is the apple, and whose right child is another binary node for the multiplication, and that nesting is the parser silently proving it grasped precedence without a single special case written anywhere by hand.

Parentheses fit naturally into this same model, when the parser meets an opening parenthesis it parses a completely fresh expression from scratch and treats the whole result as one single operand, which means grouping simply overrides precedence by forcing an early subtree, so no extra machinery is needed beyond a small recursive call back into the expression rule.

Structure now fills the tree, holding the full shape of the input, and the next part walks it to produce a genuine real answer.

parse(tokenize('🍎 + 🍌 * 🍒'))
// {
//   type: 'binary', op: '+',
//   left:  { type: 'number', value: '🍎' },
//   right: {
//     type: 'binary', op: '*',
//     left:  { type: 'number', value: '🍌' },
//     right: { type: 'number', value: '🍒' }
//   }
// }