CB-I im WS99/00Blatt 1 mit Lösungen |
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.
+-------------+ | 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| +---+
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?
+---------------+ 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
bison
-Info - ein
Interpreter für arithmethische Ausdrücke!)
Polnische Postfix-Notation: Die
Operatoren werden hinter die Operanden geschrieben,
z.Bsp. sollte 7 3 4 + -
Null ergeben.
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 }
.
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}
L1 = {aibj | i,j aus N0, i
ungleich j }
und
L2 = { aibj | i,j aus N0,
i=j2 }
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
.
L2
ist nicht kontextfrei. Man zeigt das mit
Hilfe des Pumping-Lemmas:
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.