Building a Language Interpreter in JavaScript - Part 1

Building a language is hard, we all know that. So let's build one!

In this article series, we will build a usable language interpreter using pure JavaScript. Keep in mind that we will cover the most important (and most fun) parts of building a programming language. We will not concentrate on things like optimization or emitting bytecode.

Implementation will probably not be super-optimal too, but the purpose is to learn. And the end product can be used for many applications which do not require high-speed computing.

We will be using NodeJS for this project, but the end product can easily be tested in the browser too.

Another thing to note, this series will not use any existing libraries to build this. We will learn much much more this way than just using a library. But, to help those just wanting tldr, in the end, I will show you an easier way to do this by using a library that solves a lot of things we will implement manually.

Let's meet the language

Let's meet our language we will be making -- printly. Below is a simple snippet of what we will be interpreting:

1firstName = 'John';
2lastName = 'Smith';
3age = 50;
4
5print(firstName + ',' + lastName);
6
7if (age > 40) {
8    print(firstName + ' is over 40 years old');
9}

So, let's see what we have here:

• Variable assignments like firstName = 'John';‍
• Print function call print(firstName + ',' + lastName);‍
• Operators + , >‍
• Parentheses ( )‍
• If statement if (age > 40) {‍
• Code blocks inside an if statement { }‍
• String literals 'John'‍
• Numbers 50‍
• And of course, so that we do not forget... the dreaded semicolon ; :)

Overview

Here is the overview of stages we will perform in interpreting our language:

1. We will read the code with the lexer and produce tokens
2. We will read the tokens and create a structure that can be interpreted
3. We will interpret the structure and execute it.
4. We will return the result of the ran code.

Note: You can follow the parts of this article by checking out specific branches mentioned in the article. Complete code is available at: https://github.com/ArekX/javascript-interpreter-example

Building a lexer

We will start our journey by building a lexer. Lexer is a piece of software that reads characters and transforms them into tokens. We will then use those tokens in the next stage.

You might think "ok this is easy, we will just use some regex to find things in the code string we want and produce tokens". This is not a good approach as you need to be able to also detect the correct positions of the token without a really complicated regex that might not be possible and can lead to bugs.

That is not to say that we won't use regex at all, we will use it but on a character level to detect a specific range of characters like uppercase / lowercase letters and numbers.

Our first order of business is to read the characters one by one. We will need to read characters and store the state where we are so that lexer can check for some characters ahead or before to make decisions on whether it can detect a specific token or not.

So to start we need a character reader:

1module.exports = class CharacterReader {
2    constructor(code) {
3        this.code = code; // store code which we will read through
4        this.characterPosition = 0; // Current character in a line of code text
5        this.linePosition = 0; // Current line in the code text
6        this.position = 0; // Current character in the code string.
7    }
8
9    // Return the number of characters specified by `amount`
10    // without advancing the character reader.
11    peek(amount = 1) {
12        return this.code.substring(this.position, this.position + amount);
13    }
14
15    // Advance the character reader by specified amount
16    next(amount = 1) {
17        // we need a loop to go through all of the characters
18        // by the specified amount so that we can properly
19        // determine when a new line happened so that we
20        // can keep proper line and character position.
21        for(let i = this.position; i < this.position + amount; i++) {
22            if (this.code[i] == '\n') { // If a new line character is detected
23                this.linePosition++; // Increase line position
24                this.characterPosition = 0; // Reset character position as it is a new line.
25                continue;
26            }
27
28            this.characterPosition++; // Increase character position for the line.
29        }
30
31        this.position += amount; // Change current reader position in code string.
32    }
33
34    // Getter to just return current character position in the line in the code.
35    getCharacterPosition() {
36        return this.characterPosition;
37    }
38
39    // Getter to return current line position in the code
40    getLinePosition() {
41        return this.linePosition;
42    }
43
44    // Check and return whether there is more code to parse.
45    hasNext() {
46        return this.position < this.code.length;
47    }
48}

And to use it let's write:

1const CharacterReader = require('./character-reader');
2
3// Code which we want to parse
4const code = `variable = 5`;
5
6// Create an instance of character reader.
7const reader = new CharacterReader(code);
8
9// Should output a 'v'
10console.log(reader.peek());

If you wish to follow this part through the code please checkout the branch part1-chapter1.

Reading characters into Tokens

A token is a representation of a concept we support in our language, like a variable name, equal sign a string, etc.

The reason why we need to use tokens multiple:

We can perform syntax validation to ensure that the code is written correctly. We can ensure that token B comes after token A.

We can process tokens instead of detecting things going one character at a time without having to worry if there is one space between a variable and equal sign or if there are 50.

Tokens are normalized, meaning it's easy to know what they are, and where they are in the text without having to write differently 'if' statements to handle specific edge cases you can usually have like whether a number is a floating point if it has a . or not.

To read tokens we first need to define them. In our language we have the following tokens:

1. Numbers
2. Strings between ' character
3. Operators !, +, -, *, /, ==, !=, &&, ||, <, >, <=, >=, =, !=
4. Keywords like if
5. Names like variable names, function names, etc.
6. Parentheses ()
7. Code blocks between {}
8. End of line ;
9. Commas ,
10. Whitespace like tabs, new lines, space characters

We need to create a detection algorithm for each of these. We will separate them into functions.

Keep in mind that the order of detection also matters here. If we for instance detect variable names before keywords we will not be able to detect keywords. The order of detection we will use is noted above.

Implementing a detection loop

Our detection loop will detect characters using the character reader implemented. We will create it like this:

1// Character reader we implemented
2const CharacterReader = require('./character-reader');
3
4// List of token detector functions we will implement.
5const tokenDetectors = [];
6
7const detectTokens = code => {
8    // Create character reader for our code.
9    const reader = new CharacterReader(code);
10
11    // List of tokens we found in the code.
12    const foundTokens = [];
13
14    // We loop until we go through all of the characters.
15    while (reader.hasNext()) {
16        let token = null;
17
18        // Store the positions in case we detect the token
19        let startPosition = reader.position;
20        let linePosition = reader.getLinePosition();
21        let characterPosition = reader.getCharacterPosition();
22
23        // We go through each of the token detectors
24        // and call the function for detecting each token.
25        for (const detectToken of tokenDetectors) {
26            token = detectToken(reader);
27
28            if (token) {
29                // Token is detected so we do not
30                // continue detection.
31                break;
32            }
33        }
34
35        // If no token could detect the character at this
36        // position means that we have a syntax error in our
37        // language so we should not continue.
38        if (!token) {
39            throw new Error(`Invalid character '${reader.peek()}' at ${linePosition}:${characterPosition}`);
40        }
41
42        // If a token is found we store the token data
43        // together with the position information.
44        foundTokens.push({
45            ...token,
46            start: startPosition,
47            end: reader.position,
48            line: linePosition,
49            character: characterPosition
50        });
51    }
52
53    // After we found all of the tokens we remove the whitespace
54    // tokens because we will not use them.
55    return foundTokens.filter(i => i.type !== 'whitespace');
56};

Now we will implement each of the token detectors.

Numbers

For numbers detection, we will need to detect number characters. We will only detect integer numbers, in this case, to keep things simple but this function can easily be modified to detect a full number specification.

1const readNumberToken = reader => {
2    let numberText = '';
3    const numberMatch = /\d/; // Regex for detecing a digit.
4
5    // We read until we characters to read.
6    while (reader.hasNext()) {
7        if (reader.peek().match(numberMatch)) { 
8            // If a number matches the regex we add the
9            // character to our string
10            numberText += reader.peek();
11            reader.next();
12        } else {
13            // if the number is not matched we do not need to search anymore.
14            break;
15        }
16    }
17
18    if (numberText.length == 0) {
19        // if no number was detected, return null meaning no token detected.
20        return null;
21    }
22
23    // We found the token and we return type and value of the token.
24    return { type: 'number', value: numberText };
25}

Strings

For string literal, we need more code because we need to handle specific states. The string starts with a quote ' and ends with 'a quote character.

Between those characters, we need to capture any characters (also known as consuming characters). We also have a special case we need to solve. This is when we want to have a quote inside a string.

In our implementation, we decided that if you prepend \ character, we will not treat the quote character as an end of the string. This is called character escaping.

This is the implementation function below:

1const readString = reader => {
2    let value = '';
3    let startedReading = false; // Flag if we started reading a string
4    let isEscaping = false; // Flag if we need to ignore the next character.
5
6    // We read until we characters to read.
7    while (reader.hasNext()) {
8        const matchFound = reader.peek() == "'";
9
10        // if we didnt start reading the string and the string character didnt match
11        // this means that we didn't encounter a string.
12        if (!startedReading && !matchFound) {
13            break;
14        }
15
16        // This allow us to have a ' character inside
17        // our strings as long as we escape it.
18        if (reader.peek() == '\\' && !isEscaping) {
19            isEscaping = true;
20            reader.next();
21            continue; // we only consume this character and not add it to value.
22        }
23
24        // if we started reading and found a string character,
25        // this means that we reached the end of string literal
26        if (startedReading && matchFound && !isEscaping) {
27            reader.next(); // move to a character after ' in the code.
28            break;
29        }
30
31        // if we didn't start reading but we found a valid string start
32        // we set the state for reading the string.
33        if (!startedReading && matchFound) {
34            startedReading = true;
35            reader.next();
36            continue;
37        }
38
39        // Add the character to our detected string.
40        value += reader.peek();
41        reader.next(); // Move the reader to a next character.
42        isEscaping = false; // Reset escape flag so that we do not escape the next character.
43    }
44
45    if (value.length == 0) {
46        return null; // if no string token was found
47    }
48
49    // return token of type string
50    return { type: 'string', value };
51}

Operators

Now, let's detect our operators. We have different types of operators from
mathematical to relational. In this case, we will detect them all.

Since some operators have two characters like ==, &&, || we need to peek
for two characters and for one character in the character reader. There are other ways to do this but this way is easier to understand.

1const readOperator = reader => {
2    // Regex for operator characters we want to detect.
3    const operatorMatch = /^(!|\+|-|\*|\/|==|!=|&&|\|\||<|>|<=|>=|=|!=)$/;
4
5    // Peek one character to detect one character operator
6    const oneCharacterOperator = reader.peek();
7
8    // Peek one character to detect two characters operator
9    const twoCharacterOperator = reader.peek(2);
10
11    let value = null;
12
13    if (twoCharacterOperator.match(operatorMatch)) {
14        reader.next(2);
15        value = twoCharacterOperator; // two character operator was found
16    } else if (oneCharacterOperator.match(operatorMatch)) {
17        reader.next();
18        value = oneCharacterOperator; // one character operator was found
19    }
20
21    if (value) {
22        // Operator is found, we return the token.
23        return { type: 'operator', value };
24    }
25
26    // Nothing was found so we return null that the token was not found.
27    return null;
28}

Keywords

After that, we have to detect keywords. Keywords are names that we decided have a special meaning in our language. For our language, we will only have one. That is if keyword.

1const readKeyword = reader => {
2    if (reader.peek(2).match(/^if$/i)) {
3        // We detected if keywords and return the token.
4        reader.next(2);
5        return { type: 'keyword', value: 'if' };
6    }
7
8    // No keyword detected
9    return null;
10}

Names

Now for variable and function names, we need to define what those are. Both variable 'name' and function 'name' are just that, names. We can detect them using the same token. Then depending on the context, we can deduce that we are calling a function or returning a variable name.

For our language, a name must start with a lowercase letter and then needs to have a continuous string of letters and numbers.

We can represent a name with two regular expressions:

• /[a-z]/ for the start of the name, if this is not detected we do not detect anything further.
• /[a-zA-Z0-9]+/ for the rest of the name, we detect until we match this.

1const readName = reader => {
2    let value = '';
3    const startOfVariableMatch = /[a-z]/;
4    const restOfVariableMatch = /[a-zA-Z0-9]/;
5
6    // If we did not match the variable, do not return a token.
7    if (!reader.peek().match(startOfVariableMatch)) {
8        return null;
9    }
10
11    value = reader.peek();
12    reader.next();
13
14    while (reader.hasNext() && reader.peek().match(restOfVariableMatch)) {
15        // add a character to the value as long as we match the variable name.
16        value += reader.peek();
17        reader.next();
18    }
19
20    // we return a variable token
21    return { type: 'name', value };
22}

Parentheses

This is an easy one. We detect ( or ) and return a different token based on what we detected.

1const readParentheses = reader => {
2    if (reader.peek() == '(') {
3        // We detected '(', start of parentheses
4        reader.next();
5        return { type: 'parenStart', value: '(' };
6    }
7
8    if (reader.peek() == ')') {
9        // We detected ')', end of parentheses
10        reader.next();
11        return { type: 'parenEnd', value: ')' };
12    }
13
14    // No token was detected.
15    return null;
16}

Code blocks

Another easy one. We detect { or } and return a different token based on what we detected.

1const readCodeBlocks = reader => {
2    if (reader.peek() == '{') {
3        // We detected '{', start of code block
4        reader.next();
5        return { type: 'codeBlockStart' };
6    }
7
8    if (reader.peek() == '}') {
9        // We detected '}', end of code block
10        reader.next();
11        return { type: 'codeBlockEnd' };
12    }
13
14    // No token was detected.
15    return null;
16}

End of line

Ah yes, the semicolon :). Fortunately, it is easy to detect this. We just detect a; character and move on.

1const readEndOfLine = reader => {
2    if (reader.peek() == ';') {
3        // Semicolon is detected
4        reader.next();
5        return { type: 'endOfLine', value: ';' };
6    }
7
8    // Semicolon is not detected
9    return null;
10}

Commas

Where would we use a comma? Well, we have a few places, function arguments for one. Similar to semicolons, we just detect the , character.

1const readComma = reader => {
2    if (reader.peek() == ',') {
3        // Comma was detected
4        reader.next();
5        return { type: 'comma', value: ',' };
6    }
7
8    // Token was not detected.
9    return null;
10}

Whitespace

And finally, the last token we detect is the whitespace. This token has the lowest priority because we do not want it being detected in front of something like strings which can also have whitespace characters. For us we will treat tabs, spaces, a new line character and carrier return character as whitespace.

Remember that in the reader loop above, we remove this token from the list after it is detected because we do not have a need for it.

1const readWhitespace = reader => {
2    const whitespaceRegex = /[\t\r\n ]/; // Regex for detecting whitespace.
3    let value = '';
4    while(reader.hasNext() && reader.peek().match(whitespaceRegex)) {
5        // add detected whitespace to the value
6        value += reader.peek();
7        reader.next();
8    }
9
10    if (value.length > 0) {
11        // Return detected whitespace.
12        return {type: 'whitespace', value};
13    }
14
15    // No whitespace token was detected.
16    return null;
17}

And our lexer is complete. Passing code to this lexer will result in a list of tokens we can use for parsing.

As a final thing, we will modify our main function a little bit into the following code:

1// Code which we want to parse
2const code = `variable = 5`;
3
4// Import the lexer
5const analyseCode = require('./lexer-analyser');
6
7// Run the lexer
8const tokens = analyseCode(code);
9
10// Should output the tokens
11console.log(tokens);

And as an output we will get the following:

1[
2  {
3    type: 'name',
4    value: 'variable',
5    start: 0,
6    end: 8,
7    line: 0,
8    character: 0
9  },
10  {
11    type: 'operator',
12    value: '=',
13    start: 9,
14    end: 10,
15    line: 0,
16    character: 9
17  },
18  {
19    type: 'number',
20    value: '5',
21    start: 11,
22    end: 12,
23    line: 0,
24    character: 11
25  }
26]

And this is a token set for assigning the number 5 to a variable named variable.

In the next part, we will continue by implementing a parser that parses these tokens.

If you followed the code from GitHub you can get to this point by switching to the branch part1-chapter2.