Γράφοντας ένα Lexer με το SableCC 3.2 (μέρος 1/2)

Posted in Computer Science, sablecc, Προγραμματισμός by cyberpython on Μαρτίου 20, 2009

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

Τί είναι το SableCC;

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

εκφράσεων της γλώσσας αλλά και το μετασχηματισμό του συντακτικού δέντρου σε αφηρημένο και τη διάσχιση του δέντρου αυτού.
Το SableCC 3.2 είναι διαθέσιμο εδώ: http://sablecc.org/wiki/DownloadPage
Εμείς θα περιγράψουμε πως μπορούμε να κατασκευάσουμε ένα λεκτικό αναλυτή για ένα μικρό υποσύνολο της QBasic που θα παίρνει ως είσοδο ένα πρόγραμμα γραμμένο σε αυτό το υποσύνολο της QBasic και στη συνέχεια θα το “σπάει” στα κομμάτια (tokens) από τα οποία αποτελείται και θα προσπαθεί να αναγνωρίσει κάθε κομμάτι. Έτσι στο τέλος θα έχουμε ένα σύνολο από tokens που μπορούμε να τα κάνουμε ότι θέλουμε – εμείς θα παράγουμε ένα έγγραφο html μορφοποιημένο κατάλληλα (π.χ. έντονα keywords) – σημαντικό είναι οτι σε αυτή την περίπτωση μας χρειάζονται και τα κενά, τα tabs και οι αλλαγές γραμμής (για να έχει την ίδια μορφή και στοίχιση και το τελικό αρχείο html).

Η γλώσσα που θα επεξεργαστούμε

Η γλώσσα που θα αναγνωρίζει ο lexer μας θα είναι αυτή:

Δεσμευμένες Λέξεις (token: keyword)
PRINT, CLS, DO, WHILE, LOOP, INPUT, IF, THEN, ELSE, END, SELECT, CASE, OR, FOR, TO, NEXT, STEP, CONST
(εδώ δε χρειαζόμαστε διαφορετικό token για κάθε δεσμευμένη λέξη – όπως π.χ. αν έπειτα θέλαμε να κάνουμε συντακτική ανάλυση – αφού απλά θέλουμε οι δεσμευμένες λέξεις να έχουν το ίδιο στυλ)
Μεταβλητές (για αλφαριθμητικά, token: string_var)
γράμμα ακολουθούμενο από γράμματα ή ψηφία ή κάτω παύλες και στο τέλος $
π.χ. alphanum_1$
Αλφαριθμητικές σταθερές (token: string_const)
οποιοαδήποτε ακολουθία χαρακτήρων ανάμεσα σε διπλά εισαγωγικά (quotes)
π.χ. “This is – a – test string. “
Αριθμητικές σταθερές (token: num_const)
οποιοαδήποτε ακολουθία ενός ή περισσότερων ψηφίων
π.χ. 0 12 213 κλπ.
Σύμβολα (token: symbol)
+-*/(),=;

Για τα σύμβολα ‘<’ και ‘>’ πρέπει να ορίσουμε ειδικά tokens αφού θα απαιτούν ξεχωριστό χειρισμό (δεν επιτρέπονται στην html οι αντίστοιχοι χαρακτήρες) :

lt
<
gt
>
Σχόλια (token: comment)
Μονό εισαγωγικό (‘) ακολουθούμενο από οποιοδήποτε χαρακτήρα έως την αλλαγή γραμμής

Επίσης, θα χρειαστούμε και τα κενά και tabs για διατήρηση της στοίχισης του κώδικα (ενώ αν ο lexer προοριζόταν για χρήση από έναν συντακτικό αναλυτή τότε θα έπρεπε να αγνοούνται). Ακόμη, τα κενά θα παράγουν διαφορετικό token από τα tabs αφού θέλουμε να τα χειριστούμε διαφορετικά στη συνέχεια (για κάθε tab θα παράγουμε 8   στην html):

Κενό (token: space)
‘ ‘
Tab (token: tab)
ο χαρακτήρας με ascii-code 9

Ομοίως πρέπει να χειριστούμε και τις αλλαγές γραμμής:

Αλλαγή γραμμής (token: newline)
cr, lf ή cr lf

Τώρα πρέπει με κάποιο τρόπο να εκφράσουμε τα παραπάνω με τρόπο που να μπορεί να τα καταλάβει το SableCC.
Αρχικά δημιουργούμε ένα νέο κενό αρχείο απλού κειμένου και γράφουμε τα εξής:
Package subbasic;

Helpers

Tokens

Η γραμμή

Package subbasic;

θα χρησιμοποιηθεί από το SableCC για τη δημιουργία ενός φακέλου με το όνομα subbasic όπου θα τοποθετηθούν όλα τα αρχεία που θα παράγει.

Ορισμός βοηθητικών συμβόλων (helpers)

Κάτω από το Helpers μπορούμε να ορίσουμε σύμβολα που θα μας χρειαστούν για τον ορισμό των tokens.
Π.χ. για να ορίσουμε τις αριθμητικές σταθερές πρέπει πρώτα να έχουμε ορίσει το ψηφίο (δε θέλουμε όμως να αναγνωρίζεται ως token γι’ αυτό το ορίζουμε ως helper ώστε να μην υπάρχει στην έξοδο που παράγει ο λεκτικός αναλυτής). Έτσι, ορίζουμε τα ψηφία στο τμήμα helpers ως εξής:

digit = ['0'..'9'];

Για να ορίσουμε ένα helper γράφουμε το όνομά του και στη συνέχεια ένα ίσον. Δεξιά από το ίσον μπορούμε να γράψουμε την αριθμητική τιμή που αντιστοιχεί στο χαρακτήρα του helper ή το χαρακτήρα μέσα σε απλά εισαγωγικά. Τέλος, βάζουμε ένα ερωτηματικό (semicolon). Για παράδειγμα :

quote             = ‘”‘;
cr            = 13;
lf            = 10;
single_quote        = 0×0027; //Ο χαρακτήρας ‘ (απλό εισαγωγικό)

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

any_unicode_char = [0..0xffff] ; //Όλοι οι χαρακτήρες Unicode

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

letter = ['a'..'z'] | ['A'..'Z'];

Επίσης, μπορούμε να αφαιρέσουμε/προσθέσουμε κάποιο χαρακτήρα από μία ακολουθία/σετ. Π.χ. :

non_quote        = [any_unicode_char - quote];
permitted_in_string    = [non_quote - new_line];
permitted_in_comment    = [any_unicode_char - new_line];
new_line        = [cr + lf];

Τέλος, θα μπορούσαμε να χρησιμοποιήσουμε τα σύμβολα *, + και ?:

a* -> το a καμία, μία η περισσότερες φορές
a+ -> το a μία η περισσότερες φορές
a? -> το a μία ή καμία φορά

όπου a ένας χαρακτήρας, ένας προηγουμένως ορισμένoς helper ή κάποιος συνδυασμός μέσα σε παρενθέσεις.

Έτσι πλέον το αρχείο μας έχει τη μορφή:

Package subbasic;

Helpers

any_unicode_char     = [0..0xffff] ; //Όλοι οι χαρακτήρες Unicode
cr            = 13;
lf            = 10;
new_line        = [cr + lf];
quote             = ‘”‘;
single_quote        = 0×0027; //Ο χαρακτήρας ‘ (απλό εισαγωγικό)
non_quote        = [any_unicode_char - quote];
permitted_in_string    = [non_quote - new_line];
permitted_in_comment    = [any_unicode_char - new_line];
letter             = ['a'..'z'] | ['A'..'Z'];
digit             = ['0'..'9'];

Tokens

Ορισμός των tokens

Πλέον είναι ώρα να ορίσουμε τα tokens. Οι ορισμοί γράφονται κάτω από τη γραμμή :

Tokens

με τον ίδιο τρόπο όπως για τους helpers.
Αρχικά ορίζουμε το κενό, την αλλαγή γραμμής και το tab:

space = ‘ ‘;
newline = cr | lf | cr lf;
tab = 9;

Ορίζουμε τις δεσμευμένες λέξεις(case sensitive):

Μεταβλητές:

string_var = letter (letter | digit | ‘_’)* ‘$’; //γράμμα ακολουθούμενο από γράμματα ή ψηφία ή κάτω παύλες και στο τέλος $
num_var = letter (letter | digit | ‘_’)*;

Σταθερές:

string_const = quote permitted_in_string* quote;
num_const = digit+; // ένα ή περισσότερα ψηφία

Σύμβολα:

symbol = ‘+’| ‘-’ | ‘*’ | ‘/’ | ‘(‘ | ‘)’ | ‘=’ | ‘,’ | ‘;’;
lt = ‘<’;
gt = ‘>’;

Σχόλια:

comment = single_quote permitted_in_comment*;

Τέλος, θα ορίσουμε ένα token που θα περιλαμβάνει οποιοδήποτε άλλο χαρακτήρα:

misc = any_unicode_char ;

Το τελικό αρχείο θα είναι αυτό:

Package subbasic;

Helpers

Tokens

space            = ‘ ‘;
newline            = cr | lf | cr lf;
tab            = 9;

string_const = quote permitted_in_string* quote;
num_const = digit+; // ένα ή περισσότερα ψηφία

symbol            = ‘+’| ‘-’ | ‘*’ | ‘/’ | ‘(‘ | ‘)’ | ‘=’ | ‘,’ | ‘;’;
lt            = ‘<’;
gt            = ‘>’;

comment = single_quote permitted_in_comment*;

misc = any_unicode_char;

Το αποθηκεύουμε ως subbasic.grammar και το περνάμε ως είσοδο στο SableCC με την εντολή:

java -jar sablecc.jar subbasic.grammar

Μετά την εκτέλεση του SableCC πρέπει να έχει παραχθεί ένας φάκελος με το όνομα subbasic και μέσα σε αυτόν βρίσκονται οι απαραίτητες τάξεις για τη λεκτική ανάλυση.

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

Cyberpython Online