Translation Software

Computer Science A2 · System Software. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science A2 topics

The idea

An interpreter reads one statement of source code, checks it, and carries it out straight away. It then moves to the next statement. No object code file is produced, so the interpreter and the source code are needed every time the program runs.

A compiler translates the whole program in stages: lexical analysis, syntax analysis, code generation and optimisation. The result is object code that runs on its own.

The grammar of a language is written down with syntax diagrams or with Backus-Naur Form (BNF). Compilers often change expressions into Reverse Polish Notation (RPN), where the operator comes after its operands, so no brackets are needed and a stack can evaluate it.

Rules to remember

Lexical analysis: removes spaces and comments, turns the characters into tokens, and builds the symbol table.
Syntax analysis: checks the tokens against the grammar rules, builds a parse tree and reports syntax errors.
Code generation: produces the object code. Optimisation: makes the code run faster or use less memory.
BNF: ::= means "is defined as", | means "or", and a name in angle brackets such as <digit> is an item defined by another rule.
A BNF rule that uses its own name, e.g. <number> ::= <digit> | <number><digit>, allows repetition (one or more digits).
Infix to RPN: (a + b) * c becomes a b + c *, and a + b * c becomes a b c * +.
To evaluate RPN: push each operand; for an operator, pop two values, apply it as (second popped) operator (first popped), then push the result.

Common mistake

For − and ÷ students use the two popped values the wrong way round. The value popped first is the right-hand operand, so 8 3 − means 8 − 3 = 5, not 3 − 8.

Worked example

Evaluate the RPN expression 7 2 5 * + 3 − using a stack.

Push 7, 2 and 5. The stack holds 7, 2, 5.
Read *: pop 5 and 2, work out 2 × 5 = 10, push 10. The stack holds 7, 10.
Read +: pop 10 and 7, work out 7 + 10 = 17, push 17.
Push 3. Read −: pop 3 and 17, work out 17 − 3 = 14, push 14.

Answer: 14 (the infix form is 7 + 2 × 5 − 3).

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Purposes of an Operating System (OS)Encryption, Encryption Protocols and Digital Certificates →Take a Computer Science A2 test