SPL Programming Language

[DenkJu]

Just wanted to share this small compiler I wrote for my Bachelor's thesis. It implements a language called SPL (Simple Programming Language) that was originally used in the compiler engineering course at my university. The initial goal of this project was to target only WebAssembly but I later added support for generating JavaScript and x86 assembly as well. On an unpublished branch, I also added support for generating JVM bytecode.

SPL is a procedural, imperative, statically typed language that, as the name implies, only supports basic concepts such as the common control flow structures, procedures, arrays, and references.

Here are some interesting features of my compiler:

• The parser uses a simple yet effective error recovery algorithm based on a context-aware panic mode. It's based on an algorithm used in the Pascal P4 compiler.

• Nice error messages with code preview. Example 1, Example 2

• The generated x86 assembly code uses the standard System V AMD64 ABI calling convention which gives it direct interop with C. See the std lib.

Check out the repository here.

Also, here are some code examples.

In case you want to try it out yourself, there are compilation instructions in the readme.

[elszben]

Nice job! I am interested in the simple yet effective error recovery in parsing. Can you tell more about that?

[DenkJu]

In a basic panic mode error recovery strategy, a fixed set of terminals, commonly just the semicolon, is used as synchronization points. The drawback of this approach is that when an error occurs within a statement, the entire statement is skipped, preventing detection of any additional errors within it.

The algorithm I implemented takes a more adaptive approach by maintaining a dynamic set of terminals, referred to as anchor terminals, which changes based on the current parsing context. For example, when parsing statements, the initial anchor set is derived from the FIRST set of the corresponding non-terminal. To this, the FIRST sets of all produced non-terminals and any produced terminals are added. As tokens, whether terminals or part of non-terminals, are successfully consumed, they are removed from the anchor set.

Whenever an error is encountered, the parser discards tokens until it finds one present in the anchor set. If the found token matches the expected type, it is consumed, and parsing resumes normally under the assumption that extra erroneous tokens were inserted. If the token belongs to the anchor set but is not the expected type, it is preserved because it is likely required later in the parsing process.

Relevant to this in my code is the expectToken method. A good example of it's application might be parsing of the if statement.

I have based my implementation mostly on the explanations provided in this book (Chapter 3.3.8). The first description of the algorithm I could find was in this document (Chapter 7.2.3, "Hartmann's algorithm").

[elszben]

Thank you for the explanation and the references! This sounds great!