CB-I im WS99/00

Blatt 1 mit Lösungen

Aufgabe 1

Sie verfügen über einen C-Compiler, der für Intel-386-Code geschrieben ist, und auch solchen Code erzeugt. Über diesen Compiler verfügen Sie auch im Quellcode. Sie möchten nun diesen Compiler so optimieren, daß er Code für Intel-586 (Pentium) generiert, und auch für diese Architektur effizient läuft. Beschreiben Sie ihr Vorgehen, auch mit Hilfe von T-Diagrammen.

Lösung

Folgendes Vorgehen ist möglich:
     +-------------+
     | C       	386|
     +----+   +----+
          | C |
          +---+
            |   (Codeerzeugung muss von Hand angepasst werden)
            V
     +-------------+     +-------------+
     | C       	586|     | C        586|   Dieser Compiler erzeugt
     +----+   +----+     +----+   +----+   586-code und laeuft auch
          | C |+-------------+|386|    	   auf einen 586, aber noch
          +---+| C        386|+---+    	   nicht unbedingt effizient
               +----+   +----+	|          Wir "bootstrappen" ihn:
                    |386|	|
           ||       +---+	|
	              +---------+
     +-------------+  |  +-------------+
     | C        586|  |  |C        586 |   Da ist der benutzbare,
     +----+   +----+  V  +----+   +----+   effiziente Compiler.
          | C |+-------------+|586|	   Wir koennen seine Fuktion
          +---+| C        586|+---+	   aber noch testen:
               +----+   +----+	|
                    |386|   	|
           ||       +---+   	|
	              +---------+
     +-------------+  |  +-------------+
     | C       586 |  |  | C       586 |   Sind dieser und
     +----+   +----+  V  +----+   +----+
          | c |+-------------+|586|
          +---+| C       586 |+---+
               +----+   +----+  |
                    |586|	|
           ||       +---+	|  ||?
		      +---------+
     +-------------+  |  +-------------+
     | c       586 |  |  | C       586 |   dieser Compiler bitweise gleich?
     +----+   +----+  V  +----+   +----+   Dann hat der Compiler den
          | c |+-------------+|586|        Test bestanden!
          +---+| C       586 |+---+
               +----+   +----+
                    |586|
                    +---+
     

Aufgabe 2

Sie verfügen über den Java-Quellcode einer Java-Virtual-Machine (JVM) in Version 2, und über eine laufende JVM in der Version 1. Können Sie damit eine laufende JVM2 erzeugen? Wenn ja, ist diese effizient?

Lösung:

Man kann eine Laufende JVM2 erzeugen, und zwar
  +---------------+   Die nebenstehende Box, als Programm 
  | Java      JVM2|   ausgeführt auf der JVM1, realisiert
  +----+    +-----+   eine JVM2. Effizient kann sie aber nicht
       |Java|         sein, da doppelt interpretiert werden 
       +----+         muss.
        JVM1
      

Aufgabe 3

Gegeben sei ein Interpreter für arithmetische Ausdrücke. Werden für diesen auch Techniken des Compilerbaus benutzt? Welche?

Lösung:

Ja, zum Zerlegen der Eingabeausdrücke, ggf. auch zur Definition der erlaubten Eingabesprache, werden Techniken der lexikalischen Analyse und ggf. auch der Syntaxanalyse verwendet. (vgl. auch das Beispiel der bison-Info - ein Interpreter für arithmethische Ausdrücke!)

Aufgabe 4

Geben Sie eine kontextfreie Grammatik für einen Taschenrechner an, der in polnischer Postfix-Notation arbeitet.

Polnische Postfix-Notation: Die Operatoren werden hinter die Operanden geschrieben, z.Bsp. sollte 7 3 4 + - Null ergeben.

Wandeln sie die Grammatik dann in Chomsky-Normalform um.

Lösung:

(Wir machen hier nur einen ganz einfachen Interpreter)
  1. Man kann die Grammatik einfach angeben: G={{exp,op,val},{+,-,/,*,0,1,2,3,4,5,6,7,8,9},P,exp} mit P={ exp::=exp exp op | val, op::=+|-|/|*, val::=0|1|...|9|val val }.
  2. Auch die Wandlung in eine Chomsky-Normalform ist einfach, wir müssen die Regeln mit Hilfe von Hilfs-Nichtterminalen oder direkter Umsetzung von Produktionen umwandlen. Hier reicht sogar ein Hilfssymbol (h1), und nur die exp-Produktionen müssen verändert werden. P2 enthält damit folgende Produktionen:
    exp ::= exp h1
    h1 ::= exp op
    exp ::= 0|1|...|9
    exp ::= val val
    op ::= +|-|/|*
    val ::= 0|1|...|9
    val ::= val val
    Als Grammatik ergibt sich natürlich G2={{exp,op,val,h1}, {+,-,/,*,0,1,2,3,4,5,6,7,8,9}, P2, exp}

Aufgabe 5

Welche der beiden u.a. Sprachen ist kontextfrei?

L1 = {aibj | i,j aus N0, i ungleich j } und

L2 = { aibj | i,j aus N0, i=j2 }

Lösung:

  1. L1 ist kontextfrei, denn sie läßt sich mitteles der folgenden einfachen Grmmatik erzeugen: G=({S,A,B}, {a,b}, P, S) mit P = { S::=Bb|aA, A::=aA|aAb|eps, B::=Bb|aBb|eps } Die S-Regel verzweigt in einen A- nzw. in eine B-Zweig, und erzeugt dabei schon mindestens ein a bzw. b. Im A-Fall werden dann mindesten soviele a wie b erzeugt, und im B-Fall analog mindestens soviele b wie a.
  2. L2 ist nicht kontextfrei. Man zeigt das mit Hilfe des Pumping-Lemmas:
    Angenommen, L2 sei kontextfrei, und k die entsprechende Schranke des Pumping-Lemmas, und z=uvwxy ein Wort aus L2, das die Bedingungen des Lemmas erfüllt. Demnach sind alle Wörter der Form uviwxiy aus L2. Demzufolge können weder v noch x sowohl a's als auch b's enthalten, sonst hätten die resultierenden Wörter b's vor a's stehen, was nicht in der Sprache vorkommt. Sind beide nur aus a's bzw. beide nur aus b's, wird immer nur einseitig eine Buchstabensorte vermehr, was der quadratischen Wortbildungsregel von L2 widerspricht. Die Bildungsregel ist aber auch verletzt, wenn v nur aus a's und x nur aus b's besteht.
    Damit haben wir alel Fälle betrachtet, und erhalten insgesamt einen Widerspruch zur Annahme.

Dietmar Lammers
Last modified: Wed Nov 17 15:58:44 MET 1999