## CSE 428, Spring 2000: Solutions of Midterm 1

### Exercise 1

1. yes
2. no
3. no
4. yes
1. One reason why the grammar is ambiguous is taht there is no rule for associativity of +. Thus a string like 2+3+4 has two different derivation trees.
```            Exp                   Exp
/ | \                 / | \
/  |  \               /  |  \
Exp  +  Exp           Exp  +  Exp
/ | \     |             |     / | \
/  |  \    |             |    /  |  \
Exp  +  Exp Num           Num Exp  +  Exp
|       |   |             |   |       |
|       |   |             |   |       |
Num     Num  4             2  Num     Num
|       |                     |       |
|       |                     |       |
2       3                     3       4
```
2. ```   Exp ::= Exp + A | A
A ::= ~A  | B
B ::= Num | (Exp)
Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
```

### Exercise 2

1. We need to change the production
```   Exp ::= let Ide = Num in Exp end
```
into
```   Exp ::= let Ide = Exp in Exp end
```
2. We only need to change the following line in the "dec" case
```   int k = t->get_left()->get_root()->get-value()
```
into
```   int k = eval(t->get_left(),r)
```

1. 2
2. 2
3. 1

### Exercise 4

• (a) the output is 1
• (b) the output is 2
1. ```

caller of p        p I           A.R. where p is declared
^   ------------------      ^
CL |___|_               |      |
|                |      |
------------------      |
|               _|______| SL
|                |
------------------
|-->|        -----   |<-|---|----|
|   |      x | 1 |   |  |   |    |
|   |        -----   |  |   |    |
|   |      y | 2 |   |  |   |    |
|   |        -----   |  |   |    |
CL |   ------------------  |   |    |
|                       |   |    |
|          q I          |   |    |
|   ------------------  |   |    |
|___|_               |  |   |    |
|                |  |   |    |
------------------  |   |    |
|               _|__|SL |    |
|                |      |    |
------------------      |    |
|-->|        -----   |      |    |
|   |      y | 1 |   |      |    |
|   |        -----   |      |    |
CL |   ------------------      |    |
|                           |    |
|          r I              |    |
|   ------------------      |    |
|___|_               |      |    |
|                |      |    |
------------------      |    |
|               _|______| SL |
|                |           |
------------------           |
|-->|        -----   |           |
|   |      x | 1 |   |           |
|   |        -----   |           |
CL |   ------------------           |
|                                |
|          Q II                  |
|   ------------------           |
|___|_               |           |
|                |           |
------------------           |
|               _|___________| SL
|                |
------------------
|        -----   |
|      y | 2 |   |
|        -----   |
------------------