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

Εισαγωγή

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

Με πρώτη ματιά, οι διάφοροι μεταγλωττιστές φαίνεται να επικαλύπτονται. Υπάρχουν χιλιάδες γλώσσες προγραμματισμού, από τις παραδοσιακές όπως Pascal ή Fortran, μέχρι τις ειδικού σκοπού που έχουν ανακύψει σε κάθε εφαρμογή των υπολογιστών. Ποικίλλουν επίσης και οι τελικές γλώσσες(target), μια target γλώσσα είναι επίσης μια γλώσσα προγραμματισμού ή η γλώσσα μηχανής οποιουδήποτε υπολογιστή από μικροϋπολογιστή μέχρι σούπερ υπολογιστή.

Οι compilers διακρίνονται συχνά σε μονού-περάσματος(one-pass), πολλαπλών-περασμάτων(multi-pass), lead-and-go, εκσφαλμάτωσης(debugging) ή βελτιστοποίησης(optimizing), ανάλογα με το πώς φτιάχνονται ή πως λειτουργούν. Πέρα από την πολυπλοκότητά τους οι βασικές τους λειτουργίες είναι οι ίδιες. Κατανοώντας αυτές τις λειτουργίες, μπορούμε να φτιάξουμε μεταγλωττιστές(compilers), για μεγάλο εύρος γλωσσών πηγής και target, χρησιμοποιώντας κάποιες βασικές τεχνικές.

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

Κατά τη διάρκεια της δεκαετίας του '50 ήταν πολύ δύσκολο να γραφούν compilers. Π.χ. ο πρώτος μεταγλωττιστής της Fortran χρειάστηκε 18 ανθρωποέτη για να γραφεί. Από τότε επινοήθηκαν πολλές τεχνικές. Καλές γλώσσες υλοποίησης, προγραμματιστικά περιβάλλοντα και εργαλεία λογισμικού. Με αυτές τις προϋποθέσεις μπορούν και πρωτοετείς φοιτητές να γράψουν έναν compiler σε ένα εξάμηνο σπουδών.

Το μοντέλο Ανάλυσης-Σύνθεσης

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

Κατά την ανάλυση, οι λειτουργίες του πηγαίου προγράμματος καταγράφονται σε μια ιεραρχική δομή δένδρου. Συχνά χρησιμοποιείται μια ειδική δομή δένδρου, το συντακτικό δένδρο(syntax tree), στο οποίο κάθε κόμβος αναπαριστά μια λειτουργία και τα παιδιά του αναπαριστούν τα ορίσματα της λειτουργίας αυτής.

Το στάδιο της ανάλυσης εκτελείται από τα περισσότερα εργαλεία λογισμικού. Παραδείγματα τέτοιων εργαλείων είναι:

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

• Pretty printers: Αναλύει ένα πρόγραμμα και το τυπώνει με τέτοιο τρόπο ώστε να είναι ορατή η δομή του προγράμματος.(π.χ. σχόλια, εντολές κτλ.)

• Static checkers: Διαβάζει ένα πρόγραμμα, το αναλύει και προσπαθεί να ανακαλύψει δυναμικά λάθη(bugs) χωρίς να το τρέξει.

• Interpreters: Αντί να παράγει ένα πρόγραμμα τελικό(target), ένας διερμηνευτής(interpreter) εκτελεί μια μια τις εντολές του πηγαίου προγράμματος. Χρησιμοποιούνται συχνά για να εκτελέσουν γλώσσες εντολών, γιατί συνήθως, κάθε λειτουργία σ' αυτές τις γλώσσες είναι μια ανάκληση σύνθετης υπορουτίνας.

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

• Text formatters: Παίρνει σαν είσοδο μια σειρά από χαρακτήρες, σαν κείμενο, και με εντολές για παραγράφους, εικόνες ή μαθηματικές δομές όπως subscripts ή superscripts.

• Silicon compilers: Έχει μια πηγαία γλώσσα που μοιάζει με κλασσική γλώσσα προγραμματισμού. Όμως οι μεταβλητές της δεν είναι θέσεις μνήμης αλλά λογικά σήματα(0 ή 1) ή ομάδες σημάτων σε κύκλωμα. Η έξοδός του είναι η σχεδίαση ενός κυκλώματος σε κατάλληλη γλώσσα.

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

Το περιεχόμενο ενός compiler

Εκτός από τον compiler χρειάζονται και άλλα προγράμματα για να παραχθεί το τελικό. Το πηγαίο πρόγραμμα μπορεί να διαιρείται σε τμήματα(modules) αποθηκευμένα σε ξεχωριστά αρχεία. Το συμμάζεμα των επιμέρους αρχείων συχνά ανατίθεται σε ξεχωριστό πρόγραμμα που ονομάζεται preprocessor. Ο preprocessor μπορεί να αναπτύξει συντμήσεις, που λέγονται macros, σε εντολές, όπως φαίνεται στο σχήμα :

          σκελετός πηγαίου προγράμματος
                     |
                     |
                    ~~~
                preprocessor
                     |
                     |
                    ~~~
              πηγαίο πρόγραμμα
                     |
                     |
                    ~~~
                  compiler
                     |
                     |
                    ~~~
          τελικό πρόγραμμα assembly
                     |
                     |
                    ~~~
                  assembler
                     |
                     |
                    ~~~
          recolatable κώδικας μηχανής
                     |
                     |    <----------- load/link editor
                    ~~~
          απόλυτος κώδικας μηχανής

Ανάλυση του πηγαίου προγράμματος

Η φάση της ανάλυσης αποτελείται από 3 στάδια:

1. Γραμμική ανάλυση(linear analysis): στην οποία διαβάζεται μια σειρά χαρακτήρων που αποτελεί το πηγαίο από αριστερά-προς δεξιά και ομαδοποιείται σε tokens που είναι ακολουθίες χαρακτήρων με κάποιο νόημα.
2. Ιεραρχική ανάλυση(hierarchical analysis): στην οποία τα tokens ομαδοποιούνται ιεραρχικά σε φωλιασμένες(nested) συλλογές με συλλογικό νόημα.
3. Σημαντική ανάλυση(semantic analysis): όπου γίνονται συγκεκριμένοι έλεγχοι για να βεβαιωθούμε ότι τα τμήματα του προγράμματος ταιριάζουν λογικά.

Οι φάσεις ενός compiler

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

              πηγαίο πρόγραμμα
                     |
                     |
                    ~~~
              lexical analyzer
                     |
                     |
                    ~~~
              syntax analyzer
                     |
  symbol             | 
  table             ~~~             error
  manager     semantic analyzer    handler
                     |
                     |
                    ~~~
          intermediate code generator
                     |
                     |
                    ~~~
              code optimizer       
                     |
                     |
                    ~~~
              code generator
                     |
                     |
                    ~~~
              target program

Οι πρώτες τρεις φάσεις αποτελούν την ανάλυση. Δύο άλλες λειτουργίες, η διαχείριση λαθών(error handling) και η διαχείριση του symbol table, αλληλεπιδρούν με όλες τις φάσεις και αποτελούν δυνητικά φάσεις της μεταγλώττισης.

Preprocessors

Οι preprocessors παράγουν είσοδο ενός compiler. Κάνουν τα ακόλουθα:

• Macro processing
• File inclusion
• "Rational" preprocessors
• Language extensions

Εργαλεία κατασκευής μεταγλωττιστών

Τέτοια είναι οι εκσφαλματωτές(debuggers), version managers, profilers κτλ. Έχουν αναπτυχθεί επίσης και πιο ειδικευμένα εργαλεία υλοποίησης διάφορων φάσεων. Αυτά αναφέρονται ως compiler-compilers, compiler-generators, translator-writing systems. Ακολουθούν κάποια εργαλεία compiler-construction:

• Parser generators: Παράγουν συντακτικούς αναλυτές, από είσοδο που βασίζεται σε context-free γραμματικές.

• Scanner-generators: Παράγουν αυτόματα λεκτικούς αναλυτές, από προδιαγραφές βασισμένες σε regular expressions. Η βασική οργάνωση του λεκτικού αναλυτή που προκύπτει είναι τελικά ένα πεπερασμένο αυτόματο.

• Syntax-directed translation engines: Παράγουν ρουτίνες που διασχίζουν ένα parse tree για να δώσουν ενδιάμεσο κώδικα.

• Automatic code generators: Παίρνουν μια συλλογή κανόνων που καθορίζουν τη μετάφραση κάθε λειτουργίας της ενδιάμεσης γλώσσας σε γλώσσα μηχανής.

• Data-flow engines: Η "data-flow analysis", απαραίτητη για την βελτιστοποίηση του κώδικα, είναι η συλλογή πληροφοριών για το πως μεταφέρονται οι τιμές από το ένα τμήμα στο άλλο.