[CB-Logo]
Compilerbau I WS97/98
Übungen

Blatt 3

Abgabe: Montag, 10.11.1997

(ggf. Lösungen)

[Compilerbau-Homepage]

Aufgabe 1 (15 Pkt)

Die folgenden Nichtterminale aus der ab Seite 123 Script gegebenen Grammatik für MML lassen sich auch als Tokenklassen zusammenfassen und durch reguläre Mengen beschreiben: <Identifikator>, <int.-Zahl> und <real-Zahl>.
  1. (9 Pkt) Geben Sie für jedes der o.g. Nichtterminale jeweils einen aequivalenten regulären Ausdruck und den dazugehörigen Automaten (gezeichnet oder durch Text) an.
  2. (5 Pkt) Finden sie anhand der Grammatik die Schlüsselwörter in MMS. Wählen sie dann daraus vier aus, und geben Sie für diese vier einen (gemeinsamen) regulären Ausdruck und einen äquivalenten analysierenden Automaten an.
  3. (1 Pkt) Ist 
      program begin = begin _begin: goto begin end.
    ein Satz in MML entsprechend der Grammatik?

Aufgabe 2 (5 Pkt)

Seien folgende Sprachen gegeben:
L1 = { anbn | n >= 1 } und
L2 = { aibj | j = i2 }
Zeigen Sie:
  1. (2 Pkt) L1 ist kontextfrei.
  2. (3 Pkt) L2 ist nicht kontextfrei.
Ist L1 regulär?

Hinweise

Die für den ersten Teil von Aufgabe 1 verwendeten Regeln sind 
  <Identifikator> ::= <Buchstabe> | <Buchstabe><Idf.ende>
  <Idf.ende>      ::= <B.o.Z> | <B.o.Z><Idf.ende> | _<B.o.Z> | _<B.o.Z.><Idf.ende>
  <B.o.Z.>        ::= <Buchstabe> | <Ziffer>
  <Buchstabe>     ::= A | ... | Z | a | ... | z
  <Ziffer>        ::= 0 | ... | 9
  <int.-Zahl>     ::= <Ziffer> | <Ziffer><int.-Zahl>
  <real-Zahl>     ::= <int.-Zahl>.<int.-Zahl> | .<int.-Zahl> | <int.-Zahl>.

[Compilerbau-Homepage]
IfI Mathe WWU
Dietmar Lammers
Last modified: Mon Nov 3 09:48:27 MET 1997