Work Note 5, DM546, Spring 2018
Lecture February 16
Background material: Appel Chapters 4 and 5.
You can find support for my approach at the lecture with regards to
symbol tables in the Supplementary Notes for DM546;
see the literature page.
Abstract Syntax Trees.
Exercises February 22
IMADA's Computer Lab has been reserved and is used for this exercise slot,
so show up there.
These are the exercises for this date and also for the next
exercise session. It is important to get things
to work in practice as a means of understanding all the
underlying principles. Using two exercise sessions, you can
try things out, get questions cleared up, and try again.
Run the factorial example by hand on paper and/or blackboard
with the number 3 instead of 5.
Keep detailed track of the stack and the content of all registers.
Make a debug function (in assembler) which prints
the contents of the registers.
It is most convenient, when this debugging feature is used,
that as little as possible must be written in the interesting
part of the code (to be debuggged), so in this case, you
may violate the call conventions.
examples as a starting point, implement your favorite
O(n2) sorting algorithm
(bubble sort, insertion sort or selection sort).
From the examples, you can see how to handle
start and finish, interfacing the operating system,
and how to allocate space for a number of integers.
Place data directly into the code and print the result
(using repetitive calls to
printf) after the sorting.
With the factorial example as the starting point,
implement the computation of the n'th Fibonacci number.
Be careful with the stack discipline.
In Appel Chapter 6, there is an illustration of a stack frame.
Here, the static link and local variables (which were omitted
at the lecture) are placed between the arguments and the return address.
One or both of these could in our architecture
may be more naturally be placed after the return address
instead of before.
With Appel Chapter 6 as a starting point, discuss the following points:
Where should the static link point when calling a local function
in ones own scope and a function further out, respectively.
Remember recursive functions in this connection.
When using a variable defined in a scope further out,
which code must the compiler generate in order to find
this variable and where does the compiler find the
necessary information to find out which code to generate?
What code must the compiler generate when a function is called
such that static link will be set up correctly for the called function
and how does the compiler find the necessary information to do this?
Decide yourself on a small program you want to implement in assembler
to try things you may have had difficulties with in the above.