Εθνικό Μετσόβιο Πολυτεχνείο
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών

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

https://courses.softlab.ntua.gr/compilers/

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

Κατ' επιλογήν υποχρεωτικό μάθημα ροής Λ, 8ου εξαμήνου, κωδικός 3.4.40.8

Εξάμηνο:

Εαρινό 2016

Διδάσκοντες:

Κωστής Σαγώνας		()		γρ. 1.1.21		τηλ: 210-772-2487
Γιώργος Γκούμας		()		γρ. 2.1.34Β		τηλ: 210-772-2402

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Εργασία, Παλαιότερα έτη
Διαλέξεις: 25/2 | 26/2 | 3/3 | 4/3 | 10/3 | 11/3 | 17/3 | 18/3 | 24/3 | 31/3 | 1/4 | 8/4 | 14/4 | 15/4 | 21/4 | 12/5 | 13/5 | 19/5 | 20/5 | 26/5 | 27/5 | 3/6

Ανακοινώσεις

13/5/2016	Η ιστοσελίδα περιέχει πλέον κάποια βοηθητικά αρχεία που θα σας είναι χρήσιμα στην υλοποίηση του backend του μεταγλωττιστή σας.
2/4/2016	Η προθεσμία υποβολής για το σημασιολογικό αναλυτή είναι η 9 18 Μαΐου 2016.
19/3/2016	ΠΡΟΣΟΧΗ: Εγγραφείτε στο Moodle και δηλώστε τη σύνθεση της ομάδας σας για την εργασία που θα υλοποιήσετε, το συντομότερο δυνατό.
18/3/2016	Ανακοινώθηκαν οι δύο πρώτες προθεσμίες υποβολής των εργασιών του μαθήματος: 31 Μαρτίου 2016 για το λεκτικό αναλυτή και 22 29 Απριλίου 2016 για το συντακτικό αναλυτή.
25/2/2016	Οι διαλέξεις του μαθήματος αρχίζουν σήμερα. Θα διεξάγονται Πέμπτη, ώρα 10:45-12:30 στην Αίθουσα 005 και Παρασκευή, ώρα 15:15-17:00 στην Αίθουσα 012 του Νέου Κτιρίου Ηλεκτρολόγων. Τα εργαστήρια του μαθήματος θα γίνονται είτε στις παραπάνω Αίθουσες ή στο εργαστήριο Τεχνολογίας Λογισμικού μετά από σχετική ανακοίνωση.

Υλικό

Γενικά

Ενημερωτικό φυλλάδιο ( PDF, 118KB).
- Περιγραφή του μαθήματος και διαδικαστικά θέματα.
- Δείτε επίσης τις διαφάνειες “διαφήμισης” του μαθήματος (PDF, 243KB).
Ώρες γραφείου διδασκόντων: Παρασκευή 11:00–12:30.
Διαθέσιμα εργαλεία για την κατασκευή μεταγλωττιστών.

Εργασία

Εκφώνηση: Η γλώσσα προγραμματισμού Edsger (PDF, 290KB).
- Για να εξοικειωθείτε με τη γλώσσα, προσπαθήστε να γράψετε μικρά και μεγαλύτερα προγράμματα σε Edsger, είτε απευθείας είτε μεταφράζοντας υπάρχοντα προγράμματά σας από άλλες γλώσσες. Αν στερείστε από ιδέες, δείτε τις εκφωνήσεις των ασκήσεων των εισαγωγικών προγραμματιστικών μαθημάτων εδώ και εδώ (για κάποιες από αυτές, υπάρχουν και υποδειγματικές λύσεις).
- Δημοσιεύστε τα προγράμματά σας μέσω του moodle, ώστε να είναι διαθέσιμα και στους υπόλοιπους. Έτσι θα δημιουργηθεί ένα σύνολο προγραμμάτων που αργότερα θα χρησιμεύσουν ως test suite για τους μεταγλωττιστές σας.
Βοηθητικά αρχεία που θα σας είναι χρήσιμα στην υλοποίηση:
- Πηγαίος κώδικας, σε C (ZIP, 14KB ή TGZ, 9KB) και σε OCaml (ZIP, 11KB ή TGZ, 8KB).
  Περιεχόμενα του bonus pack:
  - Πίνακας κατακερματισμού για ονόματα αναγνωριστικών.
  - Απλός χειριστής σφαλμάτων.
  - Πίνακας συμβόλων. Για πληροφορίες σχετικές με τη χρήση του, δείτε το παράδειγμα (symbtest.c ή Symbtest.ml).
- Ίσως βρείτε χρήσιμο το συλλέκτη σκουπιδιών (garbage collector) του Hans Boehm, διαθέσιμο από τη σελίδα του ή από το τοπικό αντίγραφο (TGZ, 1058KB), version 7.4.2. Ίσως χρειαστείτε επίσης τη βιβλιοθήκη libatomic_ops (TGZ, 455KB), version 7.4.2.
- Περιβάλλον συμβολομετάφρασης (ZIP, 181KB) αποτελούμενο από τον Microsoft Macro Assembler 5.10, τον Microsoft Linker 5.10 και τον Microsoft Library Manager 3.17.
- Εναλλακτικό περιβάλλον συμβολομετάφρασης (ZIP, 542KB) αποτελούμενο από τον Microsoft Macro Assembler 6.11d, τον Microsoft Linker 5.31 και τον Microsoft Library Manager 3.20. Αυτή η έκδοση του συμβολομεταφραστή μετασχηματίζει αυτόματα τα relative jumps που είναι εκτός ορίων.
- Πιθανώς χρήσιμα scripts (ZIP, 3KB) για τον έλεγχο του μεταγλωττιστή σας σε Linux με dosbox.
- Βιβλιοθήκη χρόνου εκτέλεσης (LIB, 10 KB) και ο κώδικας των συναρτήσεων σε x86 assembly (ZIP, 30 KB).
Εγχειρίδια χρήσης εργαλείων που θα σας είναι χρήσιμα στην υλοποίηση:
- Για υλοποίηση με C/C++:
  - flex ( PDF, 541KB)
  - bison ( PDF, 860KB)
- Για υλοποίηση με OCaml:
  - ocamllex ( PDF, 185KB)
  - ocamlyacc ( PDF, 449KB)
  - Menhir
  - Parsing with OCamllex and Menhir
- Για υλοποίηση με SML/NJ ή MLton:
  - ML-Lex και MLLex
  - ML-Yacc και MLYacc
- Για υλοποίηση με Java:
  - JLex
  - JFLex ()
  - CUP

Παλαιότερα έτη

Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 2014-15, 2013-14, 2012-13, 2011-12, 2010-11, 2009-10, 2008-09, 2007-08, 2006-07, 2005-06, 2004-05, 2003-04, 2002-03.

Διαλέξεις

Παράδοση 25/2/2016

Διάλεξη: Εισαγωγή
- Θέματα διεξαγωγής του μαθήματος
- Τρόποι υλοποίησης γλωσσών προγραμματισμού
- Ιστορική αναδρομή
- Δομή και φάσεις ενός μεταγλωττιστή
- Διαδικασία μεταγλώττισης και ενδιάμεσες αναπαραστάσεις
- Τρέχουσες τάσεις της υλοποίησης γλωσσών προγραμματισμού
- Διαφάνειες διάλεξης

Παράδοση 26/2/2016

Διάλεξη: Λεκτική ανάλυση
- Εισαγωγή στη λεκτική ανάλυση
- Λεκτικές μονάδες (tokens)
- Θέματα σχεδιασμού λεκτικής ανάλυσης στις γλώσσες προγραμματισμού
- Κανονικές εκφράσεις και κανονικές γλώσσες
- Από κανονικές εκφράσεις σε προδιαγραφές λεκτικών αναλυτών
- Αμφισημίες και χειρισμός λαθών
- Υλοποίηση λεκτικών αναλυτών
- Διαφάνειες διάλεξης

Παράδοση 3/3/2016

Εργαστήριο: Παρουσίαση της γλώσσας Edsger
- Κάποια παραδείγματα απλών προγραμμάτων
- Περιγραφή των χαρακτηριστικών της γλώσσας
- Φυλλάδιο με την περιγραφή της Edsger

Παράδοση 4/3/2016

Εργαστήριο: Κατασκευή λεκτικού αναλυτή με το flex
- Το εργαλείο flex
- Κώδικας από το εργαστήριο:
  - lexer.l
  - Makefile

Παράδοση 10/3/2016

Διάλεξη: Εισαγωγή στη συντακτική ανάλυση
- Περιορισμοί των κανονικών γλωσσών
- Εισαγωγή στη συντακτική ανάλυση
- Γραμματικές χωρίς συμφραζόμενα (context-free grammars)
- Παραγωγές (derivations)
- Αμφισημεία (ambiguity) και χειρισμός της στη γραμματική
- Συντακτικά λάθη και χειρισμός τους
- Διαφάνειες διάλεξης

Παράδοση 11/3/2016

Διάλεξη: Αφηρημένα συντακτικά δένδρα και καθοδικοί συντακτικοί αναλυτές
- Αφηρημένα συντακτικά δένδρα
- Σημασιολογικές ενέργειες (semantic actions)
- Υλοποίηση συντακτικών αναλυτών
- Εισαγωγή στην καθοδική συντακτική ανάλυση (top-down parsing)
- Απαλοιφή αριστερής αναδρομής
- Αριστερή παραγοντοποίηση (left-factoring)
- Γλώσσες LL(1)
- Ο αλγόριθμος συντακτικής ανάλυσης LL(1)
- Σύνολα First και Follow
- Διαφάνειες διάλεξης

Παράδοση 17/3/2016

Διάλεξη: Εισαγωγή στους ανοδικούς συντακτικούς αναλυτές
- Ανασκόπηση LL συντακτικής ανάλυσης
- Κατασκευή πίνακα LL(1)
- Υπολογισμός συνόλων First και Follow
- Εισαγωγή στην ανοδική συντακτική ανάλυση (bottom-up parsing)
- Ολίσθηση (shift) και αναγωγή (reduce)
- Ένα παράδειγμα shift-reduce parsing
- Ο αλγόριθμος συντακτικής ανάλυσης LR
- Διαφάνειες διάλεξης

Παράδοση 18/3/2016

Διάλεξη: LR και LALR συντακτικοί αναλυτές
- Ανασκόπηση ανοδικής συντακτικής ανάλυσης
- Ο αλγόριθμος συντακτικής ανάλυσης LR
- Στοιχεία LR(0) και LR(1)
- Κατασκευή του DFA ενός συντακτικού αναλυτή LR(1)
- Συγκρούσεις ολισθήσεων και αναγωγών (shift/reduce conflicts) και τρόποι επίλυσής τους
- Χρήση συντακτικών αναλυτών
- Συντακτικοί αναλυτές LALR(1)
- Διαφάνειες διάλεξης

Παράδοση 24/3/2016

Εργαστήριο: Κατασκευή συντακτικού αναλυτή με το bison
- Το εργαλείο bison
- Κώδικας από το εργαστήριο:
  - lab_bison.zip

Παράδοση 31/3/2016

Διάλεξη: Σημασιολογική ανάλυση
- Ο ρόλος της σημασιολογικής ανάλυσης στους μεταγλωττιστές
- Εμβέλεια ονομάτων
  - Στατική εμβέλεια ονομάτων
  - Δυναμική εμβέλεια ονομάτων
  - Εμβέλεια και πίνακες συμβόλων
- Τύποι και συστήματα τύπων
  - Ρόλοι των τύπων στις γλώσσες προγραμματισμού
  - Γλώσσες με στατικά και δυναμικά συστήματα τύπων
- Διαφάνειες διάλεξης

Παράδοση 1/4/2016

Διάλεξη: Έλεγχος τύπων
- Στατικός έλεγχος προγραμμάτων
- Συστήματα τύπων και ιδιότητές τους
- Τύποι στις γλώσσες προγραμματισμού
- Αναπαράσταση των τύπων σε ένα μεταγλωττιστή
- Έλεγχος και συμπερασμός των τύπων
- Κανόνες συμπερασμού και ελέγχου τύπων
- Υλοποίηση ελέγχου τύπων με χρήση σημασιολογικών κανόνων του συντακτικού αναλυτή
- Έλεγχος τύπων με χρήση του bison
- Διαφάνειες διάλεξης

Παράδοση 8/4/2016

Διάλεξη: Πίνακες συμβόλων και έλεγχος εμβέλειας
- Έλεγχος εμβέλειας ονομάτων (επανάληψη)
- Πίνακες συμβόλων
  - Τρόποι οργάνωσης
  - Κύριες λειτουργίες
  - Χρήση
- Εμβέλεια σε αντικειμενοστρεφείς γλώσσες προγραμματισμού
- Εμβέλεια στην πράξη
  - Έλεγχος εμβέλειας σε μεταγλωττιστές με ένα και πολλά περάσματα
  - Έλεγχος εμβέλειαiς σε γλώσσες με πολλαπλή κληρονομικότητα
- Διαφάνειες διάλεξης

Παράδοση 14/4/2016

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

Παράδοση 15/4/2016

Διάλεξη: Παραγωγή κώδικα
- Μηχανές στοίβας
- Η γλώσσα της αρχιτεκτονικής MIPS
- Μηχανές στοίβας με συσσωρευτή
- Μετατροπή κώδικα μηχανής στοίβας σε MIPS
- Παραγωγή κώδικα με χρήση αναδρομής (για τη γλώσσα “Mini Bar”)
- Παραγωγή κώδικα για μεταβλητές και παραμέτρους
- Διαφάνειες διάλεξης

Παράδοση 21/4/2016

Εργαστήριο: Κατασκευή σημασιολογικού αναλυτή
- Κατασκευή ενός πολύ απλού σημασιολογικού αναλυτή για αριθμητικές εκρφράσεις με το bison
- Κατασκευή ενός πιο ενδιαφέροντος σημασιολογικού αναλυτή με χρήση OCaml
- Κώδικας από το εργαστήριο:
  - lab_semantic.zip

Παράδοση 12/5/2016

Διάλεξη: Ενδιάμεσος κώδικας και τοπική βελτιστοποίηση
- Ενδιάμεσος κώδικας: λόγοι ύπαρξης, τρόποι παραγωγής και χρήσης
- Ενδιάμεσος κώδικας τριών διευθύνσεων (3-address code)
- Βασικά μπλοκ (basic blocks)
- Γράφοι ελέγχου ροής (control-flow graphs)
- Εισαγωγή στη βελτιστοποίηση κώδικα
- Τοπικές βελτιστοποήσεις
  - Αλγεβρική απλοποίηση
  - Αντικατάσταση σταθερών (constant folding)
  - Βελτιστοποιήσεις ελέγχου ροής
  - Εξάλειψη κοινών υποεκφράσεων (common subexpression elimination)
  - Διάδοση αντιγράφων (copy propagation)
  - Εξάλειψη νεκρού κώδικα (dead code elimination)
- Βελτιστοποιήσεις κλειδαρότρυπας (peephole optimizations)
- Διαφάνειες διάλεξης

Παράδοση 13/5/2016

Διάλεξη: Καθολική βελτιστοποίηση
- Καθολική ανάλυση ροής δεδομένων (global dataflow analysis)
- Καθολική διάδοση σταθερών (global constant propagation)
- Ανάλυση ζωντάνιας (liveness analysis) μεταβλητών
- Διαφάνειες διάλεξης

Παράδοση 19/5/2016

Διάλεξη: Παραγωγή καλύτερου κώδικα και πέρασμα παραμέτρων
- Βελτιστοποιήσεις για μικρότερες εγγραφές δραστηριοποίησης
- Μια πιο βαθειά ματιά στις ακολουθίες κλήσεων συναρτήσεων
- Τρόποι περάσματος παραμέτρων
- Παραγωγή κώδικα για αντικειμενοστρεφείς γλώσσες
- Διαφάνειες διάλεξης

Παράδοση 20/5/2016

Εργαστήριο: Παραγωγή ενδιάμεσου και τελικού κώδικα
- Παραγωγή ενδιάμεσου κώδικα
  - Γλώσσα τετράδων: τελούμενα και τελεστές
  - Βοηθητικές υπορουτίνες
  - Παραγωγή ενδιάμεσου κώδικα για αριθμητικές και λογικές εκφράσεις
  - Παραγωγή ενδιάμεσου κώδικα για απλές και σύνθετες εντολές
  - Παραγωγή ενδιάμεσου κώδικα για κλήση υποπρογραμμάτων
  - Ένα εκτενές παράδειγμα
- Παραγωγή τελικού κώδικα x86
  - Χαρακτηριστικά του τελικού υπολογιστή
  - Εντολές του τελικού υπολογιστή
  - Διαχείριση μνήμης
  - Προσπέλαση ονομάτων
- Διαφάνειες εργαστηρίου

Παράδοση 26/5/2016

Διάλεξη: Καθολική παραχώρηση καταχωρητών
- Διαχείριση ιεραρχίας μνήμης
- Παραχώρηση καταχωρητών μέσω χρωματισμού γράφου (graph coloring)
  - Ο γράφος παρεμβολής των καταχωρητών (register interference graph)
  - Ευρεστικές τεχνικές
  - Χύσιμο (spilling)
  - Πρoχρωματισμένοι κόμβοι (precolored nodes)
- Διαχείριση κρυφής μνήμης (cache management)
- Διαφάνειες διάλεξης

Παράδοση 27/5/2016

Εργαστήριο: Παραγωγή τελικού κώδικα
- Παραγωγή τελικού κώδικα με χρήση τετράδων (quads)
- Ένα παράδειγμα σε μια πολύ απλή προστακτική γλώσσα
- Διαφάνειες εργαστηρίου
- Κώδικας από το εργαστήριο:
  - lab_quads.zip
  - lab_quads-ml.zip (σε OCaml)

Παράδοση 3/6/2016

Διάλεξη: Ανακεφαλαίωση της ύλης
- Επίλυση αποριών
- Παλαιότερα θέματα εξετάσεων

Τελευταία αλλαγή: 01/03/2016, 16:42 UTC.