Revision Notes for IGCSE

Translation Software, BNF and Reverse Polish Notation

Topic 5.2 covered which translator to use. This section goes inside the compiler to examine how translation happens, plus two formal tools: Backus-Naur Form for defining a language's syntax and reverse Polish notation for evaluating expressions without brackets.

1. The Stages of Compilation

Stage	Purpose	Output
1. Lexical analysis	Break the source into tokens	A stream of tokens plus a symbol table
2. Syntax analysis	Check the tokens obey the grammar	A parse tree, or syntax errors
3. Code generation	Produce object code	Machine code or intermediate code
4. Optimisation	Improve the code's speed or size	Optimised object code

Lexical analysis

The source code is read character by character and grouped into tokens — keywords, identifiers, operators and literals. Comments and unnecessary whitespace are removed. Identifiers are entered into a symbol table recording each name, its type and eventually its memory address.

Source: Total ← Count * 5 Tokens: [identifier: Total] [assign] [identifier: Count] [operator: *] [literal: 5]

Lexical analysis does not check whether the statement makes sense. A line of valid tokens in a meaningless order passes this stage and is rejected later, during syntax analysis.

Syntax analysis

The token stream is checked against the language's grammar rules, a process called parsing. If the tokens form a valid construct a parse tree is produced; if not, a syntax error is reported. Some semantic checks also occur here, such as detecting an undeclared identifier or a type mismatch.

Code generation and optimisation

The parse tree is converted into object code. Optimisation then improves it without changing what it does:

Removing code that can never execute (dead code)
Moving calculations that never change out of a loop
Evaluating constant expressions at compile time — 4 * 5 becomes 20
Using registers instead of main memory where possible

Optimisation must not change the program's behaviour. It changes only how efficiently the result is reached. Answers claiming optimisation "fixes errors" or "improves the logic" score nothing.

2. Backus-Naur Form (BNF)

BNF is a formal notation for defining the syntax of a language. It states precisely what counts as valid, in a form a compiler writer can implement directly.

Symbol	Meaning
::=	"is defined as"
\|	"or" — alternatives
< >	A non-terminal — something defined elsewhere by another rule
plain text	A terminal — an actual character or symbol appearing in the language

Recursion is how BNF expresses "one or more". The rule <integer> ::= <digit> | <digit> <integer> says an integer is either a single digit, or a digit followed by another integer. That definition permits digit strings of any length using only two alternatives.

Applying the rules

Candidate	Valid identifier?	Why
count	Yes	Letters only
count2	Yes	Identifier followed by a digit
2count	No	No rule allows an identifier to begin with a digit

A syntax diagram shows the same rules pictorially, with boxes for non-terminals, rounded boxes for terminals, and arrows showing permitted paths including loops for repetition.

3. Reverse Polish Notation (RPN)

In reverse Polish notation the operator is written after its operands — also called postfix. Ordinary algebra is infix, with the operator between them.

Infix	RPN (postfix)
3 + 4	3 4 +
3 + 4 * 5	3 4 5 * +
(3 + 4) * 5	3 4 + 5 *
A * B + C / D	A B * C D / +

Why compilers use RPN: it needs no brackets and no rules of precedence. The order of the symbols alone fixes the order of evaluation, so the expression can be evaluated by a simple stack with no look-ahead.

Evaluating RPN with a stack

Read left to right. Push operands. On an operator, pop two operands, apply it, push the result.

Evaluate: 5 3 4 * + Read 5 push Stack: 5 Read 3 push Stack: 5, 3 Read 4 push Stack: 5, 3, 4 Read * pop 4 and 3, compute 3*4=12, push Stack: 5, 12 Read + pop 12 and 5, compute 5+12=17, push Stack: 17 Result: 17

Mind the operand order for subtraction and division. The first value popped is the right-hand operand. For 7 2 -, pop 2 then 7, and compute 7 - 2 = 5, not 2 - 7. Reversing this is the most common RPN error.

4. Exam Focus

Keep lexical and syntax analysis apart. Lexical analysis creates tokens and removes comments and whitespace. Syntax analysis checks grammar and builds a parse tree. Attributing error detection to the lexical stage is a common mistake.

Show the stack when evaluating RPN. Marks are awarded for the intermediate states, so write out the stack contents after each symbol rather than only the final answer.

Quote BNF rules when justifying validity. Saying an identifier is invalid "because it starts with a number" is weaker than stating that no production rule permits an identifier to begin with <digit>.

Quick self-check

Name the four stages of compilation and state the output of each.
State two things lexical analysis removes from the source code.
What is stored in the symbol table?
Write BNF rules defining a non-negative integer.
Convert (A + B) * (C - D) to RPN.
Evaluate 8 2 / 3 + showing the stack at each step.

16.2 Translation Software