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

Blatt 2

Abgabe: Montag, 3.11.1997

(ggf. Lösungen)

[Compilerbau-Homepage]

Aufgabe 1 (5Pkt)

Geben Sie eine Grammatik für arithmetische Ausdrücke in polnischer Postfix-Notation mit den Operatoren + - * und / an.
  1. (2Pkt) Verwenden Sie dabei nur ganze Zahlen, die Ihnen aus der lexikalischen Analyse als Token INTEGER übermittelt werden.
  2. (3Pkt) Erweitern Sie den Eingaberaum um Float-Zahlen, die als Token FLOAT geliefert werden. Berücksichtigen Sie in der Syntax die Typwandlungskonventionen!

Aufgabe 2 (3Pkt)

Sei eine kontextfreie Grammaktik G=(N,T,P,S) in Greibach-Normalform gegeben, und ein Wort w aus T* so daß sich w in k Schritten aus S herleiten läßt ( S k--> w ).
  1. Können Sie eine Abschätzung für |w| angeben?
  2. Sei |w|=n. Wie groß ist k dann maximal?

Aufgabe 3 (2Pkt)

Schreiben Sie die folgenden, in LEX-Schreibweise angegebenen regulären Ausdrücke in die Notation der Vorlesung um.
  1. Das Schlüsselwort begin: 
      begin
  2. Float-Zahlen in Exponentschreibweise, z. Bsp. '+123e-12' 
      [\+-]?[0-9]+[eE](-?[0-9]+)?

Aufgabe 4 (10Pkt)

Der Darstellungsteil eines einfachen Terminalprogramms erhält Zeichen als Eingabe und stellt diese auf dem 24-Zeilen x 80 Spalten-Schirm dar. Besonders behandelt werden folgende Zeichenfolgen (wobei ESC das Zeichen mit dem ASCII-Code 27 ist):
Zeichenfolge Bedeutung
ESC 1 Cursor zur oberen linken Ecke (Pos. (1,1))
ESC L 1 Cursor zum Beginn der Zeile
ESC C D Cursor eine Zeile nach unten.
ESC C R Cursor eie Spalte nach rechts
ESC d Lösche von Cursorposition bis zum Zeilenende
ESC D Lösche von Cursorposition bis zum Schirmende
  1. (4Pkt) Konstruieren Sie einen vollständigen endlichen Automaten, der diesen Aspekt des Terminalprogramms realisiert. Beschreiben Sie dazu die Zustände textuell.
  2. (3Pkt) Minimieren Sie die Zustandsmenge des Automaten, bzw. zeigen Sie, daß Ihr Automat bereits minimal ist. Benutzen Sie dazu den Algorithmus aus dem Script bzw. den Übungen.
  3. (3Pkt) Erweitern Sie das Terminalprogramm um einen automatischen Zeilenumbruch am Zeilenende. Welche Zusatzinformation brauchen Sie, und wie können Sie diese sinnvoll modellieren?

[Compilerbau-Homepage]
IfI Mathe WWU
Dietmar Lammers
Last modified: Mon Oct 27 11:26:36 MET 1997