basicParser.js

import util from "util";

/**
 *  parses basic arithmetic expressions
 *  GRAMMAR:
 * <expression> ::= <term> { (MINUS|PLUS) <term> }*
 * <term> ::= <factor> { {MULT|DIV} <factor> }*
 * <factor> ::= <number> | ( <expression> )
 */

const tokens = {
  integer: "INTEGER",
  plus: "PLUS",
  minus: "MINUS",
  EOF: "EOF",
  div: "DIV",
  mul: "MUL",
  lparen: "(",
  rparen: ")",
};

class Token {
  constructor(type, value) {
    this.type = type;
    this.value = value;
  }
  [util.inspect.custom]() {
    return `Token(${this.type}, ${this.value})`;
  }
}

class Lexer {
  constructor(text) {
    this.text = text;
    this.pos = 0;
    this.currentChar = this.text[this.pos];
  }
  error(msg) {
    throw new Error(`invalid character`);
  }
  advance() {
    this.pos += 1;
    if (this.pos > this.text.length - 1) {
      this.currentChar = null;
    } else {
      this.currentChar = this.text[this.pos];
    }
  }
  skipWhitespace() {
    while (this.currentChar && this.currentChar.match(/\s/)) {
      this.advance();
    }
  }
  integer() {
    let result = "";
    while (this.currentChar && this.currentChar.match(/[0-9]/)) {
      result += this.currentChar;
      this.advance();
    }
    return new Token(tokens.integer, parseInt(result));
  }
  getNextToken() {
    while (this.currentChar) {
      if (this.currentChar === " ") {
        this.skipWhitespace();
        continue;
      }

      if (this.currentChar.match(/[0-9]/)) {
        return this.integer();
      }

      if (this.currentChar === "/") {
        this.advance();
        return new Token(tokens.div, "/");
      }

      if (this.currentChar === "*") {
        this.advance();
        return new Token(tokens.mul, "*");
      }

      if (this.currentChar === "+") {
        this.advance();
        return new Token(tokens.plus, "+");
      }

      if (this.currentChar === "-") {
        this.advance();
        return new Token(tokens.minus, "-");
      }

      if (this.currentChar === "(") {
        this.advance();
        return new Token(tokens.lparen, "(");
      }

      if (this.currentChar === ")") {
        this.advance();
        return new Token(tokens.rparen, ")");
      }

      this.error();
    }

    return new Token(tokens.EOF, null);
  }
}
class Interpreter {
  constructor(lexer) {
    this.lexer = lexer;
    this.currentToken = this.lexer.getNextToken();
  }

  error() {
    throw new Error(`invalid syntax`);
  }

  eat(tokenType) {
    if (this.currentToken.type === tokenType) {
      this.currentToken = this.lexer.getNextToken();
    } else {
      this.error();
    }
  }

  factor() {
    const token = this.currentToken;
    if (token.type === tokens.integer) {
      this.eat(tokens.integer);
      return token.value;
    }

    if (token.type === tokens.lparen) {
      this.eat(tokens.lparen);
      const result = this.expr();
      this.eat(tokens.rparen);
      return result;
    }

    this.error();
  }

  term() {
    let result = this.factor();
    while (
      this.currentToken.type === tokens.mul ||
      this.currentToken.type === tokens.div
    ) {
      const token = this.currentToken;
      if (token.type === tokens.mul) {
        this.eat(tokens.mul);
        result *= this.factor();
      } else if (token.type === tokens.div) {
        this.eat(tokens.div);
        result /= this.factor();
      }
    }

    return result;
  }

  expr() {
    let result = this.term();
    while (
      this.currentToken.type === tokens.minus ||
      this.currentToken.type === tokens.plus
    ) {
      const token = this.currentToken;
      if (token.type === tokens.minus) {
        this.eat(tokens.minus);
        result -= this.factor();
      } else if (token.type === tokens.plus) {
        this.eat(tokens.plus);
        result += this.factor();
      }
    }
    return result;
  }
}

const lexer = new Lexer(` 2 * (3 - 5)`);
const interpreter = new Interpreter(lexer);
console.log(interpreter.expr());