Programming Languages assignment I

Assignment I

Due date Tuesday September 25.


1. In FORTRAN, the exponentiation operator ** associates to the right, so
that  A ** B ** C means  A ** (B ** C), while the other arithmetic operators
associate to the left:  A - B - C means (A - B) - C. Write a grammar for
expressions in FORTRAN, that includes the arithmetic operations and exponentiation,
and that reflects these rules of associativity.

2. Consider the following grammar, which is a small subset of the grammar
for declarations in C / C++:

  N = {Declaration, Declarator, Type}
  T = {char, int, id, '*', '(', ')' ';'}

  Declaration  => Type Declarator ;
  Type         => int | char

  Declarator   => '*' Declarator
               |  Declarator '(' Type ')'
               |  id

Show that this grammar is ambiguous, by constructing a string that has more
than one parse tree. Explain in words the nature of the ambiguity, and
find out how the ambiguity is resolved in C / C++.

3. It is well known that the language L:

      L = { a^n b^n c^n}

consisting of strings over the alphabet {a, b, c}  that have the same
number of a's, b's and c's, is not context-free. This means that it is not
possible to write a CFG grammar for this language. Now, the complement of
L is the language over the alphabet {a, b, c} that contains all the strings
that do NOT have this form, Show that this language is context-free, by
writing a grammar for it. Hint: the language contains strings that either:

a) don't start with an a,
b) don't end with a c,
c) start with more a's than b's,
....

There is more than one answer to this question. Try to find the shortest
grammar that covers all cases. The resulting grammar will be most likely
ambiguous.