Επισκόπηση Γλωσσών Προγραμματισμού και Δομή Μεταγλωττιστών

Κατηγοριοποίηση Γλωσσών Προγραμματισμού

Α. Γλώσσες Μηχανής

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

Β. Συμβολικές Γλώσσες ή Γλώσσες Χαμηλού Επιπέδου

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

Γ. Γλώσσες Υψηλού Επιπέδου (3ης Γενιάς)

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

• FORTRAN
• COBOL
• ALGOL
• PL/1
• LISP
• PROLOG
• BASIC
• PASCAL
• C
• C++
• JAVA

Δ. Γλώσσες 4ης Γενιάς

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

Τύποι Σφαλμάτων στον Προγραμματισμό

Σφάλματα:

• Λεκτικά λάθη: Όπως ορθογραφικά λάθη δεσμευμένων λέξεων έως παράλειψη εισαγωγικών σε συμβολοσειρές.
• Συντακτικά λάθη: Όπως παράλειψη ερωτηματικών, ανοιχτές παρενθέσεις, κ.τ.λ.
• Σημασιολογικά λάθη: Όπως προβλήματα τύπων, για παράδειγμα επιστροφή τιμής από συνάρτηση Java η οποία είναι δηλωμένη ως void.
• Λογικά λάθη: Που μπορεί να είναι από απλά λάθη λογικής από τη μεριά του προγραμματιστή έως τη χρήση του τελεστή = αντί για == σε ένα πρόγραμμα C.

Ανάνηψη από Σφάλματα (Error Recovery)

Ανάνηψη από σφάλματα: Διαδικασία κατά την οποία ανιχνεύεται ένα συντακτικό σφάλμα και συνεχίζεται η ανάλυση για την ανίχνευση περισσοτέρων λαθών.

Τεχνικές Ανάνηψης

Οι τεχνικές ανάνηψης περιλαμβάνουν:

1. Error Recovery (Panic Mode)

1. Ανίχνευση συντακτικού λάθους.
2. Αγνόηση μέρους της εισόδου.
3. Αρχικοποίηση περιβάλλοντος αναλυτή (στοίβα, μεταβλητές) για την ανάλυση της υπόλοιπης συμβολοσειράς εισόδου.

Αυτή η μέθοδος μπορεί να οδηγήσει σε ανίχνευση επόμενων λαθών που δεν είναι στην πραγματικότητα λάθη (cascaded errors) $\Rightarrow$ ποιότητα ανάνηψης από σφάλματα. Οι φάσεις της σημασιολογικής ανάλυσης και της παραγωγής ενδιάμεσου κώδικα απενεργοποιούνται. Το Panic Mode αναζητά ένα ασφαλές σύμβολο (π.χ. ‘;’) από το οποίο επανεκκινείται η συντακτική ανάλυση.

2. Error Repair

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

• Εισαγωγή/διαγραφή τερματικών συμβόλων. (π.χ. x=a b+c; $\Rightarrow$ εισαγωγή του συμβόλου ‘=’ ή ‘+’ κτλ. μετά το a)

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

3. Error Correction

Ό,τι και στην τεχνική του Error Repair με τη διαφορά ότι οι τροποποιήσεις της εισόδου αντικατοπτρίζουν το τι ήθελε ο χρήστης να γράψει.

Μεταγλώττιση και Διερμηνεία

Μεταγλωττιστής (Compiler)

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

Διερμηνέας (Interpreter)

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

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

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

Διαδικασία Μετατροπής Κώδικα

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

Φάσεις Μεταγλώττισης: Ανάλυση και Σύνθεση

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

Το Περιεχόμενο ενός Compiler

Προεπεξεργασία και Τελικό Πρόγραμμα

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

Σκελετός Πηγαίου Προγράμματος $\rightarrow$ Preprocessor $\rightarrow$ Πηγαίο Πρόγραμμα $\rightarrow$ Μεταγλωττιστής $\rightarrow$ Τελικό Πρόγραμμα Assembly $\rightarrow$ Assembler $\rightarrow$ Relocatable Κώδικας Μηχανής $\rightarrow$ Load/Link $\rightarrow$ Απόλυτος Κώδικας Μηχανής

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

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

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

Οι Φάσεις ενός Compiler

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

Πηγαίο Πρόγραμμα $\rightarrow$ Λεκτικός Αναλυτής $\rightarrow$ Συντακτικός Αναλυτής $\rightarrow$ |Symbol Table Manager| $\rightarrow$ Σημασιολογικός Αναλυτής $\rightarrow$ Error Handler $\rightarrow$ Δημιουργός Ενδιάμεσου Κώδικα $\rightarrow$ Βελτιστοποιητής Κώδικα Ανεξάρτητος από τη Μηχανή $\rightarrow$ Δημιουργός Κώδικα $\rightarrow$ Βελτιστοποιητής Κώδικα Εξαρτώμενος από τη Μηχανή $\rightarrow$ Τελικός Κώδικας

Αλληλεπίδραση με τον Πίνακα Συμβόλων και Διαχείριση Σφαλμάτων

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

Κατά τη διάρκεια της επεξεργασίας κάθε φάσης υπάρχει αλληλεπίδραση με ένα ιδιαίτερα σημαντικό τμήμα του μεταγλωττιστή, που ονομάζεται πίνακας συμβόλων. Ο πίνακας των συμβόλων καταγράφει πληροφορίες, που σχετίζονται με ονόματα, είτε αυτά είναι ονόματα συναρτήσεων, είτε ονόματα τύπων δεδομένων, μεταβλητών ή και σταθερών. Χρησιμοποιείται σχεδόν σε όλες τις φάσεις της μεταγλώττισης. Πιο συγκεκριμένα, κατά τη λεξική, τη συντακτική και τη σημασιολογική ανάλυση καταχωρούνται σε αυτόν ονόματα, η εκμετάλλευση των οποίων γίνεται κατά τη βελτιστοποίηση και τη σύνθεση του τελικού προγράμματος. Λειτουργίες όπως η εισαγωγή, η διαγραφή και η προσπέλαση δεδομένων στον πίνακα αυτό, χρειάζεται να εκτελούνται αποδοτικά, γι' αυτό και συνήθως γίνεται χρήση πίνακα Hash ή κάποιας δομής δένδρου.

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

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

Ειδικότεροι Έλεγχοι Σφαλμάτων

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

Εργαλεία Δημιουργίας Μεταγλωττιστών

Bison

Το αρχείο εισόδου του Bison αποτελείται από τα παρακάτω τμήματα:

$ ightarrow$ Δηλώσεις της C $ ightarrow$ Δηλώσεις του yacc $ ightarrow$ Κανόνες $ ightarrow$ Κώδικα χρήστη

Η δομή του αρχείου είναι η παρακάτω:

Flex

Το Flex χωρίζεται σε τρία μέρη:

Μέρος Α: Ορισμοί

Α

• Σχόλια με τη σύμβαση της C: /* This is a comment */
• Μνημονικά ονόματα χρησιμοποιούνται στο Β μέρος ως συντομογραφίες για κανονικές εκφράσεις, π.χ. letter [A-Za-z], digit [0-9]
• Δηλώσεις αρχικών καταστάσεων
• Κώδικας C

Μέρος Β: Κανόνες

Β

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

(Παράδειγμα) %%

%%

Μέρος Γ: Συναρτήσεις

Γ

• Κώδικας C (Παράδειγμα)