Grundlagen des Übersetzerbaus - Cheatsheet

Definition und Zweck eines Compilers

Definition:

Ein Compiler ist ein Programm, das Quellcode in eine Zielprogrammiersprache übersetzt.

Details:

• Überprüft und optimiert den Quellcode.
• Erstellt ausführbare Dateien aus Hochsprachen.
• Phasen: Lexikalische Analyse, Syntaxanalyse, Semantische Analyse, Optimierung, Codegenerierung.
• Wichtige Bestandteile: Lexer, Parser, Intermediate Code Generator, Optimizer, Code Generator.

Unterschiedliche Typen von Compilern

Definition:

Unterschiedliche Typen von Compilern: verschiedene Kategorien von Programmen, die Quellcode in Maschinencode übersetzen.

Details:

• Ein-Pass-Compiler: übersetzt Quellcode in einem Durchlauf
• Mehr-Pass-Compiler: durchläuft Quellcode mehrmals, erzeugt verschiedene Zwischenrepräsentationen
• Just-In-Time (JIT) Compiler: kompiliert während der Programmausführung
• Ahead-Of-Time (AOT) Compiler: kompiliert vor der Ausführung
• Cross-Compiler: erzeugt Maschinencode für eine andere Architektur als die des Entwicklungsrechners
• Source-to-Source Compiler: transformiert Quellcode von einer Programmiersprache in eine andere

Kontextfreie Grammatiken (CFGs)

Definition:

Kontextfreie Grammatiken (CFGs) definieren formale Syntaxregeln zur Beschreibung der Struktur von Sprachen in Compilerbau und Linguistik.

Details:

• Besteht aus einer Menge von Produktionsregeln:
  • \textit{V} (Nichtterminale)
  • \textit{Σ} (Terminale)
  • \textit{R} (Regelmengen)
  • \textit{S} (Startsymbol)
• Produktionsregel: \textit{A → β} wobei \textit{A} in \textit{V} und \textit{β} in \textit{(V ∪ Σ)*}
• Einen Ableitungsbaum konstruierbar

Parsing-Algorithmen und deren Implementierung

Definition:

Parsing-Algorithmen analysieren Quellcode, um eine syntaktische Struktur zu bestimmen.

Details:

• Top-Down-Parsing: Beginnt an der Wurzel und arbeitet sich zu den Blättern herunter (z.B. Rekursiver Abstieg).
• Bottom-Up-Parsing: Beginnt mit den Blättern und arbeitet sich zur Wurzel hoch (z.B. LR-Parser).
• LL-Parser: Ein Top-Down-Parser, der liest von links nach rechts und erstellt einen Linksableitung.
• LR-Parser: Ein Bottom-Up-Parser, der liest von links nach rechts und erstellt eine Rechtsableitung.
• CYK-Algorithmus: Ein dynamischer Programmierungsalgorithmus für den Kontext-freie Grammatiken.
• Implementierung: Parsergeneratoren wie Yacc oder ANTLR können verwendet werden.

Reguläre Ausdrücke und finite Automaten

Definition:

Reguläre Ausdrücke beschreiben Mengen von Zeichenketten. Finite Automaten sind Modelle, die diese Mengen erkennen.

Details:

• Reguläre Ausdrücke: formale Notation zur Beschreibung von Zeichenkettenmustern
• Symbole: \, ., *, +, ?, []
• NFA/DFA: nichtdeterministische (NFA) und deterministische (DFA) endliche Automaten, um reguläre Ausdrücke zu erkennen
• Transformation: Regex zu NFA, NFA zu DFA, Minimierung
• Sprache: Menge der von einem Automaten akzeptierten Zeichenketten
• Wichtige Theoreme: Kleene-Theorem (Äquivalenz von Regex und endlichen Automaten)

LL-Parser vs. LR-Parser

Definition:

Unterschied zwischen LL-Parser (Top-Down) und LR-Parser (Bottom-Up); beide benutzen Parsingtabellen, aber unterschiedliche Ansätze.

Details:

• LL-Parser: Parsen von Links nach rechts, produziert Linksableitung.
• LR-Parser: Parsen von Links nach rechts, analysiert Rechtsableitung.
• LL(k)-Parser: Klookaheadsymbole werden genutzt, damit der Parser entscheiden kann.
• LR(k)-Parser: Benutzt Klookaheadsymbole und Zustände, um Parsing-Entscheidungen zu treffen.
• LL einfacher zu implementieren, aber weniger mächtig.
• LR mächtiger und handhabt größere Klassen von Grammatiken.

Typüberprüfungen und -inferenz

Definition:

Prozess in der Compiler-Konstruktion, um die Korrektheit von Typen in einem Programm sicherzustellen.

Details:

• Typüberprüfungen: Überprüfung, ob die Typen in einem Programm korrekt verwendet werden.
• Typinferenz: Bestimmung der Typen von Ausdrücken automatisch.
• Statische Typüberprüfung sorgt für Fehlererkennung zur Kompilierzeit.
• Dynamische Typüberprüfung führt Typüberprüfung zur Laufzeit durch.
• Typische Ansätze basieren auf Algorithmus W (Hindley-Milner).
• Wichtige Konzepte: Typvereinbarkeit, Typkonstrukte, und Typumwandlung.

Optimierungstechniken wie Loop Unrolling und Inlining

Definition:

Optimierungstechniken zur Verbesserung der Laufzeit und Effizienz von Code.

Details:

• Loop Unrolling: Reduziert den Overhead von Schleifensteuerung durch mehrfache Wiederholung der Schleifeninhalte.
• Inline: Ersetzt Funktionsaufrufe mit dem eigentlichen Funktionscode, um Funktionsaufrufkosten zu sparen.
• Vorteile: Geringere Schleifen- und Funktionsaufrufkosten, verbesserte Performance.
• Nachteile: Kann zu größerem Code und möglicherweise schlechterer Cache-Nutzung führen.