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

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

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

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Εργασία, Παλαιότερα έτη
Διαλέξεις: 18/2 | 21/2 | 25/2 | 28/2 | 4/3 | 7/3 | 14/3 | 18/3 | 21/3 | 28/3 | 1/4 | 4/4 | 8/4 | 11/4 | 15/4 | 18/4 | 6/5 | 9/5 | 13/5 | 16/5 | 20/5 | 23/5 | 27/5 | 30/5 | 6/6

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

Υλικό

Γενικά

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

Εργασία

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

• Βοηθητικά αρχεία που θα σας είναι χρήσιμα στην υλοποίηση:
  • Πηγαίος κώδικας, σε C (ZIP ή TGZ) και σε OCaml (ZIP ή TGZ).
    Περιεχόμενα του bonus pack:
    • Πίνακας κατακερματισμού για ονόματα αναγνωριστικών.
    • Απλός χειριστής σφαλμάτων.
    • Πίνακας συμβόλων. Για πληροφορίες σχετικές με τη χρήση του, δείτε το παράδειγμα (symbtest.c ή Symbtest.ml).
  • Ίσως βρείτε χρήσιμο το συλλέκτη σκουπιδιών (garbage collector) του Hans Boehm, διαθέσιμο από τη σελίδα του. Ίσως χρειαστείτε επίσης τη βιβλιοθήκη libatomic_ops.
  • Περιβάλλον συμβολομετάφρασης (ZIP) αποτελούμενο από τον Microsoft Macro Assembler 5.10, τον Microsoft Linker 5.10 και τον Microsoft Library Manager 3.17.
  • Εναλλακτικό περιβάλλον συμβολομετάφρασης (ZIP) αποτελούμενο από τον Microsoft Macro Assembler 6.11d, τον Microsoft Linker 5.31 και τον Microsoft Library Manager 3.20. Αυτή η έκδοση του συμβολομεταφραστή μετασχηματίζει αυτόματα τα relative jumps που είναι εκτός ορίων.
  • Πιθανώς χρήσιμα scripts (ZIP) για τον έλεγχο του μεταγλωττιστή σας σε Linux με dosbox.
  • Βιβλιοθήκη χρόνου εκτέλεσης (LIB) και ο κώδικας των συναρτήσεων σε x86 assembly (ZIP).

• Εγχειρίδια χρήσης εργαλείων που θα σας είναι χρήσιμα στην υλοποίηση:
  • Για υλοποίηση με C/C++:
    • flex ( PDF)
    • bison ( PDF)
  • Για υλοποίηση με OCaml:
    • ocamllex ( PDF)
    • ocamlyacc ( PDF)
    • Menhir
    • Parsing with OCamllex and Menhir
  • Για υλοποίηση με SML/NJ ή MLton:
    • ML-Lex και MLLex
    • ML-Yacc και MLYacc
  • Για υλοποίηση με Java:
    • JLex
    • JFLex ( PDF)
    • CUP

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

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

Διαλέξεις

Παράδοση 18/2/2019

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

Παράδοση 21/2/2019

• Παρουσίαση της γλώσσας PCL

• Τυπικές γλώσσες
  • Βασικές έννοιες
  • Ιεραρχία Chomsky
  • Κανονικές γραμματικές
  • Κανονικές εκφράσεις
  • Πεπερασμένα αυτόματα
• Λεκτική ανάλυση
  • Εισαγωγή
  • Λεκτικές μονάδες (tokens)
  • Διαγράμματα μετάβασης
  • Υλοποίηση λεκτικών αναλυτών
• Διαφάνειες διάλεξης

• Διαφάνειες προηγούμενης χρονιάς: introduction to lexical analysis

Εργαστήριο 25/2/2019

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

Παράδοση 28/2/2019

• Τυπικές γλώσσες
  • Γλώσσες χωρίς συμφραζόμενα
  • Παραγωγές
  • Ισοδύναμες και διφορούμενες γραμματικές
  • Παράδειγμα: dangling if
  • Τρόποι παράστασης γραμματικών
• Συντακτική ανάλυση bottom-up
  • Συντακτικοί αναλυτές ολίσθησης-ελάττωσης
  • Λειτουργία συντακτικού αναλυτή ολίσθησης-ελάττωσης
  • Συντακτικοί αναλυτές LR(0), SLR(1), LALR(1), LR(1)
• Διαφάνειες διάλεξης
• Διαφάνειες προηγούμενης χρονιάς: introduction to parsing

Εργαστήριο 4/3/2019

• Συντακτική ανάλυση
  • Υλοποίηση ΣΑ με το bison
  • Παράδειγμα: συντακτικός αναλυτής για τη minibasic, σε C++ και σε OCaml.
• Διαφάνειες διάλεξης

Εργαστήριο 7/3/2019

• Συντακτική ανάλυση (συνέχεια)
  • Υλοποίηση ΣΑ με το bison
  • Παράδειγμα με σημασιολογικές ρουτίνες
  • Παράδειγμα: συντακτικός αναλυτής για τη minibasic που κατασκευάζει το συντακτικό δένδρο (δεν ολοκληρώθηκε)

Εργαστήριο 18/3/2019

• Συντακτική ανάλυση (συνέχεια)
  • Παράδειγμα: συντακτικός αναλυτής για τη minibasic που κατασκευάζει το συντακτικό δένδρο (ο κώδικας ενσωματώνεται στο παρακάτω)
• Υλοποίηση διερμηνέα με σημασιολογικές ρουτίνες
  • Παράδειγμα: διερμηνέας για τη minibasic
  • Με διάσχιση του AST, σε C++
  • Από προηγούμενα έτη: σε OCaml και με συναρτήσεις υψηλής τάξης, σε OCaml

Παράδοση 21/3/2019

• Συντακτική ανάλυση top-down
  • Βοηθητικές έννοιες: FIRST, FOLLOW
  • Γραμματικές LL(1)
  • Μετασχηματισμός σε LL(1)
  • Κατασκευή συντακτικού αναλυτή LL(1)
• Διαφάνειες διάλεξης
• Διαφάνειες προηγούμενης χρονιάς

Παράδοση 28/3/2019

• Συντακτική ανάλυση bottom-up (ξανά)
  • Ολίσθηση (shift) και αναγωγή (reduce)
  • Ο αλγόριθμος συντακτικής ανάλυσης LR
  • Στοιχεία LR(0) και LR(1)
  • Κατασκευή του DFA ενός συντακτικού αναλυτή LR(1)
  • Συντακτικοί αναλυτές LALR(1)
• Διαφάνειες διάλεξης
• Διαφάνειες προηγούμενης χρονιάς – SLR(1)

Εργαστήριο 1/4/2019

• Κατηγορικές γραμματικές
• Πίνακες συμβόλων

• Περιγραφή του πίνακα συμβόλων (bonus pack)

• Διαφάνειες διάλεξης

Παράδοση 4/4/2019

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

Εργαστήριο 8/4/2019

• Υλοποίηση σημασιολογικού αναλυτή για τη minibasic
  • Προσθήκη τύπων
  • Προσθήκη λεκτικών εμβελειών

Παράδοση 11/4/2019

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

Εργαστήριο 15/4/2019

• Υλοποίηση σημασιολογικού αναλυτή για τη minibasic, ολοκλήρωση.
  • Με διάσχιση του AST, και απαραίτητες τροποποιήσεις στο διερμηνέα, σε C++
  • Από προηγούμενα έτη: σε C

Παράδοση 18/4/2019

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

Εργαστήριο 6/5/2019

• Υλοποίηση μεταγλωττιστή για τη minibasic με χρήση της στοίβας
  • Παραγωγή τελικού κώδικα για i386 (linux)
  • Περιέχει ένα μικρό μέρος της runtime library για i386

Παράδοση 9/5/2019

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

Εργαστήριο 13/5/2019

• Υλοποίηση μεταγλωττιστή για τη minibasic με χρήση της στοίβας, σε C++
  • Από προηγούμενα έτη: σε C
  • Mε λεκτικές εμβέλειες, σε C

Παράδοση 16/5/2019

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

Εργαστήριο 20/5/2019

• Κατασκευή LLVM backend για τη minibasic
  • Χρήσιμες πληροφορίες για το LLVM: - LLVM documentation
    • LLVM tutorial — Kaleidoscope
  • Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση του LLVM.

Παράδοση 23/5/2019

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

Εργαστήριο 27/5/2019

• Κατασκευή LLVM backend για τη minibasic
  • Συνέχεια του εργαστηρίου της 20/5.

Παράδοση 30/5/2019

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

Εργαστήριο 6/6/2019

• Κατασκευή LLVM backend για τη minibasic
  • Συνέχεια και ολοκλήρωση του εργαστηρίου της 20/5 και της 27/5.
  • Mεταγλωττιστής για τη minibasic με χρήση του LLVM, σε C++
• Θα χρειαστείτε τη runtime library για x86_64 (Αχιλλέας Μπενετόπουλος).