Compilerbau [CB]

Wintersemester 02/03
Lehrstuhl für Informatik II
Hauptstudium

Termine

Art	Termine/Ort	Beginn	Veranstalter
V4	Di 8:15 - 9:45 AH V	15.10.	Indermark
	Fr 8:15 - 9:45 AH V
Ü2	Mi 14:15 - 15:45 AH II	23.10.	Indermark, Stolz

Kleingruppenübungen:

Gruppe 1	Mo 14:45 - 16:15	AH II	Ibrahim Armac
Gruppe 2	Mo 16:00 - 17:30	5056	Achim Lücking
Gruppe 3	Mo 17:00 - 18:30	5055	Mladen Jovic

Scheinbedingungen

Für den Übungsschein müssen 50% der Punkte in den Übungen erreicht werden und eine kleine mündliche Prüfung bestanden werden. Die Teilnahme an dieser Prüfung empfehlen wir sehr, da sie eine gute Vorbereitung für die Diplomprüfung darstellt.

Die mündlichen Prüfungen (Dauer: 15 Minuten) finden im Anschluß an die Vorlesungszeit von Montag bis Donnerstag in meinem Büro statt!

Übungen

Die Übungen können in Gruppen, bis zu 3 Studierenden abgegeben werden. Die Übungensblätter werden jeweils mittwochs in der Frontalübung ausgegeben und sind am darauf folgenden Mittwoch abzugeben. Die korrigierten Übungen werden in der Diskussionsstunde am Montag zurückgegeben.

Musterlösungen werden in der Frontalübung am Mittoch besprochen. Weitergehende Fragen können Sie montags in den Diskussionstunden stellen. Außerdem wird hier der Vorlesungsstoff aufgearbeitet und mit weiteren Beispielen vertieft.

Sollten Sie einmal eine Vorlesung/Frontalübung verpaßt haben, finden Sie Übungsblätter und Folienkopien hier online und auch im Regal im Gang des Lehrstuhls für Informatik II.

Folien zur Vorlesung

Einführung
Lexikalische Analyse
Syntaktische Analyse
Semantische Analyse

• Beispiel einer nicht-zirkulären Grammatik, ohne das sie stark nicht-zirkulär ist
• Anwendung des Zirkularitätstests

Die Folien 3.8 & 3.9 werden nachgereicht!

Code-Erzeugung

Übungen

• 1. Übung
• 2. Übung
• 3. Übung Musterlösung lex Musterlösung Alex
• 4. Übung Musterlösung lex-Erweiterung
• 5. Übung
• 6. Übung
• 7. Übung Rekursiver Abstiegsparser: C Haskell
• 8. Übung
• 9. Übung
• 10. Übung

  In der Musterlösung zu Aufgabe 28 finden sich in der goto-Tabelle einige Einträge, die bei einem reduce in der action-Tabelle natürlich nicht dorthin gehören.

• 11. Übung

  Der Fehlerteufel schlägt zu:

  • Die Grammatik von Aufgabe 33 verletzt leider eine für das Verfahren notwendige Eigenschaft. Welche?
  • Die Produktion in Aufgabe 34 muß lauten: B->b
  • Attributauswerter für bison (wird nachgereicht)
  • Attributauswerter für Aufgabe 35 in Haskell

• 12. Übung

  Bei der gedruckten Version der Übung müssen die beiden Produktionen A->Aa / B->Bb durch A->aA bzw. B->bB ersetzt werden, der Index der Attribute ändert sich natürlich entsprechend!

  Beispiellösung Rek. Abstiegsparser in Haskell
• 13. Übung
• 14. Übung Lösung Aufgabe: 42 Lösung Aufgabe: 43
• 15. Übung

Mehr zu Lex:

• man lex
• Dinosaur Compilertools

Über Parser:

• Parsers.org
• Treecc

• Lex & Yacc Spezifikation und Hauptprogramm für Bits und Listen von Knuth

  Übersetzen:

          yacc -d knuth.y
          lex knuth.l
          cc main.c lex.yy.c y.tab.c -lfl
        

• Knuths Binärzahlen mit inheriten Attributen

  Übersetzen:

          bison -d inh.y  -- nicht notwendig 
          lex knuth.l     --    dt.
          cc *.c -lfl
        

• BPS-System mit lex/yacc (Ch.Haselbach)

• Java First/Follow-Tool(D.Friedrich)

• Abstrakte Machine Java Applet (Erhard Schultchen)

Literatur

• A.Aho, R.Sethi, J.Ullman: Compilers - Principles, Techniques, and Tools. Addison-Wesley, 1988
• W.Waite, G.Goos: Compiler Construction. Springer, 1984
• R.Wilhelm, D.Maurer: Übersetzerbau. Springer, 1992
• N.Wirth: Grundlagen und Techniken des Compilerbaus. Addison-Wesley, 1996
• J.R.Levine et al.: lex & yacc. O'Reilly, 1992.

Zuordnung

Praktische Informatik, Theoretische Informatik, Informatik Vertiefung