-
Notifications
You must be signed in to change notification settings - Fork 1
manolis-andr/compiler
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
Tony Compiler =========================== The code on this project is not meant to be used for professional use. This code was built under the isntructions of professor Nikos Papaspyrou. Χαρακτηριστικά ************************* Δημιουργία: Ανδρουλιδάκης Εμμανουήλ (03110036), Εαρινό εξάμηνο 2015 Γλώσσα: tony Γλώσσα υλοποίησης: C σε συνδυασμό με τα εργαλεία flex και bison Περιβάλλον ανάπτυξης: Ubuntu 14.04, gcc compiler Ενδιάμεσος κώδικας: κώδικας τετράδων Τελικός κώδικας: κώδικας για Intel 8086, συμβατός με τον συμβολομεταφραστή MASM Χρήση έτοιμης compiled βιβλιοθήκης tonylib και υλοποίησης garbage collector, tonygc Περιβάλλον για συμβολομετάφραση τελικού κώδικα: Microsoft Macro Assembler 5.10, τον Microsoft Linker 5.10 και τον Microsoft Library Manager 3.17 Περιβάλλον για εκτέλεση: MS-DOS μέσω του dosbox Αρχεία ************************* lexer.l: λεκτικός αναλυτής parser.y: συντακτικός αναλυτής intermediate.{c,h}: παραγωγή και βελτιστοποίηση ενδιάμεσου κώδικα final.{c,h}: παραγωγή τελικού κώδικα symbol.{c,h}: ορισμοί και συναρτήσεις πίνακα συμβόλων datastructs.{c,h}: ορισμοί και συναρτήσεις διαχείρισης μιας generic στοίβας και μιας generic ουράς που χρησιμοποιούνται σε άλλα σημεία του compiler error.{c,h}: ορισμοί και συναρτήσεις σφαλμάτων general.{c,h}: ορισμοί και συναρτήσεις για διαχείριση μνήμης, ορισμοί global μεταβλητών (προσπελάσιμες από κάθε αρχείο) και σταθερών Makefile: αρχείο για την αυτόματη μεταγλώττιση του μεταγλωττιστή μας Make options ************************* Μεταγλώττιση του μεταγλωτιστή $ make Για καθάρισμα των επιπλέον αρχείων: $ make clean Υπάρχει η δυνατότητα ο compiler να μεταγλωτιστεί για να παράγει διαγνωστικά μηνύματα με την επιλογή: $ make DEBUG=1 Επιπλέον υπάρχει η πρόσθετη δυνατότητα o compiler να μεταγλωτιστεί για να παράγει μόνο ενδιάμεσο κώδικας με την επιλογή: $ make INTERMEDIATE=1 Τέλος ο χρήστης μπορεί να ορίσει δικές του σημαίες για μεταγλώττιση (π.χ. -Wall) τοποθετώντας τες μετά το αναγνωριστικό FLAGS=. π.χ. $ make FLAGS=-Wall Παράγεται το εκτελέσιμο compiler, το οποίο για να μεταγλωτίσουμε ένα tony πρόγραμμα το τρέχουμε ως εξής: ./compiler <program.tony> Ο μεταγλωτιστής μας παράγει τα αρχεία program.imm (ενδιάμεσος κώδικας) και program.asm (τελικός κώδικας assembly για 8086) Με την επιλογή -i το πηγαίο tony πρόγραμμα θα αναγνωστεί από το standard input και θα έχει έξοδο ενδιάμεσου κώδικα στο standard output (και τελικού στο stdin.asm). Με την επιλογή -f το πηγαίο tony πρόγραμμα θα αναγνωστεί από το standard input και θα έχει έξοδο τελικού κώδικα στο standard output (και ενδιάμεσου στο stdin.imm). Προφανώς για να σηματοδοτήσουμε το τέλος του αρχείου πρέπει να δώσουμε Ctrl + D (EOF), αν και ο ενδιάμεσος ή ο τελικός κώδικας θα τυπωθεί στο stdout με το που αναγνωριστεί το end του κυρίως δομικού μπλοκ. Περίληψη O parser είναι αυτός που κινεί τα νήματα στον μεταγλωττιστή μας. Αρχικά παρσάρει τα command line arguments και καθορίζει τα streams εισόδου και εξόδου, αλλά και την ενεργοποίηση ή όχι του κομματιού βελτιστοποίησης ενδιάμεσου κώδικα. Στη συνέχεια αφού αρχικοποιεί κάποιες χρήσιμες μεταβλητές του ίδιου αλλά και υπολοίπων κομματιών του compiler (symbol table, quad array κτλ), δηλώνει σε ένα εξωτερικό scope όλες τις συναρτήσεις βιβλιοθήκης. Έπειτα, αρχίζει το parsing της εισόδου ζητώντας tokens από τον λεκτικό αναλυτή μαζί ίσως με κάποια σημασιολογική πληροφορία. Η συντακτική ανάλυση γίνεται με βάση τα tokens που λαμβάνει και τους κανόνες της γραμματικής που έχουμε γράψει. Κάθε φορά που αναγνωρίζεται ένα σύμβολο (τερματικό ή μη) της γραμματικής εκτελούνται και κάποιες σημασιολογικές ρουτίνες οι οποίες αφενός πραγματοποιούν σημασιολογικούς ελέγχους (typecheking, μοναδικότητα ονομάτων κτλ) και αφετέρου κατασκευάζουν σιγά σιγά τις τετράδες του ενδιάμεσου κώδικα. Η κατασκευή των τετράδων γίνεται στην μνήμη και δεν τυπώνονται κατεθυείαν. Εάν η συντακτική ανάλυση ολοκληρωθεί με επιτυχία, ο συντακτικός αναλυτής δίνει σήμα στο κομμάτι του ενδιάμεσου κώδικα να εκτελέσει τις βελτιστοποιήσεις ενδιάμεσου κώδικα και έπειτα να τυπώσει στην κατάλληλη έξοδο τις τετράδες (όσες απέμειναν) Τέλος, εκκινεί την διαδικασία παραγωγής τελικού κώδικα, στην οποία εκτυπώνεται ο αρχικός εισαγωγικός σκελετός του assembly προγράμματος (), κάθε τετράδα μετατρέπεται στο κατάλληλο σύνολο assembly εντολών και τέλος εκτυπώνεται ο επιλογικός σκελετός (). Παραδοχές: ************************* - Οι σταθερές συμβολοσειρές (strings), θεωρούμε ότι μπορούν να μεταβληθούν απαξ και ανατεθούν σε μια μεταβλητή τύπου char[] (char[] a ; a:=”string”; a[0]:='p'). Αυτό γιατί αφενός δεν αναγράφεται τελείως ξεκάθαρα στο πρότυπο ροδιαγραφών της γλώσσας αν κάτι τέτοιο επιτρέπεται και αφεταίρου μειώνει εν πολλοίς την πολυπλοκότητα της υλοποίησης. - Εάν γίνει κάποιο forward declaration συνάρτησης (decl) και το πρόγραμμα ολοκληρωθεί χωρίς να παρουσιαστεί κάπου ο ορισμός της, δεν βγάζουμε κάποιο προειδοποιητικό μήμυμα, ακόμα και στην περίπτωση που αυτή καλείται από το πρόγραμμα (και άρα το πρόγραμμα θα σκάσει στο run time). - Οι μεταβλητές και οι παράμετροι οποιουδήποτε τύπου, εάν δεν αρχικοποιηθούν έχουν απροσδιόριστη τιμή (θεωρούμε λογικό λάθος να ελεγχθεί μια λίστα με την nil? εάν δεν έχει πάρει πρώτα κάποιες τιμές, καθώς δεν εγγυώμαστε ότι θα είναι nil) - Οι συναρτήσεις cosnv, consp, newarrp, newarrv, head και tail ορίζονται μεν μαζί με τις υπόλοιπες συναρτήσεις βιβλιοθήκης αλλά δεν θεωρούνται callable από τον χρήστη. Μπορούν να τοποθετηθούν στον εκτελέσιμο κώδικα μόνο αν εσωτερικά τις τοποθετήσει ο compiler. - Δεν πραγματοποιούμε ελέγχους για την τιμή δεικτοδότησης σε ένα πίνακα (ελέγχουμε μόνο ότι είναι ακέραιος αλλά όχι μη αρνητικός και μικρότερος από το μέγεθος του πίνακα). Παρομοίως αγνοούμε τον ίδιο έλεγχο στον τελεστή new που δεσμεύει μνήμη για πίνακες. Αυτό θα μπορούσε να γίνει μόνο με δυναμικό έλεγχο (αφού το έντυπο προδιαγραφών ορίζει ότι μπορούν εκφράσεις και όχι σκέτοι ακέραιοι να χρησιμοποιηθούν για την δεικτοδότηση). Κατά τον δυναμικό έλεγχο θα πρέπει o compiler να προσθέσει ρητά κώδικα στο εκτελέσιμο, ο οποίος κώδικας κατά το run-time θα μπορούσε να ελέγξει την τιμή του δείκτη του πίνακα και να τερματίσει το πρόγραμμα εάν γίνει μια παράνομη προσπέλαση. - Δεν κάνουμε κάποιον έλεγχο ώστε οι μεταβλητές να αρχικοποιούνται πριν την πρώτη χρήση τους, ούτε εκτυπώνουμε κάποιο προειδοποιητικό μήνυμα - Θεωρούμε ότι δεν μπορεί να υπάρξει ούτε function overloading ούτε να υπάρχουν διαφορετικά namespaces στο ίδιο scope, οπότε και δεν επιτρέπεται ίδιο όνομα για μια μεταβλητή και για μια συνάρτηση ή για μια παράμετρο ή για μια συνάρτηση και μια παράμετρο. Παρακάτω παρέχουμε κάποιες περιγραφικές πληροφορίες για τον τρόπο σχεδιασμού και υλοποίησης των διαφόρων κομματιών του compiler, για να διευκολυνθεί η ανάγνωση του κώδικα και να εξηγηθούν πιθανώς κρυπτικά κομμάτια του. Λεκτικός αναλυτής lexer.l ************************* Δεν θα αναλύσουμε εκτενώς το αρχείο του λεκτικού αναλυτή παρά μόνο κάποια ίσως ασυνήθιστα τμήματά του. Στα tokens με ένα ascii δεν χρησιμοποιούμε κάποιο κωδικό όνομα για το token αλλά επιστρέφουμε τον ascii κωδικό. Έχουμε μια αποκλειστική κατάσταση COMMENT για τα σχόλια και μια μεταβλητή nesting ώστε να ανιχνεύουμε και εμφωλευμένα σχόλια (φεύγουμε από την κατάσταση μόνο όταν κλείνει σχόλιο και το nesting είναι 1). Οι συναρτήσεις fixChar και οι βοηθητικές της fixHex και charToInt, χρησιμοποιούνται ώστε εάν ο έχουμε χαρακτήρα διαφυγής, να επιστραφεί η ascii τιμή του. Για παρόμοιο λόγο, χρησιμοποιείται και στο κομμάτι παραγωγής τελικού κώδικα (final). Η μεταβλητή lastWhitespace χρησιμοποιείται για να βλετιωθεί το error reporting καθώς στην περίπτωση που παρουσιαστεί κάποιο συντακτικό/σημασιολογικό σφάλμα αλλά η λεκτική ανάλυση έχει στη συνέχεια “φάει” ένα χαρακτήρα αλλαγής γραμμής (μιας που αυτός ο χαρακτήρας έτυχε να διαχωρίζει το token), τότε το μήνυμα λάθους θα αναφέρεται σε λάθος γραμμή (θα έχει αυξηθεί και η μεταβλητή linecount). Με το lastWhitespace όμως είναι δυνατό αυτό να ανιχνευθεί και έτσι να “μπαλώσουμε” κατά κάποιο τρόπο αυτήν την ασυνέπεια, τυπώνοντας στην συνάρτηση λάθους, το linecount-1. Συντακτικός αναλυτής parser.y ************************* Η γραμματική που ακολουθεί ο parser είναι αυτή που ορίζεται στο έντυπο προδιαγραφών τις γλώσσας με κάποιες προσθήκες συμβόλων και αλλαγές για λειτουργικότητα. Το struct Memory δεν είναι τίποτα άλλο παρά η ομαδοποίηση κάποιων global μεταβλητών, που χρησιμοποιεί ο parser για να θυμάται ορισμένες προηγούμενες (σημασιολογικές συνήθως) πληροφορίες που προκύπτουν από ενδιάμεσα ή τερματικά σύμβολα καθώς γίνεται το parsing και οι οποίες είναι χρήσιμες αργότερα αλλά δεν μπορούν να προσπελαστούν είτε γιατί έχουμε αλλάξει κανόνα, έίτε γιατί έχουμε αλλάξει σημασιολογική ρουτίνα (και άρα δεν είμαστε στην εμβάλεια της σημασιολογικής πληροφορίας του συμβόλου). Χρησιμοποιείται μόνο για πληροφορίες που δεν μπορούν να εμφωλευτούν, και άρα να υπάρχει κίνδυνος ένα νέο εμφωλευμένο σύμβολο να επικαλύψει την πληροφορία του προηγούμενου με την δικιά του. Για αποθήκευση χρήσιμων σημασιολογικών πληοροφοριών, που μπορεί να είναι εμφωλευμένες (γιατί τα σύμβολα που μας απασχολούν μπορεί να είναι μεφωλευμένα), χρησιμοποιούμε στοίβες. Οι στοίβες αυτές είναι generic (τα δεδομένα έχουν void *) και για κάθε πληροφορία χρησιμοποιούμε ένα specific κόμβο. Τέτοιοι κόμβοι είναι ifNode, forNode, parNode, callNode, funcNode, μια που τα if, for, function parameters, function calls. function definitions, μπορούν να είναι εμφωλευμένα. Δηλώνουμε τις συναρτήσεις βιβλιοθήκης με την declareAllLibFunc, στην αρχή του parsing, στο εξωτερικότερο scope του προγράμματός μας (άρα μπορούν να χρησιμοποιηθούν από κάθε άλλη δομική μονάδα). Οι ορισμοί των συναρτήσεων (όνομα, τύποι, ορίσματα, αν είναι gcHungry) δηλώνονται σε έναν πίνακα μέσα σε αυτήν την συνάρτηση. Συνεπώς αν στη συνέχεια θέλουμε να επεκτείνουμε την βιβλιοθήκη, πρέπει να δηλωθούν με βάση ατυό το μοτίβο στο συγκεκριμένο σημείο του parser.y. Για μεγαλύτερη ευελξιά, θα μπορούσαμε στο μέλλον να επεκτείνουμε τον compiler, με την δυνατότητα να διαβάζει τους ορισμούς των συναρτήσεων βιβλιοθήκης από ένα ξεχωριστό αρχείο. Τα structs LibFunc και LibFuncParam ορίζουν τις απαραίτητες πληροφορίες που πρέπει να δοθούν για τον ορισμό κάθε συνάρτησης βιβλιοθήκης. Επίσης γίνεται και ένας διαχωρισμός ανάμεσα στις συναρτήσεις βιβλιοθήκης που δίνονται στο έντυπο προδιαγραφών της γλώσσας και στις εσωτερικές και απαραίτητες για κάποιες λειτουργίες (π.χ. consv), οι οποίες όμως δεν μπορούν να κληθούν από τον χρήστη. Κάθε συνάρτηση έχει ένα serial_num (πεδίο στο symbol.h) και φροντίζουμε να διαχωρίζουμε τις callable library functions, τις uncallable library functions και τις normal program functions με βάση αυτό το serial num. Οι σταθερές LF_*, ουσιαστικά αφορούν τον parser, όπου δηλώνονται οι library functions, αλλά τις τοποθετούμε στο general.h γιατί πρέπει το LF_NUM να είναι προσπελάσιμο και από το final.h Έχουμε χρησιμοποιήσει ένα signal handler που θα χειρίζεται το σήμα SIGSEGV (Segmentation Fault), έτσι ώστε να επιχειρείται να τυπώνονται οι τετράδες και ο τελικός κώδικας μέχρι το σημείο που έχουμε φτάσει, για λόγους debugging (πολύ πιθανό να ξανασκάσει βέβαια η εκτύπωση αλλά δεν έχουμε κάτι να χάσουμε) Σημασιολογικός αναλυτής parser.y ************************* Ουσιαστικά υλοποιείται διαμέσου των σημασιολογικών ρουτινών του συντακτικού αναλυτή και δεν είναι τίποτα περισσότερο παρά έλεγχοι τύπων, έλεγχοι ορισμών, έλεγχοι μοναδικότητας και γενικότερα έλεγχοι έτσι ώστε οι σημασιολογικές πληροφορίες των τερματικών ή μη τερματικών συμβόλων της γραμματικής να ευθυγραμμίζονται με συγκεκριμένες σημασιολογικές απαιτήσεις της γλώσσας (που υπερβαίνουν το απλό συντακτικό δέντρο). Προφανώς για την υλοποίηση του κομματιού αυτού, ζωτική είναι η δημιουργία και αποθήκευση σημασιολογικών πληροφοριών, όπως και προαναφέραμε στον parser. Δεν θα αναλύσουμε εδώ όλους τους ελέγχους που γίνονται, αλλά σημειώνουμε ότι στους περισσότερους τέτοιους ελέγχους, σε περίπτωση σφάλματος καλούνται οι συναρτήσεις sserror και ssmerror, οπότε το είδος των ελέγχων μπορεί χονδρικά να εντοπιστεί μέσω αυτών. Η διαφορά των δυο συναρτήσεων εναπόκειται στο ότι η πρώτη καλείται όταν το σφάλμα εντοπίζεται όταν ολοκληρωθεί η αναγνώριση όλων των συμβόλων στα δεξιά του κανόνα (δηλαδή δεν ακολουθεί σύμβολο μετά την σημασιολογική ρουτίνα που ελέγχει για σφάλμα) ενώ η δεύτερη καλείται σε μια σημασιολογική ρουτίνα στην που παρεμβάλλεται των δεξιών συμβόλων του κανόνα (-ssmerror από το middle-) Παραγωγή ενδιάμεσου κώδικα intermediate.{c,h} ************************* Για την αποθήκευση των τετράδων χρησιμοποιούμε έναν global πίνακα q (μοιραζόμενο και με το κομμάτι του τελικού κώδικα). Οι τετράδες λοιπόν παράγονται στην μνήμη και διατηρούνται εκεί μέχρι και το τέλος της μεαγλώττισης. Εάν εξαντληθεί ο χώρος των τετράδων που έχει δεσμευτεί, με realloc δεσμεύουμε εκ νέου τον διπλάσιο. Κάθε τετράδα αποτελείται λοιπόν από έναν Operator, 3 Operands και έναν αριθμό τετράδας. Για να κατασκευάσουμε τον ενδιάμεσο κώδικα, στις σημασιολογικές ρουτίνες χρησιμοποιούμε την συνάρτηση genquad, η οποία παράγει μια τετράδα. Η συνάρτηση αυτή παίρνει ως πρώτο όρισμα έναν operator (enum OperatorType) και τα επόμενα τρια είναι Operands. Ο τύπος των operands απλώς αποτελεί έναν τρόπο ώστε όλες οι διαφορετικές περιπτώσεις ορισμάτων της genquad να περνάνε ομοιόμορφα με τον ίδιο τύπο στην ίδια συνάρτηση. Έτσι για κάθε διαφορετικό τύπο Operand (απαριθμούνται στο enum OperandType) έχουμε και μια wrapper συνάρτηση που τον κατασκευάζει πριν περαστεί ως όρισμα στην genquad (τέτοιες wrapper είναι οι oS - symbol, oU -unit, oD -dereference κτλ). Κάποιοι τύποι είναι δυναμικοί (περιεχόμενα εξαρτώνται από πληροφορίες στο parsing) ενώ κάποιοι άλλοι είναι στατικοί (όπως το oSTAR - * για backpatching ή το oRESULT για το $$). Για κάθε Operand αποθηκεύεται ο τύπος του, το όνομα που θα τυπωθεί στην ενδιάμεση τετράδα και το SymbolEntry ή ο αριθμός μιας τετράδας (αν πρόκειται για Operand τύπου label). Για να υλοποιηθεί το backpatching για άλματα σε τετράδες που δεν έχουν ακόμα κατασκευαστεί, χρησιμοποιούμε μια ειδική λίστα (List) και την παραλλαγή της ListPair, όπου o parser μπορεί να αποθηκεύει αριθμούς τετράδων που πρέπει να γίνουν αργότερα backpatched. Προφανώς κατασκευάσαμε και ανάλογες συναρτήσεις για την βολική διαχείριση των λιστών. Οι συναρτήσεις createCondition και evaluateCondition χρησιμοποιούνται για να ομαδοποιήσουν τις λειτουργίες κατασκευής και αποτίμησης αντίστοιχα μια συνθήκης και να προσφέρουν από τη μία σχεδιαστική αφαίρεση και κομψότητα και από την άλλη ευελιξία ανάμεσα στις περιπτώσεις όπου μια λογική συνθήκη πρέπει να αποτιμηθεί σαν λογική έκφραση ή να χρησιμοποιηθεί για την ροή ελέγχου του προγράμματος. Η τοποθέτηση των τετράδων στον πίνακα q αρχίζει από το q[1] (παρακάμπτει το πρώτο στοιχείο q[0]). Αυτό γίνεται για απλότητα, ώστε να συμβαδίζει ο αριθμός της τατράδας με την θέση της στον πίνακα. Βελτιστοποίηση ενδιάμεσου κώδικα intermediate.c ************************* Η βελτιστοποίηση ενδιάμεσου κώδικα πραγματοποιείται μετά την κατασκευή όλων των τετράδων και αφού μετασχηματίσει ή διαγράψει τετράδες, αυτές τυπώνονται. (Η διαγραφή τον τετράδων συνίσταται στο να αλλάξουμε τον αριθμό της q[i].num σε -1 ώστε να σημειωθεί για να μην τυπωθεί στη συνέχεια, και όχι προφανώς στην διαγραφή του στοιχείου του πίνακα). Η βελτιστοποίηση απαρτίζεται από αυτές τις 4 τεχνικές: 1. inverse copy propagation : Οι τετράδες πρόσθεσης, αφαίρεσης, πολλαπλασιασμού, διαίρεσης ή υπολοίπου τοποθετούν το αποτέλεσμα της πράξης σε μια προσωρινή μεταβλητή. Αυτές ακολουθούνται μετά από μια τετράδα ανάθεσης, στην οποία η προσωρινή μεταβλητή ανατίθεται στην κανονική μεταβλητή αποτελέσματος. Με την τεχνική αυτή απαλείφεται η 2η τετράδα και στην πρώτη τετράδα το αποτέλεσμα τοποθετείται κατευθείαν στην μεταβλητή αποτελέσματος. 2. constant folding Αν έχουμε τετράδες πρόσθεσης, αφαίρεσης, πολλαπλασιασμού, διαίρεσης ή υπολοίπου, των οποίων και τα δύο τελούμενα είναι σταθερές, αποτιμούμε το αποτέλεσμα της πράξης μεταξύ των δυο σταθερών και αντικαθιστούμε την τετράδα πράξης με μια τετράδα ανάθεσης στην μεταβλητή αποτελέσματος 3. algebraic transformations Μετασχηματισμοί που απλοποιούν πράξεις με τα ουδέτερα στοιχεία του πολλαπλασιασμού και τις πρόσθεσης 0 και 1, αντικαθιστώντας την τετράδα πράξης με μια τετράδα ανάθεσης. 4. remove jumps to next instr Υπάρχουν κάποιες φορές που έχουμε εντολές jump που αναφέρονται στην αμέσως επόμενη τετράδα. Δεν υπάρχει κανένας λόγος για αυτό, αφού η ροή του προγράμματος θα ήταν ούτως ή άλλως αυτή, οπότε τις αφαιρούμε. Να σημειώσουμε ότι πρώτα εκτελείται το inverse copy propagation και στη συνέχεια το constant folding ούτως ώστε να εκμεταλλευτούμε τα οφέλη της πρώτης τεχνικής στην δεύτερη (ειδάλλως επειδή δεν είναι πάρα πολύ έξυπνος ο τρόπος αναγνώρισης δεν θα τα εκμεταλλευόμασταν). Παραγωγή τελικού κώδικα final.{c,h} ************************* Θα παράξουμε τελικό κώδικα assembly για Intel 8086, MS-DOS μοντέλο tiny COM και συμβολική γλώσσα συμβατή με τον MASM. Χρησιμοποιούμε 1 segment και όλοι οι καταχωρητές τμημάτων δείχνουν στο ίδιο segment. Επίσης για αριθμητική modulo 2^16 θα πάρουμε μόνο τον ax και τον dx θα τον αγνοήσουμε. Στον πίνακα extrn, τοποθετούμε τα ονόματα των συναρτήσεων βιβλιοθήκης που καλούνται στο πρόγραμμά μας και πρέπει να δηλωθούν με μια extrn assembly εντολή στον επίλογο. Παρομοίως χρησιμοποιούμε μια ουρά strings, για να αποθηκεύσουμε τα strings που υπάρχουν ως σταθερές στο πρόγραμμά μας και τα οποία επιλέγουμε να δηλώσουμε στον επίλογο. Η μετατροπή των τετράδων σε εντολές assembly γίνεται μέσω της printFinal(), η οποία καλεί κυρίως τις συναρτήσεις code* και load, loadAddr, store. Η code, τυπώνει μια κανονική assembly εντολή, η codel εκτυπώνει μια έντολή προθεματίζοντάς την με ένα label και η codeq τυπώνει σε σχόλια assembly την τετράδα από την οποία θα προκύψουν οι εντολές assembly. Οι load, loadAddr και store χρησιμοποιούνται για να δημιουργήσουν τις κατάλληλες εντολές ανάλογα με το τελούμενο της τετράδας (σταθερά, τοπική/μη τοπική μεταβλητή/παράμετρος/... ). Οι getAR φορτώνει την διεύθυνση ενός δελτίου ενεργοποίησης που ορίζεται από το SymbolEntry και η updateAL ενημερώνει τους συνδέσμους προσπέλασης. Οι skeletonBegin και skeletonEnd τυπώνουν τον πρόλογο και τον επίλογο του προγράμματος. Οι συναρτήσεις name, label, endof δημιουργούν ετικέτες του τελικού κώδικα ανάλογα με το είδος της ετικέτας που θέλουμε. Δυστυχώς το κομμάτι παραγωγής τελικού κώδικα δεν είναι ανεξάρτητο από το κομμάτι παραγωγής ενδιάμεσου κώδικα, αφού για να λειτουργήσει το πρώτο πρέπει να να υπάρχει στη μνήμη ένας πίνακας τετράδων, στη μορφή num, Operators και Operands που περιγράφτηκε προηγουμένως. Εναλλακτικά θα έπρεπε να παρσάρουμε ξανά την είσοδο του .imm αρχείου. Tony Garabage Collector ************************* Δημιουργούμε call table μόνο για τις συναρτήσεις που καλούν άμεσα ή έμμεσα τον συλλέκτη σκουπιδιών. Για να καλέσει μια συνάρτηση άμεσα τον garbage collector πρέπει να χρησιμοποιεί έναν από τους τελεστές head, tail, new, # οι οποίοι υλοποιούνται με τις assembly ρουτίνες consv, consp, newarrp, newarrv, head, tail που σηματοδοτούν την χήρση του garbage collector. Για να καλέσει μια συνάρτηση έμμεσα τον garbage collector πρέπει να καλεί μια συνάρτηση που μπορεί να καταλήξει σε κλήση κάποιας άλλης συνάρτησης που καλεί τον garbage collector. Kάθε τέτοια συνάρτηση την εντοπίζουμε κατά το parsing υψόνοντας την σημαία gcHungry στο currentScope (δικιά μας προσθήκη). Μόλις ολοκληρωθεί ο ορισμός της συνάρτησης (αναγνωριστεί το τερματικό σύμβολο για δήλωση συνάρτησης), αποθηκεύουμε το SymbolEntry της σε μια ουρά (gcHungryFunc) έτσι ώστε αργότερα (final code generation) να την δηλώσουμε στον πρόλογο του τελικού assembly (πρέπει να δηλώσουμε στον πρόλογο τις συναρτήσεις των οποίων τα Ε.Δ. μπορεί να βρίσκονται στη στοίβα όταν ενεργοποιηθεί ο συλλέκτης). Επίσης τοποθετούμε σε μια άλλη ουρά (gcHungryVar) τα SymbolEntries που μπορούν να προσπελαστούν από αυτήν την συνάρτηση, πληροφορία χρήσιμη για την κατασκευή του call table αργότερα (final code generation). Για τις συναρτήσεις που καλούνται χωρίς πρώτα να έχει δοθεί ο ορισμός τους (άρα έχουν δηλωθεί με forward declaration), εν τη απουσία data flow analysis, αναγκαστικά απαισιόδοξα υποθέτουμε ότι θα καλέσουν τον συλλέκτη σκουπιδιών. Στον τελικό κώδικα, στον πρόλογο και στον επίλογο προσθέτουμε τον κατάλληλο κώδικα όπως προτάσσεται στο αρχείο README του tonygc (πακέτο με τον tony garbage collector). Επίσης για κάθε κλήση συνάρτησης που έχει σημειωθεί ως gcHungry, τοποθετούμε μια ετικέτα που αντιστοιχεί στη διεύθυνση επιστροφής της (χρησιμοποιούμε και ένα counter gcCallNumγια να υποστηρίξουμε πολλές κλήσεις gcHungry συναρτήσεων στην ίδια δομική μονάδα). Ταυτόχρονα, τοποθετούμε σε μια άλλη ουρά (gcCallParam) τον αριθμό των παραμέτρων που δέχεται αυτή η συνάρτηση, πληροφορία χρήσιμη για την κατασκευή του call table του δομικού μπλοκ που περιέχει την κλήση της gcHungry συνατησης. Η κατασκευή αυτού του call table γίνεται όταν βρεθεί η τετράδα ENDU με την συνάρτηση createCallTable, σύμφωνα με τις προτροπές του αρχείου README του tonygc. Πίνακας Συμβόλων symbol.{c,h} ************************* Να σημειώσουμε επίσης ότι έχουμε μεταβάλλει λίγο τον κώδικα του symbol.c (Πίνακας συμβόλων), προσαρμόζοντάς τον στη συγκεκριμένη γλώσσα. Μια σημαντική αλλαγή είναι ότι αν και όταν κλείνει ένα scope κάνουμε τα SymbolEntrys απροσπέλαστα από την lookupEntry, δεν τα διαγράφουμε από την μνήμη, αφού χρειαζόμαστε την αναφορά σε αυτά για μεταγενέστερα της συντακτικής ανάλυσης στάδια του compiler (κρατάμε άλλωστε pointers σε αυτά στους Operands). Προσθέσαμε τον τύπο TYPE_LIST και αφαιρέσαμε τον τύπο TYPE_ARRAY αφού δεν έχουμε σταθερούς πίνακες (μόνο τα strings που όμως τα μεταχειριζόμαστε σαν σταθερές τύπου TYPE_IARRAY). Δεν έχουμε και πραγματικούς αριθμούς οπότε αφαιρέσαμε και τον TPYE_REAL. Επίσης αν και δεν έχουμε ρητά pointers στην tony, κρατήσαμε τον τύπο TYPE_POINTER σαν ένα ενοποιητικό τύπο TYPE_IARRAY και TYPE_LIST, για να διευκολύνουμε τον ορισμό συναρτήσεων που μπορούν να περάσουν είτε τύπο λίστας είτε τύπο πίνακα (π.χ consv).
About
Tony compiler for NTUA-compilers course
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published