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

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

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

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Εργασία, Παλαιότερα έτη
Διαλέξεις: 2/3 | 3/3 | 9/3 | 10/3 | 16/3 | 17/3 | 23/3 | 24/3 | 30/3 | 31/3 | 6/4 | 7/4 | 27/4 | 28/4 | 4/5 | 5/5 | 11/5 | 12/5 | 18/5 | 19/5 | 25/5 | 26/5 | 1/6 | 2/6 | 8/6 | (9/6)

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

Υλικό

Γενικά

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

Εργασία

• Εκφώνηση: Η γλώσσα προγραμματισμού Dana (PDF, 345KB).
  • Για να εξοικειωθείτε με τη γλώσσα, προσπαθήστε να γράψετε μικρά και μεγαλύτερα προγράμματα σε Dana, είτε απευθείας είτε μεταφράζοντας υπάρχοντα προγράμματά σας από άλλες γλώσσες. Αν στερείστε από ιδέες, δείτε τις εκφωνήσεις των ασκήσεων των εισαγωγικών προγραμματιστικών μαθημάτων εδώ και εδώ (για κάποιες από αυτές, υπάρχουν και υποδειγματικές λύσεις).
  • Δημοσιεύστε τα προγράμματά σας μέσω του 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, 5KB) και ο κώδικας των συναρτήσεων σε x86 assembly (ZIP, 32KB).

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

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

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

Διαλέξεις

Παράδοση 2/3/2017

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

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

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

Παράδοση 9/3/2017

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

Παράδοση 16/3/2017

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

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

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

Παράδοση 23/3/2017

• Διάλεξη: Συντακτική ανάλυση
  • Ανοδικοί και καθοδικοί συντακτικοί αναλυτές
  • Βοηθητικές έννοιες, υπολογισμός FIRST και FOLLOW
  • Γραμματικές LL(1)
    • Αντικατάσταση
    • Αριστερή παραγοντοποίηση
    • Απαλοιφή αριστερής αναδρομής Συντακτικοί αναλυτές αναδρομικής κατάβασης Συντακτικοί αναλυτές LL(1)
    • Κατασκευή του πίνακα συντακτικής ανάλυσης LL(1)
    • Λειτουργία συντακτικού αναλυτή LL(1)
  • Ανοδική συντακτική ανάλυση
    • Συντακτικοί αναλυτές LR(1)
  • Διαφάνειες διάλεξης

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

• Εργαστήριο: Κατασκευή συντακτικού αναλυτή με το bison
  • Το εργαλείο bison
  • Παράδειγμα, λεκτικός αναλυτής για τη minibasic, σε C και σε OCaml (από παλιότερο έτος)
  • Παράδειγμα, συντακτικός αναλυτής για τη minibasic, σε C και σε OCaml (από παλιότερο έτος)

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

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

Παράδοση 6/4/2017

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

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

• Εργαστήριο: Κατασκευή διερμηνέα για τη minibasic
  • Παράδειγμα: διερμηνέας για τη minibasic
  • Με διάσχιση του AST, σε C
  • Από προηγούμενα έτη: σε OCaml και με συναρτήσεις υψηλής τάξης, σε OCaml

Παράδοση 27/4/2017

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

Παράδοση 28/4/2017

• Εργαστήριο: Κατασκευή σημασιολογικού αναλυτή για τη minibasic
  • Προσθήκη τύπων και λεκτικών εμβελειών (blocks) στη minibasic
  • Παράδειγμα: σημασιολογικός αναλυτής για τη minibasic, με διάσχιση του AST, σε C
  • Περιγραφή του πίνακα συμβόλων (bonus pack)

Παράδοση 4/5/2017

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

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

• Εργαστήριο: Κατασκευή σημασιολογικού αναλυτή για τη minibasic
  • Παράδειγμα: ολοκλήρωση του σημασιολογικού αναλυτή για τη minibasic, με διάσχιση του AST, σε C
  • Σκέψεις και συζήτηση για τις απαιτούμενες τροποποιήσεις στον διερμηνέα της minibasic

Παράδοση 11/5/2017

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

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

• Εργαστήριο: Τροποποίηση του διερμηνέα της minibasic
  • Παράδειγμα: τροποποίηση του διερμηνέα της minibasic, ώστε να υποστηρίζει λεκτικές εμβέλειες (blocks), σε C

Παράδοση 18/5/2017

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

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

• Εργαστήριο: Κατασκευή μεταγλωττιστή για τη minibasic
  • Παραγωγή τελικού κώδικα
  • Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση της στοίβας, σε C
    • Παραγωγή τελικού κώδικα για i386 (linux)
    • Περιέχει ένα μικρό μέρος της runtime library για i386

Παράδοση 25/5/2017

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

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

• Εργαστήριο: Κατασκευή μεταγλωττιστή για τη minibasic (συνέχεια)
  • Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση της στοίβας, σε C
    • Υποστήριξη λεκτικών εμβελειών (blocks)

Παράδοση 1/6/2017

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

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

• Εργαστήριο: Ενδιάμεσος κώδικας σε μορφή τετράδων
  • Παραγωγή ενδιάμεσου κώδικα με τη μορφή τετράδων
  • Ένα απλό σχέδιο παραγωγής τετράδων
    • Αριθμητικές εκφράσεις
    • Λογικές εκφράσεις
    • Απλές εντολές
    • Σύνθετη εντολή
    • Εντολή if
    • Εντολή while
    • Κλήση υποπρογραμμάτων
  • Διαφάνειες διάλεξης

Παράδοση 8/6/2017

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

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

• Εργαστήριο: Κατασκευή LLVM backend για τη minibasic
  • [Το εργαστήριο δεν έγινε λόγω κωλύματος του διδάσκοντος]
  • Χρήσιμες πληροφορίες για το LLVM:
    • LLVM documentation
    • LLVM tutorial — Kaleidoscope
  • Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση του LLVM, σε C++
  • Θα χρειαστείτε τη runtime library για x86_64 (Αχιλλέας Μπενετόπουλος).