Simple lexical analysis - basic calculator

Question

I recently found an interesting series that describes the specifics of how interpreters and compilers work, explaining each step (with code) and encouraging the reader to do exercises.

My code is mostly based on the boilerplate provided in the first tutorial. The description didn't really seem clear enough to me, so I went on to consult the actual code. That was probably the best idea in my case, as it helped me grasp the very basics of lexical analysis.

Once I'd had the code working, I reread the article and by then I felt confident enough to approach the exercises.

I had no problem with getting my code to satisfy the conditions in the exercises.
However, I'm not sure whether my approach was good. I used regular expressions to tokenize the input and remove whitespaces at the same time. That kind of solution seemed robust; the code worked, but I felt a bit uneasy about it (though I couldn't really explain to myself why the use of regular expressions here was wrong). I then looked at the code in the second tutorial that solved all the exercises, and it didn't use regular expressions at all — instead, it iterated over each character (including whitespaces).

I coded my lexer in JavaScript and run it in Node.js (though it can be run in virtually every environment that supports ES6 classes).

What kind of feedback do I expect? I would like to see my doubts about regular expressions explained (does any lexer do that? If not, why?), but there are probably many things about the code that can be done better — and I will really appreciate the answers which suggest improvements. There are also a few more questions at the bottom of this post.

Note: The script does not yet respond to user input, the input sequence needs to be hardcoded as a string.

See below for explanations on certain parts of the code.

'use strict';

class Token {
  constructor(type, value) {
    this.type = type;
    this.value = value;
  }
}
['EOF', 'INT', 'MATHOP'].forEach(function (el) {                                  // #1
  Token[el] = el;
});

class Interpreter {
  constructor(source) {
    this.source = source;
    this.pos = 0;
    this.currentToken = null;
  }
  eat(type) {
    if (this.currentToken.type === type) {
      this.currentToken = this.getNextToken();
    } else {
      throw new Error('Unexpected token of type ' + this.currentToken.type);
    }
  }
  getNextToken() {
    if (this.pos >= this.source.length) {
      return new Token(Token.EOF, null);
    }
    var s = this.source.slice(this.pos);                                          // #2
    var re;                                                                       // #3
    if (re = /^\s*([0-9]+)/.exec(s)) {
      this.pos += re[0].length;
      return new Token(Token.INT, +re[1]);
    }
    if (re = /^\s*([-+*/])/.exec(s)) {
      this.pos += re[0].length;
      return new Token(Token.MATHOP, re[1]);
    }
    throw new Error('Erroneous input');
  }
  expr() {
    this.currentToken = this.getNextToken();

    var left = this.currentToken;
    this.eat(Token.INT);
    var op = this.currentToken;
    this.eat(Token.MATHOP);                                                       // #4
    var right = this.currentToken;
    this.eat(Token.INT);

    switch (op.value) {
      case '+':
        return left.value + right.value;
      case '-':
        return left.value - right.value;
      case '*':
        return left.value * right.value;
      case '/':
        return left.value / right.value;
    }
  }
}

var i = new Interpreter('11 * 23');                                               // #5
console.log(i.expr());

Explanations:

1. At first, all I had was Token.EOF = 0; and so on, each token being assigned a unique, successive number. That wasn't really useful, as stack traces would display the number and I'd have to either remember the type or look it up in the code. I thought that string equivalents would be much more useful, and, to automate the task, I used a forEach() call here. The strings are identical to the keys of Token, so one could think I could stick to strings only and never use variables for that. I think that would get out of control quickly, so, to keep things in place, I assigned the string values as Token's properties. I'd like to know if this is a good idea.
2. Once the number of characters to drop in the beginning (calculated in earlier calls to getNextToken(), initially 0) is known, slice the string.
3. This variable is used in the following if statements and serves two purposes — it keeps the result of the regex match, but also passes null on to the if statement if there is no match. Is this clever, or "too clever"?
   The actual regexes ensure that any whitespace preceding the expected token is dropped.
4. The second part of the tutorial mentioned above uses separate tokens for both the + and - signs. My code unifies all the basic arithmetic operators and uses the token's value to determine the operation to be performed. This is what I would like to see criticized as well. I know that in the future I would have to take operator precedence into account, but I think I could solve it sticking to this way.
5. Currently this is the only way to pass input to the interpreter. Once it gets more complex, I will ensure that the input can be supplied in a user-friendly way.

Answer 1

I'm not a compiler guy, but I'll offer some feedback, anyway. Hope it helps.

Nice work.

Regular expressions are a powerful tool, but they can become difficult to maintain and sometimes to get right. You used them, they work, seems fine. I'd suggest making it a point to always use simple regular expressions (which you did). If you need more complex matching, using multiple simple regular expressions in a sequence or loop or in combination with character / string comparisons seems to work pretty well.

To answer your questions:

1: Using integers does make error messages harder to read, so switching to strings for token types is a good idea, IMO. But, instead of adding properties onto the Token class I'd suggest doing something like the following:

var tokenTypes = Object.freeze({
    EOF: 'EOF',
    INT: 'INT',
    MATHOP: 'MATHOP'
});

In the past I've done something like this to make error messages and what not easier to read:

var tokenTypes = Object.freeze({
    EOF: 'tokenType { EOF }',
    INT: 'tokenType { INT }',
    MATHOP: 'tokenType { MATHOP }'
});

2: Slicing the string is fine. If there is more to the question, then please elaborate.

3: Use of the re variable to store the match is not too clever. I recommend against assignment inside the if condition, though, it's just something that can be error prone, in general. Down the road you may make an edit and forget to have only one =, or something like that. It's usually considered against best-practices, but is not invalid or anything.

4: As I'm not a compiler guy, take this for what it's worth (there is probably obvious conventional wisdom that I don't know about). Using a single token type for these four operations seems fine to me. They all have similar characteristics. But, it will likely be an issue if you broaden this MATHOP usage to operators that have different characteristics, like the unary - (e.g. 1 + -(3 + 4)). Having said that, you may end up keeping these four operators under one BINARY_OP type. You may end up wanting to group on precedence, though.

5: Not a question.

One thing I want to note, the eat and getNextToken methods are organized in a way that is a little strange, to me. You consume a token (move pos forward), then when you are getting the next token after that, check the type of the previous token. I like to have separate getNNNToken methods for the various tokens I have. For instance, you might have getIntToken() and getOpToken(). Each of these can attempt to consume the correct type of token, and if it fails return undefined. The method that called them can decide if that is an error or if another type of token should be attempted, like getEofToken().

As a side note, a scanner I wrote for a DSL: JavaScript and Python. It uses a mix of regular expressions and character comparisons for consuming content. The scanner has a start property and a pos property, and any time a token is created the content spans from start to pos-1. Then, start is moved forward to pos.