Written Assignment #1 (individual assignment)

1a. For the following grammar, provide parse trees that show that this grammar is, in fact, ambiguous.

<S> -><S><S> | (<S>) | ()

1b. Give an unambiguous grammar that generates the same language.

2. Write a BNF grammar for the language composed of all binary numbers that contain at least three consecutive 1s. (The language will include the strings 011101011, 000011110100, and 11111110, but not 0101011.)

Do problem 3.1 in your textbook twice: first do it for Scheme, then do it again for Java.

Textbook problem 3.4

Textbook problem 3.10

Textbook problem 3.13

Submit your work on paper at the beginning of class.