Show understanding of how an interpreter can execute programs without producing a translated version
Show understanding of various stages in compilation: lexical analysis, syntax analysis, code generation and optimisation
Show understanding of how grammar of a language can be expressed using syntax diagrams or Backus-Naur Form (BNF) notation
Show understanding of how Reverse Polish Notation (RPN) can be used to carry out evaluation of expressions
📋 Prior Knowledge Required
Understanding of high-level programming languages
Knowledge of machine code and binary representation
Basic understanding of programming concepts (variables, operators, expressions)
Familiarity with stack data structure operations (push, pop)
🌟 Did You Know?
Translation software is the bridge between human-readable code and machine-executable instructions. Without translators like compilers and interpreters, programmers would need to write programs directly in binary machine code!
1. Interpreter vs Compiler
A translator is system software that converts source code written in a high-level programming language into machine code. There are two main types: compilers and interpreters.
1.1 What is a Compiler?
📖 Definition: Compiler
A compiler is a computer program that transforms code written in a high-level programming language into machine code. It translates the entire source code before the program runs.
📝 How a Compiler Works
Source code is input to the compiler
Compiler translates entire program into object code
Object code (machine code) is produced and saved
Object code can be executed without recompilation
Any syntax errors are reported after complete analysis
1.2 What is an Interpreter?
📖 Definition: Interpreter
An interpreter is a computer program that executes high-level code line by line. It does not produce a separate translated version - it directly executes the source code.
📝 How an Interpreter Works
Source code is read one statement at a time
Each statement is analysed and translated
Statement is executed immediately if no errors
Control returns to interpreter for next statement
If error found, execution stops and error reported immediately
2. Compiler vs Interpreter Comparison
Feature
Compiler
Interpreter
Translation
Translates entire program at once before execution
Translates and executes one line at a time
Output File
Produces object code (.exe) file
No object code produced
Execution Speed
Compiled code runs faster
Interpreted code runs slower
Error Reporting
Reports all errors after compilation
Reports errors line by line immediately
Error Correction
Must recompile after fixing errors
Can correct errors and continue execution
Memory Usage
Object code saved - can run without source
Interpreter needed every time program runs
Use Cases
Production software, large applications
Development, debugging, rapid prototyping
💡 Exam Tip
Remember the key difference: Compiler = Complete translation before execution, Interpreter = Line-by-line translation during execution. Compilers produce object code that can be run independently; interpreters need to be present every time the program runs.
🧠 Memory Trick
Compiler = "Complete" - translates complete program at once
Interpreter = "Immediate" - executes immediately line by line
Think: Compiler creates a "copy" (object code), Interpreter is "interactive"
2.1 Example Use Cases
Compiler Use Cases: C, C++, Java (compiles to bytecode), production software, embedded systems.
A compiler has a 'front-end analysis' and a 'back-end synthesis'. The process of translating source code into object code can be divided into four stages:
📖 Four Stages of Compilation
Lexical Analysis - Converts source code into tokens
Syntax Analysis - Checks grammar rules and creates parse tree
Code Generation - Produces object code in machine-readable form
Optimisation - Refines code to run more efficiently
🌟 Front-End vs Back-End
The front-end performs analysis of source code and produces intermediate code. The back-end takes this intermediate code and performs synthesis of object code optimised for the target machine.
4. Lexical Analysis
Lexical analysis is the first stage in compilation. It studies the "words" or vocabulary of the programming language and converts the source program into tokens.
4.1 What Happens During Lexical Analysis?
📝 Tasks in Lexical Analysis
All unnecessary characters are removed (whitespace, comments, redundant spaces)
Keywords, constants, and identifiers are replaced by tokens
Keywords (reserved words) are checked for validity from keywords table
A symbol table is built containing all identifiers found in source code
Output is a tokenised list stored in main memory
4.2 What is a Token?
📖 Definition: Token
A token is a sequence of characters that can be treated as a unit in the grammar of the programming language. A lexeme is the actual sequence of alphanumeric characters that forms a token.
Token Type
Examples
Keywords
var, const, function, for, while, if, return, DECLARE, INTEGER
Identifiers
Variable names, function names (e.g., x, Count, max)
The keyword table contains all the reserved words and symbols that can be used in the programming language. Every program being compiled uses the same keyword table.
Symbol/Keyword
Token (Hex)
=
01
+
02
-
03
*
04
DECLARE
31
INTEGER
32
INPUT
33
OUTPUT
34
5.2 Symbol Table
The symbol table is built for every program during compilation. It contains all identifiers (variables, constants) found in the source code.
📖 Symbol Table Contents
Identifier name: Variable or constant names
Data type: INTEGER, STRING, REAL, BOOLEAN
Role: Variable, constant, array, procedure
Location/Value: Memory address or initial value
⚠️ Important
At lexical analysis stage, only variable names are noted in the symbol table. Other details like data type and scope are entered in the next stage (syntax analysis). The symbol table is used in later stages of compilation.
6. Syntax Analysis
Syntax analysis (also known as parsing) is the second stage of compilation. The tokenised output from lexical analysis is checked against the language's grammar rules.
6.1 Tasks in Syntax Analysis
📝 What Happens During Syntax Analysis
Complete tokenised list is checked for grammatical (syntax) errors
This process is called parsing
Tree data structures (parse trees) are used to check grammar rules
Rules can be set out using Backus-Naur Form (BNF) notation
Whole program goes through this process even if errors are found
📖 Parse Tree
A parse tree is a tree data structure made up of nodes and branches that represents the syntactic structure of the input based on the grammar of the language.
💡 Error Handling
If errors are found, each statement and associated error are output. Code generation will NOT be attempted if there are syntax errors. The compilation process finishes after this stage if errors exist.
7. Code Generation
During the code generation stage, the compiler transforms the tokenised form into code that can be understood by the computer's processor.
📖 Object Code
The object program is in machine-readable form (binary). It is no longer designed to be read by humans. The program must be syntactically correct for object code to be produced.
📝 Intermediate Code
Intermediate code lies between high-level language and machine code. It can support:
Portable code - program can be stored anywhere in main memory
Minimised size - smaller stored object program
8. Optimisation
The optimisation stage creates an efficient object program. Optimised programs perform tasks using minimum resources (time, storage space, memory, CPU use).
Optimisation Type
Description
Example
Redundant Instruction Elimination
Remove duplicate or unnecessary calculations
x = a + b; y = a + b → calculate once, use twice
Unreachable Code Removal
Remove code that will never execute
Code after unconditional return statement
Flow/Control Optimisation
Simplify control structures
Remove unnecessary jumps or branches
Loop Optimisation
Move invariant code outside loops
Calculations that don't change inside loop
🌟 Benefits of Optimisation
Redundant code is removed → smaller program size
Program requires less memory
Code is reorganised for efficiency
Faster execution time
9. Backus-Naur Form (BNF)
BNF is a meta-language - a way of writing rules that define the syntax of programming languages. It is a formal mathematical way to describe a language's grammar.
9.1 BNF Symbols
Symbol
Meaning
Example
::=
"is defined as" - separates name from definition
<digit> ::= 0 | 1 | 2 | ...
< >
Encloses a non-terminal element (needs further definition)
<integer>, <digit>
|
"OR" - indicates a choice between alternatives
0 | 1 | 2 | 3
;
Marks the end of a rule
End of definition
📖 Terminal vs Non-Terminal
Terminal symbols: Actual values that cannot be broken down further (e.g., 0, 1, 2, +, -, if, while). Written without angle brackets.
Non-terminal symbols: Elements that need to be defined by other rules. Enclosed in angle brackets < >
Example 2: Defining an integer (single digit) <integer> ::= <digit>
Example 3: Defining an integer (multiple digits using recursion) <integer> ::= <digit> | <digit><integer>
💡 Understanding Recursion in BNF
For the number 1524: It's a digit (1) followed by an integer (524). Then 524 is a digit (5) followed by integer (24), and so on. The recursion stops when we reach a single digit.
Start simple - define basic elements (digit, letter)
Build up - combine simple elements into complex ones
Use recursion - for repeating patterns (like multi-digit numbers)
OR (|) gives choices - allows multiple valid options
11. Syntax Diagrams
Syntax diagrams are graphical notations that use shapes and symbols to represent different elements of a language. They are a visual alternative to BNF.
11.1 How to Read Syntax Diagrams
📖 Syntax Diagram Symbols
Circles/Ovals: Terminal symbols - cannot be broken down further (e.g., 0, 1, +, IF, THEN)
Rectangles: Non-terminal symbols - need to refer to another syntax diagram for full definition
Arrows: Show the direction to read the diagram (always left to right)
Branches: Show alternatives (OR choices)
Loops: Show repetition
💡 Reading Tip
Always start reading from the left and follow the flow to the right. Rectangles mean "see another diagram"; circles are final values.
12. More Syntax Diagram Examples
12.1 IF Statement Syntax Diagram
12.2 Operator Syntax Diagram
❌ Common Mistake
Don't confuse the shapes! Circles/Ovals = Terminal symbols (actual values), Rectangles = Non-terminal symbols (need another diagram). IF, THEN, ELSE are terminals - they appear in circles!
13. Reverse Polish Notation (RPN)
RPN (also called postfix notation) is a method of representing expressions where the operator comes after the operands. It eliminates the need for brackets and precedence rules.
13.1 Infix vs Postfix (RPN)
Notation
Example
Description
Infix (standard)
A + B
Operator between operands
Postfix (RPN)
A B +
Operator after operands
Prefix (Polish)
+ A B
Operator before operands
📖 Why Use RPN?
No brackets needed - order of operations determined by position
No precedence rules - no need for BODMAS
Unambiguous - every expression has only one valid interpretation
Easy for computers - can be evaluated using a stack
Left to right processing - no backtracking required
13.2 Converting Infix to RPN
Example 1: a + b * c Apply precedence: multiplication first → (a + (b * c)) RPN: a b c * +
Example 2: (a + b) * c Brackets indicate addition first → ((a + b) * c) RPN: a b + c *
Explanation: The first rule says an integer is either a single digit OR a digit followed by another integer (recursion). This allows integers of any length.
5. Convert the infix expression (A + B) * (C - D) to RPN. [4 marks]
Answer:
A B + C D - *
Explanation: Work from inside brackets out. First (A + B) → A B +, then (C - D) → C D -, finally multiply → place * after both results.
15. Exam-Style Questions (Continued)
6. Evaluate the RPN expression: 5 3 2 * + 4 - using a stack. [6 marks]
Answer:
Read 5: PUSH 5 → Stack: [5]
Read 3: PUSH 3 → Stack: [5, 3]
Read 2: PUSH 2 → Stack: [5, 3, 2]
Read *: POP 2, 3 → 3*2=6 → PUSH 6 → Stack: [5, 6]
Read +: POP 6, 5 → 5+6=11 → PUSH 11 → Stack: [11]
Read 4: PUSH 4 → Stack: [11, 4]
Read -: POP 4, 11 → 11-4=7
Final Result: 7
7. Explain what happens during optimisation. Give two examples. [6 marks]
Answer:
Optimisation creates an efficient object program that executes faster and uses fewer resources.
Examples:
Redundant instruction elimination: Remove duplicate calculations - if x = a + b appears twice, calculate once and reuse
Unreachable code removal: Remove code that will never execute (e.g., after unconditional return)
Loop optimisation: Move calculations that don't change outside loops
8. What is the difference between terminal and non-terminal symbols in BNF? [4 marks]
Answer:
Terminal symbols are actual values that cannot be broken down further. They appear without angle brackets (e.g., 0, 1, +, if, while)
Non-terminal symbols are elements that need to be defined by other rules. They are enclosed in angle brackets < > (e.g., <digit>, <integer>)
Example: <digit> ::= 0 | 1 | 2 — <digit> is non-terminal, 0-9 are terminals
9. Why do compilers use Reverse Polish Notation? [5 marks]
Answer:
RPN can be processed left to right without backtracking
No need for brackets - order determined by position
No need for precedence rules - evaluation order is explicit
RPN is unambiguous - one valid interpretation only
Can be evaluated efficiently using a stack-based algorithm
10. Draw a syntax diagram for a signed integer. [4 marks]
Answer:
Start with either + or -, followed by an integer (defined in another diagram).
16. Glossary
Term
Definition
Compiler
System software that translates entire source code into object code before execution
Interpreter
System software that executes source code line by line without producing object code
Token
A sequence of characters treated as a unit in programming language grammar
Lexical Analysis
First compilation stage that converts source code to tokens
Syntax Analysis
Second compilation stage that checks tokens against grammar rules
Parse Tree
Tree structure representing the syntactic structure of a program
Code Generation
Third compilation stage that produces machine-readable object code
Optimisation
Fourth compilation stage that refines code for efficiency
Symbol Table
Data structure storing all identifiers with their attributes
BNF
Backus-Naur Form - meta-language for defining syntax rules
Terminal Symbol
A symbol that cannot be broken down further (actual value)
Non-terminal Symbol
A symbol that needs to be defined by other rules
Syntax Diagram
Graphical representation of grammar rules using shapes
RPN
Reverse Polish Notation - postfix notation with operator after operands
Object Code
Machine-readable code produced by a compiler
17. Exam Success Tips
💡 Compiler vs Interpreter
Compiler = "Complete" - translates complete program at once
Interpreter = "Interactive" - executes immediately line by line
Compiler produces object code; Interpreter does NOT
💡 Compilation Stages Order
Memory trick: "Little Students Create Objects" L = Lexical, S = Syntax, C = Code Generation, O = Optimisation
💡 BNF Symbols
::= means "is defined as"
< > encloses non-terminals
| means "OR"
💡 Syntax Diagrams
Circles/Ovals = Terminal symbols (actual values)
Rectangles = Non-terminals (see another diagram)
Always read left to right
❌ Common Mistakes to Avoid
Don't say interpreters produce object code - they don't!
In RPN subtraction: second popped - first popped
IF, THEN, ELSE are terminals (circles), not rectangles
Code generation only happens if syntax analysis passes
Stack evaluation: Push values, pop and apply operators
🌟 Final Reminder
Remember: Read questions carefully, check mark allocations, use technical terms (token, parse tree, BNF, RPN), show your working for RPN stack evaluation, and manage your time effectively!