Λεκτική ανάλυση

Ο λεκτικός αναλυτής

Διαχωρίζει το εισερχόμενο κείμενο σε λεκτικές μονάδες (tokens) και το μεταφέρει με τον τρόπο αυτό στο συντακτικό αναλυτή.

Αποθηκεύει τα σύμβολα που διαβάζει σε πίνακα συμβόλων.

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

Αναγνωρίζει λεκτικά λάθη στην είσοδο (π.χ. σύμβολα που δεν επιτρέπονται στη γλώσσα).

Αφαιρεί τα σχόλια

Συσχετίζει αριθμούς γραμμών με στοιχεία της εισόδου του.

Λεκτικές μονάδες

Τα στοιχεία μιας γλώσσας χωρίζονται σε λεκτικές μονάδες.

Ο χωρισμός σε λεκτικές μονάδες συχνά δεν είναι προκαθορισμένος.

Τυπικές λεκτικές μονάδες που ορίζονται είναι:

Οι δεσμευμένες λέξεις (reserved words)
Τα ονόματα (identifiers)
Οι σταθερές (constants)
Οι τελεστές (operators)
Οι διαχωριστές (delimiters)

Κάθε λεκτική μονάδα συσχετίζεται από το λεκτικό αναλυτή με τον τύπο της (π.χ. ακέραια σταθερά) και την τιμή της (π.χ. 42).

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

Οι δεσμευμένες λέξεις τυπικά διαχωρίζονται μεταξύ τους κατά το στάδιο της λεκτικής ανάλυσης.

Συχνά η αναγνώριση των δεσμευμένων λέξεων γίνεται με τη χρήση συναρτήσεων κατακερματισμού.

Διεπαφή

Η διεπαφή (interface) μεταξύ του λεκτικού αναλυτή και του συντακτικού αναλυτή υλοποιείται συχνά με την κλήση μιας συνάρτησης.

Κάθε διαφορετικός τύπος λεκτικής μονάδας ορίζεται με έναν ακέραιο. Οι ακέραιοι αυτοί ορίζονται στη C με μια απαρίθμηση ή με τη χρήση της εντολής του προεπεξεργαστή #define.

Συχνά οι λεκτικές μονάδες που απαρτίζονται από έναν χαρακτήρα ορίζονται με τον ακέραιο κωδικό του χαρακτήρα αυτού.

Η συνάρτηση του λεκτικού αναλυτή επιστρέφει τον τύπο της λεκτικής μονάδας και αποθηκεύει σε μια καθολική μεταβλητή την τιμή της.

Για λόγους ευκολίας η μεταβλητή αυτή ορίζεται συχνά ως ένωση. Παράδειγμα:

union u_lval {
        char c;
        int i;
        double d;
        char *s;
} yylval;

Οπισθοδρόμηση

Κατά τη λεκτική ανάλυση οι γλώσσες προγραμματισμού ορίζουν τυπικά πως η λεκτική οντότητα που αναγνωρίζεται είναι η μακρύτερη δυνατή από αριστερά προς τα δεξιά. Παράδειγμα (στη γλώσσα C):

	++ και όχι + +
	>= και όχι > =
	printf και όχι p r i n t f

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

Στην υλοποίηση του λεκτικού αναλυτή χρησιμοποιείται μια θέση η οποία επιτρέπει την οπισθοδρόμηση (backtracking) του λεκτικού αναλυτή με την ακύρωση του τελευταίου χαρακτήρα που διαβάστηκε.

Η βιβλιοθήκη stdio της C παρέχει τη συνάρτηση

ungetc(int c, FILE *stream);

η οποία "σπρώχνει" έναν χαρακτήρα c πίσω στο αρχείο stream από το οποίο διαβάστηκε.

Υλοποίηση με διάγραμμα μετάβασης

Οι λεκτικοί αναλυτές μπορούν να υλοποιηθούν με:

κώδικα που θα γραφεί από έναν άνθρωπο
κώδικα που θα γραφεί από ένα εξειδικευμένο μεταεργαλείο

Ένας λεκτικός αναλυτής μπορεί να γραφεί με το χέρι για τους παρακάτω λόγους:

Σε πολλές περιπτώσεις ο κώδικας που θα γραφεί από άνθρωπο θα είναι πιο σύντομος και αποδοτικότερος από αυτόν που θα γραφεί από μεταεργαλείο.
Υπάρχουν γλώσσες προγραμματισμού των οποίων οι λεκτικοί κανόνες δεν μπορούν να περιγραφούν από μια κανονική γλώσσα (π.χ. awk, Haskell). Στην περίπτωση αυτή τα μεταεργαλεία είναι άχρηστα.
Μερικές φορές μια γλώσσα προγραμματισμού μπορεί να περιγραφεί από μια κανονική γλώσσα κατά μεγάλο ποσοστό, αλλά ορισμένα στοιχεία της γλώσσας (όπως π.χ. τα σχόλια) να απαιτούν ειδικό χειρισμό. Στην περίπτωση αυτή ακολουθείται μια μικτή προσέγγιση.

Η υλοποίηση ενός λεκτικού αναλυτή βασίζεται στον ορισμό ενός διαγράμματος μετάβασης (transition diagram), τη χρήση οπισθοδρόμησης, καθώς και στη χρήση ad hoc τεχνικών. Για παράδειγμα στη C++ αφού αναγνωριστεί ένα σχόλιο γραμμής (//), ο λεκτικός αναλυτής μπορεί να διαβάσει τους χαρακτήρες μέχρι το τέλος της γραμμής με τον παρακάτω κώδικα:

        while ((c = getchar()) != EOF)
                if (c == '\n')
                        break;

Μια άλλη τεχνική που χρησιμοποιείται συχνά είναι η αναγνώριση των δεσμευμένων λέξεων και των ονομάτων ως ένα σύνολο και στη συνέχεια ο διαχωρισμός τους μέσω μια κατάλληλης δομής δεδομένων.

Ασκήσεις

Να υλοποιήσετε σε C έναν λεκτικό αναλυτή που να αναγνωρίζει τα παρακάτω λεκτικά σύμβολα:

ακέραιοι
μεταβλητές (όπως της C)
τελεστής +
τελεστής -
τελεστής *
τελεστής /

Η συνάρτηση του λεκτικού αναλυτή θα λέγεται yylex και θα επιστρέφει: των κωδικό του χαρακτήρα για τους τελεστές, 256 για τους ακέραιους, 257 για τις μεταβλητές και -1 στο τέλος του αρχείου. Ακόμα θα φυλάει στα πεδία της ένωσης yylval s και i τις τιμές των μεταβλητών και των ακεραίων αντίστοιχα. Σε περίπτωση λάθους ο λεκτικός αναλυτής θα τερματίζει τη λειτουργία του εμφανίζοντας ένα μήνυμα λάθους. Ο λεκτικός αναλυτής θα καλείται από το παρακάτω πρόγραμμα:

#include <stdio.h>

union {
        char *s;                /* Variable name */
        int i;                  /* Integer value */
} yylval;

int yylex();

main()
{
        int k;

        while ((k = yylex()) != -1) {
                switch (k) {
                case 256:
                        printf("INT: %d\n", yylval.i);
                        break;
                case 257:
                        printf("VAR: %s\n", yylval.s);
                        break;
                default:
                        printf("OPERATOR: %c\n", k);
                        break;
                }
        }
}

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

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

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

John M. Dedourek, Uday G. Gujar, and Marion E. McIntyre. Scanner design. Software: Practice & Experience, 10:959–972, 1980.

V. P. Heuring. The automatic generation of fast lexical analysers. Software: Practice & Experience, 16(9):801–808, September 1986.

R. Nigel Horspool and Michael R. Levy. Mkscan — an interactive scanner generator. Software: Practice & Experience, 17(6):369–378, June 1987.

Douglas C. Schmidt. Gperf: A perfect hash function generator. In USENIX C++ Conference, pages 87–100, San Francisco, CA, USA, April 1990. Usenix Association.

W. M. Waite. Treatment of tab characters by a compiler. Software: Practice & Experience, 15(11):1121–1123, November 1985.

W. M. Waite. The cost of lexical analysis. Software: Practice & Experience, 16(5):473–488, May 1986.