Translation Software

A compiler translates the whole program into object code before it runs. An interpreter never produces a translated program. Instead, it translates and runs the source code one statement at a time:

1. Read the next statement of the source code.
2. Check it for errors and translate it.
3. Run it straight away.
4. Go back to step 1, until the program ends. If a statement has an error, the interpreter stops there and reports it.

Nothing is saved, so the program is translated again every time it runs, and a statement inside a loop is translated every time round the loop. The interpreter must be on the computer that runs the program.

The compilation process is a set of stages that turns source code into executable object code. The programmer first creates the source code, and then the compiler takes it through four stages in order:

Note In the exam, Cambridge names the stages as lexical analysis, syntax analysis, code generation and optimisation, so learn optimisation as a stage. In practice, code can be optimised at every stage, and most of all during code generation.

Lexical analysis is the first stage in the process of compilation. All unnecessary characters that the compiler does not need, such as white space and comments, are removed.

Here is a small program before and after the unnecessary characters have been removed.

Source program

// My addition program Version 2
DECLARE x, y, z : INTEGER
OUTPUT "Please enter two numbers to add together" INPUT x, y
z=x+ y
OUTPUT "Answer is ", z

Source program after unnecessary characters have been removed (the comment line has gone)

DECLARE x, y, z : INTEGER
OUTPUT "Please enter two numbers to add together" INPUT x, y
z=x+ y
OUTPUT "Answer is ", z

Before translation, the source program must be converted to tokens. This process is called tokenisation. To tokenise the program, the compiler uses a keyword table that holds the tokens for all the reserved words and symbols of the programming language. In this example, every token is written as two hexadecimal digits.

The keyword table stores all the reserved words and symbols that can be used in the language. The term fixed symbol table can also be used for the symbols stored. Every program being compiled uses the same keyword table. Part of a keyword table could look like this:

During lexical analysis, the variables, constants and other identifiers used in the program are also added to a symbol table. The symbol table is made during compilation specially for that one program. Part of the symbol table for the program above could be:

The output from lexical analysis is a tokenised list, stored in main memory. This is the output for the first three lines of the program:

31 81 04 82 04 83 03 32 34 84 33 81 04 82 83 01 81 02 82

Syntax analysis is the compilation stage that comes straight after lexical analysis. Once tokens have been given to the code elements, the compiler checks that the tokens are in the correct order and that they follow the rules of the programming language.

In Python, the command print(user_name) is syntactically correct because it follows the rules for a print statement:

1. print in lower case
2. immediately followed by a left-hand bracket
3. followed by an identifier
4. closed by a right-hand bracket

Natural languages like English work the same way. The sentence “he Moved wearily” breaks three syntax rules. A sentence must:

1. start with a capital letter
2. continue in lower case letters
3. end with a full stop

The syntax rules of a programming language are limited, but they must be followed.

During syntax analysis, an abstract syntax tree (AST) is created. It maps the structure of the program, first dropping the brackets, semicolons and so on that the programmer used. If required tokens are missing from the tree, or are in the wrong place, the compiler reports an error.

Every language produces a different AST, depending on its syntax. Below is a general example of an AST for this small piece of pseudocode:

a = 5
b = a + 2

So far, lexical analysis has checked whether the tokens in the program are valid, and syntax analysis has checked whether the tokens are used according to the rules of the language. Another stage, semantic analysis, checks whether what has been written actually has a meaning within the language.

Suppose you are writing rules for grammatically correct English sentences. One rule for a valid sentence could be:

<pronoun> <verb> <plural noun>

So “I eat crackers” and “They play video games” are valid sentences. But a computer that only uses syntax analysis would also accept “You swim cats” and “We bite movies”, even though these make no sense in English.

Semantic analysis checks whether the code is valid within a given context. In this pseudocode, every token is valid and the assignment statement is formatted correctly:

DECLARE Total : INTEGER
Total ← "Karachi"

However, line 2 gives a semantic error when the program is compiled, because assigning a string value to an identifier that has been declared as an integer is not valid.

Here is another example, in Python:

fruit = ["apple", "peach", "pear"]
print(fruit[4])

This code gives no error at the lexical analysis stage, because all the tokens are valid in the language. It gives no error at the syntax analysis stage, because the list declaration and the print statement are correctly formed. But it has a semantic error: index 4 is out of bounds for the fruit list. Python only reports this when the program runs, as below, but a compiler could flag it during semantic analysis.

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(fruit[4])
          ~~~~~^^^
IndexError: list index out of range

Semantic analysis flags errors that do not make sense in the context the code is used in.

Code generation comes after lexical analysis, syntax analysis and semantic analysis. A separate program is created, distinct from the original source code. The generated code is a binary representation of the source code, known as object code. It is the executable version of the code, before linked libraries are included.

Here is a “Hello World” program in Python:

print("hello world")

When this code is built, an executable file is generated. The executable file is a binary file meant to be read by the computer. If you open it in a text editor, it makes no sense: the editor has turned the binary into characters because it assumes the file holds text, which it does not.

Code optimisation happens throughout the compilation process, and most of all during the code generation stage. The optimiser may find redundant or repeated code, and remove or rearrange it as needed.

Note Exam wording: the purpose of optimisation is to make the program more efficient, by reducing its execution time and the memory it needs.

This pseudocode displays the nine times table:

FOR Number ← 1 TO 12
    Multiplier ← 9
    Result ← Number * Multiplier
    OUTPUT Result
NEXT Number

This code is inefficient because Multiplier is assigned the value 9 inside the loop, so the assignment happens twelve times. The value never changes, so the optimiser moves the statement to before the loop:

Multiplier ← 9
FOR Number ← 1 TO 12
    Result ← Number * Multiplier
    OUTPUT Result
NEXT Number

Here is another piece of code that the compiler would optimise:

FUNCTION DoubleIt(Num : INTEGER) RETURNS INTEGER
    DECLARE Result : INTEGER
    Result ← Num * 2
    RETURN Result
    OUTPUT "The number doubled is ", Result
ENDFUNCTION

The OUTPUT statement is dead code, because it can never be executed. As soon as the function reaches the RETURN statement, it stops, and the program goes back to the place the function was called from. The optimiser can remove dead code.

Backus-Naur Form is used to describe a class of languages called context-free languages. The diagram shows how they fit inside the set of all languages.

Most programming languages can be defined as context-free languages. To define the set of strings in a particular context-free language, you use a context-free grammar: a set of production rules that describe all the possible strings in that language. One example of a context-free grammar is Backus-Naur Form.

Backus-Naur Form (BNF) is a context-free grammar that developers of programming languages often use to set out the syntax rules of a language. John Backus was a programming language designer who created a notation to document IAL (an early version of Algol). Peter Naur later worked on Backus’ ideas, and the notation is credited to both computer scientists.

BNF uses a set of symbols to write production rules. A simple BNF production rule looks like this:

<digit> ::= 0|1|2|3|4|5|6|7|8|9

This means: a digit can be defined as 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9.

The chevrons < > mark a non-terminal symbol. If a non-terminal symbol appears on the right side of a production rule, there will be another production rule (or set of rules) that defines what it can be replaced by. Look at this rule:

<fullname> ::= <title><name><name>

This shows that a full name is made of a title, a name and another name. All three parts are non-terminal, so more production rules are needed. For example, a rule could define title:

<title> ::= Mr|Mrs|Ms|Miss|Dr

In this rule, Mr, Mrs, Ms, Miss and Dr are terminal symbols. They are not in chevrons, so they are the actual values allowed for a title. The pipe symbol | is a metacharacter that separates alternatives. Each production rule is applied strictly: you may know that other titles exist, such as Lord, but only the production rule decides what is valid in this formal language.

The production rules for something as complex as a whole programming language form a very large set of BNF statements that set out how every part of the language is defined. Whenever a non-terminal symbol appears on the right side of a production rule, there should be another rule with that symbol on the left side. This goes on until everything is defined in terms of terminal symbols.

Here is a complete set of rules for a small part of a programming language:

<addition> ::= <number>+<number>
<number>   ::= <sign><integer>|<integer>
<integer>  ::= <digit>|<digit><integer>
<digit>    ::= 0|1|2|3|4|5|6|7|8|9
<sign>     ::= +|-

The terminal symbols are the digits 0 to 9 and the plus and minus signs. The plus sign appears twice: once as an operator and once as the sign of a number. So a valid addition can have a double plus sign, for example 23++6.

Recursion is used in BNF to write production rules for “one or more” of a symbol. For example, a number can be made of one or more digits. You might start by writing an ordinary production rule:

<number> ::= <digit>|<digit><digit>|<digit><digit><digit>|...

But where would you stop? How many digits can a number have? Recursion gives a neat solution:

<number> ::= <digit>|<digit><number>
<digit>  ::= 0|1|2|3|4|5|6|7|8|9

Notice how you go back to the rule, taking each symbol one at a time, until the symbols run out (or you meet a symbol that means the rule cannot be satisfied).

This recursive production rule has a base case (a single digit) and a general case (a digit followed by a number). The general case uses the recursive definition. The problem gets smaller and smaller until it reaches the base case: is 234 a number? Is 34 a number? Is 4 a number?

Note In BNF, recursion is the only way to show “one or more” or a loop.

A parse tree is a useful way to check whether a string satisfies a set of production rules. Parsing means breaking something down into its parts. Here are the production rules from before:

<addition> ::= <number>+<number>
<number>   ::= <sign><integer>|<integer>
<integer>  ::= <digit>|<digit><integer>
<digit>    ::= 0|1|2|3|4|5|6|7|8|9
<sign>     ::= +|-

As well as BNF, you can use a diagram that mirrors the formal grammar: a syntax diagram. When no key is given, you must be able to recognise the terminal and non-terminal symbols yourself. Here is a syntax diagram for this production rule:

<special> ::= @|?|&|*

By following any one of the lines, you get a character that is a valid special. The alternatives are stacked under each other, and you can pick any of them as you follow the line through the diagram from start to end.

Now a more complex rule:

<date> ::= <day-name><month-name>|<day-name><month-name><year>

This can be drawn as syntax diagrams like this:

Year is optional, as the production rule says. Syntax diagrams are always read from left to right, following the arrows. You can follow the top line, which leaves out the year, or drop down to include it. You cannot go back on yourself unless the arrows allow it.

Recursion is shown by a loop back through the diagram (in BNF, the only way to show a loop is recursion). The rule

<number> ::= <digit>|<digit><number>

is drawn as a syntax diagram like this:

Reverse Polish Notation (RPN) was invented as a way of simplifying mathematical expressions.

RPN is older than modern computers. It became useful with the first electronic calculators, which were not good at handling complex expressions with brackets. RPN needs no brackets, because expressions are entered in an unambiguous postfix form.

Early program translators converted expressions to RPN to evaluate them. Today only a few fairly specialised stack-based languages use RPN.

When you write an arithmetic expression normally, you use infix notation: the operator is placed in between the operands. So 2+3 means “add together the values 2 and 3”.

For more complex expressions, a set of agreed rules decides the order of evaluation. The mnemonic BODMAS (sometimes BIDMAS or PEDMAS) helps you remember the order of precedence of the operators:

In postfix notation, or Reverse Polish Notation, the operator comes after its operands. The infix expression

2 + 3

is written in postfix notation as

2 3 +

Now take the more complex expression from before, 7 + (8 * 3² + 4). Using ^ for the power operator, it is written in postfix as:

7 8 3 2 ^ * 4 + +

There are no brackets. You also do not need a mnemonic to remember the order of precedence: the expression is simply evaluated from left to right.

To evaluate a postfix (RPN) expression, use a stack. A stack is a LIFO (last in, first out) data structure. Work through the expression from left to right:

• When you meet an operand, push it onto the stack.
• When you meet an operator, pop two values from the stack, apply the operator to them, and push the result back onto the stack.
• When you have been through the whole expression, pop the final answer from the stack.

Here is the method applied to 7 8 3 2 ^ * 4 + +. The stack is written from bottom to top, so the last number in each row is the top of the stack.

This method is almost foolproof. The one thing to remember is that when you pop two items for an operator, the first item off the stack is the right operand and the second is the left operand. With addition and multiplication the order makes no difference, but with subtraction, division and powers it does. In the example above, working out 2 ^ 3 (= 8) instead of 3 ^ 2 (= 9) would give a different result. To check your order, make sure the operands always stay in the same left-to-right order as in the original expression.

Another way to evaluate an RPN expression, which you may find easier, is to “slide” the operators into place and evaluate. At each step:

1. Take the leftmost operator.
2. Slide it one place to the left.
3. Apply the operator to the operands on either side.
4. Substitute the result.

A well-known algorithm for converting from infix to postfix notation is Dijkstra’s Shunting Yard Algorithm. It uses a queue and a stack to do the conversion, and is good programming practice when you study data structures.

To do the conversion by hand, use the fully parenthesising method.