Writing an Interpreter: High-Level Overview

Creating a new language for specific logic is sometimes unavoidable. Some use cases can be listed out:

• We want to develop a highly dynamic application that enables non-technical business users and system admins to customize the system and its workflow by writing code. I aim to make the application highly configurable without the need for a complex user interface. This approach is commonly referred to as a domain-specific language (DSL).
• Code Generation and Automation: Building a custom language can facilitate code generation and automation for repetitive or complex tasks. By defining a language that closely matches the problem domain, developers can write code at a higher level of abstraction and generate boilerplate or repetitive code automatically.

This article aims to offer simple instructions on constructing an interpreter for a custom programming language.

Interpreter and Compiler

An interpreter is a software component or program that directly reads and executes code without prior compilation. It is often used with scripting languages and high-level programming languages. Notable interpreted languages include Python, JavaScript, and PHP.

In contrast, compilers take code as input and generate assembly or bytecode that requires a virtual machine for execution. Examples of compiled languages are C/C++, Java, C#, Go, and Rust.

Compiled languages tend to offer higher performance compared to interpreted ones because compilers perform extensive optimization during the compilation process.

Main Components

Lexer, Parser, and Evaluator

There are three main components of an interpreter:

• Lexer (or Tokenizer): responsible for breaking down the source code into individual tokens. It scans the code character by character and groups them into meaningful units such as keywords, identifiers, operators, literals, and symbols.
• Parser: takes the tokens produced by the lexer and analyzes their structure based on defined grammar or syntax rules. It ensures that the code follows the correct syntax and creates a data structure called an Abstract Syntax Tree (AST) or parse tree, which represents the hierarchical structure of the code.
• Evaluator: is responsible for executing the code and producing the desired results. It takes the parsed and analyzed code, such as an Abstract Syntax Tree (AST) or an intermediate representation, and performs the necessary computations and operations specified by the code

While advanced interpreters may include additional components like the Semantic Analyzer and IR Generator for the purpose of understanding how to write an interpreter, we won't discuss those specifics here.

Example

Given the code:

print 10 + 2;

The following logics will happen in components:

• Lexer breaks down the code and represents it as a list of token objects with type. In this example, there are 4 types: print, int number (10 and 2), plus, and semicolon.
• Parser iterates through the list of tokens to form a statement object. In this case, it's a PrintStatement with expression is an infix AST.
• The evaluator iterates through the list of statements getting from the Parser, evaluates them, and gives the final result. In this case, it's printing 12 to the console

Part 2: Implementation

Source code: Tholangforfun