Homework 1

Due Friday, September 30 at the start of class. Late homeworks will be accepted, with a 20% penalty, until the corrected papers are returned to the class. You may discuss the problems with other students, but your submitted work should be done independently. These problems are from Chapter 3 of the text.

(3.2a) Given the grammar G=
```
A --> Ba | bC
B --> d | eBf
C --> gC | g
```
determine which of the following strings are in L(G). Construct parse trees for those that are.
```
bg  bffd  bggg  edfa  eedffa  faae  defa
```

(3.5) Given the grammar

S --> aS | SB | d
B --> Bb | c

the parse tree below shows the derivation of the string aadccb. Show that this grammar is ambiguous by exhibiting a different parse tree for the same string.

   S
  / \
 /   \
a     S
     / \
    /   \
   a     S
        / \
       /   \
      S     B
     / \   / \
    /  |   |  \
   S   B   B   b
   |   |   |
   |   |   |
   d   c   c

(3.9) Our usual expression grammar
```
E --> E+T | E-T | T
T --> T*F | T/F | F
F --> (E) | i
```
can't be used as is in a predictive parser because it has left recursions. Someone had the idea that he could remove left recursions from this grammar by changing it to
```
E --> T+E | T-E | T
T --> F*T | F/T | F
F --> (E) | i
```
Show that this isn't such a great idea by (a) drawing parse trees for a-b-c using both the original and the revised grammar and (b) using the trees as a guide to determine the results of the corresponding computations if a=3, b=5, and c=8.
(3.11) Find the FIRST and FOLLOW sets for the grammar
```
S --> ABC
A --> a | Cb | e
B --> c | dA | e
C --> e | f
```
(Note the difference between the terminal e and the empty string e.)