Compiler Construction
Spring 2000
Assignment I

Due : February 9.

1. from text, page 79: problem 2.5 (binary strings that represent numbers
divisible by 3).

2. from text, page 80: problem 2.16 (the dangling else problem).

3. Read the code for scanning numeric literals (scn-nlit.adb), and draw the
corresponding finite-state automaton for numeric literals in Ada. Note the
error transitions as well, and label them with the error message from the
GNAT source.

4. It is well-known that the language defined over the alphabet {a, b, c}
and that consists of strings of a number of a's followed by the same number
of b's and the same number of c's:

                         n  n  n
                        a  b  c

is not context-free. It is less well-known that its complement, that is to
say the language that includes all the strings made of {a, b, c} but never
the strings described above, IS context-free. Prove it by writing a grammar
for it. Try to make the grammar as concise as possible.

4. Read section A.5 and A.9 of "The C++ programming language", 3rd edition,
by Bjarne Stroustrup, in particular pages 802 and 812, and make sure you
understand the nature of the syntatic ambiguites involving functions and
declarations, and those involving templates and comparison operators.