Building something that executes code tends to follow very similar paths. On one side we gradually work from individual chars to increasingly meaningful representations of data, until we reach a peak. Where by we then go down the other side of the mountain, successively breaking it down until we have something we can execute.

Parts of a Language

Front-End

The Front-End is specific to the DSL (Domain Specific Language), its goal is to get the language from a series of chars into a data structure with meaning.

Scanning

Or Lexing or Lexical Analysis.

This is the process where we breakdown a stream of chars into meaningful chucks like words. Here we tend to ignore irrelevant chars like whitespace and comments.

We call these “words” Tokens.

Parsing

A Parser takes a flat set of tokens and assembles them into a tree structure.

We call this tree structure a Parse Tree, or an Abstract Syntax Tree or just AST.

When we mess up the syntax, the parser will let us know with a syntax error.

Static Analysis

The first stage is called binding or resolution. We find each identifier and map it to where it is defined. For example a + b we might know we are adding a and b but what do those names refer to. Globals or local vars? This is dependent on your specific language and its implementation.

We also will do type checking among other checks on the resulting data structure and throw errors accordingly.

So where do we store all the semantic insights?

1. Store it back into the attributes on the syntax tree

2. Store the data in a lookup table off to the side called a symbol table

3. ORRRR Transform the tree into a new data structure that directly expresses the semantics of the code

Middle End

This state focuses on maybe creating IR and then optimisation among other things that you may want to bolt in.

Interesting side note: Anything in the middle end is stuff that was not part of the traditional compilers, but tends to be found in modern compilers.

Intermediate representations

This stage is optional, but comes with many benefits. We convert the AST into a intermediate representation or IR examples include “three-address code” and “control flow graph”.

This comes with two benefits:

1. Your front end and back end become independent, allowing you to change what you compile to or even what language you parse. This makes changing what you compile to so easy and fast. This is how GCC and other are able to support so many targets.

2. You can optimise

Optimisation

There are many things you can do here (and for the project I am working on this is not really nessisary). But if you can’t resist poking your foot into that hole, some keywords to get you started are “constant propagation”, “common subexpression elimination”, “loop invariant code motion”, “global value numbering”, “strength reduction”, “scalar replacement of aggregates”, “dead code elimination”, and “loop unrolling”.

Back End

Concerned with the final architecture of how the code will run.

Code generation

In this stage we begin to generate code that the machine can understand. You have two options:

1. Generate for the specific architecture aka ARM or X86

2. Generate for a virtual CPU

Generating for a specific architecture can be a huge pain, but its fast. Where as generating for a virtual CPU will be slower, but will be at a level that is super generalisable. We call this generalisable code bytecode, or historically p-code for portable.

Language Virtual machine

If you do decide to use bytecode, then you must still translate it for the specific architecture. You can consider bytecode as a sort of IR.

You have two ways to make your bytecode run on a machine:

1. Create a language virtual machine in say C, this will execute line by line the bytecode. C is a great choice here because gcc supports many architectures

2. Create a mini-compiler for each target architecture, this still requires effort but it will be super fast, especially if you include architecture specific optimisations

Runtime

The runtime handles anything that needs managing while the application is running, such as garbage collection & reflection. In compiled languages the runtime is included in the executable, in interpreted languages the runtime lives in the interpreter.

Shortcuts

Single-pass compilers

They go line by line or by a very small window at a time, and directly translate the code into machine code. These compilers existed to solve an issue of their time, that the available memory was so low that sometimes the entire file could not be held in memory at a single time.

This all meant that what the window could see had to be enough information to convert it into machine code.

This explains limitations where some languages require certain ordering; such as in C, where you cannot call a function before you define it.

Tree-walk interpreters

Tree-walkers begin execution immediately after parsing (maybe with static analysis) into an AST. The interpreter then immediately starts walking the tree evaluating a node at a time. This works well for small projects, but is extremely slow.

Transpilers

These are compilers that maintain the front end; but exploit the back-end of other languages by creating source code for other compilers. So what you could do is generate say C and then use gcc to create the machine code. A good practical example for this is creating JS, since may browsers (before web assembly) could only execute JS, your compiler could create JS.

Just-in-time compilation

Likely the most complex form of compiler. This methodology is used when you do not know the architecture of the hosts machine. You create a platform independent bytecode, when the program executes you convert the bytecode to machine code just before you get to it and then execute it. As the program executes over a period of time, the compiler will recognise hotspots and optimise the machine code for them.

Compilers and Interpreters

• A compiler converts a source code into a target code machine code or otherwise

• An interpreter takes a source code and immediately executes it

It is common with some languages to convert into an IR then execute, thus we can have a compiler and an interpreter.