** This post is a work-in-progress. Same with the code implementation.**
<a href="https://github.com/Uzoamaka126/lox-js">Link to Github</a>
To build a programming language that feels natural and intuitive, certain things have to be taken into consideration, including working around abstractions. I'm 100 pages into Robert Nystrom's book, Crafting Interpreters, where he offers really good insight on interpreters, compilers and language implementation as a whole. It's quite detailed and a great exercise to get into if you are interested in learning how programming languages work.
Lox, the language used in this book, is a small-scale, dynamically-typed scripting language with a syntax similar to C. The book is split into two parts: implementing Java and C interpreters. Since my knowledge of either language is close to nil at best, I opted to build this interpreter with JavaScript.
<h4>Intro</h4>
When we run a program, even one as simple as "Hello world!", the execution process is divided into several phases. Each phase operates like a pipeline; returning a different representation of the source code before passing it to the next phase, until the representation is (or close to) machine code.
In typical language processing, the final phase generates machine code, a low-level set of instructions, far less readable for humans, but a virtual or real-time CPU can execute. With this interpreter, some phases are skipped in favour of a simpler process; scanning, parsing and evaluating the code. The scanner takes the source code as a series of characters, and outputs a sequence of tokens. The parser then constructs a tree-like structure from these tokens, using grammar rules to ensure validity of the tokens.
An interesting aspect highlighted in the book is the concept of a shared intermediate representation (IR) for reusability. Basically, an IR is a data structure used further down the line to represent and optimize source code without being too tightly coupled with the source or destination language. The reusability function of shared IRs means that support can exist for the translation of multiple languages without having to write a new data structure for each one after parsing has occurred.
Built as a tree-walk interpreter, the Lox interpreter walks (or traverses) an Abstract Syntax Tree (AST), returned when the parser processes the scanned tokens.
<h4>Error handling</h4>
Error handling is high up on the list of things to consider when building a good programming language. A good error handling mechanism goes a long way. In the event of an error, it's not just enough to indicate that an error has occurred, users of the language also need additional context like what line the error occurred, what type of error...etc
The code contains a separate error class that can be referenced externally to handle all errors. The error class extends the standard built-in JavaScript Error class, and has its own custom functionality; a private boolean variable for tracking the occurrence of an error and a static method for reporting errors. When called, the report method logs the error line and message to the terminal before internally updating the private boolean variable to true.
<pre><code>LoxError.js
 class LoxError extends Error {
 static hadError = false;

 constructor(token, message) {
 super(`${token.line}: '${token.lexeme}' ${message}`)
 this.name = 'LoxError: '
 }

 static setError(boolValue) {
 this.hadError = boolValue;
 }

 static report(line, where = "", message = "") {
 console.log('\x1b[34m%s\x1b[0m', "[line " + line + "] Error" + where + ": " + message);
 this.setError(true);
 }
}
</code></pre>
<h4>Tokens</h4>
The process of identifying and classifying lexemes is called lexical analysis or tokenization. [Lexemes are distinctly different from characters. Characters make up the source code while lexemes consist of one or more characters representing a single token]. During the lexical analysis phase, characters are grouped into several categories like, single characters, new lines, whitespaces, keywords, identifiers, comments, ...etc. Typically, white spaces and comments get ignored or discarded, while characters that are unrecognizable by the scanner get returned as an error.
To represent and group various lexemes, we are going to create a Token class to group and output the desired token and an enum that houses a list of all the various ways lexemes can be grouped.
*See full list of enum <a href="https://github.com/Uzoamaka126/lox-js/blob/main/src/TokenType.js">here</a>
<pre><code>Token.js

class Token {
 static type; // enum
 static lexemme; //string
 static literal; // object
 static line; // number

 constructor(type, lexeme, literal, line) {
 this.type = type;
 this.lexemme = lexeme;
 this.literal = literal;
 this.line = line;
 }

 toString() {
 return this.type + " " + this.lexemme + " " + this.literal;
 }
}
</code></pre>
<h4>Writing the scanner</h4>
We are going to create a scanner class with the following: a string variable to hold the raw source code, a default empty array to hold the result tokens, two integer variables, "start" and "current" to keep track of the starting and current points in the loop. On each iteration, we take the current character, group it with its relative lexeme and emit a token based on that grouping. The goal of the scanning phase is to return a different representation as tokens.
<pre><code>Scanner.js
 class Scanner {
 #SOURCE = ""; // raw source code as a string
 #TOKENS = []; // a default empty list to add generated tokens to
 #start = 0; // points to the first character being scanned
 #current = 0; // points to the character in the current iteration
 #line = 1; // tracks what source line "current" character is on 

 constructor(source = "") {
 this.#SOURCE = source;
 }

 ...
 }
</code></pre>
The Scanner class contains a "scanTokens" method, which calls a different private method "scanToken" during iteration. Inside the "scanTokens" method block, once the loop ends, we append a final "end-of-file" token to help make the parser cleaner and then we return a list of tokens.
<pre><code>Scanner.js
 ...
 scanTokens() {
 while(!this.isAtEnd()) {
 this.#start = this.#current;
 this.#scanToken();
 }

 this.#TOKENS.push(new Token(TOKEN_TYPE.EOF, "", null, this.#line));
 return this.#TOKENS;
 }

 isAtEnd() {
 return this.#current >= this.#SOURCE.length;
 }
</code></pre>
On each iteration, the private "scanToken" method checks to see what token type the current character falls under. If the character doesn't fit into any of the existing groups, we can report an error without interrupting the loop. We make use of two helper methods; 1) an "advance" method that consumes the next character in the source string and returns it 2) an "addToken" method that grabs the text of the current lexeme, outputs a new token from it before pushing to the tokens array we created earlier.
Inside the default block, we check for digits and alphanumeric values to group them accordingly or we handle unrecognized characters by calling the error class we created earlier.
<pre><code>Scanner.js
 #scanToken() {
 const c = this.#advance();

 switch (c) {
 // single character
 case "(": this.#addToken(TOKEN_TYPE.LEFT_PAREN); break;
 case ")": this.#addToken(TOKEN_TYPE.RIGHT_PAREN); break;
 case "{": this.#addToken(TOKEN_TYPE.LEFT_BRACE); break;
 case "}": this.#addToken(TOKEN_TYPE.RIGHT_BRACE); break;
 case ",": this.#addToken(TOKEN_TYPE.COMMA); break;
 case ".": this.#addToken(TOKEN_TYPE.DOT); break;
 case "-": this.#addToken(TOKEN_TYPE.MINUS); break;
 case "+": this.#addToken(TOKEN_TYPE.PLUS); break;
 case ";": this.#addToken(TOKEN_TYPE.SEMICOLON); break;
 case "*": this.#addToken(TOKEN_TYPE.STAR); break;

 // second character
 case "!": this.#addToken(this.#match("=") ? TOKEN_TYPE.BANG_EQUAL : TOKEN_TYPE.BANG); break;
 case "=": this.#addToken(this.#match("=") ? TOKEN_TYPE.EQUAL_EQUAL : TOKEN_TYPE.EQUAL); break;
 case "&#x3C;": this.#addToken(this.#match("=") ? TOKEN_TYPE.LESS_EQUAL : TOKEN_TYPE.LESS); break;
 case ">": this.#addToken(this.#match("=") ? TOKEN_TYPE.GREATER_EQUAL : TOKEN_TYPE.GREATER); break;

 case "/": 
 if (this.#match("/")) {
 while (this.#peek() != '\n' &#x26;&#x26; !this.isAtEnd()) this.#advance();
 } else {
 this.#addToken(TOKEN_TYPE.SLASH);
 }
 break;

 case " ": 
 case "\r": 
 case "\t": 
 break;
 
 case "\n": 
 this.#line++;
 break;
 
 case '""': 
 this.#string();
 break;

 default:
 if (this.#isDigit(c)) {
 this.#number();
 } else if (this.#isAlpha(c)) {
 this.#identifier();
 } else {
 LoxError.report(this.#line, "", "Unexpected character.")
 }
 break;
 }
 }

 #advance() {
 this.#current++;
 return this.#SOURCE.charAt(this.#current - 1);
 }

 #match(expected = "") {
 if (this.isAtEnd()) return false;
 
 if (this.#SOURCE.charAt(this.#current) != expected) return false;

 this.#current++;
 return true;
 }
</code></pre>
<h4>Writing the parser</h4>
Parsers make use of grammar production rules to convert a sequence of tokens into a different representation: a Parse Tree or an Abstract Syntax Tree (AST). To create new representations, we make use of formal grammars instead of regular grammars.
Formal grammars specify production rules that describe how to form valid strings in a language. These rules define things like the structure of expressions, statements and program constructs, allowing the language to be parsed and understood by an interpreter or compiler. They also closely resemble regular expressions.
For example: given grammar G, where G = {(S,A) (a,b) (S → aAb, A → aAb | ϵ)}, generate an equal number of "a's and b's", with the production rules P defined below:
<pre><code> 𝑆 → aAb
 A → aAb | ϵ

 S is the start symbol.
</code></pre>
Starting with 'S', we apply the production rule S → aAb once, then recursively apply A → aAb, exactly n-1 times. To maintain a balance, on every iteration, we add a single "a" at the start and "b" at the end of the string. Then finally, we apply the rule A → ϵ (where ϵ = an empty string) to terminate the recursion. This gives us the result below:
<pre><code> S → aAb
 → aaAbb (where A → aAb )
 → aaaAbbb
 → aaabbb (where A → ϵ)
 → a³b³
</code></pre>
Our parser is going to make use of the grammar below to translate the rules to code:
<pre><code> expression → literal | unary | binary | grouping ;
 literal → NUMBER | STRING | "true" | "false" | "nil" ;
 grouping → "(" expression ")" ;
 unary → ( "-" | "!" ) expression ;
 binary → expression operator expression ;
 operator → "==" | "!=" | "&#x3C;" | "&#x3C;=" | ">" | ">=" | "+" | "-" | "*" | "/" ;
</code></pre>
When parsing, certain things have to be taken into consideration, like the validity of the sequence of tokens or precedence of the grammar rules being applied. This means we have to determine the order the operators are evaluated, especially if an input has multiple operators. Operators with higher precedence will get evaluated before their lower counterparts.
For example, the expression 6 / 3 - 1 * 4 gets parsed as (- (/ 6 3) (* 1 4))
We're going to create a Parser class with a parse method that kickstarts the entire parsing operation. Our Parser class uses an array to store the list of tokens received and an integer variable, "current" to track the next token to be parsed. For each grammar rule defined above, we are going to create an equivalent method that outputs a different expression before calling the next method.
We use the "recursive descent" parsing technique to translate our grammar rules into code. Also called a "top-down" technique, this technique parses from the outermost grammar rule, moves to nested subexpressions before finally moving to the bottom part of the tree. It is able to do this by recursively calling itself until the entire process is done.
<pre><code>class Parser {
 current = 0;
 tokens = [];

 constructor(tokens = []) {
 // validation
 if (!Array.isArray(tokens)) {
 throw new TypeError('Tokens must be an array');
 }
 this.tokens = tokens;
 }

 parse() {
 try {
 return this.expression() 
 } catch (error) {
 return null
 }
 }
 ...
}
</code></pre>
I've also created a class to help with traversing and printing the expression tree. In the AstPrinter class, we try to mimic a similar functionality to the visitor pattern implementation in Java. We use a base Expr class which other expression sub-classes inherit from, mimic the visitor pattern through the accept method, and finally creating an AstPrinter class that invokes methods defined on the other sub-classes. See the example below:
<pre><code>// Base expression class
class Expr {
 accept(visitor) {
 throw new Error("accept() not implemented");
 }
}

class Binary extends Expr {
 constructor(left, operator, right) {
 super();
 this.left = left;
 this.operator = operator;
 this.right = right;
 }

 accept(visitor) {
 return visitor.visitBinaryExpr(this);
 }
}

class Literal extends Expr {
 constructor(value) {
 super();
 this.value = value;
 }

 accept(visitor) {
 return visitor.visitLiteralExpr(this);
 }
}

</code></pre>
The rest of the code can be found <a href="https://github.com/Uzoamaka126/lox-js/blob/main/src/AstPrinter.js">here</a>.
<h4>Error reporting for the parser</h4>
While parsers take in a valid sequence of tokens, there might be instances where invalid tokens get passed in. When this happens, our parser should be able to detect and notify the user without interrupting the system. We use an error method to handle this:
<pre><code> error(token, message) {
 // LoxError.error(token, message);

 if (token.type === TOKEN_TYPE.EOF) {
 throw new SyntaxError(`Invalid or unexpected token, at end, ${message}`);
 } else {
 throw new SyntaxError(`Invalid or unexpected token ${token.lexemme}, at line ${token.line}, ${message}`);
 }
}
</code></pre>
*The LoxError.error part is intentionally commented out. In a future refactor, the system will make use of the central error reporting class to report all errors.
<h4>Wiring up the interpreter</h4>
<h3>Notes</h3>
Here are some resources I found helpful:
<ol>
<li><a href="https://pgrandinetti.github.io/compilers/page/what-is-a-programming-language-parser/">What is a Programming Language Parser?</a>,</li>
<li><a href="https://en.wikipedia.org/wiki/Separation_of_concerns">Separation of concerns</a></li>
<li><a href="https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools">Compilers, Principles, Techniques, and Tools</a></li>
<li><a href="https://www.youtube.com/watch?v=U8SXIlCTLuk">YT video on Grammars</a></li>
<li><a href="https://en.wikipedia.org/wiki/Control-flow_graph#:~:text=In%20computer%20science%2C%20a%20control,matrices%20for%20flow%20analysis%20before">Control Flow Graph</a></li>
</ol>

Building a Lox interpreter with JavaScript; An exercise from Robert Nystrom's Crafting Interpreters