Top Down Operator Precedence: basic implementation in JavaScript

TopDownOperatorPrecedence.js

const PRECEDENCE = {
    "=": 1,
    "+": 2,
    "-": 2,
    "*": 3,
    "/": 3,
    "(": 0,
    ")": 0
};

class Token {
    constructor(type, value) {
        this.type = type;
        this.value = value;
    }
}

class Lexer {
    constructor(input) {
        this.input = input;
        this.position = 0;
    }

    nextToken() {
        while (this.position < this.input.length) {
            const char = this.input[this.position];
            if (/\s/.test(char)) {
                this.position++;
                continue;
            }
            if (/[a-zA-Z_]/.test(char)) {
                let value = '';
                while (this.position < this.input.length && /[a-zA-Z_]/.test(this.input[this.position])) {
                    value += this.input[this.position++];
                }
                return new Token('IDENTIFIER', value);
            }
            if (/[0-9]/.test(char)) {
                let value = '';
                while (this.position < this.input.length && /[0-9]/.test(this.input[this.position])) {
                    value += this.input[this.position++];
                }
                return new Token('NUMBER', parseInt(value, 10));
            }
            if (char in PRECEDENCE) {
                this.position++;
                return new Token(char, char);
            }
            throw new Error(`Unexpected character: ${char}`);
        }
        return new Token('EOF', null);
    }
}

class Parser {
    constructor(lexer) {
        this.lexer = lexer;
        this.token = this.lexer.nextToken();
    }

    parseExpression(precedence) {
        let left = this.parsePrefix();
        while (precedence < this.getPrecedence()) {
            left = this.parseInfix(left);
        }
        return left;
    }

    parsePrefix() {
        const token = this.token;
        if (token.type === 'NUMBER' || token.type === 'IDENTIFIER') {
            this.nextToken();
            return token;
        }
        if (token.type === '(') {
            this.nextToken();
            const expr = this.parseExpression(0);
            if (this.token.type !== ')') {
                throw new Error("Expected ')'");
            }
            this.nextToken();
            return expr;
        }
        throw new Error(`Unexpected token: ${token.type}`);
    }

    parseInfix(left) {
        const token = this.token;
        const precedence = this.getPrecedence();
        this.nextToken();
        const right = this.parseExpression(precedence);
        return { type: 'BINARY', operator: token.type, left, right };
    }

    getPrecedence() {
        return PRECEDENCE[this.token.type] || 0;
    }

    nextToken() {
        this.token = this.lexer.nextToken();
    }
}

test

const input = "3 + 5 * (2 - 8)";
const lexer = new Lexer(input);
const parser = new Parser(lexer);
const expression = parser.parseExpression(0);
console.log(JSON.stringify(expression, null, 2));

const PRECEDENCE: { [key: string]: number } = {
    "=": 1,
    "+": 2,
    "-": 2,
    "*": 3,
    "/": 3,
    "(": 0,
    ")": 0
};

class Token {
    constructor(public type: string, public value: string | number | null) {}
}

class Lexer {
    private position: number = 0;

    constructor(private input: string) {}

    nextToken(): Token {
        while (this.position < this.input.length) {
            const char = this.input[this.position];
            if (/\s/.test(char)) {
                this.position++;
                continue;
            }
            if (/[a-zA-Z_]/.test(char)) {
                let value = '';
                while (this.position < this.input.length && /[a-zA-Z_]/.test(this.input[this.position])) {
                    value += this.input[this.position++];
                }
                return new Token('IDENTIFIER', value);
            }
            if (/[0-9]/.test(char)) {
                let value = '';
                while (this.position < this.input.length && /[0-9]/.test(this.input[this.position])) {
                    value += this.input[this.position++];
                }
                return new Token('NUMBER', parseInt(value, 10));
            }
            if (char in PRECEDENCE) {
                this.position++;
                return new Token(char, char);
            }
            throw new Error(`Unexpected character: ${char}`);
        }
        return new Token('EOF', null);
    }
}

class Parser {
    private token: Token;

    constructor(private lexer: Lexer) {
        this.token = this.lexer.nextToken();
    }

    parseExpression(precedence: number): any {
        let left = this.parsePrefix();
        while (precedence < this.getPrecedence()) {
            left = this.parseInfix(left);
        }
        return left;
    }

    parsePrefix(): any {
        const token = this.token;
        if (token.type === 'NUMBER' || token.type === 'IDENTIFIER') {
            this.nextToken();
            return token;
        }
        if (token.type === '(') {
            this.nextToken();
            const expr = this.parseExpression(0);
            if (this.token.type !== ')') {
                throw new Error("Expected ')'");
            }
            this.nextToken();
            return expr;
        }
        throw new Error(`Unexpected token: ${token.type}`);
    }

    parseInfix(left: any): any {
        const token = this.token;
        const precedence = this.getPrecedence();
        this.nextToken();
        const right = this.parseExpression(precedence);
        return { type: 'BINARY', operator: token.type, left, right };
    }

    getPrecedence(): number {
        return PRECEDENCE[this.token.type] || 0;
    }

    nextToken(): void {
        this.token = this.lexer.nextToken();
    }
}

const input = "3 + 5 * (2 - 8)";
const lexer = new Lexer(input);
const parser = new Parser(lexer);
const expression = parser.parseExpression(0);
console.log(JSON.stringify(expression, null, 2));