Parsing Addition and Subtraction

Recursive Descent Parsing

A recursive descent parser uses one function per grammar rule. For simple addition/subtraction:

expr   -> number (('+' | '-') number)*
number -> NUMBER

This means: parse a number, then keep parsing + or - followed by another number.

Parser Structure

class Parser {
    constructor(tokens) {
        this.tokens = tokens;
        this.pos = 0;
    }
    peek() { return this.tokens[this.pos]; }
    advance() { return this.tokens[this.pos++]; }
    expect(type) {
        const tok = this.advance();
        if (tok.type !== type) throw new Error("Expected " + type);
        return tok;
    }
}

Parsing an Expression

parseExpr() {
    let left = this.parseNumber();
    while (this.peek().type === "PLUS" || this.peek().type === "MINUS") {
        const op = this.advance().value;
        const right = this.parseNumber();
        left = { type: "BinaryExpr", op, left, right };
    }
    return left;
}

This builds a left-associative tree: 1 + 2 + 3 becomes (+ (+ 1 2) 3).

Your Task

Write a tokenize function and a Parser class that parses addition and subtraction into an AST. Include a printAST function to display the result.