Kapitel 8 - Hochsprachen und Compiler

Zum Abschluß unserer Tour von den Transistoren bis zur Hochsprache betrachten wir den Compiler der Hochsprache Jack in der Hack-Architektur. Dafür studieren wir zunächst den Aufbau von Jack als einfaches Beispiel für eine Hochsprache, und überlegen, nach welchen Regeln syntaktisch gültige Programme generiert werden. Diese Regeln nennt man die Grammatik der Sprache. Das sogenannte Frontend des Compilers, das wir uns danach anschauen, übersetzt von Jack in die Sprache der VM - das Backend ist der Übersetzer von VM in Machinensprache, den wir schon kennen. Das Fronend besteht aus Syntaxanalyse und Codegenerator. In der Syntaxanalyse durchläuft das Programm zunächst den Tokenizer, der es in eine Liste von Sprachatomen zerlegt, und danach den Parser, der es in eine Hierarchie von Grammatikelementen übersetzt. Danach folgt der Codegenerator, der aus dieser Hierarchie den eigentlichen Code erzeugt. Besonderes Augenmerk verdient hier die Speicherverwaltung, bei der die VM mit ihren Speichersegmenten hilft.

Inhalt

Abschnitt 1 - Einleitung, grundlegende Elemente der Programmiersprache Jack

Folien 1-16

Wir betrachten zunächst allgemein verschiedene Programmierparadigmen und die Entwicklung der symbolischen Programmierung. Wir wollen jedoch insbesondere die Abbildung von höheren Programmiersprachen auf tiefere Ebenen verstehen, und studieren daher als Beispiel die Sprache Jack der Hack-Architektur, welche der objektorientierten Sprache Java nachempfunden ist. Zur Einstimmung schauen wir uns ein paar Beispiele und grundlegende Konstruktionen der Sprache an, um zu verstehen, wie Jack-Programme aufgebaut sind.


Index

00:00 Einleitung: Überblick des Kapitels, Programmiersprachen und -paradigmen
07:17 Einführung in die Programmiersprache Jack, ein erstes Beispielprogramm
10:58 Prozedurale Programmierung in Jack: statische Funktionen einer Klasse
13:25 Klassen in Jack: statische Variablen und Felder
16:05 Der Konstruktur eines Objektes, Heap vs. Static-Segment
20:35 Lokale Variablen vom Typ einer Klasse
22:45 Methoden einer Klasse und der Unterschied zu Funktionen, Freigabe von Objekten
26:45 Eingebaute Datentypen von Jack, Definition eigener Datentypen als Klassen
32:00 Implementation der Beispielklasse "Fraction"


Abschnitt 2 - Vollständige Beschreibung der Programmiersprache Jack

Folien 17-30

Wir verschaffen uns hier einen umfassenden Überblick über die Programmiersprache Jack. Die Sprache ist so einfach gehalten, daß sie auf 13 Folien komplett beschrieben werden kann. Insbesondere betrachten wir bereits ein paar Sprachelemente genauer im Hinblick darauf, wie sie auf das Speichermanagement der VM abgebildet werden müssen, und begründen ein paar der Besonderheiten von Jack, die vor allem dem Wunsch nach einfacher Übersetzung entspringen.


Index

00:00 Einleitung, Elemente der Syntax von Jack
08:00 Datentypen von Jack, Speicheranforderungen für Klassen, Heap vs. Stack
13:45 Arten und Sichtbarkeit von Variablen
16:26 Ausdrücke in Jack (expressions)
19:25 Anweisungen in Jack (statements)
22:10 Unterprogrammaufrufe, Behandlung von Objekten als Argumente
25:30 Struktur eines Jack-Programms
27:20 Besonderheiten der Sprache Jack
31:20 Standardbibliothek und Betriebssystemfunktionen
35:50 Zusammenfassung und Ausblick


Abschnitt 3 - Aufbau eines Compilers: Tokenizer und Parser für Jack

Folien 30-45

Wir betrachten den grundlegenden Aufbau des sogenannten Frontend eines Compilers aus den Modulen Syntaxanalyse (Tokenizer und Parser) sowie Codegenerator. In diesem Abschnitt gehen wir zunächst auf die Syntaxanalyse ein. Der Tokenizer zerlegt zunächst die Eingabedatei in einzelne annotierte Sprachatome, wobei Kommentare und Leerzeichen entfernt werden. Der Parser organisiert die Sprachatome hierarchisch, die Bildungsregeln der Sprachgrammatik bestimmt werden, welche das vorliegende Programm erzeugen. Programmiersprachen benutzen einfache Grammatiken (Jack ist sogar fast vollständig LL(1)), das heisst dass man durch die Prüfung von idealerweise nur des nächsten Tokens bereits die korrekte Bildungsregel der Grammatik bestimmen kann. Insbesondere muss die anzuwendende Regel stets eindeutig sein. Wir betrachten an konkreten Beispielen in Pseudo-Code, wie der Jack-Compiler einzelne Grammatikregeln implementiert.


Index

00:00 Einleitung, grundlegender Aufbau eines Compilers
02:55 Das Frontend eines Compilers, Aufgaben von Tokenizer, Parser und Codegenerator
05:10 Arbeitsweise des Tokenizers, Zerlegung des Programms in annotierte Sprachatome
09:30 Kontextfreie Grammatiken und Parser
11:52 Beispiele für das Parsen von Sätzen in deutscher Sprache, Mehrdeutigkeiten
17:25 Überlegungen zu Bildungsregeln von Ausdrücken in Jack
21:55 Beipiele für Bildungsregeln einer C-artigen Sprache
23:40 Ziel: Aufbau des Parse-Baums für eine Liste von Tokens (Satz)
27:40 Parsen durch Rekursion, die LL(1)-Eigenschaft von Jack (fast) und ein Überblick über die Grammatik
32:50 Beipiel für Parsing-Funktionen: Let-Statement
41:40 Beipiel für Parsing-Funktionen: Statement
44:27 Aufbau der Ausgabedatei, strukturierter Parse-Baum im XML-Format
46:35 Abschliessende Bemerkungen zur Syntaxanalyse, Ausblick


Abschnitt 4 - Aufbau eines Compilers: Codegenerator für die Programmiersprache Jack

Folien 45-61

Wir untersuchen den zweiten Teil des Compiler Frontends der Programmiersprache Jack, den Codegenerator. Hier wird die Ausgabe des Parsers in die Sprache der virtuellen Maschine umgewandelt. Der Codegenerator hat vor allem zwei Aufgaben, die wir im Detail studieren: Zuweisung von Speicherplatz zu den Variablen, was wie schon beim Assembler in Symboltabellen festgehalten wird, sowie das eigentliche Hinausschreiben von Programmcode für die virtuelle Maschine. Wie schauen uns den erzeugten Code für die wesentlichen Sprachelemente von Jack an, und betrachten insbesondere für Jack-Ausdrücke einen Algorithmus, um den Parse-Baum in Code zu übertragen.


Index

00:00 Einleitung, Aufgaben des Codegenerators: Daten- und Anweisungsbehandlung
04:15 Abbildung der Variablen in einer Klasse auf Speichersegmente
07:26 Symboltabellen des Compilers, Sichtbarkeit von Variablen
10:!2 Bemerkung: Sichbarkeit von Variablen in C++ im Vergleich zu Jack
14:10 Lebenszyklus von Variablen, Verwaltung durch VM oder Hochsprache/Programmierer?
16:05 Speicheranforderungen für Objekte auf dem Heap
20:30 Referenzen auf Objekte und Freigabe von Speicher
22:55 Speicherzugriff auf Objekte, Erzeugen von Code für Zugriff auf Felder
27:20 Methodenaufrufe für Objekte, Übergeben des this-Pointers als erstes Argument
30:40 Behandlung von Arrays in Jack durch die virtuelle Maschine
32:50 Erinnerung: Zugriff auf Array-Elemente durch die VM, Übersetzung aus Jack
36:36 Algorithmus: Erzeugung von Code für die Parse-Bäume von Ausdrücken
40:20 Ausführliches Beispiel für die Funktionsweise den Algorithmus
46:55 Codeerzeugung für die Programmablaufsteuerung
51:30 Abschluss des Teils "Rechnersysteme" der Vorlesung !