COMPSCI110 · Introduction to Computer Systems
Compilers
Module 7 of University of Auckland COMPSCI110 explains how a high-level program becomes machine code — a one-to-many translation that needs real linguistic analysis, unlike an assembler's table lookup. You cover the four compiler phases (lexical analysis, parsing, semantic analysis & code generation, optimisation), tokens and their classes, BNF grammar and parse trees, and semantic records. It carries 7 marks on the final exam — one of the two heaviest modules — so it deserves proportionate revision time.
What this chapter covers
- 01Compiler vs assembler: high-level → machine code is one-to-many and needs syntax + semantic analysis; assembly → machine code is one-to-one
- 02The four phases: I lexical analysis (scanner), II parsing (grammar → parse tree), III semantic analysis & code generation, IV code optimisation
- 03Lexical analysis: characters → tokens, discarding whitespace and comments (comments are never tokens)
- 04Tokens and token classes (keywords, symbols/identifiers, operators, brackets, numbers, literals); == is a single token distinct from =
- 05The scanner does NOT check syntax — an illegal sequence still tokenises; keywords like else are classed as keywords even when misused
- 06Parsing: BNF grammar, productions and non-terminals, and building a parse tree that shows the statement's structure
- 07Semantic analysis: semantic records carry meaning (types, addresses) forward to code generation
Tokenising a statement into tokens and classes
- +1Lexical analysis scans the characters left to right, grouping them into the longest valid tokens and discarding whitespace (and any comments — comments never become tokens).
- +1First four tokens: if → keyword; ( → bracket; a → symbol (identifier); == → operator (the equality operator, matched as ONE token, not two = signs).
- +1Next four: b → symbol; ) → bracket; answer → symbol; = → operator (assignment — a different token class from ==).
- +1Last two: 42 → number; ; → symbol/terminator. Total = 10 tokens. Note the scanner does NOT verify that this is valid syntax — that is the parser's job in phase II.
Key terms
- Compiler
- A program that translates a high-level language into machine code. Unlike an assembler (one-to-one table lookup), a compiler performs a one-to-many translation and needs full linguistic analysis — checking syntax and meaning — because one source statement can expand into many machine instructions.
- Lexical analysis (scanner)
- The first compiler phase: the scanner (lexer/tokeniser) reads the source characters and groups them into tokens, discarding whitespace and comments. It classifies tokens but does not check whether their arrangement is grammatically valid — that is the parser's responsibility.
- Token & token class
- A token is the smallest meaningful unit of source code (a keyword, identifier, operator, bracket, number or literal), and its class is which of those categories it belongs to. Multi-character operators like == are matched as a single token and classed separately from the single-character = .
- Parser & parse tree
- The second phase checks that the token stream obeys the language's grammar and builds a parse tree — a hierarchical structure showing how the statement is composed from the grammar's rules. A stream that tokenises fine can still be rejected here if it doesn't fit the grammar.
- BNF grammar
- Backus–Naur Form: a formal notation of productions (rules) that define a language's syntax, expanding non-terminal symbols into sequences of other symbols and terminals. The parser uses the grammar's productions to decide whether a token sequence is legal and to shape the parse tree.
- Semantic analysis & records
- The third phase attaches meaning to a syntactically valid program — checking types, resolving names — and carries that information in semantic records so the code-generation step can emit correct machine instructions. Syntax is about form; semantics is about whether the form makes sense.
Compilers FAQ
What are the four phases of a compiler?
Lexical analysis (the scanner turns characters into tokens), parsing (checks the tokens against the grammar and builds a parse tree), semantic analysis & code generation (attaches meaning and emits machine instructions) and code optimisation (improves the result's time or space). The first two deal with form, the third with meaning and translation, and the fourth with efficiency.
How do I count the tokens in a statement?
Scan left to right and group characters into the longest valid tokens, classifying each as a keyword, symbol/identifier, operator, bracket, number or literal. Discard whitespace and comments — they are never tokens. Watch multi-character operators: == is one operator token, not two = signs, and is a different class from the assignment = . Then simply count the tokens you produced.
Can AI help me with compilers in COMPSCI110?
Yes, as a study aid. Sia can tokenise a statement with you and explain each class, walk the four phases in order, and describe how a parse tree is built from grammar productions. Use it to understand the method and rehearse on fresh statements — it explains and checks your reasoning but does not do graded assignments or the exam for you, and the University of Auckland's academic-integrity rules apply to controlled assessments.
Are comments tokens, and does the scanner catch errors?
Comments are never tokens — the scanner discards them along with whitespace. And the scanner does not catch syntax errors: its only job is to classify tokens, so an illegal arrangement like X = ; (14 still tokenises successfully. Detecting that the arrangement is ungrammatical happens in the next phase, parsing. Even a keyword used in the wrong place (e.g. else on the left of an assignment) is still classified as a keyword.
How heavily is Module 7 examined?
It is worth 7 marks on the final exam — tied among the heaviest modules with Operating Systems (8) just above it. That weighting justifies spending real revision time here: make sure you can tokenise fluently, recite the four phases, and explain the difference between syntax (parsing) and semantics. Confirm the current per-module breakdown on Canvas, since exam structure can be updated between offerings.
Exam move
Give Compilers revision time in proportion to its 7 marks. The most reliable points come from tokenising, so drill it: scan left to right, produce the longest tokens, classify each, discard whitespace and comments, and treat == as one operator token distinct from = . Practise several statements of increasing messiness, including deliberately invalid ones, to internalise that the scanner classifies but does not check syntax. Then memorise the four phases in order and be able to say what each does in a sentence — lexical (tokens), parsing (grammar → parse tree), semantic analysis & code generation (meaning → instructions), optimisation (efficiency) — and pin down the key distinction that syntax is form (parsing) while semantics is meaning. For BNF and parse trees, understand the idea of productions expanding non-terminals and be able to read a supplied grammar rather than memorising any particular one. If a past paper supplies a specific grammar, practise building its parse tree by hand.
Working through Compilers in COMPSCI 110? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI 110 Compilers question and get a clear, step-by-step explanation grounded in how COMPSCI 110 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
