Computer Science Department
Programming Methods Laboratory

Compilation     winter 00/01
Ecole Polytechnique Federale de Lausanne

1) Find a context-free grammar (BNF) for the following languages. [6 credits]
  • All palindroms over the alphabet T = {a, b, c}. A palindrom is a word that read backwards yields the same word; e.g. aa, bbccbb, etc.

  • All words over the alphabet T = {a, b, c} that have at least two c characters; e.g. ccc, abcbc, cacacac etc.

  • All function calls to the functions f and g. The function f has a single argument, whereas function g can get an arbitrary number of arguments, separated by commas. Arguments are again function calls. It is also possible to pass no parameter to g. Here are examples for function calls: g(),   f(g()),   g(g(), f(g())),   g(g(), g(), g()) etc.

2) Which of the languages of question 1 are regular? Prove for the regular languages that they are indeed regular. [3 credits]

3) The following grammars define regular languages. Give a single EBNF rule without recursion for every grammar. [6 credits]
  • A = a A | A b | c
  • A = A a b | A A | c
  • A = A a | B b B
    B = B b | c
The word cbbca belongs to the language described by the third grammar. Draw a derivation tree with respect to the given BNF.

4) Find an EBNF grammar without recursion that specifies the syntax of floating point numbers. The following numbers should be in the language defined by your grammar: [3 credits]

    -3.1415927, 1.4e10, 127.0e-2, -0.1e-1, .0

Integer numbers like 1, 4589 or -000335 (i.e. numbers without dots in the representation) should not be covered by your grammar.

Please return your solutions to the box in INR, third floor, next to room 321 until Friday, 03.11.2K, 12:00. It is also possible to return your solutions in the next tutorial.