Compiling higher-level languages
As you may have noticed, programming in assembly can be time-consuming and
error-prone, so to make programming easier higher-level languages have been de-
veloped. These languages abstract away the details of particular processors and al-
low for the expression of common operations in a more concise and comprehensible
manner. Typical early examples of higher-level programming languages are Fortran,
Cobol, Algol 60 and Lisp. These days C/C++, Java and Python are the most popular
languages. There are more than 1000 programming languages in existence and this
number is quickly growing.
The introduction of higher-level programming languages did not resolve the
problem that programming can be error-prone. Programs in higher-level languages
tend to become large and complicated as well, where systems consisting of hun-
dreds of millions of lines of code are no exception. To combat the ensuing com-
plexity, new domain-specific languages are developed that allow for more compact
descriptions of the desired behaviour of a computer by using knowledge of the ap-
plication domain. Classic examples are HTML (HyperText Markup Language [26])
for the design of web pages, SQL (Structured Query Language [14]) to query rela-
tional databases and BPEL (Business Processes Execution Language, [33]) to con-
nect business processes with web services.
Such higher-level and domain-specific languages need to be executed by a com-
puter. There are essentially two ways to do this. The first one is by using an in-
terpreter, which is a program that acts as a computer that can directly execute the
higher-level program. The other way is to use a compiler that translates the higher-
level program to the assembly code for a particular processor and have the proces-
sor execute this assembly code. Some languages use a mixture of a compiler and an
interpreter. In such cases the higher-level language is translated to an intermediate
language which is subsequently interpreted. For instance, programs in Java are often
compiled to Java byte code that is interpreted using the Java virtual machine.
The advantage of an interpreter is that it can execute a program without any
preprocessing step, which often is faster than if a program is changed, compiled and
run repeatedly. The advantage of using a compiler is that the compiled code runs
much faster than interpreted code.
In this chapter we show the essence of building a compiler. We provide a simple
programming language and we describe how to construct a compiler that trans-
lates programs in this language to the assembly code for our simple processor. An
interpreter can be built in a similar way, but instead of generating assembly code
instructions, the interpreter executes such instructions immediately.
A simple higher-level programming language
The language that we define consists of the primary language constructs of higher-
level languages. This is sufficient to understand the structure of a compiler. We will
briefly mention more complex language constructs, which generally require only
slight extensions to be compiled.
A program essentially consists of a number of variables that are manipulated. We
use variables of the types bool, nat and int as they all fit in a single 16-bit word. In
particular we use one whole word for each boolean, where true is represented by the
16-bit number 1 and false by the 16-bit number 0. The type nat contains the positive
numbers and int the two’s complement numbers. Each variable that is used must be
declared at the beginning of the program or at the beginning of a function in what is
called a declaration. Variables only have a local scope, which means that a value of
a variable declared in the main program can only be used in a function when passed
as a parameter.
The task of the main program is to repeatedly calculate new values for the vari-
ables until some desired end result is achieved. The parts of the program that express
how such manipulations take place are called program statements. The basic pro-
gramming statement is the assignment, often written as x := e meaning that variable
x obtains the value represented by the expression e. The type of x must be equal to
or compatible with that of e as otherwise the assignment cannot take place. An ex-
pression consists of variables and/or constants to which operations, and functions,
can be applied. A typical expression involving numbers is x + 1. The assignment
x := x + 1 means that the value in variable x is incremented by 1. Our simple pro-
gramming language has the operators plus (+), multiplication (*) and unary minus
(-) as the operations on numbers.
For expressions of type bool we write 0 and 1 for false and true. Numbers can
be compared using the ‘smaller than’ operator (<) and equality (==), yielding a
boolean. We restrict ourselves to a limited set of comparison operators, as the other
operations can be expressed using those given above, and therefore adding them is
not very instructive.
There are two operators used to combine boolean values, namely the unary oper-
ator not and the binary operator and. We also allow them to be used on numbers, in
which case it is the bitwise inversion and the bitwise and. There is no or operation,
as it can be expressed using the other operators.