Advanced System Software and Security: Question 4
Syllabus 16.2
A compiler is translating a line of source code containing the expression below. Before generating machine code, the compiler's code generation stage first converts this checked infix expression into Reverse Polish Notation (RPN), also called postfix notation, which can then be evaluated using a stack without needing any brackets.
(a + b) * (c - d) / e
(a) Write the Reverse Polish Notation (postfix) form of the expression
(a + b) * (c - d) / e. [2]
(b) The variables take the values a = 6, b = 2, c = 9, d = 5 and e = 4. Copy and
complete a trace table to show the contents of the stack after each token of your RPN expression
from part (a) is processed, and state the final value the expression evaluates to. [4]
(c) Name the stage of compilation that is responsible for producing this RPN and generating the final machine code from it, and briefly describe what happens during the stage that comes immediately before it. [2]
Show worked solution Hide worked solution
Worked solution
Part (a): Converting infix to Reverse Polish Notation
Working through (a + b) * (c - d) / e from left to right, an operator is written immediately
after both of its operands, with brackets removed because the order is now built into the
notation itself:
(a + b)becomesa b +(c - d)becomesc d -- Multiplying these two results together:
a b + c d - * - Finally dividing by
e:a b + c d - * e /
So the RPN form is:
a b + c d - * e /[2 marks]: [1] for correctly converting each bracketed sub-expression (a b + and
c d -), [1] for combining them with * and e / in the correct final order.
Part (b): Evaluating the RPN expression with a stack
An RPN expression is evaluated by scanning it left to right: whenever a number is found, it is
pushed onto the stack; whenever an operator is found, the top two values are popped off, the
operator is applied to them (second-from-top, then top. Important for - and /, since they are
not commutative), and the result is pushed back onto the stack.
With a = 6, b = 2, c = 9, d = 5, e = 4, the tokens a b + c d - * e / become
6 2 + 9 5 - * 4 /:
| Token processed | Action | Stack after this step |
|---|---|---|
6 | push 6 | 6 |
2 | push 2 | 6, 2 |
+ | pop 2, 6; compute 6 + 2 = 8; push 8 | 8 |
9 | push 9 | 8, 9 |
5 | push 5 | 8, 9, 5 |
- | pop 5, 9; compute 9 - 5 = 4; push 4 | 8, 4 |
* | pop 4, 8; compute 8 * 4 = 32; push 32 | 32 |
4 | push 4 | 32, 4 |
/ | pop 4, 32; compute 32 / 4 = 8; push 8 | 8 |
Only one value, 8, remains on the stack once every token has been processed, so the expression
evaluates to 8. (Check against the original infix expression: (6 + 2) * (9 - 5) / 4 = 8 * 4 / 4 = 32 / 4 = 8, the same result.)
[4 marks]: [1] for correctly pushing the three initial numeric values, [1] for
correctly applying +, [1] for correctly applying - and * in the right operand order,
[1] for correctly applying the final / and stating the result 8.
Part (c): Identifying the compilation stage
The stage responsible for producing this RPN form and generating the target machine code from it is code generation. The stage that comes immediately before code generation is syntax analysis: it takes the stream of tokens already produced by lexical analysis and checks whether they are arranged according to the grammar rules of the programming language (which can be expressed as a syntax diagram or in Backus-Naur Form), typically building a parse tree that represents the structure of the expression if it is valid. Only once the expression has passed this check can code generation safely convert it into RPN and then machine code. [2 marks]: [1] for naming code generation, [1] for correctly describing syntax analysis as the preceding stage.
Final answers
- (a)
a b + c d - * e / - (b) The expression evaluates to 8 (stack trace:
[6],[6,2],[8],[8,9],[8,9,5],[8,4],[32],[32,4],[8]). - (c) Code generation produces the RPN/machine code; the preceding stage is syntax analysis, which checks the token stream against the language’s grammar.