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

Από Βικιεπιστήμιο
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
           ΜΕΤΑΓΛΩΤΤΙΣΤΕΣ

Ένας μεταγλωττιστής (compiler) είναι ένα πρόγραμμα που διαβάζει ένα άλλο
πρόγραμμα γραμμένο σε κάποια γλώσσα πηγή(source) - και το μεταφράζει
σε ένα ισοδύναμο πρόγραμμα σε άλλη γλώσσα - τη γλώσσα στόχο(target).
Σημαντικό κομμάτι της μετάφρασης, είναι η αναφορά στο χρήστη της ύπαρξης 
σφαλμάτων(bugs) στο πρόγραμμα πηγή.
Με πρώτη ματιά, οι διάφοροι μεταγλωττιστές φαίνεται να επικαλύπτονται.
Υπάρχουν χιλιάδες γλώσσες προγραμματισμού, από τις παραδοσιακές όπως Pascal 
ή Fortran, μέχρι τις ειδικού σκοπού που έχουν ανακύψει σε κάθε εφαρμογή των
υπολογιστών. Ποικίλλουν επίσης και οι τελικές γλώσσες(target), μια target
γλώσσα είναι επίσης μια γλώσσα προγραμματισμού ή η γλώσσα μηχανής οποιουδή
ποτε υπολογιστή από μικροϋπολογιστή μέχρι σούπερ υπολογιστή.
Οι compilers διακρίνονται συχνά σε απλού-περάσματος(one-pass), πολλαπλών-
περασμάτων(multi-pass), lead-and-go, εκσφαλμάτωσης(debugging) ή βελτιστοποί
ησης(optimizing), ανάλογα με το πώς φτιάχνονται ή πως λειτουργούν. Πέρα από
την πολυπλοκότητά τους οι βασικές τους λειτουργίες είναι οι ίδιες. Κατανοώ
ντας αυτές τις λειτουργίες, μπορούμε να φτιάξουμε μεταγλωττιστές(compilers),
για μεγάλο εύρος γλωσσών πηγής και target, χρησιμοποιώντας κάποιες βασικές 
τεχνικές.
Η γνώση μας για το πως οργανώνουμε και γράφουμε μεταγλωττιστές, έχει αυξηθεί
πολύ από τη δεκαετία το '50 που πρωτοεμφανίστηκαν. Δεν υπάρχει ακριβής ημε
ρομηνία κατασκευής του πρώτου compiler, γιατί είχαν γίνει προσπάθειες από 
πολλές ομάδες. Έχει γίνει επίσης πολλή δουλειά τελευταία για τη μετάφραση
μαθηματικών τύπων σε γλώσσα μηχανής.
Κατά τη διάρκεια της δεκαετίας του '50 ήταν πολύ δύσκολο να γραφούν compi
lers. Π.χ. ο πρώτος μεταγλωττιστής της Fortran χρειάστηκε 18 ανθρωποέτη 
για να γραφεί. Από τότε επινοήθηκαν πολλές τεχνικές. Καλές γλώσσες υλοποί
ησης, προγραμματιστικά περιβάλλοντα και εργαλεία λογισμικού. Με αυτές τις
προϋποθέσεις μπορούν και πρωτοετείς φοιτητές να γράψουν έναν compiler σε 
ένα εξάμηνο σπουδών.

       ΤΟ ΜΟΝΤΕΛΟ ΑΝΑΛΥΣΗΣ - ΣΥΝΘΕΣΗΣ

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

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

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

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

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

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

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

3. 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. Κάνουν τα ακόλουθα:
1. Macro processing
2. File inclusion
3. "Rational" preprocessors
4. Language extensions


        ΕΡΓΑΛΕΙΑ ΚΑΤΑΣΚΕΥΗΣ ΜΕΤΑΓΛΩΤΤΙΣΤΩΝ

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

1. Parser generators: Παράγουν συντακτικούς αναλυτές, από είσοδο που βασίζεται σε
context-free γραμματικές.
2. Scanner-generators: Παράγουν αυτόματα λεκτικούς αναλυτές, από προδιαγραφές
βασισμένες σε regular expressions. Η βασική οργάνωση του λεκτικού αναλυτή που προκύ
πτει είναι τελικά ένα πεπερασμένο αυτόματο.
3. Syntax-directed translation engines: Παράγουν ρουτίνες που διασχίζουν ένα parse
tree για να δώσουν ενδιάμεσο κώδικα.
4. Automatic code generators: Παίρνουν μια συλλογή κανόνων που καθορίζουν τη μετά
φραση κάθε λειτουργίας της ενδιάμεσης γλώσσας σε γλώσσα μηχανής.
5. Data-flow engines: Η "data-flow analysis", απαραίτητη για την βελτιστοποίηση του
κώδικα, είναι η συλλογή πληροφοριών για το πως μεταφέρονται οι τιμές από το ένα τμή
μα στο άλλο.