Μεταγλωττιστές
Κατ' επιλογήν υποχρεωτικό μάθημα ροής Λ, 8ου εξαμήνου, κωδικός 3.4.3186.8
Εξάμηνο: Εαρινό 2022
Διδάσκων:
Κωστής Σαγώνας
(kostis (AT) cs (DOT) ntua.gr )
γρ. 1.1.21
τηλ: 210-772-2487
Ανακοινώσεις
| Υλικό:
Γενικά ,
Helios ,
Videos (2021) ,
Εργασία ,
Παλαιότερα έτη Διαλέξεις:
3/3 |
4/3 |
10/3 |
11/3 |
17/3 |
18/3 |
24/3 |
31/3 |
1/4 |
7/4 |
8/4 |
14/4 |
15/4 |
5/5 |
6/5 |
12/5 |
13/5 |
20/5 |
26/5 |
27/5 |
2/6 |
3/6 |
9/6 |
10/6
13/7/2022 Τα αποτελέσματα της εξέτασης του Ιουνίου του μαθήματος ανακοινώθηκαν και είναι διαθέσιμα στην σελίδα του μαθήματος στο helios .
10/6/2022 Η εξέταση του μαθήματος Θα πραγματοποιηθεί την Τετάρτη 22 Ιουνίου 2022, ώρα 12:00-15:00 στην Αίθουσα 013 του Νέου Κτιρίου Ηλεκτρολόγων. Μπορείτε να έχετε μαζί σας μια κόλλα Α4 με χειρόγραφες σημειώσεις (και το ονοματεπώνυμό σας σε εμφανές σημείο) για τα κομμάτια από την ύλη του μαθήματος τα οποία θέλετε να έχετε διαθέσιμα.
3/3/2022 Οι διαλέξεις του μαθήματος αρχίζουν σήμερα. Θα διεξάγονται Πέμπτη, ώρα 12:45-14:30 και Παρασκευή, ώρα 15:15-17:00 στην Αίθουσα 013 του Νέου Κτιρίου Ηλεκτρολόγων. Τα εργαστήρια του μαθήματος θα γίνονται είτε στις παραπάνω Αίθουσες ή στο εργαστήριο Τεχνολογίας Λογισμικού ή/και στο διαδίκτυο μετά από σχετική ανακοίνωση.
Υλικό
Τα βίντεο των διαλέξεων του τρέχοντος έτους και περασμένων βρίσκονται συγκεντρωμένα στα παρακάτω αποθετήρια. Σε κάποια από αυτά, είναι πιθανό να πρέπει να συνδεθείτε με τους κωδικούς σας του ΕΜΠ.
Εκφώνηση: Η γλώσσα προγραμματισμού Edsger (
Για να εξοικειωθείτε με τη γλώσσα, προσπαθήστε να γράψετε μικρά και μεγαλύτερα προγράμματα σε Edsger, είτε απευθείας είτε μεταφράζοντας υπάρχοντα προγράμματά σας από άλλες γλώσσες. Αν στερείστε από ιδέες, δείτε τις εκφωνήσεις των ασκήσεων των εισαγωγικών προγραμματιστικών μαθημάτων εδώ και εδώ (για κάποιες από αυτές, υπάρχουν και υποδειγματικές λύσεις).
Δημοσιεύστε τα προγράμματά σας με κατάλληλα pull requests στο GitHub repository του μαθήματος , ώστε να είναι διαθέσιμα και στους υπόλοιπους. Έτσι θα δημιουργηθεί ένα σύνολο προγραμμάτων που αργότερα θα χρησιμεύσουν ως test suite για τους μεταγλωττιστές σας.
Γεννήτρια συντακτικά ορθών προγραμμάτων Edsger
Πηγαίος κώδικας, σε Erlang, για τη γεννήτρια και την εκτύπωση τυχαίων συντακτικά ορθών προγραμμάτων Edsger και ένα μικρό shell script για την εύκολη χρήση τους.
Για να χρησιμοποιήσετε τα παραπάνω, θα χρειαστείτε να έχετε εγκαταστήσει την Erlang και το εργαλείο PropEr .
Εγχειρίδια χρήσης εργαλείων που θα σας είναι χρήσιμα στην υλοποίηση:
Για υλοποίηση με C/C++:
Για υλοποίηση με OCaml:
Για υλοποίηση με SML/NJ ή MLton:
Για υλοποίηση με Java:
Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 2020-21 , 2019-20 , 2018-19 , 2017-18 , 2016-17 , 2015-16 , 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 .
Διαλέξεις
Θέματα διεξαγωγής του μαθήματος
Εισαγωγή
Τρόποι υλοποίησης γλωσσών προγραμματισμού
Ιστορική αναδρομή
Δομή και φάσεις ενός μεταγλωττιστή
Διαδικασία μεταγλώττισης και ενδιάμεσες αναπαραστάσεις
Τρέχουσες τάσεις της υλοποίησης γλωσσών προγραμματισμού
Διαφάνειες διάλεξης
Εισαγωγή στη λεκτική ανάλυση
Λεκτικές μονάδες (tokens)
Θέματα σχεδιασμού λεκτικής ανάλυσης στις γλώσσες προγραμματισμού
Κανονικές εκφράσεις και κανονικές γλώσσες
Από κανονικές εκφράσεις σε προδιαγραφές λεκτικών αναλυτών
Αμφισημίες και χειρισμός λαθών
Υλοποίηση λεκτικών αναλυτών
Διαφάνειες διάλεξης
Εισαγωγή στην συντακτική ανάλυση
Ο ρόλος του συντακτικού αναλυτή
Γλώσσες χωρίς συμφραζόμενα
Παραγωγές
Ισοδύναμες και διφορούμενες γραμματικές
Παράδειγμα: dangling if
Τρόποι εξάλειψης της αμφισημίας
Συντακτικά σφάλματα και τρόποι χειρισμού τους
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (του 2021)
Συντακτικός αναλυτής
Αφηρημένα συντακτικά δένδρα
Σημασιολογικές ενέργειες
Μετάφραση βασισμένη στη σύνταξη
Συντακτική ανάλυση top-down
Recursive Descent Parsing
Γραμματικές LL(1)
Μετασχηματισμός σε LL(1)
Αλγόριθμος συντακτικής ανάλυσης γραμματικών LL(1)
Πίνακας LL(1) και ένα παράδειγμα χρήσης του
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (του 2021)
Συγγραφή προγραμμάτων για τη γλώσσα Edsger
Συγγραφή του λεκτικού αναλυτή για την παραπάνω γλώσσα
Συντακτική ανάλυση (συνέχεια)
Μετατροπή του ΣΑ για τη minibasic από C σε C++
Σημασιολογικές τιμές
Κατασκευή του αφηρημένου συντατικού δένδρου με χρήση του bison σε C++ (Ημιτελές πρόγραμμα)
Συντακτική ανάλυση top-down, ξανά
Ανασκόπηση LL συντακτικής ανάλυσης
Κατασκευή πίνακα LL(1)
Υπολογισμός συνόλων First και Follow
Συντακτική ανάλυση bottom-up
Εισαγωγή στην ανοδική συντακτική ανάλυση (bottom-up parsing)
Ολίσθηση (shift) και αναγωγή (reduce)
Ένα παράδειγμα shift-reduce parsing
Ο αλγόριθμος συντακτικής ανάλυσης LR
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (του 2021)
LR και LALR συντακτικοί αναλυτές
Ανασκόπηση ανοδικής συντακτικής ανάλυσης
Ο αλγόριθμος συντακτικής ανάλυσης LR
Στοιχεία LR(0) και LR(1)
Κατασκευή του DFA ενός συντακτικού αναλυτή LR(1)
Συγκρούσεις ολισθήσεων και αναγωγών (shift/reduce conflicts) και τρόποι επίλυσής τους
Χρήση συντακτικών αναλυτών
Συντακτικοί αναλυτές LALR(1)
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (του 2021)
Συντακτική ανάλυση και σημασιολογικές τιμές (συνέχεια)
Κατασκευή του αφηρημένου συντατικού δένδρου με χρήση του bison και μετατροπή του σε μοντέρνα C++
Διερμηνέας για τη minibasic με διάσχιση του AST, σε C++
Μαγνητοσκοπημένο εργαστήριο (Teams)
Σημασιολογική ανάλυση
Ο ρόλος της σημασιολογικής ανάλυσης στους μεταγλωττιστές
Εμβέλεια ονομάτων
Στατική εμβέλεια ονομάτων
Δυναμική εμβέλεια ονομάτων
Εμβέλεια και πίνακες συμβόλων
Τύποι και συστήματα τύπων
Ρόλοι των τύπων στις γλώσσες προγραμματισμού
Γλώσσες με στατικά και δυναμικά συστήματα τύπων
Διαφάνειες διάλεξης
Έλεγχος τύπων
Στατικός έλεγχος προγραμμάτων
Συστήματα τύπων και ιδιότητές τους
Τύποι στις γλώσσες προγραμματισμού
Αναπαράσταση των τύπων σε ένα μεταγλωττιστή
Έλεγχος και συμπερασμός των τύπων
Κανόνες συμπερασμού και ελέγχου τύπων
Υλοποίηση ελέγχου τύπων με χρήση σημασιολογικών κανόνων του συντακτικού αναλυτή
Διαφάνειες διάλεξης
Μαγνητοσκοπημένη διάλεξη (του 2021)
Επέκταση της γλώσσας minibasic
Προσθήκη δήλωσης μεταβλητών
Προσθήκη τύπων int και bool
Προσθήκη δομών block
Επέκταση του συντακτικού αναλυτή για την παραπάνω γλώσσα
Απαραίτητες τροποποιήσεις για τη δημιουργία και την εκτύπωση του AST σε C++
Από προηγούμενα έτη: σε C++ και σε C
Μαγνητοσκοπημένο εργαστήριο (του 2021)
Υλοποίηση σημασιολογικού αναλυτή για την επέκταση της minibasic
Προσθήκη ελέγχου τύπων
Προσθήκη λεκτικών εμβελειών
Υλοποίηση του πίνακα συμβόλων
Σημασιολογική ανάλυση με διάσχιση του AST για τη minibasic+ σε C++
Διαφάνειες για τη δημιουργία και χρήση του πίνακα συμβόλων Το video του εργαστηρίου από παλαιότερη χρονιά είναι σε αυτό του εργαστηρίου της 5/5/2022
Παραγωγή κώδικα
Μηχανές στοίβας
Η γλώσσα της αρχιτεκτονικής MIPS
Μηχανές στοίβας με συσσωρευτή
Μετατροπή κώδικα μηχανής στοίβας σε MIPS
Παραγωγή κώδικα με χρήση αναδρομής (για τη γλώσσα “Mini Bar”)
Παραγωγή κώδικα για μεταβλητές και παραμέτρους
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (του 2021)
Ενδιάμεσος κώδικας και τοπική βελτιστοποίηση
Ενδιάμεσος κώδικας: λόγοι ύπαρξης, τρόποι παραγωγής και χρήσης
Ενδιάμεσος κώδικας τριών διευθύνσεων (3-address code)
Βασικά μπλοκ (basic blocks)
Γράφοι ελέγχου ροής (control-flow graphs)
Εισαγωγή στη βελτιστοποίηση κώδικα
Τοπικές βελτιστοποήσεις
Αλγεβρική απλοποίηση
Αντικατάσταση σταθερών (constant folding)
Βελτιστοποιήσεις ελέγχου ροής
Εξάλειψη κοινών υποεκφράσεων (common subexpression elimination)
Διάδοση αντιγράφων (copy propagation)
Εξάλειψη νεκρού κώδικα (dead code elimination)
Βελτιστοποιήσεις κλειδαρότρυπας (peephole optimizations)
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (από το 2021)
Καθολική παραχώρηση καταχωρητών
Διαχείριση ιεραρχίας μνήμης
Παραχώρηση καταχωρητών μέσω χρωματισμού γράφου (graph coloring)
Ο γράφος παρεμβολής των καταχωρητών (register interference graph)
Ευρεστικές τεχνικές
Spilling
Πρoχρωματισμένοι κόμβοι (precolored nodes)
Διαχείριση κρυφής μνήμης (cache management)
Διαφάνειες διάλεξης Μαγνητοσκοπημένη διάλεξη (από το 2021)
Τελευταία αλλαγή: 08/03/2022, 12:20 UTC.
webmaster (AT) courses (DOT) softlab.ntua.gr
PDF).