Writing a simple Pascal interpreter in Swift

About a month ago I stumbled on a series of blog post called Let’s build a simple interpreter by Ruslan Spivak. In these blog posts the author write about building a simple interpreter for the Pascal programming language in Python. It is very well written and explained, I would even say that all the concepts are explained better than in the compiler course I took at the university.

In that class I had to write a Pascal compiler not interpreter in C++ and with tools like lex and yacc so I remembered most concepts but the interpreter is a bit different than a compiler and not using any external tools makes you think more about the problem.

Motivation

I felt a bit nostalgic and wanted to tackle an algorithmically challenging problem, especially because Pascal was my first programming language back in high school so I decided to follow along and write a simple Pascal interpreter in Swift, the language I switched to from C# nearly a year ago.

Swift is a different language than Python so I had to do many things differently, especially those where the Python implementation relayed on the dynamicity of the language.

But the biggest challenge was that the series ended before introducing function calling and the call stack so I had to come with a good way to do this. I also wanted to support recursion and basic loops and flow controls.

Goal

The goal was to be able to interpret a Pascal program like factorial computation or a simple number guessing game.

The project

I managed to achieve everything I wanted and my project was born, the Swift Pascal Interpreter, available on Github.

The interpreter is a framework that can be used with macOS and with some small changes also iOS. The Github project contains a command line utility for interpreting Pascal programs (as shown in the Gif above) and a Playground.

In the Playground you can try out all the parts independently; the Lexer that reads the programs as text and converts them into a stream of tokens, the Parser that reads the stream of tokens and a builds an abstract syntax tree of the program, the Semantic Analyzer that checks the abstract syntax tree and builds a symbols table and finally the Interpreter that executes the program. There is a complete explanation of the structure in the README file.

The current implementation supports arithmetic expressions, if statements with simple conditions, loops, variables, functions and procedures and even some standard Pascal function.

You can also access many useful extensions, like printing the abstract syntax tree of the program in a “graphic” representation. There are many things missing, like support for arrays and records or most of the default functions.

Lexer

The Lexer reads the Pascal program as String (a sequence of characters) and converts it into a sequence of Tokens. You can see the result by trying it our in the Playground or on the unit tests.

Parser

The Parser reads the sequence of tokens produced by the Lexer and builds an Abstract Syntax Tree representation (AST for short) of the Pascal program according to the grammar.

You can see what the AST looks like in the unit tests or in the Playground where you can also use the printTree() method on any AST to see its visual representation printed into the console.

Semantic analyzer

The Semantic analyzer does static semantic checks on the Pascal program AST. It currently checks if all the used variables are declared beforehand and if there are any duplicate declarations. The result of semantic analysis is a Symbol table that holds all the symbols used by a Pascal program, currently built in types (Integer, Real) and declared variable names.

Interpreter

The Interpreter reads the AST representing the Pascal program from Parser and interprets it by walking the AST recursively. It can handle basic Pascal programs.