CS

Translation Software

Understanding interpreters, compilers, and how programs are translated

Learning Objectives

By the end of this lesson, you will be able to:

  • Show understanding of how an interpreter can execute programs without producing a translated version
  • Show understanding of various stages in compilation of a program including lexical analysis, syntax analysis, code generation and optimization
  • 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

Key Terms

Translation Software

  • Interpreter: Software that executes a program line by line without producing a translated version
  • Compiler: Software that translates entire source code into object code before execution
  • Lexical Analysis: First compilation stage that removes unnecessary characters and creates tokens
  • Syntax Analysis: Checks tokenized code for grammatical errors using language rules
  • Code Generation: Transforms tokenized code into machine-readable object code
  • Optimization: Improves object code efficiency by reducing instructions and memory usage

Language Representation

  • Token: Smallest meaningful unit of a program (keywords, symbols, identifiers)
  • Symbol Table: Data structure storing all identifiers used in a program
  • Syntax Diagram: Graphical notation showing language syntax using shapes and symbols
  • Backus-Naur Form (BNF): Textual notation for describing grammar rules of a language
  • Reverse Polish Notation (RPN): Postfix notation where operators follow operands
  • Meta Language: Language used to describe the syntax of programming languages

Interpreters vs Compilers

Compiler

  • Translates entire source code into object code before execution
  • Outputs either object code or error messages
  • Object code can be executed without recompilation
  • Checks entire program at once, reports all errors together

Compiler Process:

source code → COMPILER → object code

Interpreter

  • Executes program line by line without producing object code
  • No object code is output - only program output and error messages
  • Interpreter must be used every time program is executed
  • Checks each statement individually, reports errors before execution

Interpreter Process:

source code → INTERPRETER → program output

Real-Life Example: Cooking Instructions

Think of a compiler as preparing all ingredients before cooking (chopping vegetables, measuring spices), while an interpreter is like following a recipe step-by-step, checking each step as you go.

  • Compiler (Preparatory Chef): Prepares everything in advance. If there's a missing ingredient, you find out before you start cooking.
  • Interpreter (Step-by-Step Chef): Follows the recipe line by line. If step 3 says "add salt" but you don't have salt, you only find out when you reach step 3.

Activity 1: Interpreter vs Compiler Scenarios

For each scenario below, determine whether an interpreter or compiler would be more appropriate and explain why.

1. A student is learning Python programming and testing small code snippets

Answer: Interpreter would be more appropriate because:

  • Python is often used with interpreters for immediate feedback
  • Small code snippets can be tested quickly without compilation delay
  • Errors are shown immediately, helping learning process

2. A software company is building a large Windows application in C++ for distribution to customers

Answer: Compiler would be more appropriate because:

  • C++ is typically compiled for performance
  • Large applications benefit from optimization during compilation
  • Customers receive executable files that don't require an interpreter
  • All errors can be fixed before distribution

Check Your Understanding

  • [1 mark] An interpreter executes the program line by line without producing object code
  • [1 mark] A compiler translates the entire program into object code before execution
  • [1 mark] An interpreter doesn't produce object code during execution
  • [1 mark] A compiler produces object code that can be saved and executed multiple times without recompilation

Stages of Compilation

The process of translating source code into machine code involves four main stages. A compiler has a front-end analysis (lexical and syntax analysis) and a back-end synthesis (code generation and optimization).

Compilation Process Flow

Source Code
High-level language
1. Lexical Analysis
Tokenization
2. Syntax Analysis
Parsing
3. Code Generation
Machine code
4. Optimization
Efficiency
Object Code
Executable
1

Lexical Analysis (Tokenization)

Purpose: Converts source code into tokens - the smallest meaningful units.

  • Removes unnecessary characters (whitespace, comments)
  • Identifies keywords, identifiers, constants, operators
  • Creates a stream of tokens for next stage
  • Builds the symbol table for identifiers

Example:

// Original source code
z = x + y

// After lexical analysis:
z = x + y
// Token IDs might be:
83 01 81 02 82

Symbol Table Created:

Symbol Value Type
X 81 variable
Y 82 variable
Z 83 variable
2

Syntax Analysis (Parsing)

Purpose: Checks tokenized code for grammatical errors using language rules.

  • Uses grammar rules (syntax diagrams or BNF)
  • Checks if tokens form valid statements
  • Uses tree data structures to check grammar
  • If errors found, compilation stops after this stage

Example Error:

// Tokenized input:
83 02 81 02 82

// Syntax error: "=" expected after variable
// z + x + y is not a valid assignment
3

Code Generation

Purpose: Transforms tokenized code into machine-readable object code.

  • Uses information from symbol table
  • Includes code from program libraries
  • Produces binary machine code
  • Code must be syntactically correct to reach this stage

Result:

// High-level code:
z = x + y

// Generated machine code (simplified):
LOAD R1, [address_of_x]
LOAD R2, [address_of_y]
ADD R3, R1, R2
STORE R3, [address_of_z]
4

Optimization

Purpose: Improves efficiency of generated code.

  • Removes redundant code
  • Reduces memory usage
  • Reorganizes code for faster execution
  • Minimizes CPU usage and execution time

Before vs After Optimization:

// Before optimization:
x = 5 * 2
y = x + 1
z = 5 * 2

// After optimization:
x = 10
y = 11
z = 10
// Or even better:
x = 10
y = 11
// z removed if not used

Real-Life Example: Language Translation

Think of compilation like translating a book from English to French:

  • Lexical Analysis: Breaking sentences into words and punctuation
  • Syntax Analysis: Checking if sentences follow grammar rules
  • Code Generation: Translating each sentence to French
  • Optimization: Improving the French translation to be more elegant and concise

Activity 2: Compilation Stage Identification

For each action below, identify which compilation stage it belongs to and explain why.

1. Removing comments and whitespace from source code

Answer: Lexical Analysis

Why: This is part of tokenization where unnecessary characters are removed to create a stream of tokens.

2. Checking if "x = y +" follows language grammar rules

Answer: Syntax Analysis (Parsing)

Why: This involves checking grammatical correctness of token sequences.

Check Your Understanding

  • [1 mark] Stores all identifiers (variables, constants) found in the source code
  • [1 mark] Contains variable types and values, used in later compilation stages
  • [1 mark] Redundant code is removed
  • [1 mark] Code is reorganized to be more efficient
  • [1 mark] Program uses less memory and executes faster
  • [1 mark] It analyzes the grammatical structure of the tokenized code
  • [1 mark] It checks if tokens form valid statements according to language grammar rules

Syntax Diagrams & BNF

Meta languages describe the syntax of programming languages. Grammar rules can be shown graphically using syntax diagrams or textually using Backus-Naur Form (BNF).

Syntax Diagrams

Graphical notation using shapes and symbols:

  • Circle: Terminal symbol (no further definition)
  • Rectangle: Non-terminal (defined in another diagram)
  • Arrow: Direction to read the diagram

Example: Variable definition

variable
letter
digit

A variable is a letter followed by a digit

Backus-Naur Form (BNF)

Textual notation using specific symbols:

Symbol Meaning
::= "is defined as"
< > Non-terminal element
| OR (choice between items)
; End of a rule

Example: Integer definition

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

This is a recursive definition - integer is defined in terms of itself to allow multiple digits.

Real-Life Example: Recipe Instructions

Think of BNF as a precise way to write cooking instructions:

<recipe> ::= <ingredients> <instructions> ;
<ingredients> ::= "Ingredients:" <ingredient-list> ;
<ingredient-list> ::= <ingredient> | <ingredient> , <ingredient-list> ;

Check Your Understanding

A rectangle represents a non-terminal symbol - an item that is defined in greater detail in another syntax diagram.

Reverse Polish Notation (RPN)

Reverse Polish Notation (RPN), also called postfix notation, is a way to write expressions where operators follow their operands. It never requires brackets and has no precedence rules.

RPN Evaluation Simulation

Infix Expression:

( 3 + 4 ) × 5

RPN Expression:

3 4 + 5 ×

Stack Evaluation:

5
7

Result: 35

How it works: Read RPN from left to right. Push numbers onto stack. When you encounter an operator, pop the top two values, apply the operator, push result back.

Step 1: Push 3 → Stack: [3]

Step 2: Push 4 → Stack: [3, 4]

Step 3: Encounter "+" → Pop 4 and 3, calculate 3+4=7 → Push 7 → Stack: [7]

Step 4: Push 5 → Stack: [7, 5]

Step 5: Encounter "×" → Pop 5 and 7, calculate 7×5=35 → Push 35 → Stack: [35]

Why Use RPN?

  • No brackets needed - order determined by operator position
  • No precedence rules (BODMAS/BIDMAS not needed)
  • Easy to evaluate using a stack algorithm
  • Used in some calculators and compilers
  • Efficient and unambiguous

Conversion Examples

// Infix to RPN:
A + B → A B +
(A + B) × C → A B + C ×
A + B × C → A B C × +
(3 - 4) + 5 → 3 4 - 5 +

Real-Life Example: Calculator Input

Old HP calculators used RPN. To calculate (2+3)×4:

  • Infix calculator: Press: 2, +, 3, =, ×, 4, =
  • RPN calculator: Press: 2, ENTER, 3, +, 4, ×
  • The RPN method is more efficient for complex calculations and doesn't need parentheses keys.

Check Your Understanding

A B × C +

Explanation: Multiplication has higher precedence than addition in infix, so B is multiplied by A first, then C is added.

  • [1 mark] Order of operations is determined by the position of operators
  • [1 mark] Operators are applied immediately to the preceding operands

Key Takeaways

  • Interpreters execute line by line without producing object code, while compilers translate entire programs before execution
  • Lexical analysis (tokenization) removes unnecessary characters and creates tokens, building a symbol table
  • Syntax analysis (parsing) checks tokenized code for grammatical errors using language rules
  • Code generation transforms correct tokenized code into machine-readable object code
  • Optimization improves efficiency by removing redundant code and reorganizing instructions
  • Syntax diagrams use circles for terminals and rectangles for non-terminals to visually represent grammar
  • Backus-Naur Form (BNF) uses ::=, |, < >, and ; to define language grammar textually
  • Reverse Polish Notation (RPN) places operators after operands, eliminating need for brackets and precedence rules
  • RPN evaluation uses a stack - push operands, pop and apply operators, push results
  • Compilation stages must occur in order - each stage depends on the output of the previous stage

Question Bank

Marking Scheme & Answer
  • [2 marks each] Any three from:
    • Interpreter executes line by line / compiler translates entire program first
    • Interpreter doesn't produce object code / compiler produces object code
    • Interpreter must be used every time program runs / compiled program can run without compiler
    • Interpreter reports errors as they occur / compiler reports all errors after analysis
    • Interpreter returns control after each statement / compiler produces standalone executable
Marking Scheme & Answer
  • [1 mark] Unnecessary characters (whitespace, comments) are removed
  • [1 mark] Program is tokenized (broken into keywords, identifiers, operators)
  • [1 mark] Symbol table is created for variables and constants
  • [1 mark] Tokens are represented (e.g., as hexadecimal numbers)
  • [Additional] Output is a tokenized list stored in memory
Marking Scheme & Answer
  • [1 mark] Stores all identifiers (variables, constants) found in source code
  • [1 mark] Contains type and value information for each identifier
  • [1 mark] Used in later compilation stages (syntax analysis, code generation)
  • [Additional] Each identifier is assigned a token for reference
Marking Scheme & Answer
  • [1 mark] Uses tokenized output from lexical analysis
  • [1 mark] Checks against grammatical rules of the programming language
  • [1 mark] Uses tree data structures to verify syntax
  • [1 mark] If errors found, compilation stops; if error-free, proceeds to code generation
  • [Additional] Rules can be expressed in BNF or syntax diagrams
Marking Scheme & Answer
  • [1 mark] Reduces number of instructions (more efficient code)
  • [1 mark] Occupies less memory space
  • [1 mark] Minimizes execution time and CPU usage
  • [Additional] Removes redundant code and reorganizes for efficiency
Marking Scheme & Answer
  • [1 mark] Syntax diagrams use graphical notation (shapes, symbols)
  • [1 mark] BNF uses textual notation (::=, |, < >, ;)
  • [1 mark] Circles in diagrams = terminals; rectangles = non-terminals
  • [1 mark] BNF uses ::= for definition, | for alternatives
  • [Additional] Both can represent the same grammar rules, just different formats
Marking Scheme & Answer

A B + C D - ×

Explanation: First convert A+B to RPN: A B +. Then convert C-D to RPN: C D -. Then combine with multiplication: A B + C D - ×

Marking Scheme & Answer
  • [1 mark] Can be processed from left to right without backtracking
  • [1 mark] No brackets or precedence rules needed
  • [1 mark] Easy to evaluate using a stack-based algorithm
  • [Additional] Efficient and unambiguous expression representation
Marking Scheme & Answer
<unsigned integer> ::= <digit> | <digit><unsigned integer> ;
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ;

Note: This is a recursive definition allowing one or more digits.

Marking Scheme & Answer
  1. [2 marks] Lexical Analysis: Removes unnecessary characters, tokenizes program, creates symbol table
  2. [2 marks] Syntax Analysis: Checks tokenized code for grammatical errors using language rules (parsing)
  3. [2 marks] Code Generation: Transforms tokenized code into machine-readable object code
  4. [2 marks] Optimization: Improves efficiency by removing redundant code, reducing memory usage, speeding execution