Programming language principles, part 1, CS 288, April 23, 2007

Each of the three questions is worth 20 points

This question deals with the FIRST and FOLLOW sets used in parsing.
1. (8 points) Given the context-free grammar below, compute the sets FIRST(S), FIRST(VP), FOLLOW(VT), and FOLLOW(Det). In this grammar, nonterminals are represented by capitalized symbols, and the start symbol is S.
```
      S → NP VP
     NP → Det Adjs N
   Adjs → ε | Adj Adjs
     VP → VI | VT NP
    Det → a | the
    Adj → big
      N → dog | cat
     VI → arrived
     VT → saw | chased
```
2. (4 points) Describe briefly how FIRST and FOLLOW sets are used in recursive descent parsing algorithms.
3. (4 points) Describe briefly how FIRST and FOLLOW sets are used in table-driven top-down parsing algorithms.
4. (4 points) Describe briefly how FIRST and FOLLOW sets are used in shift-reduce parsing.
In numerous applications, it is convenient if functions are allowed to take other functions as arguments. For example, it's convenient to allow a sorting function to take as an argument a function that compares pairs of elements.
1. Find the value of the expression (fold + '(2 3 4) 0) in Scheme, if fold is defined by
```
(define fold (lambda (f l i)
  (if (null? l) i
      (f (car l) (fold f (cdr l) i)))))
```
2. In C, functions can't be passed directly to other functions. How could the passing of a comparison function to a sorting function be simulated in C?
3. In Java, functions (i.e., methods) cannot be passed directly to other functions. However in Java there is a sort method in the Collections library class that takes a List argument and a Comparator argument. Here, Comparator is an interface (that is, a class with no members other than abstract methods). Describe how Java can use this mechanism to sort lists.
4. In the functional language Scheme, the value bound to a function name is a closure with two components. One of these components points to the function's code, and the other points to the environment to be used when the function is applied. Since Scheme is statically scoped, this environment must represent the environment in which the function is defined.
  Describe how this environment component is initialized. Assume that the language is being interpreted rather than being compiled, so that the initialization necessarily takes place at run time.
5. Why doesn't C need to maintain an environment component for closures?
This question deals with the interaction between hardware issues and programming issues.
1. What is a frame pointer? Why might a compiler or processor dedicate a register to hold frame pointers?
2. Describe briefly how a cache miss can lead to a pipeline stall.
3. Give two additional sources of pipeline stalls besides cache misses.
4. Answer one of the two questions below:
  1. Why can it be awkward to have two instructions in an instruction set that take different amounts of time to complete?
  2. Why can it be awkward to have two instructions in an instruction set that take different amounts of space?
5. CISC machines commonly use condition codes. What is a condition code? Why are condition codes found less often on RISC machines than on CISC machines?