• Introduction
• 1. 1.Introduction
• 2. 2.A Simple Syntax-Directed Translator
• 3. 3.Lexical Analysis
• 4. 4.Syntax Analysis
• 5. 5.Syntax-Directed Translation
• 6. 6.Intermediate-Code Generation
• 7. 7.Run-Time Environments
• 8. 8.Code Generation
• 9. 12.InterProcedural Analysis
• Published with GitBook

# Exercises for Section 7.3

### 7.3.1

In Fig. 7.15 is a ML function main that computes Fibonacci numbers in a nonstandard way. Function fibO will compute the nth Fibonacci number for any n >= O. Nested within in is fib1, which computes the nth Fibonacci number on the assumption n >= 2, and nested within fib1 is fib2, which assumes n >= 4. Note that neither fib1 nor fib2 need to check for the basis cases. Show the stack of activation records that result from a call to main, up until the time that the first call (to fibO(1)) is about to return. Show the access link in each of the activation records on the stack.

``````fun main() {
let
fun fibO(n)
let
fun fib1(n) =
let
fun fib2(n) = fib1(n-l) + fib1(n-2)
in
if n >= 4 then fib2(n)
else fibO(n-l) + fibO(n-2)
end
in
if n >= 2 then fib1(n) else 1
end
in
fibO(4)
end ;
``````

Figure 7.15: Nested functions computing Fibonacci numbers

activation tree: activation stack when first call to fib0(1) is about to return: ### 7.3.2

Suppose that we implement the functions of Fig. 7.15 using a display. Show the display at the moment the first call to fibO(1) is about to return. Also, indicate the saved display entry in each of the activation records on the stack at that time. ￼ 