Μεταγλωτιστές

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

2. Λεκτική Ανάλυση (Lexical Analysis)
Πρόκειται για το έργο του μετασχηματισμού της ανεπεξέργαστης σειράς χαρακτήρων ενός προγράμματος σε μια ροή από tokens (token stream). Η κατασκευή των Λεκτικών Αναλυτών χρησιμοποιεί βασικές έννοιες της Επιστήμης των Υπολογιστών με σημαντική χρησιμότητα σε πλήθος εφαρμογών.
Συγκεκριμένα εισάγεται η έννοια των Κανονικών Εκφράσεων (Regular Expressions) και των συσχετιζόμενων Μαθηματικών Μοντέλων των Μη-αιτιοκρατικών Πεπερασμένων Αυτομάτων (Nondeterministic Finite Automata) και των Αιτιοκρατικών Πεπερασμένων Αυτομάτων (Deterministic Finite Automata). Παρουσιάζεται η συστηματική κατασκευή λεκτικών αναλυτών βασισμένων στα παραπάνω μαθηματικά εργαλεία, με την πιθανή χρησιμοποίηση και αυτόματων εργαλείων λογισμικού (lexer generators).

3. Συντακτική Ανάλυση (Syntax Analysis)
Η φάση της συντακτικής ανάλυσης πραγματοποιεί το σημαντικότατο έργο της κατασκευής του δέντρου σύνταξης (syntax tree) από την ροή tokens που λαμβάνεται από τον λεκτικό αναλυτή. Η εύρεση των συντακτικών σφαλμάτων (syntax errors) του προγράμματος είναι αρμοδιότητα της παρούσας φάσης.
Η έννοια των γραμματικών (grammars) αποτελεί την θεωρητική βάση στην κατασκευή συντακτικών αναλυτών. Η κατηγορία των γραμματικών ανεξάρτητων συμφραζόμενων (context free grammars) είναι προεξέχουσας σημασίας. Αναλύονται μέθοδοι κατασκευής δέντρων σύνταξης (syntax trees) με σαρωτές (parsers) βασιζόμενους σε τυπικές γραμματικές. Ο χειρισμός της ασάφειας (ambiguity) και η υλοποίηση της επιθυμητής προτεραιότητας τελεστών (operator precedence) αποτελούν σημαντικά θέματα. Μελετούνται τα συναφή θέματα του LL(1) Parsing, LR Parsing, Recursive Descent Parsing και SLR Parsing .

4. Εμβέλειες και Πίνακες Συμβόλων (Scopes and Symbol Tables)
Οι σύγχρονες γλώσσες προγραμματισμού, ιδιαίτερα οι αντικειμενοστραφείς, παρέχουν την δυνατότητα καθορισμού της εμβέλειας στην οποία κάθε μεταβλητή είναι ορατή. Ο μεταγλωτιστής χρησιμοποιώντας ευέλικτες δομές πινάκων συμβόλων (symbol tables) υλοποιεί τους αντίστοιχους κανόνες ορατότητας (ή εμβέλειας) μεταβλητών της γλώσσας.

5. Διερμήνευση (Interpretation)
Στο σημείο αυτό, της κατασκευής δηλαδή του δέντρου σύνταξης και των συσχετισμένων πινάκων συμβόλων, γίνεται δυνατή η διερμήνευση (interpretation) του προγράμματος, δίχως την παραγωγή εκτελέσιμου κώδικα. Το έργο αυτό πραγματοποιείται με μια συστηματική επίσκεψη στους κόμβους του δέντρου σύνταξης (syntax tree traversal). Με την διερμήνευση του κώδικα παρέχεται η δυνατότητα ευέλικτης αποσφαλμάτωσης (debugging). Παρά ταύτα, η ταχύτητα της διερμηνευμένου κώδικα δεν επιδέχεται σύγκριση με μεταφρασμένο κώδικα. Για τον λόγο αυτό, οι interpreters περιορίζονται μόνο στην φάση ανάπτυξης και πρωτοτυποποίησης συστημάτων και για την “συγκόληση” (gluing) μεταφρασμένων τμημάτων κώδικα.

6. Έλεγχος Τύπων (Type checking)
Στο σημείο αυτό εισάγεται η έννοια της σημασιολογικής ανάλυσης (semantic analysis), που έχει ως στόχο την ανίχνευση σφαλμάτων που έχουν να κάνουν με την σημασιολογία των εκφράσεων και όχι απλά της σύνταξης. Ένα εργαλείο για ανίχνευση μερικών τέτοιων σφαλμάτων είναι ο συσχετισμός τύπων με μεταβλητές και η επιβολή κανόνων ορθής χρησιμοποίησης και σύνθεσης τύπων.
Η κατασκευή μιας γλώσσας ως statically typed , προαπαιτεί από τον μεταγλωτιστή τον υπολογισμό τύπων για όλες τις μεταβλητές. Παραδοσιακά αυτό γίνεται με δηλώσεις τύπων (type declarations), αν και πολλές σύγχρονες γλώσσες συνδυάζουν και συστήματα για αυτόματη ανακάλυψη του τύπου (type inference systems).
Οι dynamically typed γλώσσες αναβάλουν τον καθορισμό των τύπων των μεταβλητών μέχρι τον χρόνο εκτέλεσης (run time). Η τεχνολογία τους είναι πολύ διαφορετική. Αναπτύσσονται οι βασικές προσεγγίσεις υλοποίησης του “duck typing” και αλγόριθμοι για σχετικά αποτελεσματική εκτέλεση δυναμικού κώδικα (dynamically typed κώδικα). Παραδοσιακά χρησιμοποιούνται σχήματα caching, αλλά σύγχρονα περιβάλλοντα εκτέλεσης, όπως η Java 7, παρέχουν και υποστήριξη σε χαμηλό επίπεδο (π.χ. εντολή invoke dynamic της Java 7).

7. Ενδιάμεση Παραγωγή Κώδικα (Intermediate Code Generation)
Η παραγωγή μιας ευέλικτης μορφής κώδικα από το δέντρο σύνταξης διευκολύνει εξαιρετικά το δύσκολο έργο της βελτιστοποίησης (optimization) και της παραγωγής τπου τελικού κώδικα (code generation). Μελετούνται παραδείγματα μετάφρασης προγραμματιστικών δομών σε ενδιάμεσες μορφές κώδικα. Στο ίδιο πλαίσιο είναι και η αντιστοίχηση σύνθετων δομών δεδομένων (structures, classes), πινάκων (arrays) και δηλώσεων συναρτήσεων/μεθόδων.

8. Παραγωγή Κώδικα (Code Generation)
Η παραγωγή του τελικού κώδικα από την ενδιάμεση μορφή, περιπλέκει πολλά νέα προβλήματα, τα οποία έχουν σχέση και με την αρχιτεκτονική του hardware για την οποία προορίζεται ο κώδικας. Μελετούνται θέματα όπως η κατανομή καταχωρητών (register allocation), η κατασκευή των activation records για την κλήση μεθόδων, η ανάλυση liveness μεταβλητών και γίνεται εισαγωγή σε σχήματα για data-flow ανάλυση και βελτιστοποίηση του κώδικα.