The shape of the lesson
By the end of the lesson, learners can
- Running code without translating it: At AS Level you compared compilers and interpreters.
- Lexical and syntax analysis: The front end of the compiler checks the source code and turns it into a form the code generator can use.
- Code generation and optimisation: Once the program is known to be valid, the back end of the compiler produces and improves the object code.
- Lexical analysis: remove spaces and comments, tokens, keyword table, symbol table.
- Syntax analysis: check tokens against the grammar, parse tree, syntax errors listed.
- Code generation: object code, addresses from the symbol table.
- Optimisation: faster and/or smaller code, same result. Interpreter: analyse then execute with its own routines; nothing saved.
One picture every idea returns to
Compilation has four main stages. Lexical analysis removes white space and comments and converts the source code into tokens, adding identifiers and constants to the symbol table. Syntax analysis (parsing) checks that the sequence of tokens obeys the grammar of the language, builds a parse tree and reports syntax errors. Code generation produces object code from the parse tree. Optimisation makes the object code run faster or use less memory without changing what it does. An interpreter analyses each statement in turn and executes it by calling its own pre-written machine code routines, so no translated version of the program is produced.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, From source to object code.. A compiler does not translate a program in one leap. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Running code without translating it | At AS Level you compared compilers and interpreters. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Lexical and syntax analysis | The front end of the compiler checks the source code and turns it into a form the code generator can use. Model the worked example Tokenise a statement on the board, one line at a time. | Pairs |
| 21 to 30 min | Teach and check: Code generation and optimisation | Once the program is known to be valid, the back end of the compiler produces and improves the object code. Model the worked example Remove a redundant instruction on the board, one line at a time. Your turn: In the loop above, how many multiplications are carried out before and after optimisation? | Jigsaw |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 18 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Code generation and optimisation, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Jigsaw
Split the content into expert pieces. Expert groups master one piece each, then regroup so every home team has one expert per piece, and each expert teaches their piece to the team.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| Saying an interpreter "translates line by line into machine code" loses the mark at A Level. | The point is that it executes each statement using its own routines without producing a translated version. |
| Lexical analysis does not check the order of the tokens. | Total + ← Price passes lexical analysis (every token is valid) and is rejected at syntax analysis. |
The stages of compilation: worksheet
6 questions, 18 marks. Written in the style of the papers; no past paper question is reproduced.
Explain how an interpreter can execute a program without producing a translated version of it.
Describe what happens during the lexical analysis stage of compilation.
Describe what happens during the syntax analysis stage of compilation.
State the stage of compilation at which each error would be detected: (a) the identifier Cost# contains a character that is not allowed (b) a FOR loop has no NEXT (c) the statement Total ← * 3 has two operators together.
Explain the purpose of the optimisation stage and give two examples of optimisation.
The symbol table is used by more than one stage of compilation. Explain how it is used by lexical analysis and by code generation.
Answer key and marking notes
- The interpreter reads and analyses one statement at a time (lexical and syntax analysis).
- It then executes the statement by calling its own pre-written machine code routines that carry out that type of statement.
- No object code / executable file is produced; each statement is analysed again every time it is executed.
- White space and comments are removed.
- The source code is split into tokens (keywords, identifiers, operators, constants).
- Keywords are looked up in a keyword table and replaced by tokens.
- Identifiers and constants are entered into the symbol table; illegal characters / identifiers are reported as errors.
- The sequence of tokens is checked against the grammar rules of the language (e.g. defined in BNF).
- A parse tree is built for each valid statement.
- Syntax errors such as a missing keyword or bracket are reported (as a list of all errors).
- (a) Lexical analysis.
- (b) Syntax analysis.
- (c) Syntax analysis.
- Purpose: to make the object code execute in less time and/or use less memory, without changing what the program does.
- Example: remove redundant instructions, such as reloading a value already in the accumulator.
- Example: move a calculation that does not change out of a loop / evaluate constant expressions at compile time / remove code that can never be executed.
- Lexical analysis adds each new identifier and constant to the symbol table (and replaces it in the token stream with a reference to its entry).
- Code generation uses the symbol table to find the data type of each identifier and to allocate / look up its memory address for the object code.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
At which stage of compilation is a parse tree built and the order of the tokens checked against the grammar of the language?
- ASyntax analysis
- BLexical analysis
- CCode generation
- DOptimisation
How many tokens does lexical analysis produce from this line of source code?
Count ← Count + 1 // next item
- A5
- B6
- C8
- D4
Which error would be reported during lexical analysis rather than syntax analysis?
- AThe constant 3.4.5 is not a valid number
- BAn IF statement has no matching ENDIF
- CThe statement Total ← * 3 has two operators together
- DA closing bracket is missing from an expression
How does an interpreter execute a program without producing a translated version of it?
- AIt analyses each statement in turn and carries it out by calling its own pre-written machine code routines
- BIt translates the whole program into object code in memory, runs it and then deletes the file
- CIt converts each statement into machine code, saves it and runs the saved code on later passes
- DIt sends each statement directly to the processor, which can execute high-level source code
A code generator produced this assembly code for X ← A + B and then Y ← X + C, with A, B, X, C and Y at addresses 300 to 304. Which change is a valid optimisation?
LDD 300 ADD 301 STO 302 LDD 302 ADD 303 STO 304
- ADelete LDD 302, because the accumulator still holds A + B after STO 302
- BDelete STO 302, because the value A + B stays in the accumulator anyway
- CDelete LDD 300, because ADD 301 can load and add in one instruction
- DChange ADD 303 to ADD 302, because X is already at address 302
The optimiser moves the calculation that does not change out of this loop. How many multiplications are carried out after optimisation?
FOR Count ← 1 TO 50
Rate ← Base * 12
Total ← Total + Rate * Count
NEXT Count- A51
- B100
- C50
- D52
Quiz key
Syntax analysis (parsing) checks the token sequence against the grammar rules, often written in BNF, and builds a parse tree. Lexical analysis only produces the tokens and fills the symbol table; it does not check their order. Code generation turns the finished parse tree into object code, and optimisation improves that object code.
White space and the comment are removed, leaving Count, ←, Count, + and 1: five tokens (two identifiers, two operators and a constant). 6 keeps the whole comment as a token, and 8 makes a token of each of //, next and item. 4 counts the identifier Count only once; it is entered in the symbol table once, but it still appears twice in the token stream.
3.4.5 cannot be formed into any valid token, so lexical analysis rejects it. A missing ENDIF, two operators side by side and an unmatched bracket are all made of perfectly valid tokens in an illegal order, so they are found by syntax analysis.
The interpreter analyses one statement, then performs it with its own routines for that kind of statement, so no object code is ever produced and the statement is analysed again next time it is reached. Translating the whole program first, even temporarily, is what a compiler does. Saving machine code for later passes would be a translated version. A processor can only execute machine code, never source code.
STO copies the accumulator to memory without changing it, so after STO 302 the accumulator already holds A + B; reloading it with LDD 302 is redundant, and deleting it leaves both results unchanged. Deleting STO 302 would mean X is never stored. ADD only adds to the existing accumulator value, so LDD 300 is needed to load A. Changing ADD 303 to ADD 302 would calculate 2(A + B) instead of A + B + C.
Base * 12 does not change inside the loop, so it is moved before the loop and done once; Rate * Count still happens on each of the 50 passes: 1 + 50 = 51. 100 is the count before optimisation (2 per pass). 50 forgets the single multiplication now before the loop. 52 counts the moved multiplication twice.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.