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

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

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

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

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

Υλικό

Γενικά

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

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

Εργασία

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

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

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

Διαλέξεις

Διάλεξη στο αμφιθέατρο, πρώτη ώρα 12/2/2025

• Θέματα διεξαγωγής του μαθήματος
• Διαφάνειες με πληροφορίες για το μάθημα

Διάλεξη στο αμφιθέατρο, επόμενο δίωρο 12/2/2025

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

Διάλεξη στο αμφιθέατρο 14/2/2025

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

Εργαστήριο λεκτικού αναλυτή με το flex 14/2/2025

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

Διάλεξη από απόσταση (στο helios) 26/2/2025

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

Διάλεξη στο αμφιθέατρο 5/3/2025

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

Εργαστήριο συντακτικού αναλυτή με το bison από απόσταση 7/3/2025

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

Διάλεξη στο αμφιθέατρο, πρώτο δίωρο 12/3/2025

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

Διάλεξη στο αμφιθέατρο, έξτρα ώρα αναπλήρωσης 12/3/2025

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

Διάλεξη στο αμφιθέατρο, έξτρα ώρα αναπλήρωσης 14/3/2025

• LR και LALR συντακτικοί αναλυτές (Συνέχεια)
  • Συγκρούσεις ολισθήσεων και αναγωγών (shift/reduce conflicts) και τρόποι επίλυσής τους
  • Χρήση συντακτικών αναλυτών
  • Συντακτικοί αναλυτές LALR(1)
• Οι διαφάνειες και το video της διάλεξης βρίσκονται στη διάλεξη της 12/3/2025

Εργαστήριο συντακτικού αναλυτή με το bison στο αμφιθέατρο 14/3/2025

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

Εργαστήριο interpreter στο αμφιθέατρο 19/3/2025

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

Διάλεξη στο αμφιθέατρο 19/3/2025

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

Διάλεξη στο αμφιθέατρο 21/3/2025

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