Stages of compilation: lexical analysis, syntax analysis, code generation and optimisation

Stages of compilation (lexical analysis, syntax analysis, code generation and optimisation)

1.2.2 Applications Generation

Applications Generation — Note 5 of 6

Candidates need to understand that there are a number of stages involved in compilation. Candidates need to understand how lexical analysis works and how the code is converted into tokens with the removal of unnecessary elements (e.g. comments and whitespace). Candidates need to understand how syntax errors are identified and reported at the end of the syntax analysis. Candidates need to understand how the abstract syntax tree will be fed into the next stage of code generation, and that the object code is then created. Candidates need to understand why optimisation is important and how the results of lexical analysis feeds into syntax analysis, and how the tokens are checked to ensure they meet during (and after) code generation.

What you need to know

A compiler translates source code in several stages. Each stage takes the output of the previous one, gradually turning human-readable code into efficient machine code and reporting errors along the way.

What to know

LEXICAL ANALYSIS: whitespace and comments are removed; the code is split into tokens (keywords, identifiers, operators, constants); identifiers are added to the symbol table.
SYNTAX ANALYSIS: the tokens are checked against the grammar rules of the language. Syntax errors are reported. An abstract syntax tree is built to represent the structure of the program.
CODE GENERATION: the abstract syntax tree is converted into object code (machine code) for the target processor.
OPTIMISATION: the code is changed to run faster or use less memory without changing what it does, e.g. removing redundant or unreachable code, or replacing a calculation with a simpler equivalent.
Optimisation can take place before and during code generation.
Over-optimisation can make compilation slower and occasionally introduce errors, so it is a trade-off.

Key terms

Exam tipCommon mistake

Token: The smallest meaningful unit of code, e.g. while, count, <=, 10.
Exam tip: Learn the stages in order and say what each stage TAKES IN and PRODUCES: source code → tokens → abstract syntax tree → object code → optimised object code.
Common mistake: Saying lexical analysis finds syntax errors. Lexical analysis only finds invalid tokens; grammar errors are found during syntax analysis.
Symbol table: A table of the identifiers (variables, subroutines) in the program with information such as data type, scope and memory address.

Code examples

Lexical analysis turns a line of code into tokens

text

Source:  total = total + price  // add price

Tokens:  <identifier: total> <operator: => <identifier: total>
         <operator: +> <identifier: price>

Comment and whitespace removed; 'total' and 'price'
are added to the symbol table.