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:
- 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 aforEach()
call here. The strings are identical to the keys ofToken
, 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 asToken
's properties. I'd like to know if this is a good idea. - Once the number of characters to drop in the beginning (calculated in earlier calls to
getNextToken()
, initially0
) is known, slice the string. - This variable is used in the following
if
statements and serves two purposes — it keeps the result of the regex match, but also passesnull
on to theif
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. - 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. - 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.