Μεταγλωττιστής (υπολογιστές)

Μεταγλωττιστής ή μεταφραστής (compiler) ονομάζεται ένα πρόγραμμα υπολογιστή που διαβάζει κώδικα γραμμένο σε μια γλώσσα προγραμματισμού (την πηγαία γλώσσα) και τον μεταφράζει σε ισοδύναμο κώδικα σε μια άλλη γλώσσα προγραμματισμού (τη γλώσσα στόχο). Το κείμενο της εισόδου ονομάζεται πηγαίος κώδικας (source code), ενώ η έξοδος του προγράμματος, η οποία συχνά έχει δυαδική μορφή, αντικειμενικός κώδικας (object code).

Ο όρος «μεταγλωττιστής» χρησιμοποιείται κυρίως για προγράμματα που μεταφράζουν μια γλώσσα προγραμματισμού υψηλού επιπέδου σε μια γλώσσα χαμηλότερου επιπέδου (όπως η συμβολική γλώσσα ή η γλώσσα μηχανής). Αν το μεταγλωττισμένο πρόγραμμα πρόκειται να εκτελεστεί σε έναν υπολογιστή που έχει διαφορετικό επεξεργαστή ή λειτουργικό σύστημα σε σχέση με την πλατφόρμα που εκτελείται ο μεταγλωττιστής, ο τελευταίος τότε ονομάζεται cross-compiler. Ένα πρόγραμμα που μεταφράζει από μια γλώσσα χαμηλού επιπέδου σε μια υψηλότερου επιπέδου ονομάζεται decompiler. Ένα πρόγραμμα που μεταφράζει από μια γλώσσα υψηλού επιπέδου σε μια άλλη, επίσης υψηλού επιπέδου, ονομάζεται συνήθως γλωσσικός μεταφραστής, μεταφραστής από πηγαίο κώδικα σε πηγαίο κώδικα (source to source translator) ή μετατροπέας γλωσσών. Ένα πρόγραμμα που μεταφράζει τη μορφή εκφράσεων σε άλλη μορφή, διατηρώντας την ίδια γλώσσα, ονομάζεται language rewriter.

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

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

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

Ιστορία

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

Κατά τα τέλη της δεκαετίας του 1950, προτάθηκαν οι πρώτες γλώσσες προγραμματισμού που ήταν ανεξάρτητες από τη μηχανή και ακολούθησε η ανάπτυξη αρκετών πειραματικών μεταγλωττιστών. Ο πρώτος μεταγλωττιστής γράφτηκε από τη Γκρέις Χόπερ, το 1952, για τη γλώσσα προγραμματισμού A-0. Η ομάδας της FORTRAN με αρχηγό τον Τζον Μπάκους στην IBM θεωρείται γενικά ότι παρουσίασε τον πρώτο πλήρη μεταγλωττιστή το 1957. Η COBOL ήταν μια από τις πρώτες γλώσσες που μεταγλωττίστηκαν σε πολλαπλές αρχιτεκτονικές, το 1960.

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

Οι πρώτοι μεταγλωττιστές γράφτηκαν σε συμβολική γλώσσα. Ο πρώτος μεταγλωττιστής που μπορούσε να μεταγλωττίσει τον εαυτό του σε μια γλώσσα υψηλού επιπέδου (self-hosting) κατασκευάστηκε το 1962 για τη Lisp από τους Τιμ Χαρτ και Μάικ Λέβιν στο MIT. Από τη δεκαετία του 1970 είναι συνηθισμένο να υλοποιείται ένας μεταγλωττιστής στη γλώσσα που μεταγλωττίζει, αν και τόσο η Pascal όσο και η C έχουν υπάρξει δημοφιλείς επιλογές ως γλώσσες υλοποίησης. Η κατασκευή ενός μεταγλωττιστή που να μπορεί να μεταγλωττίσει τον εαυτό του απαιτεί μια μέθοδο bootstrapping: ο πρώτος μεταγλωττιστής πρέπει να μεταγλωττιστεί είτε με το χέρι, είτε από έναν μεταγλωττιστή γραμμένο σε άλλη γλώσσα, είτε (όπως στον μεταγλωττιστή Lisp των Χαρτ και Λέβιν) να μεταγλωττιστεί εκτελώντας τον μεταγλωττιστή σαν διερμηνέα.

Οι μεταγλωττιστές στην εκπαίδευση

Η κατασκευή και η βελτιστοποίηση των μεταγλωττιστών διδάσκονται στα σχολεία και στα πανεπιστήμια ως μέρος της επιστήμης υπολογιστών. Σε μαθήματα αυτού του τύπου συνήθως δίνεται η υλοποίηση ενός μεταγλωττιστή για μια εκπαιδευτική γλώσσα προγραμματισμού. Ένα γνωστό παράδειγμα είναι ο μεταγλωττιστής της PL/0 από τον Νίκλαους Βιρθ, που χρησιμοποιήθηκε από τον Βιρθ για να διδάξει κατασκευή μεταγλωττιστών κατά τη δεκαετία του 1970. Παρά την απλότητά του, ο μεταγλωττιστής της PL/0 εισήγαγε αρκετές επιδραστικές ιδέες στον χώρο:

1. Ανάπτυξη προγράμματος με βαθμιαία εκλέπτυνση (stepwise refinement)
2. Χρήση ενός συντακτικού αναλυτή αναδρομικής κατάβασης (recursive descent parser)
3. Χρήση EBNF για τον ορισμό της σύνταξης μιας γλώσσας
4. Μια γεννήτρια κώδικα που παρήγαγε φορητό κώδικα (P-code)
5. Χρήση T-διαγραμμάτων στην τυπική περιγραφή του προβλήματος bootstrapping

Μεταγλώττιση

Οι μεταγλωττιστές επέτρεψαν τη δημιουργία προγραμμάτων που είναι ανεξάρτητα από τη μηχανή. Πριν από την ανάπτυξη της FORTRAN (FORmula TRANslator), της πρώτης γλώσσας υψηλού επιπέδου, τη δεκαετία του 1950, γινόταν χρήση συμβολικής γλώσσας, που είχε εξαρτήσεις από τον εκάστοτε υπολογιστή. Αν και η συμβολική γλώσσα παράγει προγράμματα που μπορούν να επαναχρησιμοποιηθούν και να τοποθετηθούν σε διαφορετικές θέσεις μνήμης, στην ίδια αρχιτεκτονική, πρέπει να τροποποιηθεί ή να ξαναγραφτεί αν το πρόγραμμα πρέπει να εκτελεστεί σε διαφορετική αρχιτεκτονική υπολογιστή.

Με τις γλώσσες προγραμματισμού υψηλού επιπέδου που ακολούθησαν τη FORTRAN, όπως η COBOL, η C και η BASIC, ο προγραμματιστής μπορούσε να γράφει πηγαίο κώδικα που να είναι ανεξάρτητος από τη μηχανή. Ο μεταγλωττιστής αναλάμβανε να μεταφράσει τον πηγαίο κώδικα υψηλού επιπέδου σε τελικά προγράμματα σε γλώσσα μηχανής για κάθε πλατφόρμα υλικού. Όταν το τελικό πρόγραμμα παραχθεί, ο χρήστης μπορεί να το εκτελέσει.

Δομή ενός μεταγλωττιστή

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

Το εμπρόσθιο τμήμα (front end) ελέγχει αν το πρόγραμμα είναι σωστά γραμμένο με βάση τη σύνταξη και τη σημασιολογία της γλώσσας προγραμματισμού. Σε αυτό το σημείο φαίνεται ποιο πρόγραμμα είναι έγκυρο και ποιο όχι, και εμφανίζονται μηνύματα σφάλματος. Εδώ επίσης ελέγχονται οι τύποι συλλέγοντας πληροφορία τύπων. Το εμπρόσθιο τμήμα παράγει επίσης μια ενδιάμεση αναπαράσταση (intermediate representation ή IR) του πηγαίου κώδικα, η οποία πρόκειται να δοθεί στο ενδιάμεσο τμήμα για επεξεργασία. Στο εμπρόσθιο τμήμα μπορούν να ανήκουν μεταξύ άλλων και τα εξής στάδια:

• ένα προεπεξεργαστή που αναλαμβάνει να επεξεργαστεί κάποιες ειδικές εντολές ή άλλα χαρακτηριστικά του πηγαίου κώδικα, ώστε να είναι σε κατάλληλη μορφή για τη μεταγλώττιση,
• ένα λεκτικό αναλυτή (lexical analyzer ή lexer) που τεμαχίζει τον πηγαίο κώδικα σε λεκτικές μονάδες (tokens), ξεχωρίζοντας για παράδειγμα τις λέξεις-κλειδιά, τις εντολές της γλώσσας και τις τιμές του προγράμματος,
• ένα συντακτικό αναλυτή (parser) που συνθέτει τις λεκτικές μονάδες με βάση τη σύνταξη της γλώσσας, ώστε να προκύψει μια αφηρημένη μορφή του προγράμματος (συντακτικό δέντρο), κατάλληλη για περαιτέρω επεξεργασία.

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

Στο ενδιάμεσο τμήμα (middle end) γίνονται οι βελτιστοποιήσεις. Συνηθισμένοι μετασχηματισμοί βελτιστοποίησης είναι η αφαίρεση άχρηστου ή απρόσιτου κώδικα, ο εντοπισμός και η διάδοση των σταθερών (constant propagation), η μεταφορά υπολογισμών εκτός συχνά χρησιμοποιούμενων τμημάτων (για παράδειγμα, μετακίνηση έξω από μια δομή επανάληψης), ή η εξειδίκευση ενός υπολογισμού ανάλογα με τον κώδικα που τον περιβάλλει. Το ενδιάμεσο τμήμα παράγει στη συνέχεια μια άλλη ενδιάμεση αναπαράσταση, για το οπίσθιο τμήμα. Οι περισσότερες βελτιστοποιήσεις έχουν ήδη γίνει στο ενδιάμεσο τμήμα.

Το οπίσθιο τμήμα (back end) είναι υπεύθυνο για τη μετάφραση της ενδιάμεσης αναπαράστασης του ενδιάμεσου τμήματος σε γλώσσα μηχανής, συμβολική γλώσσα, γλώσσα προγραμματισμού (όπως η C) ή κώδικα για κάποια αφηρημένη μηχανή (abstract machine) όπως ο κώδικας byte (bytecode). Κάθε εντολή της ενδιάμεσης αναπαράστασης αντιστοιχεί σε κάποιες συμβολικές εντολές. Η κατανομή καταχωρητών αντιστοιχεί καταχωρητές στις μεταβλητές του προγράμματος. Το οπίσθιο τμήμα χρησιμοποιεί το υλικό με τέτοιο τρόπο ώστε να χρησιμοποιούνται όλες οι λειτουργικές μονάδες του υλικού με αποδοτικό τρόπο. Αν και οι περισσότεροι αλγόριθμοι βελτιστοποίησης για αυτά τα προβλήματα είναι πολυπλοκότητας NP, έχουν αναπτυχθεί και αρκετά προχωρημένες ευριστικές τεχνικές.

Έξοδος του μεταγλωττιστή

Οι μεταγλωττιστές μπορούν να χωριστούν σε κατηγορίες ανάλογα με την πλατφόρμα στην οποία πρόκειται να εκτελεστεί ο παραγόμενος κώδικας (target platform).

Ένας μεταγλωττιστής ονομάζεται native ή hosted αν παράγει κώδικα που πρόκειται να εκτελεστεί στον ίδιο τύπο υπολογιστή και λειτουργικού συστήματος με αυτά στα οποία εκτελείται ο ίδιος ο μεταγλωττιστής. Αν ο παραγόμενος κώδικας πρόκειται να εκτελεστεί σε διαφορετική πλατφόρμα, τότε αναφερόμαστε σε cross compiler. Οι cross-compilers χρησιμοποιούνται συχνά στην ανάπτυξη λογισμικού για ενσωματωμένα συστήματα, τα οποία δεν προτίθεντε τα ίδια να υποστηρίξουν κάποιο περιβάλλον ανάπτυξης λογισμικού.

Η έξοδος ενός μεταγλωττιστή που παράγει κώδικα για μια εικονική μηχανή (virtual machine - VM) μπορεί να εκτελεστεί ή να μην εκτελεστεί στην ίδια πλατφόρμα με το μεταγλωττιστή που την παρήγαγε. Για αυτόν τον λόγο, οι μεταγλωττιστές αυτού του τύπου δεν θεωρείται ότι ανήκουν σε μια από τις προηγούμενες κατηγορίες.

Η γλώσσα χαμηλού επιπέδου στην οποία παράγει κώδικα ο μεταγλωττιστής μπορεί η ίδια να είναι μια γλώσσα υψηλού επιπέδου. Η C, η οποία συχνά θεωρείται ένα είδος φορητής συμβολικής γλώσσας, μπορεί επίσης να είναι η γλώσσα στόχος του μεταγλωττιστή. Για παράδειγμα, το Cfront, ο πρωτότυπος μεταγλωττιστής της C++, χρησιμοποιούσε τη C σαν γλώσσα παραγόμενου κώδικα. Ο κώδικας C που παράγεται από μεταγλωττιστές αυτού του τύπου συνήθως δεν προορίζεται για ανάγνωση και συντήρηση από ανθρώπους. Αυτό σημαίνει ότι μπορεί να μην ακολουθεί κανόνες στοίχισης ή άλλου τύπου για ευανάγνωστο κώδικα. Κάποια χαρακτηριστικά της C την κάνουν καλή γλώσσα στόχο, για παράδειγμα μπορεί να παραχθεί κώδικας C με οδηγίες #line ώστε να βοηθήσει στην αποσφαλμάτωση του αρχικού πηγαίου κώδικα.

Δείτε επίσης

• gcc, μεταγλωττιστής για τη C και άλλες, παρόμοιες γλώσσες, από το εγχείρημα GNU
• Lex, γεννήτρια λεκτικών αναλυτών
• Yacc, γεννήτρια συντακτικών αναλυτών

Εξωτερικοί σύνδεσμοι

• Compilers στο Curlie
• Compile-Howto (Αγγλικά)
• Basics of Compiler Design (Αγγλικά)
• Interpreters and Compilers (Αγγλικά)