CS 217: Programming Languages

Written Assignment #1

Assigned on Wednesday, January 22.
Duein class on Monday, January 27.

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

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

1(b). 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.)

3. Consider the following C++ code:

while (x < 5)
x++;

For each syntactic component of the above code (variable names, operation symbols, etc.), list the various bindings that are necessary to completely determine the semantics of the statement when it is executed. For each binding, identify the binding time used in the language.

Also turn in Problems 3.6 and 3.11 from your textbook (Scott).

Problems 1-3 above are inspired by or originally written by Pratt & Zelkowitz.