Fragen und Antworten zu Compilern und lexikalischer Analyse

Wer ist ein Übersetzer?

Ein Übersetzer ist ein Programm, das als Eingabe Code in einer geschriebenen Sprache erhält und als Ausgabe eine andere Sprache erzeugt.

Beispiele für Übersetzer

Assembler und Compiler.

Was ist ein Assembler?

Ein Programm, das Assemblersprache in Maschinensprache übersetzt.

Definition einer Programmiersprache

Eine Programmiersprache wird definiert durch ihre Syntax und Semantik.

Struktur eines Compilers

Die Struktur eines Compilers umfasst typischerweise folgende Phasen/Komponenten:

• Quellcode
• Präprozessor
• Compiler
• Assembler-Code
• Assembler
• Objekt-Code
• Linker
• Ausführbarer Code

Phase der lexikalischen Analyse

In dieser Phase werden die Zeichen des Quellprogramms gelesen und in Zeichenketten (Tokens) gruppiert, die die lexikalischen Komponenten darstellen.

Phase der syntaktischen Analyse

Die lexikalischen Komponenten (Tokens) werden zu grammatischen Sätzen gruppiert, die der Compiler verwendet, um die Ausgabe zu synthetisieren.

Phase der semantischen Analyse

Es wird versucht, Anweisungen zu erkennen, die zwar die korrekte syntaktische Struktur haben, aber semantisch (inhaltlich) keinen Sinn ergeben.

Phase der Zwischencode-Generierung

Nach Abschluss der Analysephasen wird eine explizite Zwischenrepräsentation des Quellprogramms generiert.

Phase der Code-Generierung

Bei der Code-Generierung wird in der Regel Objektcode in Maschinensprache oder Assembler-Code erzeugt.

Was ist eine Symboltabelle?

Eine Symboltabelle ist eine Datenstruktur, die einen Eintrag für jede Kennung (Bezeichner) enthält. Der Eintrag enthält Felder für die Attribute des Bezeichners.

Fehlerbehandlung im Compiler

Die Fehlerbehandlung ist ein zentraler Bestandteil des Kompilierungsprozesses.

Anderer Name für lexikalische Analyse

Die lexikalische Analyse wird auch Scanner oder Lexer genannt. Sie führt eine lineare Abtastung der Eingabezeichen durch und wandelt sie in eine Folge von Tokens (lexikalische Komponenten) um.

Aufteilung von Tokens

Tokens können in bestimmte Tokens (nur Typ, z.B. Schlüsselwörter) und unspezifische Tokens (Typ und Wert, z.B. Bezeichner, Konstanten) unterteilt werden.

Ergebnis der lexikalischen Analyse

Eine lexikalische Analyse erstellt Tokens aus einer Folge von eingegebenen Zeichen.

Linearer Analysator

Der lexikalische Analysator (Scanner/Lexer) führt eine lineare Transformation der Eingabesymbole in eine Folge von lexikalischen Komponenten (Tokens) durch.

Bau eines lexikalischen Analysators

Phasen für den Bau eines lexikalischen Analysators sind:

• Definition aller reservierten Wörter/Schlüsselwörter der Sprache
• Bau des Automaten (z.B. endlicher Automat)
• Bau der Übergangstabelle

Prozess der lexikalischen Analyse

Der Prozess der lexikalischen Analyse bezieht sich auf die Arbeit, die vom Scanner bei der Erstellung der Tokens geleistet wird.

Ziel des Parsers

Das Ziel des Parsers ist es, einen Syntaxbaum des Quellprogramms gemäß einer Grammatik zu erzeugen.

Was ist ein Muster (Pattern)?

Ein Muster (Pattern) stellt die Regel für eine Folge von Zeichen dar, die als eine bestimmte Einheit des Lexikons (Token) erkannt wird.

Was ist ein Lexem?

Ein Lexem ist eine Folge von Zeichen im Quellcode, die einem bestimmten Muster entspricht und als Instanz eines Tokens erkannt wird.

Was ist ein Token?

Ein Token ist eine Gruppe von Zeichen (ein Lexem), die eine bestimmte Bedeutungseinheit darstellt und durch ihren Token-Typ und optional einen Wert charakterisiert wird.

Was sind lexikalische Kategorien?

Lexikalische Kategorien sind Klassifizierungen für gültige Zeichenfolgen (Lexeme) in einer Sprache, die zu einem bestimmten Token-Typ gehören (z.B. Bezeichner, Schlüsselwörter, Operatoren).

Rolle der lexikalischen Analyse

Die lexikalische Analyse verarbeitet den Quellcode und übermittelt die erkannten Tokens an den Parser.

Was beschreibt ein Muster?

Ein Muster (Pattern) beschreibt die Regel für eine Folge von Zeichen, die als bestimmte lexikalische Einheit (Token) erkannt wird.

Endlicher Automat (Finite-State Acceptor)

Ein endlicher Automat (Finite-State Acceptor) ist ein mathematisches Modell zur Beschreibung, wie Tokens erkannt (akzeptiert) werden können.

Zustandsübergangsdiagramm (Transition Diagram)

Ein Zustandsübergangsdiagramm stellt die Zustände und Übergänge eines endlichen Automaten dar, einschließlich Start-, Zwischen- und Endzuständen.

Knoten in Zustandsdiagrammen

Knoten in einem Zustandsdiagramm repräsentieren die Zustände des endlichen Automaten.

Bögen in Zustandsdiagrammen

Bögen (Kanten/Pfeile) in einem Zustandsdiagramm zeigen die Zustandsübergänge an.

Akzeptierender Zustand

Ein akzeptierender Zustand (Endzustand) ist ein Zustand im endlichen Automaten, der anzeigt, dass eine gültige Eingabesequenz (ein Lexem) erkannt wurde.

Hinweis zu Zustandsdiagrammen

Bei einem Zustandsübergangsdiagramm muss berücksichtigt werden, dass von jedem Zustand aus für jede mögliche Eingabe (Zeichen) der nächste Zustand eindeutig bestimmt ist (bei deterministischen Automaten).

Beispiele lexikalischer Einheiten

Beispiele für lexikalische Einheiten sind: Kennung (Identifier), Kommentar, EOF (End of File) und Fehler.

Selektoren für Muster

Die Zeichen des Quellcodes dienen als Selektoren, die den Mustern für lexikalische Einheiten wie Kennungen, Kommentare, EOF oder Fehler entsprechen.

Puffer für lexikalische Analyse

Informationen werden oft in einem Puffer repräsentiert, der in zwei Hälften geteilt ist (z.B. Puffer[0...n/2-1] und Puffer[n/2...n-1]), um effizientes Lesen zu ermöglichen (z.B. mit Zeigern wie 'Anfang' und 'Vorwärts').

Tabelle für lexikalische Analyse

Eine Tabelle für die lexikalische Analyse (z.B. Übergangstabelle) zeigt die Übergänge zwischen Zuständen basierend auf Eingabezeichen. Endzustände (Akzeptierzustände) markieren das Ende eines erkannten Lexems.

Funktionen eines Lexers

Ein Lexer verwendet Funktionen zum Lesen und Verarbeiten der Eingabe, z.B.:

• Advance: Liest das nächste Zeichen und bewegt den Vorwärts-Zeiger.
• Backup: Bewegt den Vorwärts-Zeiger zurück (falls ein Zeichen zu viel gelesen wurde, um den Endzustand zu erreichen).

Speicher für lexikalische Analyse

Für die lexikalische Analyse wird der Quellcode in einen Eingabepuffer geladen (oft im RAM), wo der Scanner den Inhalt direkt inspiziert und verarbeitet.