Πίνακες συμβόλων

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Λειτουργία

Ο πίνακας συμβόλων είναι μια αφηρημένη δομή δεδομένων ή κλάση που αντιστοιχεί ονόματα που διαβάζει ο μεταγλωττιστής με τις πληροφορίες που τους αντιστοιχούν.
Οι πληροφορία που αντιστοιχεί σε ένα σύμβολο μπορεί να είναι το είδος του, ο τύπος του, η ορατότητά του κ.λπ.
Τυπικά ένα σύμβολο μπορεί να είναι μέλος σε πολλές ονοματικές περιοχές (namespaces):
struct i {int i;};

void
i(void)
{
int i;

i:
goto i;
}

Στο παραπάνω παράδειγμα το σύμβολο i χρησιμοποιείται ως ετικέτα δομής, μέλος δομής, όνομα συνάρτησης, όνομα μεταβλητής και ετικέτα άλματος.
Επίσης, σε διαφορετικά σημεία του προγράμματος μπορεί να είναι ορατά (visible) διαφορετικά σύμβολα:
int i;

fun(void)
{
        int i;

        for (;;) {
                int i;

Οι λειτουργίες που θέλουμε να εκτελούμε σε έναν πίνακα συμβόλων περιλαμβάνουν:

Την προσθήκη ενός νέου συμβόλου.
Την ενημέρωση των πληροφοριών που σχετίζονται με ένα σύμβολο.
Την ανάκτηση των πληροφοριών που σχετίζονται με ένα σύμβολο.
Την αλλαγή του πεδίου ορατότητας των συμβόλων.
Τη διαγραφή ενός συμβόλου.

Περιεχόμενα

Τα στοιχεία που θέλουμε να αποθηκεύσουμε για κάθε σύμβολο είναι:

Τη συμβολοσειρά που το παριστάνει.
Το πεδίο ονομάτων στο οποίο ανήκει. Για παράδειγμα στη γλώσσα C το ίδιο σύμβολο μπορεί να χρησιμοποιηθεί ταυτόχρονα στα παρακάτω πεδία ονομάτων:
- συναρτήσεις, ονομάτα typedef, μεταβλητές και σταθερές enum
- ετικέτες εντολών
- ετικέτες δομών, ενώσεων και απαριθμήσεων
- τα μέλη κάθε ξεχωριστής δομής ή ένωσης
Το είδος του. Για παράδειγμα στη C το είδος μπορεί να είναι ένα από τα παρακάτω:
- συναρτήση,
- όνομα typedef,
- μεταβλητή
- σταθερά enum
- ετικέτα εντολών
- ετικέτα δομής
- ετικέτα ένωσης
- ετικέτα απαρίθμησης
- μέλος συγκεκριμένης δομής ή ένωσης
Ο τύπος του
Πρόσθετα στοιχεία που σχετίζονται με τον τύπο του όπως:
- τις διαστάσεις του πίνακα
- τα ονόματα μελών της δομής ή ένωσης
- τα μέλη μιας κλάσης
Το αρχείο και τη γραμμή που έχει δηλωθεί και οριστεί.

Δομές

Ένας πίνακας συμβόλων είναι πολύ βολικό να σχεδιαστεί ως ένας αφηρημένος τύπος δεδομένων ή ως μια κλάση. Με τον τρόπο αυτό:

εσωτερικές αλλαγές στον τρόπο οργάνωσής του δε θα επηρεάσουν τον κώδικα του υπόλοιπου μεταγλωττιστή.
διαφορετικά πεδία ονομάτων ορίζονται εύκολα ως διαφορετικοί πίνακες συμβόλων.

Δομές κατάλλληλες για τη φύλαξη των συμβόλων είναι οι παρακάτω:

Συνδεδεμένη λίστα ή πίνακας: Κατάλληλη μόνο για πίνακες με πολύ μικρό αριθμό συμβόλων (π.χ. τα μέλη μιας δομής)
Πίνακας κατακερματισμού: Γρήγορος στην εισαγωγή και αναζήτηση, αλλά απαιτεί προσεκτικό σχεδιασμό της συνάρτησης κατακερματισμού και πρόβλεψη για περιπτώσεις συγκρούσεων. Μπορεί να οδηγήσει σε σπατάλη μνήμης.
Δυαδικό δένδρο: Σχετικά γρήγορο στην εισαγωγή και αναζήτηση με μικρές απαιτήσεις μνήμης.

Εμβέλεια ονομάτων

Κάθε αναζήτηση στον πίνακα συμβόλων πρέπει να γίνεται σύμφωνα με τους κανόνες εμβέλειας ορατότητας της γλώσσας. Αυτό σημαίνει πως για το σύμβολο που γίνεται η αναζήτηση πρέπει να βρεθεί το πιο εσωτερικό ορατό σύμβολο με το ίδιο όνομα. Δύο πιθανοί τρόποι οργάνωσης είναι οι παρακάτω:

η χρήση στοίβας από ενεργούς πίνακες συμβόλων που αντιστοιχεί στις ενότητες (block) που είναι ενεργά κάθε στιγμή,
η κατάλληλη αρίθμηση των ενοτήτων και των αντιστοίχων πινάκων συμβόλων.

Βιβλιογραφία

Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 209-222 (τμήματα). Συμμετρία 1993.

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 229–440. Addison-Wesley, 1985.

Περιεχόμενα