Grundlagen des Übersetzerbaus - Cheatsheet

Tokenisierung des Quellcodes und Reguläre Ausdrücke

Definition:

Tokenisierung teilt Quellcode in kleinere Einheiten (Tokens) auf. Reguläre Ausdrücke werden verwendet, um Muster in Texten zu erkennen und zu manipulieren.

Details:

• Token: kleinste bedeutungsvolle Einheit
• Lexikalische Analyse: erster Schritt des Compilervorgangs
• Reguläre Ausdruck: benutzt syntaktische Regeln zur Mustererkennung
• Grammatik: formale Beschreibung von Syntaxregeln
• Beispiel für Tokenisierung: Schlüsselwörter, Bezeichner, Literale
• Regex: gängige Operatoren (*, +, ?, {n}, [abc], etc.)

Top-Down und Bottom-Up Parsing Techniken (LL- und LR-Parser)

Definition:

Top-Down und Bottom-Up Parsing sind Techniken für die syntaktische Analyse. LL-Parser arbeiten von links nach rechts und konstruieren die linke Ableitung, während LR-Parser die rechte Ableitung konstruieren.

Details:

• Top-Down Parsing: Analysiert die Eingabe ab der Wurzel des Ableitungsbaums (z.B. LL-Parser)
• Bottom-Up Parsing: Analysiert die Eingabe ab den Blättern hin zur Wurzel (z.B. LR-Parser)
• LL-Parser: Steht für Left-to-right, Leftmost derivation (k-Präsizion)
• LL(k)-Parser: Liest die Eingabe von links nach rechts und konstruiert die linke Ableitung mit k-Vorrausschau
• LR-Parser: Steht für Left-to-right, Rightmost derivation
• LR(k)-Parser: Liest die Eingabe von links nach rechts und konstruiert die rechte Ableitung mit k-Vorrausschau
• Wichtige Arten von LR-Parsern: SLR(1), LALR(1), CLR(1)

Typprüfung, Typinferenz und Attributgrammatiken

Definition:

Typprüfung überprüft, ob Programmausdrücke mit korrekten Datentypen verwendet werden. Typinferenz bestimmt die Typen unbeschrifteter Ausdrücke. Attributgrammatiken beschreiben Kontextbedingungen und Typinformationen in einem Compiler.

Details:

• Typprüfung: Statisch (zur Compilezeit) oder dynamisch (zur Laufzeit).
• Typsysteme: Stark/schwach, statisch/dynamisch.
• Typinferenz: Algorithmen wie Hindley-Milner zur automatischen Typbestimmung.
• Attributgrammatiken: Zuweisung von Attributen zu Grammatikregeln, Verwendung für Synthese- und Inhärente-Attribute.
• Beispiel für Attributgrammatik:

P → E { P.typ = E.typ }E → E₁ + E₂ { E.typ = if (E₁.typ == int && E₂.typ == int) then int else error }

Zwischenrepräsentationen (IR) und Maschinencodierung

Definition:

Zwischenrepräsentationen (IR) und Maschinencodierung - essentieller Teil des Übersetzungsvorgangs, wo hochsprachliche Anweisungen in maschinenlesbaren Code umgewandelt werden.

Details:

• IR: Abstrakte Repräsentation des Programmcodes
• Maschinencodierung: Übersetzung der IR in den Maschinencode
• IR-Beispiele: Drei-Adress-Code, SSA
• IR-Ziele: Optimierung, Portabilität
• Maschinencodierung nutzt Back-End-Compiler-Phase

Peep-Hole-Optimierung und Schleifen-Optimierungen

Definition:

Kleine, lokal begrenzte Optimierungen in Assembler oder Maschinencode zur Leistungssteigerung.

Details:

• Werden nach Übersetzung des Programms durchgeführt.
• Kennzeichen: einfache Mustererkennung und Umwandlung ineffizienter Konstrukte in effizientere.
• Beispiele: Beseitigung von totem Code, Vereinfachung von Rechenoperationen.
• \textbf{Schleifen-Optimierungen}: Reduzierung der Berechnungen innerhalb von Schleifen, Schleifenfusion, Schleifenverlagerung.
• Ziel: Beschleunigung der Schleifen und Reduktion der Schleifen-Overheads.

Kontextfreie Grammatiken und Aufbau von Parsebäumen

Definition:

Kontextfreie Grammatiken definieren durch Produktionsregeln die Syntax einer formalen Sprache. Parsebäume veranschaulichen, wie ein String gemäß diesen Regeln erzeugt wird.

Details:

• Kontextfreie Grammatik (CFG): Menge von Produktionsregeln
• Form von Produktionsregel: A → γ, wobei A ein Nichtterminal und γ eine Folge von Terminalen und/oder Nichtterminalen ist
• Derivationsprozess: Startsymbol → Folge von Terminalsymbolen
• Parsebaum-Repräsentation: Baumdiagramm, das Ableitungen zeigt
• Knoten im Parsebaum:
  • Innere Knoten = Nichtterminalsymbole
  • Blätter = Terminalsymbole
• Sicherstellen von eindeutigen Ableitungen (falls notwendig): LL(1) oder LR(1) Analyseverfahren verwenden
• Anwendungen: Syntaxprüfung, automatische Übersetzerbau und mehr

Register- und Speicherverwaltung in der Codegenerierung

Definition:

Verwaltung von Registern und Speicher während der Codegenerierung, um Variablen effizient zu speichern und zu laden.

Details:

• Registerallokation: Zuweisung von Variablen zu Registern.
• Spill Code: Laden/Speichern von Variablen bei Registermangel.
• Registerzuweisung: Priorisierung kritischer Variablen.
• Speicherverwaltung: Organisation und Zugriff auf Hauptspeicher.
• Register-Zu-Speicher-Optimierungen: Minimiere Speicherzugriffe, maximiere Registernutzung.
• Lebenszeit-Analyse: Bestimme die Lebensspanne einer Variable für effiziente Nutzung.

Fehlererkennung und -behandlung in allen Analysephasen

Definition:

Identifikation und Behandlung von Fehlern in verschiedenen Phasen der Übersetzungsanalyse (Lexikal-, Syntax-, und Semantikanalyse).

Details:

• Lexikalische Analyse: Erkennung ungültiger Tokens, z.B. unbekannte Symbole.
• Syntaxanalyse: Parsen-Fehler identifizieren, z.B. durch unerwartete Token-Sequenzen.
• Semantische Analyse: Typenfehler und andere semantische Inkonsistenzen erkennen.
• Fehlerbehandlungsstrategien: Panikmodus, Fehlerproduktion, Vorwärtsprüfung.