ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ Σχολή Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών Εργαστήριο Τεχνολογίας Λογισμικού Τσόκος Θεόδωρος (tsokos@softlab.ntua.gr) Παπακυριάκου Μιχάλης (mpapakyr@softlab.ntua.gr)

 

Calvin Compiler

 

 

Παρακάτω, θα βρείτε μια αρκετά πλήρη περιγραφή της εργασίας των Μιχάλη Παπακυριάκου και Θοδωρή Τσόκου, για το μάθημα Εισαγωγή στους Μεταγλωττιστές, της Σχολής Ηλεκτρολόγων Μηχανικών και Μηχανικών Η/Υ , EΜΠ. Το μάθημα διδάσκεται στο 8ο εξάμηνο, ως κατ' επιλογήν της ροής Λογισμικού (Λ), από τον Λέκτορα Νίκο Παπασπύρου . Αντικείμενο του μαθήματος αποτελεί η εισαγωγή και μελέτη στην λειτουργία και κατασκευή των μεταγλωττιστών.

Εισαγωγή  |  Η γλώσσα Calvin  |  Υλοποίηση  |  Κώδικας

1) Εισαγωγή.

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

2) Η γλώσσα Calvin

Η προδιαγραφές της γλώσσας, σύμφωνα με τον αρχικό σχεδιασμό βρισκονται στο Calvin Specification . Η Calvin είναι μια προστακτικη γλώσσα με σύνταξη παρόμοια με την ansi C. Η γραμματική της παρατίθεται στη συνέχεια. Από αυτό το σημείο και έπειτα, προκειμένου να διατηρηθεί το project σε λογικά επίπεδα δυσκολίας, η γλώσσα απλουστεύθηκε σημαντικά. Έτσι, π.χ. έχουμε μόνο εσωτερικούς τύπους int και char, ενώ δεν επιτρέπεται η κατασκευή τύπων από τον προγραματιστή. Δεν υπάρχουν pointers, ενώ οι πίνακες κατά τη δήλωσή τους πρέπει να έχουν καθορισμένο μέγεθος. Επιπλέον της ansi C, επιτρέπει τον εμφωλιασμό συναρτήσεων με κανόνες εμβέλειας παρόμοιους με τη Pascal.

3) Υλοποίηση

H υλοποίηση σε γενικές γραμμές δεν ξέφυγε από την αντίστοιχη προτεινόμενη του βιβλίου. Αναλυτικά, ακολουθούν τα 5 διαφορετικά κομμάτια της υλοποίησης (χρησιμοποιήθηκαν τα εργαλεία της σουίτας djgpp(GNU) σε περιβάλλον Win32) :

Λεκτικός Αναλυτής: υλοποιήθηκε με τη βοήθεια του μετεργαλείου flex. Δέχεται ως είσοδο ένα αρχείο πηγαίου κώδικα Calvin. Λειτουργεί ως προεπεξεργαστής για την εντολή #include "file" και ελέγχει δυναμικά να μη γίνει εισαχθεί το ίδιο αρχείο παραπάνω από μία φορές (αποτελεί προαιρετική υλοποίηση). Η λειτουργία του συνίσταται στην ανάγνωση του αρχείου πηγαίου κώδικα, την ανάγνωριση των λεκτικών μονάδων και την επιστροφή ενός κωδικού αριθμού για κάθε μια από αυτές.

Συντακτικός Αναλυτής: υλοποιήθηκε με τη βοήθεια του μετεργαλείου bison. Δέχεται ως είσοδο την έξοδο του λεκτικού αναλυτή. Αναλαμβάνει να κωδικοποιήσει σε συντακτικό δένδρο το πρόγραμμα. Σε περίπτωση λάθους, καλείται η προκαθορισμένη συνάρτηση λάθους του bison, η yyparse.

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

function(data_type & variable_name).

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

Ενδιάμεσος Κώδικας: Ο ενδιάμεσος κώδικας υλοποιήθηκε στη μορφή τετράδων. Διαφορετική προσέγγιση ακολουθήθηκε στην υλοποίηση των τετράδων πίνακα. Βασικό στοιχείο για την κατασκευή των διαδοχικών τετράδων, αποτελεί μια γραμμική λίστα αποτελούμενη από κόμβους τύπου Quad_list. Στο αρχείο quad2asm.c υπάρχουν οι συναρτήσεις χειρισμού τετράδων, όπως η

int genquad(int , Quad_Type , b , c , d ,bool);

που αναλαμβάνει την δημιουργία των τετράδων, η

void printquad(FILE *, Quad_list *);

που τυπώνει μία τετράδα, η

void ScopeQuads2file(FILE *, Quad_list **);

που τυπώνει τις υπόλοιπες τετράδες που έχουν δημιουργηθεί.

Σχετικά με την υλοποίηση του πίνακα, κατασκευάσαμε δύο τύπους τετράδων, τους:

ARR2T, x, y, z : με λειτουργία z:=x[y], και

T2ARR, x, y, z : με λειτουργία z[y]:=x.

Τελικός Κώδικας: Eίναι σε γλώσσα μηχανής, στη μορφή του masm assembler της Microsoft. Δεν έχει κάποια βελτιστοποίηση, ακολουθώντας το σχήμα μιας-μιας τετράδας. Σύμφωνα με τη πρόταση του βιβλίου ακολουθήθηκε το μοντέλο μνήμης tiny σε πρόγραμμα .com.

---

4) Kώδικας

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

Last Update: 10/04/2004 21:09μμ

This page will not be updated