2000 Paper 6 Question 6
Compiler Construction
Describe how a parse tree can be translated into a sequence of assembly language
instructions based on a pattern matching graph derived from a set of tree rewriting
rules where each rule has a cost and a corresponding fragment of code. Illustrate
your answer using the following rules:
Ri = Kk LDI Ri,Kk Cost 2
Ri = add(Ri,Kk) ADDI Ri,Kk Cost 3
Ri = add(Ri,Rj) ADD Ri,Rj Cost 3
Ri = add(Ri,add(Rj,Kk)) ADD Ri,Rj,Kk Cost 4
applied to the following parse tree:
add(K1,add(add(K2,add(K3,K4)),add(K5,K6))) [15 marks]
Discuss the advantages and disadvantages of this approach to code generation.
[5 marks]