Solutions -- programming language principles, part 1, CS 288, April 24, 2006

1. The nodes of a parse tree necessarily correspond to the left-hand sides of the rules used to build it, and their children correspond precisely to the symbols on the right-hand side of the rule. Compared to a parse tree, a syntax tree tends to have fewer nodes (cf. Scott, p 19), and different sorts of data in its nonleaf nodes. Some rules of a parse tree may be unrepresented in a corresponding syntax tree.
2. Note that the grammar given in the question has no need for parentheses, since they will not appear in syntax trees.
```
Program -> E
E -> E + E | E - E | E * E | E / E | ( E ) | ID
```
3. No. For one thing, it is left-recursive. It's also ambiguous, and thus not a realistic candidate to be used as part of a programming language grammar.
4. ```
        Program
           |
           *
         /   \
        +     -
       / \   / \
      a   b c   /
               / \
              d   e
```
1. For the first fragment, zero-argument constructors are invoked for a and b, and copy constructors are invoked for c and d. For the second fragment, there are separate invocations of the appropriate zero-argument constructors for a, c, d, and b, and then assignment operators are invoked to assign new values to c and d.
2. Lisp uses the reference model. Java uses the value model for its built-in types, and a reference model for user-defined types.
3. A shallow notion of equality would simply require two expressions to refer to the same object. A deeper notion of equality can be defined recursively as long as shallow equality or another different notion of equality is used to terminate the recursion.
1. In Scheme, yes; in Ada-83, no.
2. So that an appropriate referencing environment may be set up when the corresponding function is called
3. C does not allow nested subroutines.
4. 7
5. After evaluation of (p 5), the binding of p's local variable a to 5 is still available for the addition that is performed when ((p 5) 2) is evaluated.