The Function and Purpose of Translators

4.2.1 Interpreters and Compilers

When electronic computers were first used, the programs had to be written in machine
code. This code was comprised of simple instructions each of which was represented by a
binary pattern in the computer. To produce these programs, programmers had to write the
instructions in binary. This not only took a long time, it was also prone to errors. To improve
program writing assembly languages were developed. Assembly languages allowed the use
of mnemonics and names for locations in memory. Each assembly instruction mapped to a
single machine instruction which meant that it was fairly easy to translate a program written
in assembly language to machine code. To speed up this translation process, assemblers
were written which could be loaded into the computer and then the computer could translate
the assembly language to machine code. Writing programs in assembly language, although
easier than using machine code, was still tedious and took a long time.

After assembly languages came high-level languages which used the type of language used
by the person writing the program. Thus FORTRAN (FORmula TRANslation) was developed
for science and engineering programs and it used formulae in the same way as would
scientists and engineers. COBOL (Common Business Oriented Language) was developed for
business applications. Programs written in these languages needed to be translated into
machine code. This led to the birth of compilers.

A compiler takes a program written in a high-level language and translates into an
equivalent program in machine code. Once this is done, the machine code version can be
loaded into the machine and run without any further help as it is complete in itself. The
high-level language version of the program is usually called the source code and the
resulting machine code program is called the object code. The relationship between them is
shown in Fig. 4.2.1.

Fig. 4.2.1

The problem with using a compiler is that it uses a lot of computer resources. It has to be
loaded in the computer's memory at the same time as the source code and there has to be
sufficient memory to hold the object code. Further, there has to be sufficient memory for
working storage while the translation is taking place. Another disadvantage is that when an
error in a program occurs it is difficult to pin-point its source in the original program.

An alternative system is to use interpretation. In this system each instruction is taken in
turn and translated to machine code. The instruction is then executed before the next
instruction is translated. This system was developed because early personal computers
lacked the power and memory needed for compilation. This method also has the advantage
of producing error messages as soon as an error is encountered. This means that the
instruction causing the problem can be easily identified. Against interpretation is the fact
that execution of a program is slow compared to that of a compiled program. This is
because the original program has to be translated every time it is executed. Also,
instructions inside a loop will have to be translated each time the loop is entered.

However, interpretation is very useful during program development as errors can be found
and corrected as soon as they are encountered. In fact many languages, such as Visual
Basic, use both an interpreter and a compiler. This enables the programmer to use the
interpreter during program development and, when the program is fully working, it can be
translated by the compiler into machine code. This machine code version can then be
distributed to users who do not have access to the original code.

Whether a compiler or interpreter is used, the translation from a high-level language to
machine code has to go through various stages and these are shown in Fig. 4.2.2.

Lexical Analysis

Syntax Analysis

Semantic Analysis

Code Generation

Code Optimisation

4.2.2 Lexical Analysis

The lexical analyser uses the source program as input and creates a stream of tokens for
the syntax analyser. Tokens are normally 16-bit unsigned integers. Each group of
characters is replaced by a token. Single characters, which have a meaning in their own
right, are replaced by their ASCII values. Multiple character tokens are represented by
integers greater than 255. Variable names will need to have extra information stored about
them. This is done by means of a symbol table. This table is used throughout compilation to
build up information about names used in the program. During lexical analysis only the
variable's name will be noted. It is during syntax and semantic analysis that details such as
the variable's type and scope are added. The lexical analyser may output some error
messages and diagnostics. For example, it will report errors such as illegal identifier or
identifier too long.

At various stages during compilation it will be necessary to look up details about the names
in the symbol table. This must be done efficiently so a linear search is not sufficiently fast.
In fact, it is usual to use a hash table and to calculate the position of a name by hashing the
name itself. When two names are hashed to the same address, a linked list can be used to
avoid the symbol table filling up.

The lexical analyser also removes redundant characters such as white space (spaces, tabs,
etc.) and comments. Often the lexical analysis takes longer than the other stages of
compilation. This is because it has to handle the original source code, which can have many
formats. For example, the following two pieces of code are equivalent although their format
is considerably different.

IF X = Y THEN 'square X IF X = Y THEN Z := X * X
Z := X * X ELSE Z := Y * Y
ELSE 'square Y PRINT Z
Z := Y *Y

When the lexical analyser has completed its task, the code will be in a standard format
which means that the syntax analyser can always expect the format of its input to be the
same. Consider the instructions

X := 54

the lexical analyser will turn this into paired tokens. The first part describes the token, if
necessary, and the second part defines what the token represents. Thus the above input is
turned into

Variable X
Assignment symbol
Integer 54
Return symbol
Variable X

4.2.3 Syntax Analysis

This Section should be read in conjunction with Section 4.5.11 which discusses Backus-Naur
Form (BNF) and syntax diagrams.

During this stage of compilation the code generated by the lexical analyser is parsed
(broken into small units) to check that it is grammatically correct. All languages have rules
of grammar and computer languages are no exception. The grammar of programming
languages is defined by means of BNF notation or syntax diagrams. It is against these rules
that the code has to be checked.

For example, taking a very elementary language, an assignment statement may be defined
to be of the form

<variable> <assignment_operator> <expression>

and expression is

<variable> <arithmetic_operator> <variable>

and the parser must take the output from the lexical analyser and check that it is of this

If the statement is

sum := sum + number

the parser will receive

<variable> <assignment_operator> <variable> <arithmetic_operator> <variable>

which becomes

<variable> <assignment_operator> <expression>

and then

<assignment statement>

which is valid.

If the original statement is

sum := sum + + number

this will be input as

<variable> <assignment_operator> <variable> <arithmetic_operator>
<arithmetic_operator> <variable>

and this does not represent a valid statement hence an error message will be returned.

It is at this stage that invalid names can be found such as PRIT instead of PRINT as PRIT will
be read as a variable name instead of a reserved word. This will mean that the statement
containing PRIT will not parse to a valid statement. Note that in languages that require
variables to be declared before being used, the lexical analyser may pick up this error
because PRIT has not been declared as a variable and so is not in the symbol table.

Most compilers will report errors found during syntax analysis as soon as they are found
and will attempt to show where the error has occurred. However, they may not be very
accurate in their conclusions nor may the error message be very clear.

During syntax analysis certain semantic checks are carried out. These include label checks,
flow of control checks and declaration checks.

Some languages allow GOTO statements (not recommended by the authors) which allow
control to be passed, unconditionally, to another statement which has a label. The GOTO
statement specifies the label to which the control must pass. The compiler must check that
such a label exists.

Certain control constructs can only be placed in certain parts of a program. For example in
C (and C++) the CONTINUE statement can only be placed inside a loop and the BREAK
statement can only be placed inside a loop or SWITCH statement. The compiler must ensure
that statements like these are used in the correct place.

Many languages insist on the programmer declaring variables and their types. It is at this
stage that the compiler verifies that all variables have been properly declared and that they
are used correctly.
4.2.4 Code Generation

It is at this stage, when all the errors due to incorrect use of the language have been
removed, that the program is translated into code suitable for use by the computer's

During lexical and syntax analysis a table of variables has been built up which includes
details of the variable name, its type and the block in which it is valid. The address of the
variable is now calculated and stored in the symbol table. This is done as soon as the
variable is encountered during code generation.

Before the final code can be generated, an intermediate code is produced. This intermediate
code can then be interpreted or translated into machine code. In the latter case, the code
can be saved and distributed as an executable program. Two methods can be used to
represent the high-level language in machine code. The one uses a tree structure and the
other a three address code (TAC). TAC allows no more than three operands and instructions
take the form

Operand1 := Operand2 Operator Operand3

For example, using three address code, the assignment statement

A := (B + C) * (D – E) / F

can be evaluated in the following order, where Ri represents an intermediate result.

R1 := B + C

R2 := D – E

R3 := R1 * R2

A := R3 / F

This can also be represented by the tree shown in Fig.


Other statements can be represented in similar ways and the final stage of compilation can
then take place.

The compiler has to consider, at this point, the type of code that is required. Code can be
optimised for speed of execution or for size of program. Often compilers try to compromise
between the two.

An example of code optimisation is shown in Fig. where the code on the left has
been changed to that on the right so that r1 * b is only evaluated once.

a := 5+ 3 a := 5 + 3
b := 5 * 3 b := 5 * 3
r1 := a + b r1 := a + b
r2 := r1 * b r2 := r1 * b
r3 := r2 / a r3 := r2 / a
r4 := r1 - b r4 := r2
r5 := r4 + 6 r5 := r4 + 6
c := r3 – r5 c := r3 – r5


However, care must be taken when doing this as it does not work in the case shown in Fig. because the value of b changes between the two evaluations of r1 * b. Hence the
code on the right is not equivalent to that on the left.

a := 5+ 3 a := 5 + 3
b := 5 * 3 b := 5 * 3
r1 := a + b r1 := a + b
r2 := r1 * b r2 := r1 * b
r3 := r2 / a r3 := r2 / a
b := b + 2 b := b + 2
r4 := r1 - b r4 := r2
r5 := r4 + 6 r5 := r4 + 6
c := r3 – r5 c := r3 – r5


In the first example we have, in the revised code, the copy statement r4 := r2. This means
that r4 and r2 represent the same value and hence one of them can be removed. This leads
to the code in Fig.

a := 5 + 3
b := 5 * 3
r1 := a + b
r2 := r1 - b
r3 := r2 / a
b := b + 2
r5 := r2 + 6
c := r3 – r5


Another way of optimising code is to use algebraic transformations. For example, the

a := b * 1

can be replaced by the statement

a := b


a := b + 0


a := b

There are many other ways of optimising code but they are beyond that expected at this

4.2.5 Linkers and Loaders

Programs are usually built up in modules. These modules are then compiled into machine
code that has to be loaded into the computer's memory. This process is done by the loader.
The loader decides where in memory to place the code and then adjusts memory addresses
as described in Chapter 4.1. As the whole program may consist of many modules, all of
which have been separately compiled, the modules will have to be correctly linked once
they have been loaded. This is the job of the linker. The linker calculates the addresses of
the separate pieces that make up the whole program and then links these pieces so that all
the modules can interact with one another.

The idea of using modules that can be used in many programs was explained in Section
1.3.2. This method of creating programs is important as it reduces the need to keep
rewriting code and will be further discussed under object oriented programming in Section
4.2.6 Example Questions.

1. Explain why the size of the memory available is particularly relevant to the process of
compilation. (4)

A. The computer must be able to simultaneously hold in memory:
-The compiler software/without which the process cannot be carried out.
-The source code/the code that needs to be compiled
-The object code/because the compilation process produces the program in machine code
-Working space/processing area to be used by the compiler during the process.
Notes: This question is trying to make the candidate think about the implications of the
creation of a machine code version of the high-level language program. The significance of
the size of the memory is not as significant as it used to be because the memory in a micro
is now large enough for the problem not to arise in the main, but in the past the compilation
of programs could cause trouble on a micro leading to the standard translation technique of

2. a) Explain the difference between the two translation techniques of interpretation and
compilation. (2)

b) Give one advantage of the use of each of the two translation techniques. (2)

A.a) -Interpretation involves the translation of an instruction and the execution of that
instruction before the translation of the next.
-The compilation of a program involves creating the machine code version of the program
before allowing any of it to be run. (2)

b) -Interpretation provides the programmer with better error diagnostics because the
source code is always present and hence can be used to provide a reference whenever the
error occurs.
-When a program is compiled no further translation is necessary no matter how many
times the program is run, consequently there is nothing to slow down the execution of the
program. (2)

Notes: The question is probably not in its best form as there are many responses that could
justifiably be given to the difference between the two processes. A perfectly acceptable
response here would be that interpretation does not create an object code while compilation

3. State the three stages of compilation and describe, briefly, the purpose of each. (6)
A. -Lexical analysis
-puts each statement into the form best suited to the syntax analyser.

-Syntax analysis
-Language statements are checked against the rules of the language.

-Code generation
-The machine code (object code) is produced. (6)

Notes: The number of marks for the question plays a big part in this answer. There are
only six marks, three of which must be for stating the three stages. This means that there is
only one mark each for saying what the purpose of each is. Do not launch into a long essay,
you don’t have time in the constraints of the examination room, the examiner is simply
looking for an outline description of what the stage does. Be careful about writing down all
you know about each stage. There is a danger that the first thing you write down may be
wrong. There is only one mark available and, if the answer is very long, the mark will be
lost immediately. Also, don’t think that the marks can be carried across from another part.
You may not know anything about code generation, but you do know a lot about lexical
analysis – sorry, the marks cannot be transferred over in a question like this.

4. Explain, in detail, the stage of compilation known as lexical analysis. (6)

A. -Source program is used as the input
-Tokens are created from the individual characters and from…
-the special reserved words in the program.
-A token is a string of binary digits.
-Variable names are loaded into a look up table known as the symbol table
-Redundant characters (e.g. spaces) are removed
-Comments are removed
-Error diagnostics are issued. (6)

Notes: Compare this question with the last one. This one is asking for the details, so it
becomes important to say as much as possible. The examiner may be a little more lenient
about something in a student’s list that is wrong, but only a little! After all, the main thing
about the stages of compilation is to know when each of them is appropriate, so don’t make
too many errors.