Symboltabelle

Eine Symboltabelle ist eine Zentralisierung von Informationen, die an die Kennungen eines Computerprogramms angehängt sind . Es ist eine Beschleunigerfunktion der Kompilierung , deren Wirksamkeit vom Design abhängt. In einer Symboltabelle finden wir Informationen wie: Typ, Speicherort, Reichweite , Sichtbarkeit usw.

Allgemeines

Tabellenerstellung

Normalerweise wird die Tabelle dynamisch erstellt. Ein erster Teil wird zu Beginn der Kompilierung erstellt . Dann wird es opportunistisch, je nach den Bedürfnissen, abgeschlossen.

Ein Symbol erstellen

Wenn ein Symbol zum ersten Mal angezeigt wird (im Sinne der Sprachsichtbarkeitsregeln), wird ein Eintrag in der Tabelle erstellt.

Sammlung

Das Ausfüllen dieser Tabelle (das Sammeln von Informationen) erfolgt während der Analysephasen.

Identifizierung

Bei der Identifizierung wird eine Kennung in der Symboltabelle gefunden.

Die Symboltabelle sammelt Informationen zu den Bezeichnern: Art, Typ, Anfangswert, Zuordnungseigenschaften:

• Für jede Variable werden folgende Informationen gespeichert : Name, Typ, Gültigkeitsbereich und Adresse im Speicher;
• Für jede Funktion oder Prozedur werden folgende Informationen gespeichert: Name, Umfang , Name und Art der Argumente sowie die Art der Übergabe und möglicherweise die Art des von ihr bereitgestellten Ergebnisses;
• Um einen schnellen Zugriff zu ermöglichen, wird die Symboltabelle durch den Namen des Bezeichners (Zeichenfolge) indiziert , daher wird eine Hash-Tabelle verwendet  .
• Beim Definieren eines Bezeichners wird ein Eintrag in die Symboltabelle eingefügt. Diese Deklaration ist im Allgemeinen eindeutig, es sei denn, es liegt eine Überlastung vor.
• Wenn Sie einen Bezeichner verwenden, wird dieser in der Tabelle nachgeschlagen.
• In einigen Compilern sind die Sprachschlüsselwörter nicht Teil der Syntax, sondern werden in die Symboltabelle eingefügt.
• Die Eigenschaften eines Bezeichners können komplexe Strukturen sein ( Bäume , Tabellen , Listen , Felder usw.).

Operation

• Symbol setzen
• Symbol abrufen (Typponsistenzprüfung)
• Beginnen Sie mit dem Umfang
• Umfang beenden

Somit kann die Symboltabelle als Stapel modelliert werden, was es beim Lesen des Programms ermöglicht, die Bereichsstruktur dieses Computerprogramms beizubehalten .

Hash-Struktur

Die Hash- Struktur bietet schnellen und konstanten Zugriff auf die Namen von Variablen, Prozeduren und Funktionen.

Umfang einer Kennung

Umfang einer Erklärung

Der Umfang eines Bezeichners entspricht seiner Existenzzone (dem Block, in dem er deklariert wurde). Somit können mehrere Bezeichner mit demselben Namen auf verschiedene Elemente verweisen. Beispiel eines C-Code-Fragments:

int i() { int i; if (1) { int i; i = 2; } i = 3; return i; }

Symbolstab im Stab strukturiert

Jedem Programmblock (mit unterschiedlichen Bereichen) ist eine Symboltabelle zugeordnet. Jede dieser Tabellen wird selbst in einem globalen Stapel gespeichert .

Beim Lesen des Programms:

Wenn ein neuer Block entsteht , wird eine neue Symboltabelle im globalen Stapel („lokaler“ Stapel) gestapelt.

Wenn ein Block endet, wird die zugehörige Symboltabelle entstapelt und daher zerstört.

Für einen bestimmten Block:

Wenn wir in einer Deklaration auf einen Bezeichner stoßen: Wir überprüfen dessen Fehlen in der Tabelle vom oberen Rand des Stapels bis zum Ende des Bereichs (dh des gesamten „lokalen“ Stapels). Ist dies der Fall, wird es der Tabelle hinzugefügt (vgl. 5. Geltungsbereich eines Bezeichners).

Wenn wir in einem ausführbaren Teil auf einen Bezeichner stoßen, überprüfen wir dessen Vorhandensein in der Tabelle („lokaler“ Stapel) vom oberen Rand des Stapels bis zum Ende. Wenn dieser Bezeichner nicht vorhanden ist, liegt ein Fehler vor (siehe 5. Umfang eines Bezeichners).

Beispiel in C:

L1 int main () L2 { //début premier bloc L3 while () L4 { //début 2e bloc L5 for () L6 {;//début 3e bloc L7 } //fin 3e bloc L8 } //fin 2e bloc L9 If () L10 { //début 4e bloc L11 For () L12 {;//début 5e bloc L13 } //fin 5e bloc L14 } //fin 4e bloc L15 } //fin premier bloc

• Globaler Batteriestatus für L2: [TS1]
• Globaler Batteriestatus für L4: [TS1, TS2]
• Globaler Batteriestatus für L6: [TS1, TS2, TS3]
• Globaler Batteriestatus für L7: [TS1, TS2]
• Globaler Batteriestatus für L8: [TS1]
• Globaler Batteriestatus für L10: [TS1, TS4]
• Globaler Batteriestatus für L12: [TS1, TS4, TS5]
• Globaler Batteriestatus für L13: [TS1, TS4]
• Globaler Batteriestatus für L14: [TS1]
• Globaler Batteriestatus für L15: [LEER]

(mit TSi: Symboltabellennummer i)

Die Identifizierung erfolgt durch Gehen durch den Stapel von oben nach unten.

Vorteil

Einfachheit: Jedes Mal, wenn ein neuer Programmblock analysiert wird, wird eine neue Tabelle gestapelt.

Die Symboltabelle des aktuellen Blocks wird am Ende der Analyse angezeigt.

Nachteil

Das Identifizieren eines Namens kann langsam sein (aufgrund des Zugriffs auf mehrere aufeinanderfolgende Tabellen).

Symbolstab im Stab mit assoziativer Tabelle strukturiert

Konzept

Eine zentrale assoziative Tabelle, die durch die Namen der Bezeichner indiziert ist. Jeder Eintrag zeigt auf einen Stapel von Definitionen. Der obere Rand jedes Stapels ist die neueste Definition.

Für das obige Beispiel hätten wir einen C-Code wie:

int compte; // portée 0 int main() { char signal; // portée 1 { int faux; // portée 2 { compte++;// portée 3 { if (faux){} // portée 4 } } } } Vorteil

Schnelle Identifizierung

Nachteil

Komplexe Deletionen:

Beim Verlassen eines Blocks muss der Compiler die sichtbaren Deklarationen (Namensbereich) aktualisieren. Wenn wir nur die assoziative Tabelle verwenden würden, müssten wir alle Einträge der Tabelle durchsuchen, da uns Informationen fehlen, die es ermöglichen, die Liste der in einem Block deklarierten Bezeichner zu finden. Es erfordert daher eine andere Datenstruktur.

Lösung zur Beschleunigung der Entfernung

Um das Löschen von Einträgen (Definitionen) zu beschleunigen, verwenden wir auch einen Stapel von Bereichen, der auf alle Deklarationen eines Bereichs verweist. Somit ist es am Ende eines Blocks leicht, alle Deklarationen zu finden: Das Löschen der Einträge im TS wird beschleunigt.

Dank dieser zusätzlichen Struktur können wir die Bezeichner desselben Blocks finden.

Überlast

Definition

Durch die Überladung kann derselbe Bezeichner mehrmals deklariert werden (wir sprechen von einer Überladung nur zwischen Bezeichnern desselben Namespace und desselben Bereichs). Dies ist nur unter Einhaltung bestimmter Regeln möglich, und nur bestimmte Sprachen ( C ++ , Ada , Java …) erlauben diese Eigenschaft.

Problem

Die Überlastung wirft ein Problem der Mehrdeutigkeit auf: Tatsächlich gibt der Identifikationsprozess eine Reihe von Definitionen anstelle von nur einer zurück.

Lösung für das Problem

Die Lösung für dieses Problem besteht darin, alle Deklarationen (Definitionen) in die Symboltabelle aufzunehmen. Ein Bereich kann daher mehrere Deklarationen für denselben Bezeichner enthalten!
Die Reduktion von Definitionen folgt Regeln, die von der Sprache vorgegeben werden. Es ist notwendig, den Kontext analysieren zu können, um sich selbst zu finden, wenn nur eine Definition möglich ist.

Einige Sprachen führen diese Reduzierung beispielsweise durch Vergleichen von Parameterlisten durch (siehe „  Typensignatur  “).

Siehe auch

• Tabelle der mathematischen Symbole