Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Μεταγλωττιστές https://courses.softlab.ntua.gr/compilers/

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

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

Ανακοινώσεις | Υλικό: Γενικά, Helios, Videos (2021), Εργασία, Παλαιότερα έτη
Διαλέξεις: 2/3 | 3/3 | 10/3 | 24/3 | 24/3 | 31/3 | 31/3 | 7/4 | 7/4 | 28/4 | 28/4 | 5/5 | 12/5 | 12/5 | 19/5 | 26/5 | 26/5 | 2/6 | 2/6 | 7/6 | 9/6 | 9/6 | 9/6

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

Υλικό

Γενικά

• Ενημερωτικό φυλλάδιο ( PDF).
  • Περιγραφή του μαθήματος και διαδικαστικά θέματα.
  • Δείτε επίσης τις διαφάνειες “διαφήμισης” του μαθήματος (PDF).
• Εργαλεία για την κατασκευή μεταγλωττιστών.
• Βιβλιογραφία

• Τα βίντεο των διαλέξεων του τρέχοντος έτους και περασμένων βρίσκονται συγκεντρωμένα στα παρακάτω αποθετήρια. Σε κάποια από αυτά, είναι πιθανό να πρέπει να συνδεθείτε με τους κωδικούς σας του ΕΜΠ.
  • 2021: YouTube
  • 2020: MS Stream, YouTube
  • 2010: AoC

Εργασία

• Εκφώνηση: Η γλώσσα προγραμματισμού Grace ( PDF)
  • Για να εξοικειωθείτε με τη γλώσσα, προσπαθήστε να γράψετε μικρά και μεγαλύτερα προγράμματα σε Grace, είτε απευθείας είτε μεταφράζοντας υπάρχοντα προγράμματά σας από άλλες γλώσσες. Αν στερείστε από ιδέες, δείτε τις εκφωνήσεις των ασκήσεων των εισαγωγικών προγραμματιστικών μαθημάτων εδώ και εδώ (για κάποιες από αυτές, υπάρχουν και υποδειγματικές λύσεις).
  • Δημοσιεύστε τα προγράμματά σας με κατάλληλα pull requests στο GitHub repository του μαθήματος, ώστε να είναι διαθέσιμα και στους υπόλοιπους. Έτσι θα δημιουργηθεί ένα σύνολο προγραμμάτων που αργότερα θα χρησιμεύσουν ως test suite για τους μεταγλωττιστές σας.

• Εγχειρίδια χρήσης εργαλείων που θα σας είναι χρήσιμα στην υλοποίηση:
  • Για υλοποίηση με 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

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

Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 2021-22, 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.

Διαλέξεις

Διάλεξη "Αντεστραμμένου Αμφιθέατρου" (Flipped classroom) 2/3/2023

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

Διάλεξη "Αντεστραμμένου Αμφιθέατρου" (Flipped Classroom) 3/3/2023

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

Εργαστήριο 10/3/2023

• Λεκτική ανάλυση
  • Υλοποίηση ΛΑ με το flex.
  • Παράδειγμα: λεκτικός αναλυτής για τη minibasic σε C (και για C++).
• Παραδείγματα από προηγούμενα έτη:
  • Λεκτικός αναλυτής για τη minibasic σε OCaml.
  • Πρόγραμμα επεξεργασίας κειμένου: tp.l και αρχεία για έλεγχο tp1.txt και tp2.txt.
• Διαφάνειες εργαστηρίου
• Κώδικας εργαστηρίου
• Μαγνητοσκοπημένο εργαστήριο (του 2021)

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

• Εισαγωγή στην συντακτική ανάλυση
  • Ο ρόλος του συντακτικού αναλυτή
  • Γλώσσες χωρίς συμφραζόμενα
  • Παραγωγές
  • Ισοδύναμες και διφορούμενες γραμματικές
  • Παράδειγμα: dangling if
  • Τρόποι εξάλειψης της αμφισημίας
  • Συντακτικά σφάλματα και τρόποι χειρισμού τους
• Διαφάνειες διάλεξης
• Μαγνητοσκοπημένη διάλεξη (του 2021)

Εργαστήριο (στο helios) 24/3/2023

• Συντακτική ανάλυση
  • Υλοποίηση ΣΑ με το bison
  • Παράδειγμα: συντακτικός αναλυτής για τη minibasic σε C.
• Παραδείγματα από προηγούμενα έτη:
  • Συντακτικός αναλυτής για τη minibasic σε C++.
  • Συντακτικός αναλυτής για τη minibasic σε OCaml.
• Διαφάνειες εργαστηρίου
• Κώδικας εργαστηρίου
• Μαγνητοσκοπημένο εργαστήριο (2023 στο helios)

Παράδοση (πρώτο δίωρο) 31/3/2023

• Συντακτικός αναλυτής
  • Αφηρημένα συντακτικά δένδρα
  • Σημασιολογικές ενέργειες
  • Μετάφραση βασισμένη στη σύνταξη
• Συντακτική ανάλυση top-down
  • Recursive Descent Parsing
  • Γραμματικές LL(1)
  • Μετασχηματισμός σε LL(1)
  • Αλγόριθμος συντακτικής ανάλυσης γραμματικών LL(1)
  • Πίνακας LL(1) και ένα παράδειγμα χρήσης του
• Διαφάνειες διάλεξης
• Μαγνητοσκοπημένη διάλεξη (του 2021)

Παράδοση (δεύτερο δίωρο) 31/3/2023

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

Παράδοση 7/4/2023

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

Εργαστήριο 7/4/2023

• Παρουσίαση του αρχείου parser.output που bison ο κατασκευάζει όταν χρησιμοποιηθεί το option -v
• Σημασιολογικές τιμές στο αρχείο του bison και η σύνδεσή τους με τις τιμές των tokens του lexer
• Παρουσίαση της γεννήτριας συντακτικά ορθών προγραμμάτων Grace με χρήση του εργαλείου PropEr

Εργαστήριο (στο helios - πρώτο μέρος) 28/4/2023

• Συντακτική ανάλυση (συνέχεια)
  • Μετατροπή του ΣΑ για τη minibasic από C σε C++
  • Σημασιολογικές τιμές
  • Κατασκευή του αφηρημένου συντατικού δένδρου με χρήση του bison σε C++
• Κώδικας εργαστηρίου
• Μαγνητοσκοπημένο εργαστήριο (2023 στο helios)

Εργαστήριο (στο helios - δεύτερο μέρος) 28/4/2023

• Διερμηνέας για τη minibasic με διάσχιση του AST, σε C++
• Κώδικας εργαστηρίου
• Το video του εργαστηρίου είναι στην τελευταία ώρα του παραπάνω video

Παράδοση 5/5/2023

• Σημασιολογική ανάλυση
  • Ο ρόλος της σημασιολογικής ανάλυσης στους μεταγλωττιστές
  • Εμβέλεια ονομάτων
    • Στατική εμβέλεια ονομάτων
    • Δυναμική εμβέλεια ονομάτων
    • Εμβέλεια και πίνακες συμβόλων
  • Τύποι και συστήματα τύπων
    • Ρόλοι των τύπων στις γλώσσες προγραμματισμού
    • Γλώσσες με στατικά και δυναμικά συστήματα τύπων
  • Διαφάνειες διάλεξης
• Έλεγχος τύπων
  • Στατικός έλεγχος προγραμμάτων
  • Συστήματα τύπων και ιδιότητές τους
  • Τύποι στις γλώσσες προγραμματισμού
  • Αναπαράσταση των τύπων σε ένα μεταγλωττιστή
  • Έλεγχος και συμπερασμός των τύπων
  • Κανόνες συμπερασμού και ελέγχου τύπων
  • Υλοποίηση ελέγχου τύπων με χρήση σημασιολογικών κανόνων του συντακτικού αναλυτή
  • Διαφάνειες διάλεξης
• Μαγνητοσκοπημένη διάλεξη (του 2021)

Εργαστήριο 12/5/2023

• Επέκταση της γλώσσας minibasic
  • Προσθήκη δήλωσης μεταβλητών
  • Προσθήκη τύπων int και bool
  • Προσθήκη δομών block
• Επέκταση του συντακτικού αναλυτή για την παραπάνω γλώσσα
  • Απαραίτητες τροποποιήσεις για τη δημιουργία και την εκτύπωση του AST σε C++
  • Από προηγούμενα έτη: σε C++ και σε C
• Μαγνητοσκοπημένο εργαστήριο (του 2021)

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

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

Εργαστήριο (στο helios) 19/5/2023

• Υλοποίηση σημασιολογικού αναλυτή για την επέκταση της minibasic
  • Προσθήκη ελέγχου τύπων
  • Προσθήκη λεκτικών εμβελειών
  • Υλοποίηση του πίνακα συμβόλων
  • Σημασιολογική ανάλυση με διάσχιση του AST για τη minibasic+ σε C++
• Διαφάνειες για τη δημιουργία και χρήση του πίνακα συμβόλων
• Κώδικας εργαστηρίου
• Μαγνητοσκοπημένο εργαστήριο (2023 στο helios)

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

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

Εργαστήριο 26/5/2023

• Ανασκόπηση του σημασιολογικού αναλυτή για τη minibasic+
• Τροποποίηση του διερμηνέα για τη σωστή υλοποίηση εμβελειών και οι διαφορές του με τον κώδικα του σημασιολογικού αναλυτή σε C++
• Από προηγούμενα έτη: σε C++, σε C και σε OCaml
• Ολοκληρωμένος κώδικας εργαστηρίου
• Μαγνητοσκοπημένο εργαστήριο (του 2021)

Εργαστήριο 2/6/2023

• Υλοποίηση μεταγλωττιστή για τη minibasic με χρήση της στοίβας, σε C++
  • Παραγωγή τελικού κώδικα για i386 (linux)
  • Από προηγούμενο έτος: σε OCaml
• Κώδικας εργαστηρίου (ημιτελής)
• Μαγνητοσκοπημένο εργαστήριο (από το 2021)

Παράδοση 2/6/2023

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

Εργαστήριο 7/6/2023

• Συνέχεια της υλοποίησης του μεταγλωττιστή για τη minibasic με χρήση της στοίβας, σε C++
  • Ολοκλήρωση της παραγωγής τελικού κώδικα για i386 (linux)
  • Περιέχει ένα μικρό μέρος της runtime library για i386
  • Από προηγούμενο έτος: σε OCaml
• Ολοκληρωμένος κώδικας εργαστηρίου
• Κατασκευή κώδικα LLVM IR για ένα πρόγραμμα minibasic με το χέρι
• Μαγνητοσκοπημένο εργαστήριο (από το 2021)

Εργαστήριο 9/6/2023

• Κατασκευή LLVM backend για τη minibasic
  • Χρήσιμες πληροφορίες για το LLVM:
    • LLVM documentation
    • LLVM tutorial — Kaleidoscope
  • Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση του LLVM, σε C++.
  • Για την υλοποίηση του print, θα χρειαστείτε τη runtime library για x86_64.
• Ολοκληρωμένος κώδικας εργαστηρίου (για LLVM versions 7 έως 11
• Μαγνητοσκοπημένο εργαστήριο (1ο μέρος - από το 2021)
• Μαγνητοσκοπημένο εργαστήριο (2ο μέρος - από το 2021)

Παράδοση 9/6/2023

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

Παράδοση 9/6/2023

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