Formale Sprachen A

Thema dieses Semesters:

Theoretische Grundlagen des Compilerbaus

Beschreibung der Veranstaltung:

Die theoretischen Grundlagen des Compilerbaus sind sehr eng mit der klassischen Theorie der formalen Sprachen verknüpft. Beispielsweise basieren wichtige Verfahren zur lexikalischen Analyse auf der algorithmischen Nutzung grundlegender Konzepte aus der Theorie der regulären Sprachen wie reguläre Grammatiken, endliche Automaten, reguläre Ausdrücke. Sogenannte Parser sind für die syntaktische Analyse von Bedeutung und ihre Konstruktion basiert auf Konzepten der Theorie der kontextfreien Sprachen wie kontextfreie Grammatiken und Pushdownautomaten.

Wir wollen uns in dieser Veranstaltung eingehender mit dem Teil der Theorie der formalen Sprachen beschäftigen, der für die Entwicklung von Parsern und Compilern von Bedeutung ist. Unser Schwerpunkt wird dabei auf grundlegenden Sichtweisen liegen und sich nicht auf konkrete Anwendungen, wie beispielsweise das Compilen von Hochsprachen beschränken. Unser Ziel ist es viel mehr, die Theorie grundlegender und im Bereich des Compilerbaus immer wiederkehrender Prinzipien zu verstehen.

Ein Beispiel: Das Wortproblem, also die Zugehörigkeit eines Wortes w zu einer kontextfreien Sprache L zu überprüfen - darin besteht im Wesentlichen die syntaktische Analyse beim Compilen -­­ kann mit dem CYK Algorithmus in Laufzeit O(|w|^3) gelöst werden (unter der Annahme, dass die Beschreibung von L als Konstante angesehen wird). Dieser Algorithmus ist aber für die Praxis, beispielsweise für die Implementierung eines Compilers, ungeeignet, da die Laufzeit zu hoch ist. Deshalb besteht ein wesentlicher Teil der Theorie des Parsens daraus, schnellere Algorithmen für das Lösen des Wortproblems zu finden.

Materialien:

Materialien werden über die zugehörige STUD.IP Seite zur Verfügung gestellt.

Termin:

Dozenten:

Dr. Markus L. Schmid