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

Νικόλαος Σ. Παπασπύρου και Εμμανουήλ Σ. Σκορδαλάκης

Πρόλογος

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

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

Ο ηλεκτρονικός υπολογιστής (Η/Υ) άνοιξε το δρόμο για την αυτοματοποίηση εργασιών που επεξεργάζονται δεδομένα (data processes), πράγμα που ήταν το όνειρο πολλών γενεών ανθρώπων. Όπως κατασκευάζεται σήμερα, ο Η/Υ μπορεί να αυτοματοποιεί την εκτέλεση τέτοιων εργασιών αν του δοθεί μια περιγραφή τους, που ονομάζεται πρόγραμμα, σε μια κατάλληλη γλώσσα, που ονομάζεται γλώσσα προγραμματισμού. Η μόνη γλώσσα προγραμματισμού που μπορεί να εκτελεί τυφλά ο Η/Υ είναι η γλώσσα μηχανής του, η οποία όμως είναι πολύ χαμηλού επιπέδου και επομένως δύσχρηστη. Για να εκτελεστεί ένα πρόγραμμα πρέπει να γραφεί σ' αυτή τη γλώσσα, αυτό όμως είναι ένα εξαιρετικά δύσκολο εγχείρημα. Τόσο δύσκολο που πρακτικά η συγγραφή και συντήρηση μεγάλων προγραμμάτων σε γλώσσα μηχανής είναι σχεδόν αδύνατη.

Αυτό το σοβαρό πρόβλημα επιλύουν οι μεταγλωττιστές με αυτόματο τρόπο. Επιτρέπουν τη συγγραφή προγραμμάτων σε μια γλώσσα υψηλού επιπέδου, κατανοητή στον άνθρωπο αλλά όχι άμεσα εκτελέσιμη από τον Η/Υ. Τη γλώσσα αυτή μεταφράζουν οι μεταγλωττιστές στη γλώσσα μηχανής που ο Η/Υ μπορεί να εκτελεί. Με αυτόν τον τρόπο, οι μεταγλωττιστές λύνουν το πρόβλημα της χρησιμοποίησης γλωσσών προγραμματισμού υψηλού επιπέδου. Χωρίς αυτούς θα ήταν αδύνατο να αξιοποιήσουμε τους Η/Υ, αυτές τις εκπληκτικές μηχανές που έφεραν την τρίτη βιομηχανική επανάσταση και μας οδήγησαν στη σημερινή κοινωνία της πληροφορίας.

Σκοπός και στόχοι

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

Στόχοι του βιβλίου είναι:

• να συνδράμει στην απόκτηση γνώσεων χρήσιμων στην κατασκευή μεταγλωττιστών, μέσα από την ύλη που καλύπτεται σε αυτό, και

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

Αναγνωστικό κοινό

Το βιβλίο αυτό απευθύνεται στους διδάσκοντες και τους σπουδαστές των τελευταίων ετών τμημάτων Μηχανικών Υπολογιστών ή Πληροφορικής, και επίσης σε επαγγελματίες προγραμματιστές που θέλουν να αποκτήσουν γνώσεις και δεξιότητες στην κατασκευή μεταγλωττιστών, σε εισαγωγικό επίπεδο. Προϋποτίθεται ότι οι αναγνώστες έχουν βασικές γνώσεις αλγορίθμων, δομών δεδομένων, γλωσσών προγραμματισμού και αρχιτεκτονικής υπολογιστών. Απαραίτητο επίσης είναι να διαθέτουν εμπειρία στον προγραμματισμό Η/Υ και να είναι εξοικειωμένοι με μια γλώσσα προγραμματισμού όπως η Pascal, η C, η C++ και η Java.

Περιεχόμενο

Η ύλη του βιβλίου χωρίζεται σε δέκα κεφάλαια και δύο παραρτήματα. Η δομή της ύλης και οι αλληλεξαρτήσεις μεταξύ των ενοτήτων από τις οποίες αυτή αποτελείται φαίνονται στο σχήμα Π.1.

Σχήμα Π.1.  Δομή της ύλης και αλληλεξαρτήσεις μεταξύ των ενοτήτων αυτής.

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

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

Στο Κεφάλαιο 2 γίνεται μια εισαγωγή σε έννοιες που σχετίζονται με την περιγραφή και την αναγνώριση τυπικών γλωσσών και είναι χρήσιμες κατά την κατασκευή μεταγλωττιστών: κανονικές γλώσσες και εκφράσεις, πεπερασμένα αυτόματα, γλώσσες και γραμματικές χωρίς συμφραζόμενα, αυτόματα στοίβας και κατηγορικές γραμματικές.

Στο Κεφάλαιο 3 περιγράφεται η φάση της λεκτικής ανάλυσης. Η παρουσίαση εστιάζεται στην περιγραφή και την αναγνώριση των λεκτικών μονάδων, με χρήση τροποποιημένων πεπερασμένων αυτομάτων που ονομάζονται διαγράμματα μετάβασης. Περιγράφεται πρώτα ο τρόπος σχεδίασης και υλοποίησης ενός λεκτικού αναλυτή βασισμένου στα διαγράμματα μετάβασης, και στη συνέχεια ο τρόπος υλοποίησης χρησιμοποιώντας τα μεταεργαλεία lex / flex.

Στο Κεφάλαιο 4 περιγράφεται η φάση της συντακτικής ανάλυσης. Περιγράφεται ο τρόπος σχεδίασης των δυο βασικών κατηγοριών συντακτικών αναλυτών, από πάνω προς τα κάτω (top-down) και από κάτω προς τα πάνω (bottom-up), που διαφέρουν ως προς τον τρόπο κατασκευής του συντακτικού δέντρου. Στη συνέχεια περιγράφεται ο τρόπος υλοποίησης ενός συντακτικού αναλυτή χρησιμοποιώντας τα μεταεργαλεία yacc / bison.

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

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

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

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

Στο Κεφάλαιο 9 περιγράφεται η φάση παραγωγής τελικού κώδικα. Παρουσιάζονται κατ' αρχήν ορισμένα γενικά θέματα πού αφορούν στη σχεδίαση του γεννήτορα τελικού κώδικα και στη συνέχεια περιγράφεται ένας αντιπροσωπευτικός προσωπικός υπολογιστής, βασισμένος στον επεξεργαστή 8086 της Intel, και η συμβολική του γλώσσα. Αφού συζητηθούν εν συντομία οι τεχνικές που χρησιμοποιούνται στους σύγχρονους μεταγλωττιστές για την παραγωγή τελικού κώδικα, περιγράφεται ένα απλοϊκό σχήμα μετάφρασης από τον ενδιάμεσο κώδικα σε μορφή τετράδων σε αυτή την τελική γλώσσα.

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

Στο Παράρτημα Α περιγράφεται πλήρως η σύνταξη και η σημασιολογία της υποθετικής γλώσσας προγραμματισμού PCL, που χρησιμοποιείται σε αυτό το βιβλίο ως παράδειγμα για την κατασκευή ενός απλού μεταγλωττιστή. Η PCL βασίζεται σε ένα γνήσιο υποσύνολο της ISO Pascal και, λόγω των πολλών ομοιοτήτων με αυτήν τόσο από πλευράς σύνταξης όσο και από πλευράς σημασιολογίας, η περιγραφή της είναι σύντομη με εξαίρεση τα σημεία όπου οι δυο γλώσσες διαφέρουν.

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

Ασκήσεις

Στο τέλος κάθε κεφαλαίου υπάρχει μια σειρά ασκήσεων που βοηθούν τον αναγνώστη στην κατανόηση και εμπέδωση της διδαχθείσας ύλης. Οι ασκήσεις που σημειώνονται με αστεράκι (π.χ. 1.1*) είναι δυσκολότερες από τις υπόλοιπες. Οι ασκήσεις που σημειώνονται με το γράμμα πι (π.χ. 1.2^π) αφορούν στην κατασκευή προγραμμάτων που, τις περισσότερες φορές, αντιστοιχούν σε τμήματα ενός υποθετικού μεταγλωττιστή. Για την επίλυση αυτών των ασκήσεων απαιτείται συνήθως πολύωρη προγραμματιστική εργασία.

Τρόπος χρήσης

Οι συγγραφείς αυτού του βιβλίου είναι της άποψης ότι για να κατανοήσει κανείς σε βάθος τις αρχές που διέπουν τη θεωρία και την πράξη των μεταγλωττιστών είναι απαραίτητο να "βουτήξει τα χέρια του" και να κατασκευάσει ο ίδιος ένα μεταγλωττιστή. Για το λόγο αυτό, οι συγγραφείς προτείνουν τον ισοβαρή διαχωρισμό του μαθήματος σε δύο μέρη, το θεωρητικό και το πρακτικό. Αντικείμενο του δεύτερου είναι η κατασκευή ενός πειραματικού μεταγλωττιστή από τους σπουδαστές. Ανάλογα με το επίπεδο των σπουδαστών, η κατασκευή μπορεί να περιορίζεται σε επιλεγμένα τμήματα του μεταγλωττιστή, ενώ τα υπόλοιπα μπορούν να δίνονται από τους διδάσκοντες. Επίσης, οι σπουδαστές μπορούν να είναι χωρισμένοι σε ομάδες των δύο ή τριών, ώστε να αποκτούν εμπειρία συνεργασίας σε ένα έργο ανάπτυξης λογισμικού αρκετά μεγάλης κλίμακας.

Συγκεκριμένα, οι συγγραφείς προτείνουν τη χρήση του βιβλίου στο πλαίσιο ενός εξαμηνιαίου μαθήματος με τέσσερις ώρες εβδομαδιαίως, δύο ώρες διαλέξεων και δύο ώρες εργαστηρίου, ως εξής (βλ. και σχήμα Π.2):

Σχήμα Π.2.  Πρόγραμμα μαθήματος 1.
Ισοβαρής θεωρία και εργαστήριο με πλήρη υλοποίηση μεταγλωττιστή.

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

Σχήμα Π.3.  Πρόγραμμα μαθήματος 2.
Έμφαση στη θεωρία, εργαστήριο με μερική υλοποίηση μεταγλωττιστή.

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

Σχήμα Π.4.  Πρόγραμμα μαθήματος 3.
Χωρίς εργαστηριακό μέρος.

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

Συμπλήρωμα

Το βιβλίο αυτό συμπληρώνεται με επιπρόσθετο εκπαιδευτικό υλικό που έχει τοποθετηθεί στο διαδίκτυο στην ηλεκτρονική διεύθυνση:

http://www.softlab.ntua.gr/~nickie/Books/Compilers/

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

• Ένα μεταγλωττιστή ενός περάσματος σε πλήρη μορφή για την υποθετική γλώσσα PCL που περιγράφεται σε αυτό το βιβλίο, αποτελούμενο από λεκτικό αναλυτή, συντακτικό αναλυτή, σημασιολογικό αναλυτή, πίνακα συμβόλων, γεννήτορα ενδιάμεσου κώδικα και γεννήτορα τελικού κώδικα. Ο μεταγλωττιστής αυτός είναι διαθέσιμος σε μορφή πηγαίου κώδικα, γραμμένου σε ANSI C, με αναλυτικά σχόλια.

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

• Μια βιβλιοθήκη χρόνου εκτέλεσης, που μπορεί να χρησιμοποιηθεί για την εκτέλεση προγραμμάτων της PCL. Με μικρές τροποποιήσεις, η βιβλιοθήκη αυτή μπορεί να χρησιμοποιηθεί και για άλλες αρχικές γλώσσες.

• Περιγραφές μερικών υποθετικών γλωσσών προγραμματισμού που μπορούν να αποτελέσουν θέματα εργασιών στο πλαίσιο ενός εισαγωγικού μαθήματος στους μεταγλωττιστές.

• Θέματα εξετάσεων, μαζί με τις λύσεις τους, τα οποία έχουν δοθεί στο παρελθόν για την εξέταση του μαθήματος "Εισαγωγή στους Μεταγλωττιστές" στο Τμήμα Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών του Εθνικού Μετσόβιου Πολυτεχνείου.

• Συνδέσμους προς άλλες χρήσιμες πηγές στο διαδίκτυο, σχετικές με το θέμα αυτού του βιβλίου.

Ευχαριστίες

Πολλοί συνέβαλαν στην προετοιμασία του υλικού που συμπεριλαμβάνεται σε αυτό το βιβλίο. Ιδιαίτερα, θα θέλαμε να ευχαριστήσουμε θερμά τους μεταπτυχιακούς σπουδαστές Γιάννη Κασσιό και Σπύρο Τριανταφύλλη για την πολύτιμη βοήθεια που μας πρόσφεραν κατά την προετοιμασία της παρούσας έκδοσης. Επίσης ευχαριστούμε τους διδάκτορες Πληροφορικής: Δημήτρη Ματσάκη, Παναγιώτη Τραχανιά και Γιάννη Ψαρομήλιγκο, τους μεταπτυχιακούς σπουδαστές: Αντώνη Καβαρνό και Κώστα Ταβερναράκη, καθώς και πολλούς προπτυχιακούς σπουδαστές για τη βοήθειά τους σε προγενέστερες εκδόσεις αυτού του βιβλίου, σε μορφή πανεπιστημιακών σημειώσεων.

Αθήνα, Ιούλιος 2002.

Νίκος Παπασπύρου
Μανόλης Σκορδαλάκης

Οι ηλεκτρονικές διευθύνσεις των συγγραφέων είναι: