Εθνικό Μετσόβιο Πολυτεχνείο
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών

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

https://courses.softlab.ntua.gr/compilers/

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

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

Εξάμηνο:

Εαρινό 2008

Διδάσκων:

Νίκος Παπασπύρου

()

γρ. 1.1.21

τηλ: 210-772-3393

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

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

10/9/2008	Ανακοινώθηκε η βαθμολογία της γραπτής επαναληπτικής εξέτασης (Σεπτεμβρίου) και η πρώτη έκδοση της βαθμολογίας των εργασιών. Οι τελικοί βαθμοί κατατίθενται στη γραμματεία ως βαθμοί Ιουνίου. Όσες ομάδες δεν έχουν παραδώσει την εργασία τους, ή πρόκειται να κάνουν διορθώσεις ή βελτιώσεις, θα συμπεριληφθούν στην κατάσταση βαθμολογίας Σεπτεμβρίου.
22/7/2008	Ανακοινώθηκε η βαθμολογία της γραπτής τελικής εξέτασης (Ιουνίου). Η τελική βαθμολόγηση των εργασιών, και κατά συνέπεια η αποστολή των βαθμών στη γραμματεία θα γίνει το Σεπτέμβριο, καθώς όλες σχεδόν οι ομάδες δεν έχουν παραδώσει την εργασία τους. Για τους σπουδαστές που θα έχουν συμμετάσχει και στις δύο γραπτές τελικές εξετάσεις (Ιουνίου και Σεπτεμβρίου) προφανώς θα μετρήσει ο μεγαλύτερος βαθμός.
9/4/2008	Την Πέμπτη 10/4, ώρα 10:45-12:30, θα γίνει έκτακτο μάθημα στην Αίθουσα 01 του Νέου Κτιρίου Ηλεκτρολόγων. Την εβδομάδα από 14/4 έως 18/4 δε θα γίνει μάθημα, λόγω απουσίας του διδάσκοντα στο εξωτερικό.
8/4/2008	Οι παραδόσεις στο εργαστήριο του μαθήματος θα γίνονται στο εξής κάθε Τρίτη, ώρα 19:00-21:00, στην Αίθουσα 03 του Νέου Κτιρίου Ηλεκτρολόγων.
26/3/2008	ΠΡΟΣΟΧΗ: Εγγραφείτε στο Moodle και δηλώστε τη διαθεσιμότητά σας για την πιθανή μεταφορά των διώρων του εργαστηρίου και της θεωρίας, ακολουθώντας τις οδηγίες που περιέχονται σε αυτό το μήνυμα το αργότερο μέχρι τις 31/3, ώρα 8:00.
17/3/2008	Το μάθημα της Τετάρτης 19/3 δεν έγινε, λόγω απεργίας του διδάσκοντα.
17/3/2008	Το μάθημα θα αρχίσει με την πρώτη παράδοση εργαστηρίου την Τρίτη 18/3, ώρα 18:00-20:00, στο Αμφιθέατρο Ηλεκτρολόγων.

Υλικό

Γενικά

Ενημερωτικό φυλλάδιο (PDF, 137KB).
- Περιγραφή του μαθήματος και διαδικαστικά θέματα.

Δείτε επίσης τις διαφάνειες "διαφήμισης" του μαθήματος (PDF, 236KB).

Ώρες γραφείου διδασκόντων:
- Ν. Παπασπύρου: Τετάρτη 14:00–15:00, Κτίριο Ηλεκτρολόγων, 1.1.21, τηλ. 210-772-3393.
Διαθέσιμα εργαλεία για την κατασκευή μεταγλωττιστών.

Εργασία

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

Βοηθητικά αρχεία που θα σας είναι χρήσιμα στην υλοποίηση
- Πηγαίος κώδικας, σε C (ZIP, 13KB ή TGZ, 9KB) και σε OCaml (ZIP, 10KB ή TGZ, 7KB), version 1.1.
  Περιεχόμενα του bonus pack:
  - Πίνακας κατακερματισμού για ονόματα αναγνωριστικών.
  - Απλός χειριστής σφαλμάτων.
  - Πίνακας συμβόλων. Για πληροφορίες σχετικές με τη χρήση του, δείτε το παράδειγμα (symbtest.c ή Symbtest.ml)
- Ίσως βρείτε χρήσιμο το συλλέκτη σκουπιδιών (garbage collector) του Hans Boehm, διαθέσιμο από τη σελίδα του ή από το τοπικό αντίγραφο (TGZ, 1048KB), version 7.0.
- Περιβάλλον συμβολομετάφρασης (ZIP, 181KB) αποτελούμενο από τον Microsoft Macro Assembler 5.10, τον Microsoft Linker 5.10 και τον Microsoft Library Manager 3.17.
- Η βιβλιοθήκη χρόνου εκτέλεσης (LIB, 5 KB) και ο κώδικας των συναρτήσεων σε x86 assembly (ZIP, 33 KB).

Εγχειρίδια χρήσης εργαλείων που θα σας είναι χρήσιμα στην υλοποίηση
- Για υλοποίηση με C/C++: flex (PDF, 669KB), bison (PDF, 763KB).
- Για υλοποίηση με OCaml: ocamllex (PDF, 185KB), ocamlyacc (PDF, 449KB).

Διαφάνειες

Οι διαφάνειες που θα χρησιμοποιούνται στις διαλέξεις είναι διαθέσιμες από την παρούσα σελίδα για τη διευκόλυνση των σπουδαστών, ώστε αυτοί να μη χρειάζεται να κρατούν εκτενείς σημειώσεις κατά τη διάρκεια των μαθημάτων. Μη βιαστείτε να εκτυπώσετε όλες τις διαφάνειες! Θα αλλάζουν κατά τη διάρκεια του εξαμήνου. Η ύλη των διαφανειών παρουσιάζεται αναλυτικά στις σημειώσεις του μαθήματος.

Σε μορφή για παρουσίαση (PDF, 1543KB), μία διαφάνεια ανά σελίδα.
Σε μορφή για εκτύπωση (PDF, 1011KB), έξι διαφάνειες ανά σελίδα.
Τελευταία ενημέρωση των διαφανειών: 07/05/2008.

Επιπλέον διαφάνειες:

Ενδιάμεσος κώδικας
- Σε μορφή για παρουσίαση (PDF, 378KB), μία διαφάνεια ανά σελίδα.
- Σε μορφή για εκτύπωση (PDF, 377KB), έξι διαφάνειες ανά σελίδα.
Βελτιστοποίηση ενδιάμεσου κώδικα
- Σε μορφή για παρουσίαση (PDF, 340KB), μία διαφάνεια ανά σελίδα.
- Σε μορφή για εκτύπωση (PDF, 259KB), έξι διαφάνειες ανά σελίδα.
Τελικός κώδικας
- Σε μορφή για παρουσίαση (PDF, 489KB), μία διαφάνεια ανά σελίδα.
- Σε μορφή για εκτύπωση (PDF, 567KB), έξι διαφάνειες ανά σελίδα.
Προχωρημένα θέματα: μεταγλώττιση αντικειμενοστρεφών γλωσσών
- Σε μορφή για παρουσίαση (PDF, 228KB), μία διαφάνεια ανά σελίδα.
- Σε μορφή για εκτύπωση (PDF, 268KB), έξι διαφάνειες ανά σελίδα.

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

Διαλέξεις

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

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

Παράδοση 26/3/2008

Εισαγωγή (επανάληψη)
Περιγραφή της εργασίας
Τυπικές γλώσσες
- Γεννητικά και αναγνωριστικά μοντέλα
- Γραμματικές
- Ιεραρχία Chomsky
- Αναγνωριστές
Κανονικές γλώσσες
- Κανονικές εκφράσεις
- Πεπερασμένα αυτόματα
- Αναγωγές και ισοδυναμίες

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

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

Παράδοση 2/4/2008

Λεκτική ανάλυση
- Διαγράμματα μετάβασης
- Κατασκευή του λεκτικού αναλυτή
Γλώσσες χωρίς συμφραζόμενα
- Διφορούμενες γλώσσες
- Τρόποι παράστασης γλωσσών χωρίς συμφραζόμενα
Συντακτική ανάλυση
- Ανοδικοί και καθοδικοί συντακτικοί αναλυτές
- Βοηθητικές έννοιες, υπολογισμός FIRST και FOLLOW
- Ανοδική συντακτική ανάλυση
  - Συντακτικοί αναλυτές LR(1)
  - Συντακτικοί αναλυτές SLR(1)

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

Συντακτική ανάλυση
- Υλοποίηση ΣΑ με το bison
- Παράδειγμα, συντακτικός αναλυτής για τη minibasic, σε C και σε OCaml
Αντίστοιχα παραδείγματα από προηγούμενα έτη:
- Πρόγραμμα #1 (2007), αριθμητικές εκφράσεις με σταθερές: expr.l, expr.y και Makefile

Πρόγραμμα #2 (2006), απλή συντακτική ανάλυση εκφράσεων: simple.l και simple.y
Πρόγραμμα #3 (2006), ομοίως με προτεραιότητες τελεστών: lesssimp.l και lesssimp.y
Πρόγραμμα #4 (2006), ομοίως με υπολογισμό αποτελέσματος: eval.l και eval.y

Παράδοση 10/4/2008

Συντακτικοί αναλυτές από πάνω προς τα κάτω
- Γραμματικές LL(1)
  - Αντικατάσταση
  - Αριστερή παραγοντοποίηση
  - Απαλοιφή αριστερής αναδρομής
- Συντακτικοί αναλυτές αναδρομικής κατάβασης
- Συντακτικοί αναλυτές LL(1)
  - Κατασκευή του πίνακα συντακτικής ανάλυσης LL(1)
  - Λειτουργία συντακτικού αναλυτή LL(1)
Κατηγορικές γραμματικές
Πίνακας συμβόλων

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

Περιγραφή του πίνακα συμβόλων (bonus pack)
Σημασιολογικές ρουτίνες στο bison
- Παράδειγμα, διερμηνέας για minibasic (θα συνεχιστεί)

Παράδοση 7/5/2008

Συντακτικοί αναλυτές από πάνω προς τα κάτω
- Γραμματικές LL(1)
  - Αντικατάσταση
  - Αριστερή παραγοντοποίηση
  - Απαλοιφή αριστερής αναδρομής
- Συντακτικοί αναλυτές αναδρομικής κατάβασης
- Συντακτικοί αναλυτές LL(1)
  - Κατασκευή του πίνακα συντακτικής ανάλυσης LL(1)
  - Λειτουργία συντακτικού αναλυτή LL(1)
Κατηγορικές γραμματικές
Πίνακας συμβόλων

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

Σημασιολογικές ρουτίνες στο bison
- Παράδειγμα, διερμηνέας για τη minibasic, σε C και σε OCaml
Παραγωγή ενδιάμεσου κώδικα
- Η γλώσσα των τετράδων
  - Τελούμενα
  - Τελεστές
- Παράδειγμα παραγωγής ενδιάμεσου κώδικα: quicksort

Παράδοση 14/5/2008

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

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

Παραγωγή τελικού κώδικα, εισαγωγή
- Τελικός υπολογιστής: x86
  - Καταχωρητές
  - Εντολές
- Παράδειγμα προγράμματος σε x86 assembly

Παράδοση 21/5/2008

Βελτιστοποίηση
- Εισαγωγή
- Ανάλυση ροής ελέγχου
- Ανάλυση ροής δεδομένων
- Βελτιστοποιητικοί μετασχηματισμοί
  - Μετασχηματισμοί υψηλού επιπέδου
    - Αποτίμηση σταθερών εκφράσεων
    - Αλγεβρικοί μετασχηματισμοί
    - Απαλοιφή κοινών υποεκφράσεων
    - Διάδοση αντιγράφων
    - Ενοποίηση κώδικα
  - Μετασχηματισμοί βρόχων
  - Μετασχηματισμοί χαμηλού επιπέδου
  - Μετασχηματισμοί υποπρογραμμάτων

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

Παραγωγή τελικού κώδικα
- Παράδειγμα: μεταγλωττιστής για τη minibasic με χρήση της στοίβας

Παράδοση 28/5/2008

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

Εργαστήριο 3/6/2008

Ένας γεννήτορας τελικού κώδικα για τη γλώσσα των τετράδων
- Βοηθητικές ρουτίνες
- Παραγωγή κώδικα
Παράδειγμα παραγωγής τελικού κώδικα
Λύση ασκήσεων

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

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

Παράδοση 11/6/2008

Συντακτικοί αναλυτές από κάτω προς τα πάνω
- Συντακτικοί αναλυτές SLR(1)
  - Στοιχεία και συναρτήσεις CLOSURE και GOTO
  - Εύρεση του συνόλου καταστάσεων
  - Κατασκευή των πινάκων ελέγχου SLR(1)

Εργαστήριο 17/6/2008

Απορίες
Λύση ασκήσεων από παλιά θέματα εξετάσεων

Τελευταία αλλαγή: 11/9/08, 16:17.