Ausgewählte Kapitel aus dem Übersetzerbau - Cheatsheet

Definition von Tokens und Tokenisierung

Definition:

Prozess der Unterteilung eines Quellcodes in kleinere, bedeutungstragende Einheiten (Tokens).

Details:

• Token-Arten: Bezeichner, Schlüsselwörter, Literale, Operatoren, Trennzeichen
• Tokens repräsentieren kleinste syntaktisch unterscheidbare Elemente einer Programmiersprache
• Token-Format: \texttt{}
• Verwendung eines Lexers (lexikalischer Analyse-Tool) zum Erstellen von Tokens
• Eingabe des Lexers: Quellcode-Text
• Ausgabe des Lexers: Folge von Tokens

Reguläre Ausdrücke für Mustererkennung

Definition:

Reguläre Ausdrücke sind formale Sprachen zur Beschreibung von Textmustern.

Details:

• Syntax: Verwendungen von Zeichen wie '.', '*', '+', '[]'.
• Kleenesche Star: \texttt{*} für beliebig viele Wiederholungen.
• Optionale Vorkommen: \texttt{?} für 0 oder 1 Vorkommen.
• Gruppierung: \texttt{()} für Gruppenbildung.
• Alternativen: \texttt{|} für logisches ODER.

Kontextfreie Grammatiken und Parsing-Strategien (Top-Down, Bottom-Up)

Definition:

Kontextfreie Grammatiken (CFGs) definieren formale Sprachen durch Produktionsregeln. Parsing-Strategien: Top-Down beginnt bei Startsymbol und arbeitet sich bis zu Terminalsymbolen vor, Bottom-Up beginnt bei Terminalsymbolen und arbeitet sich bis zum Startsymbol zurück.

Details:

• CFGs bestehen aus: Nicht-Terminale, Terminalsymbole, Startsymbol, Produktionsregeln.
• Top-Down Parsing: z.B. Rekursiver Abstieg, Predictive Parsing (LL-Parser).
• Bottom-Up Parsing: z.B. Shift-Reduce, LR-Parser (SLR, LALR, Canonical LR).
• Prädiktive Parser verwenden First- und Follow-Mengen.
• LR-Parser benötigen Parsing-Tabellen und Zustandsautomaten.
• Parsing-Komplexität: Top-Down (einfachere Grammatik), Bottom-Up (komplexere Grammatik).

Recursive-Descent-Parser und LR-Parser

Definition:

Recursive-Descent-Parser und LR-Parser sind Parsing-Techniken zur Analyse und Verarbeitung von Programmiersprachen; sie helfen, Quellcode in eine abstrakte Syntaxbaumstruktur umzuwandeln

Details:

• Recursive-Descent-Parser: Top-Down Parsing, einfache Implementierung, aber begrenzte Sprachabdeckung (meist für LL(k)-Grammatiken)
• LR-Parser: Bottom-Up Parsing, komplexer, dafür mächtiger und weit verbreitet, weil sie größere Klasse von Grammatiken (LR(k)-Grammatiken) verarbeiten können
• Recursive-Descent-Parser: Jeder Knoten im Parsebaum entspricht einer Prozedur/Funktion im Parser
• LR-Parser: Verwendet Parsing-Tabelle und Automat zur Steuerung des Parsing-Prozesses

Symboltabellenverwaltung und Typüberprüfung

Definition:

Symboltabellenverwaltung: Verwaltung von Bezeichnern und deren Attributen in einer Tabelle. Typüberprüfung: Überprüfung der Kompatibilität von Typen anhand vorgegebener Regeln.

Details:

• Symboltabellenverwaltung: Speicherung von Informationen wie Namen, Typen und Speicheradressen.
• Typprüfung: Sicherstellung, dass Operationen mit kompatiblen Typen durchgeführt werden, z.B. Addition von zwei Ganzzahlen。
• Nutzung während der Analysephasen des Compilers.
• \texttt{lookup} und \texttt{insert} Operationen in der Symboltabelle.
• Nutzung von Typregeln wie \texttt{int + int = int}, \texttt{float + int = float} usw.

Zwischencodegenerierung und Registerzuweisung

Definition:

Zwischencodegenerierung wandelt die geparsten Strukturen in eine Zwischenrepräsentation um; Registerzuweisung ordnet Variablen Maschinencode-Register zu.

Details:

• Zwischencode für plattformunabhängige Optimierungen
• Common Formen: drei-Adresse-Code (TAC), abstrakte Syntaxbäume (AST)
• Registerzuweisung: Mapping von Variablen auf begrenzte Hardware-Register
• Register Allokation: Verteilungsverfahren, wie graphfärbung und lineare Scan-Algorithmen
• Ziele: Minimierung der Speicherzugriffe, Erhöhung der Effizienz
• Spilling: Temporäres Auslagern von Variablen auf den Speicher

Optimierungstechniken: Loop-Optimierungen und Peephole-Optimierungen

Definition:

Optimierungstechniken zur Verbesserung der Effizienz von Schleifen und kleineren Code-Segmenten

Details:

• Loop-Optimierungen: Techniken zur Effizienzsteigerung von Schleifen (z.B. Loop Unrolling, Loop Interchange)
• Loop Unrolling: Verringert Anzahl der Iterationen, reduziert Schleifen-Overhead
• Loop Interchange: Vertauscht verschachtelte Schleifen zur Verbesserung der Speicherzugriffsmuster
• Peephole-Optimierungen: Optimieren kurze Code-Segmente durch einfache Transformationsregeln
• Typische Peephole-Transformationen: Konstante Subexpressionen eliminieren, unnötige Sprünge entfernen, einfache Algebra Vereinfachungen
• Ziel: Reduktion von Laufzeit und Speicherverbrauch

Fehlererkennung und -behandlung in jeder Phase

Definition:

Details:

• Fehlererkennung und -behandlung während Lexikalischer Analyse: Lexikalische Fehler wie unerkannte Tokens
• Fehlererkennung und -behandlung während Syntaktischer Analyse: Syntaxfehler wie fehlende Semikolons, Klammerfehler
• Fehlererkennung und -behandlung während Semantischer Analyse: Typfehler, Namensauflösungsfehler
• Fehlererkennung und -behandlung während der Laufzeit: Laufzeitfehler wie Division durch Null, Speicherzugriffsverletzungen