Programming language principles, part 1, CS 288, April 24, 2006

Each of the three questions is worth 20 points

1. What is the difference between a parse tree and a syntax tree?
2. Construct a context-free grammar that has start symbol Program, preterminal symbol ID, and one other nonterminal symbol, and is consistent with the simplified attribute grammar given below.
3. Is the grammar that you constructed an LL(1) grammar? Justify your answer.
4. Show the syntax tree for the expression (a + b) * (c - d / e) that is consistent with the given simplified attribute grammar. Note that you don't need to know about the attributes or annotations to answer this question.
```
program → expr
'+' : expr₁ → expr₂ expr₃
'-' : expr₁ → expr₂ expr₃
'*' : expr₁ → expr₂ expr₃
'/' : expr₁ → expr₂ expr₃
id : expr → ε
```
Recall that in the value model of variables, a variable is a named container for a value, while in the reference model, a variable is a named reference to a value.
1. (8 points) Describe the difference between the behaviors of the the two C++ code fragments given below, assuming that all of the constructors and assigment operators that are invoked are properly defined:
```
       // fragment 1                  // fragment 2
       foo a;                         foo a, c, d;
       bar b;                         bar b;
       foo c = a;                     c = a;
       foo d = b;                     d = b;
```
2. (8 points) For the two languages Lisp and Java, state whether the language uses a value model or a reference model for names, or both. If your answer is "both", state under what conditions the language uses each model.
3. (4 points) In the reference model of variables, there are at least two different relevant types of equality. Describe briefly two different types of equality under this model.
This question deals with the treatment of subroutines as values in programming languages. Recall that deep and shallow binding refer to early and late binding of referencing environments, respectively. Also recall the following definitions:
A value is a first class value iff it can be passed as a parameter, returned from a subroutine, and assigned into a variable. A closure consists of a reference to the code for a subroutine, and a reference to an environment.
1. Are subroutines first class values in Scheme? in Ada-83?
2. Why is there an environment component in a closure?
3. Why doesn't it matter whether C uses deep binding or shallow binding?
4. Scheme uses static scoping and deep binding. Recall that it also uses a prefix notation for functions. What is the value of ((p 5) 2) given the following definition of p?
```
        (define (p a)
          (lambda (x) (+ x a)))
```
5. How does the example of part 4 above show that in Scheme, lifetimes of local variables can extend past the end of their scope's execution?