# Work Note 5, DM546, Spring 2018

## Lecture February 16

• Abstract Syntax Trees.
• Weeding.
• Symbol tables.
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.

## 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.

• With the GAS 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.