Table of Contents

1. What Is an AST?
2. Operator Precedence
3. The Parser Class
4. Recursive Descent
5. Primary Expressions
6. AST Node Types
7. Extracting Variables
8. Worked Example
9. What’s Next

What Is an AST?

An Abstract Syntax Tree (AST) is a tree representation of the structure of an expression. Each internal node is an operator and each leaf is a variable. The tree encodes both the operators and their grouping without needing parentheses - the structure itself captures which operands belong to which operator.

For example, the expression (A & B) -> C becomes:

      implies
      /     \
    and      C
   /   \
  A     B

The tree tells us: first evaluate A & B, then check whether that result implies C. Without the tree we’d have to re-analyze precedence and parentheses every time we evaluate.

Operator Precedence

Our parser handles five operators with the following precedence (highest binds tightest):

This means A | B & C is parsed as A | (B & C) because AND binds tighter than OR, and A & B -> C is parsed as (A & B) -> C because AND binds tighter than IMPLIES.

The Parser Class

The parser wraps the token array with a simple cursor. Four methods give us everything we need:

class Parser {
  constructor(tokens) {
    this.tokens = tokens;
    this.pos = 0;
  }

  peek() {
    return this.tokens[this.pos];
  }

  pop() {
    return this.tokens[this.pos++];
  }

  isEmpty() {
    return this.pos >= this.tokens.length;
  }

  isNext(t, val) {
    const token = this.peek();
    return token && token.type === t && token.value === val;
  }
}

• peek() - look at the current token without consuming it.
• pop() - consume the current token and advance.
• isEmpty() - check if we’ve consumed everything.
• isNext(type, value) - check if the current token matches a given type and value.

Recursive Descent

The key idea behind recursive descent parsing is: each precedence level gets its own function. A lower-precedence function calls the next-higher-precedence function to parse its operands. This naturally handles the binding order.

The call chain looks like this:

parseIfAndOnlyIf  →  parseImplies  →  parseOr  →  parseAnd  →  parseNot  →  parsePrimary
    (lowest)                                                                     (highest)

The entry point is parseExpression, which starts the chain and checks that all tokens were consumed:

function parseExpression(tokens) {
  let parser = new Parser(tokens);
  let expr = parseIfAndOnlyIf(parser);

  if (parser.pos < parser.tokens.length) {
    throw new Error('Unexpected token: ' + parser.tokens[parser.pos].value);
  }
  return expr;
}

Each binary operator function follows the same pattern: parse the left operand by calling the next level up, then loop as long as we see the operator at this level, consuming it and parsing the right operand:

function parseIfAndOnlyIf(parser) {
  let left = parseImplies(parser);

  while (parser.isNext('operator', '<->')) {
    parser.pop();
    let right = parseImplies(parser);
    left = { type: 'equiv', left: left, right: right };
  }
  return left;
}

function parseImplies(parser) {
  let left = parseOr(parser);
  while (parser.isNext('operator', '->')) {
    parser.pop();
    let right = parseOr(parser);
    left = { type: 'implies', left: left, right: right };
  }
  return left;
}

function parseOr(parser) {
  let left = parseAnd(parser);
  while (parser.isNext('operator', '|')) {
    parser.pop();
    let right = parseAnd(parser);
    left = { type: 'or', left: left, right: right };
  }
  return left;
}

function parseAnd(parser) {
  let left = parseNot(parser);
  while (parser.isNext('operator', '&')) {
    parser.pop();
    let right = parseNot(parser);
    left = { type: 'and', left: left, right: right };
  }
  return left;
}

Why this works:

Because parseAnd calls parseNot for its operands (not itself), AND will never “capture” a NOT

• the NOT is evaluated first. Similarly, parseOr calls parseAnd, so AND groups before OR. The recursive structure mirrors the precedence table exactly.

Negation is different - it’s a unary prefix operator, so it recurses into itself (right-associative):

function parseNot(parser) {
  if (parser.isNext('operator', '~')) {
    parser.pop();
    let operand = parseNot(parser);
    return { type: 'not', operand: operand };
  }

  return parsePrimary(parser);
}

This means ~~A is parsed as ~(~A), which is the correct behavior - double negation.

Primary Expressions

At the bottom of the chain, parsePrimary handles two cases:

1. A variable - return a leaf node.
2. An opening parenthesis - parse the sub-expression inside by calling back to parseIfAndOnlyIf (the lowest precedence), then consume the closing ).

function parsePrimary(parser) {
  const token = parser.pop();
  if (!token) {
    throw new Error('Unexpected end of input');
  }

  if (token.type === 'variable') {
    return { type: 'var', value: token.value };
  }
  if (token.type === 'paren' && token.value === '(') {
    let expr = parseIfAndOnlyIf(parser);
    if (parser.isNext('paren', ')')) {
      parser.pop();
    } else {
      throw new Error("Expected ')'");
    }
    return expr;
  }
  throw new Error('Unexpected token: ' + token.value);
}

Note:

When we encounter (, we call parseIfAndOnlyIf - not parsePrimary. This resets the precedence chain, allowing any operator inside the parentheses. That’s how (A | B) & C works correctly: the OR inside the parens is fully parsed before the AND outside.

AST Node Types

Our AST uses three node types:

VarNode - a leaf representing a variable:

{ type: 'var', value: 'A' }

NotNode - a unary node with one child:

{ type: 'not', operand: /* ASTNode */ }

BinaryNode - a node with two children, for AND, OR, IMPLIES, and EQUIV:

{ type: 'and',     left: /* ASTNode */, right: /* ASTNode */ }
{ type: 'or',      left: /* ASTNode */, right: /* ASTNode */ }
{ type: 'implies', left: /* ASTNode */, right: /* ASTNode */ }
{ type: 'equiv',   left: /* ASTNode */, right: /* ASTNode */ }

Extracting Variables

Once we have the AST, we need to know which variables appear in it to build the truth table. getVariables traverses the tree and collects unique variable names:

function getVariables(ast) {
  let vars = new Set();
  function traverse(node) {
    switch (node.type) {
      case 'var':
        vars.add(node.value);
        break;
      case 'not':
        traverse(node.operand);
        break;
      case 'and':
      case 'or':
      case 'implies':
      case 'equiv':
        traverse(node.left);
        traverse(node.right);
        break;
    }
  }
  traverse(ast);
  return Array.from(vars).sort();
}

The Set handles deduplication, and we sort the result alphabetically so the truth table columns are in a predictable order.

Worked Example

Let’s trace the parsing of (A & B) -> C step by step.

Starting tokens (from Chapter 2):

[(  A  &  B  )  ->  C]

1. parseExpression → calls parseIfAndOnlyIf
2. parseIfAndOnlyIf → calls parseImplies
3. parseImplies → calls parseOr → parseAnd → parseNot → parsePrimary
4. parsePrimary sees (, calls parseIfAndOnlyIf recursively
5. Inside the parens: parseIfAndOnlyIf → … → parseAnd
6. parseAnd parses left: parseNot → parsePrimary → VarNode("A")
7. parseAnd sees &, pops it, parses right: VarNode("B")
8. parseAnd returns { type: 'and', left: Var(A), right: Var(B) }
9. Back in parsePrimary, ) consumed
10. Back in parseImplies, sees ->, pops it, parses right: VarNode("C")
11. Returns { type: 'implies', left: And(A,B), right: Var(C) }

The resulting AST:

      implies
      /     \
    and      var(C)
   /   \
var(A)  var(B)

And getVariables returns ['A', 'B', 'C'].

What’s Next

We now have a structured tree that encodes the full meaning of the expression. In Chapter 4: Truth Tables and Normal Forms, we’ll walk every possible variable assignment, evaluate the AST, build the truth table, and extract the CNF and DNF.

Previous: Chapter 2: Tokenizing Logical Expressions

Series: Back to Truth Table, CNF, and DNF Generator