Aufgabe 1

Attributieren Sie die Grammatik aus Bl9/Auf2 so, das das Attribut s.n nach Auswertung der Attribute die normalisierte Darstellung der Ausdrücke enthält, und testen Sie die Attributierung am Ausdruck

( rx - rm ) / rs * 2.0 * rpi

Gehen Sie dabei davon aus, das die Lexer-Funktion StringVal(VAR) die Zeichenreihe liefert, die zum Token VAR geparsed wurde (für REAL, INT entsprechend).

Lösung:

 s::=x   { sn:=x.n; }
 x::= x1=e   { x.n:= "(" x1.n "=" e.n ")"; }    
 x::= e   { x.n:=e.n; }
 e::= e1+p   {e.n:="(" e1.n "+" p.n ")"; }
 e::= e1-p   {e.n:="(" e1.n "-" p.n ")"; }
 e::= p   { e.n:=p.n; }
 p::= p1*a   {p.n:="(" p1.n "*" a.n ")"; }
 p::= p1/p2      {p.n:="(" p1.n "/" p2.n ")"; }
 p::= a   { p.n:=a.n; }
 a::= REAL   { a.n:=StringVal(REAL); }
 a::= INT   { a.n:=StringVal(INT); }
 a::= VAR   { a.n:=StringVal(VAR); }
 a::= (e)   { a.n:=e.n; }
      

Auswertung der Attribute (Das Symbol \___/ bezieht sich jeweils auf die Gesamtableitung des darüberliegenden Teilbaums):

 (   rx    -   rm   )   /   rs   *   2.0   *   rpi
 (   VAR   -   VAR  )   /   VAR  *   REAL  *   VAR             (vom Lexer)
     |         |            |        |         |
     a {n=rx}  a {n=rm}     a {n=rs} a {n=2.0} a {n=rpi}
     |         |            |               
     p {n=rx}  p {n=rm}     p {n=rs}
     |         
     e {n=rx}  
     \_________/
        |
        e {n=(rx-rm)}
 \_________________/
        |
        a {n=(rx-rm)}
        |
        p {n=(rx-rm)}
        \___________________/
                 |
                 p {n=((rx-rm)/rs)}
                 \_____________________/
                           |
                           p {n=(((rx-rm)/rs)*2.0)}
                           \_______________________/
                                     |
                                     p {n=((((rx-rm)/rs)*2.0)*rpi)}
                                     |
                                     e {n=((((rx-rm)/rs)*2.0)*rpi)}
                                     |
                                     x {n=((((rx-rm)/rs)*2.0)*rpi)}
                                     |
                                     s {n=((((rx-rm)/rs)*2.0)*rpi)}

      

Aufgabe 2

Gegeben sei folgendes Programm:

 programm Test = 
  begin
   var res : integer;
   var i: integer;
   var a : real:
   proc fak (x : integer) = 
    begin
     var a : boolean;
     res = res * x;
     x := x - 1;
     if ( x <> 0 )
     then
      fak(x);
     fi
    end;
   res := 1;
   i := 2;
   f(i);
  end.
      

1. Geben Sie den Identifikatorenkeller für das Programm an.
2. Geben Sie den erzeugten Code für das Programm an.
3. Geben Sie den Laufzeitkeller dazu an.

Lösung:

1. Name	Typ	Dimension	Relativadresse	stat. Niveau sI	Blockzähler
   res	integer	1	5	0	1
   i	integer	1	6	0	1
   a	real	1	7	0	1
   fak	proc	1	8	0	1
   x	integer	1	5	1	2
   a	boolean	1	6	1	2

   (Hinweis: Unter Dimension verstehen wir hier die Anzahl der Zellen, die für die Speicherung des Wertes benötigt werden, bei gewöhnlichen Variablen 1, bei Feldern entsprechend Zeilen*Spalten.
   Bei Prozedurdeklarationen gehört der Prozedurname zum umgebenden Block, und wird damit mit demselben statischen Niveau gezählt wie eine gewöhnliche Varaible in dem Block. Die Prozedurparameter gehören allerdings schon zum begin-end-Block der Prozedurdeklaration, und erhalten deshalb en höheres statisches Niveau wie auch einen erhöhten Blockzähler.
   Auch für die Speicherung von Prozeduren (proc) wird eine Zelle verwendet, hier wird die Adresse des Codes des Prozedurrumpfes abgelegt. So können wir Prozedurnamen auch als Parameter an andere Prozeduren übergeben.)

2. Adresse/Label	Code	Kommentar
   2000	SRJ "Hauptprogramm Start"	Man kann auch auf diesen Call verzichten, wenn das Laufzeitsystem beim Laden eines Hauptprogramms automatisch diesen SRJ ausführt. Hier werden der Laufzeitkeller und die benötigten Register initialisiert, und der FSB für das Hauptptrogramm reserviert.
   	NOP 9	Der FSB des Hauptprogramms braucht 5 Zellen für die Linkage, und 4 Zellen für lokale Variablen
   	UJP Main	Das Label Main markiert den Anfang des Codes für den Rumpf des Hauptprgramms
   Fak:	NOP 7 & 1	Der Rumpf der Prozedur fak. Wir brauchen einen FSB von 5 Zellen Linkage + 1 Parapeter + 1 lokale Variable. Die Zahl der Parameter ist 1
   	LDA 5,0	Wir laden res in den Akkumulator. Die Relativadresse erhalten wir aus dem Indentifikatorenkeller, der Index des benötigten Indexregisters ist das statische Niveau s von res, das wir ebenfalls aus dem Identifikatorenkeller erhalten.
   2005	MUA,I 5,1	Wir multiplizieren mit x. x ist ein formaler Parameter, deswegen steht in der Zelle für x nur die Adresse, und wir müssen zusätzlich indirekt adressieren, um den Wert von x zu bekommen.
   	STA 5,0	Speichern des Ergebnisses in res.
   	ENA -1	-1 in den Akkumulator
   	ADA,I 5,1	den Wert von x dazuaddieren
   	STA,I 5,1	und wieder wegschreiben.
   2010	LDA,I 5,1	x wieder laden, um die Bedingung des ifs zu prüfen - hier eigentlich überflüssig, da x schon drin stand.
   	AJZ,EQ EndIF	Wenn x=0, springe zu EndIF
   	SRJ "Gewöhnlicher Prozeduraufruf"	Sprung ins Laufzeitsystem, um die Prozedur fak aufzurufen
   	NOP Fak & 0 & 1	Adr(fak) + stat. Niveau sfak + Anz. der Parameter. Das stat. Niveau erhalten wir wieder aus dem Identifikatorenkeller
   	NOP 5 & 1 & F	Parameter ist für diesen Aufruf der formale Parameter x mit Relativadresse 6 und stat. Niveau 1
   EndIf:	UJP "Prozedurende"	Ist die Bedingung nicht erfüllt, sind wir mit der Prozedur fertig.
   Main:	ENA 1	Hier fängt der Rumpf des Hauptprogrammes an. wir laden 1 in den Akkumulator, und
   	STA 5,0	speichern in res.
   	ENA 2	Dann laden wir 2, und
   	STA 6,0	speichern in i
   2020	SRJ "gewöhnlicher Prozeduraufruf"	Nun rufen wir fak(i) auf
   	NOP Fak & 0 & 1	sfak = 0, 1 Parameter
   	NOP 6 & 0 & RIB	Diesmal als Parameter eine gewöhnliche Variable vom Typ integer. Wir geben RIB an, da alle Basistypen gleich behandelt werden. Relativadresse von i ist 6, statisches Niveau 0.
   	UJP "Programmende"	Dieser Code kann ggf. auch wieder vom Laufzeitsystem generiert werden.

3. Wir müssen hier die Aufgabe präzisieren: Wir geben den Laufzeitkeller zum Zeitpunkt des ersten rekursiven Aufrufs der Prozedur fak an. Der Rumpf für diesen zweiten Aufrauf wurde dabei noch nicht ausgeführt. Beginne der Laufzeitkeller an der Adresse 3000, und liege der Code wie oben vorgesehen ab Zelle 2000 im Speicher:

   Adresse	Wert	Bedeutung	Bemerkungen
   3000	0	RK	FSB des Hauptprogramms. RK ist für das Hauptprogramm unnötig. Register IR0 verweist auf diese Zelle.
   	0	dyn. Niveau des dyn. Vorgängers	hat das Hauptprogramm nicht
   	-1	stat Niveau	sHauptprogramm = -1
   	0	ein dyn, Niveau des stat. Vorg.	hat das Hauptprogramm nicht
   	3009	BFS	3000+9, aus dem NOP-Befehl im Code
   	2	Speicherzelle für res	fak ist schon einmal gelaufen, deswegen 2
   	1	Speicherzelle für i	s.o.
   	undef.	Speicherzelle für a	wird nie geschrieben
   	2003	Speicherzelle für fak	Adresse vn fak
   3009	2021	RK	FSB des ersten fak-Aufrufs. Der Wert wird aus dem Register RK, das durch den SRJ gesetzt wird, entnommen.
   	3000	ein dyn. Niveau des dyn. Vorgängers	aus dem Register MDL zum Zeitpunkt des Aufbaus dieses FSB. MDL wird danach mit der Adresse dieser Zelle - 1 belegt.
   	0	sfak	Aus dem NOP bei RK (2021)
   	3000	ein dyn. Niveau des stat. Vorgängers	aus dem IRsfak
   	3016	BFS	MDL+7. Die 7 entstammt dem NOP bei der Adresse fak, die Adresse von fak aus dem NOP bei RK(=2021)
   	3006	Speicherzelle für x	enthält die Adresse von i
   	undef.	Speicherzelle für a	wird nicht benötigt, und auch nicht geschrieben
   3016	2013	RK	FSB des zweiten fak-Aufrufs. RK wieder aus dem Register RK
   	3009	dyn.Niveau des dyn. Vorgängers	aus dem Register MDL zum Zeitpunkt des Aufbaus dieses FSB. MDL wird nach Anlegen dieses FSBs mit der Adresse 3016 belegt.
   	0	sfak
   	3000	ein dyn. Niveau des stat. Vorgängers	aus IRsfak
   	3023	BFS	3016+7, aus den NOPs (s.o.)
   	3006	Speicherzelle für x	enthält die Adresse von i, kopiert aus dem x aus dem NOP in Zelle 2014
   	undef.	Speicherzelle für a
   3023			freier Speicher

   Nach Anlegen des letzten Festspeicherblocks enthält das Register MDL den Wert 3016, da das die Adresse des dem momentanen dynamischen Niveau zugeordnetem FSB ist. Auch IR1 wird auf diesen Wert gesetzt, da sfak+1=1 ist..