Gegeben Sei folgende Sprache:

L = { axnb | x=a oder x=b, n>=0 }

1. Zeichnen Sie einen Automaten auf, der diese Sprache akzeptiert (5Pkt)
2. Geben Sie den Automaten formal an, entsprechend der Definition endlicher Automaten. (5Pkt)
3. Gibt es einen deterministischen endlichen Automaten, der L akzeptiert? Falls ja, geben Sie einen solchen an. (6Pkt)

Zeigen oder wiederlegen Sie, das L kontextfrei ist, für

1. L = { anb2nc3n | n>0 } (10Pkt)

Sei folgende Grammatik gegeben:

 G = ( {S,A,B,C}, {a,b}, P, S)
 P = { S ::= eps | ABA | BC | DB ,
       A ::= eps | aA ,
       B ::= eps | bB ,
       C ::= cC ,
       D ::= dD | A }
	

Geben Sie eine eps-freie Version der Grammatik an (12Pkt)

Für die Grammatik

 G = ( {A,M}, {a,t}, P, A )
 P = { M ::= v | M * v , A ::= M | A + M }
	

1. Attributieren Sie die Produktionen von G so, daß A.val als Wert die Auswertung der Eingabe erhält. Gehen Sie dabei davon aus, das der Lexer beim Einlesen einer Zahl das Symbol v und dann die Funktion Value(v) den Zahlwert liefert, der zu v geparsed wurde. (9Pkt)
2. Prüfen Sie ihre Attributierung aus dem ersten Teil, indem Sie den Strukturbaum für den Ausdruck 4 * 3 + 2 aufzeichnen, und an den Knoten die jeweiligen Attribute vermerken. (7Pkt)

Zerlegen Sie den Ausdruck

(((( a + b ) / c ) + ( a * f )) / b )

nach der Kellermethode. Geben Sie dabei bei jedem Schritt auch die freien Hilfsvariablen an. (9Pkt)

1. Welche Bedeutung hat die reduzierte Anfangsadresse eines Feldes, und wie berechnet man sie? (7Pkt)
2. Wieviel Speicherzeller werden für das Feld

   var a array[0:12,-8:2] of boolean

   benötigt? (4Pkt)

Geben Sie den Identifikatorenkeller für folgendes Programm an (16Pkt):

  programm Keller = 
   begin
    var a: integer;
    var x: real;
    var f: array[0..2] of real;
    proc mix(y:real) =
     begin
      var a: real;
      a := y;
     end;
    proc max(u:integer,w:integer) =
    begin
      proc diff(v:integer) =
      begin
       var x: real;
       x := 5.0/v;
      end;
      u := 2 * w;
      diff(u);
    end;

    mix(x);
    max(a,a);
   end.
      

Erläutern Sie, woher das Laufzeitsystem die notwendigen Informationen erhält, um die Inhalte der 5 Linkage-Zellen eines neu anzulegenden Festspeicherblocks festzulegen. (14Pkt)

1. Welche Code wird für die folgende Anweisung erzeugt, wenn a und b gewöhnliche Identifikatoren sind, und x ein formaler Parameter? (6Pkt)

      a := b + x
   	  

2. Welcher Code wird für folgendes Programm erzeugt? (Die Ellipsen stehen für beliebigen Code und können auch im generierten Code durch drei Punkte dargestellt werden) (10Pkt)

    programm Demo =
     begin
      ...
      var   a: integer;
      var   b: integer;
      proc  p(x:integer) = begin a:=x end;
      ...
      a := b;
      p(a);
      ...
     end.