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

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

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

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

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

Εξάμηνο:

Εαρινό 2005

Διδάσκων:

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

()

γρ. 1.1.21

τηλ: 210-772-3393

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Εργασία, Διαφάνειες, Παλαιότερα έτη
Διαλέξεις: 23/2 | 2/3 | 8/3 | 16/3 | 22/3 | 6/4 | 12/4 | 20/4 | 1/6 | 8/6

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

14/11/2005	Η τελική βαθμολογία του μαθήματος κατατέθηκε στη γραμματεία. Θα δοθεί συμπληρωματική κατάσταση με όσους έχουν καθυστερήσει την παράδοση της εργασίας.
13/10/2005	Ανακοινώθηκε η βαθμολογία της επαναληπτικής γραπτής εξέτασης (Σεπτεμβρίου). Όλοι οι σπουδαστές παρακαλούνται να παραδώσουν τις εργασίες τους το συντομότερο δυνατό για να υπολογιστεί η τελική τους βαθμολογία.
27/7/2005	Ανακοινώθηκε η βαθμολογία της γραπτής τελικής εξέτασης. Η τελική βαθμολόγηση των εργασιών, και κατά συνέπεια η αποστολή των βαθμών στη γραμματεία θα γίνει το Σεπτέμβριο, καθώς όλες σχεδόν οι ομάδες δεν έχουν παραδώσει την εργασία τους. Για τους σπουδαστές που θα έχουν συμμετάσχει και στις δύο γραπτές τελικές εξετάσεις (Ιουνίου και Σεπτεμβρίου) προφανώς θα μετρήσει ο μεγαλύτερος βαθμός.
13/7/2005	ΠΡΟΣΟΧΗ: Οι σπουδαστές που παρακολούθησαν το μάθημα παρακαλούνται να συμπληρώσουν το ανώνυμο ερωτηματολόγιο αξιολόγησης, που αποσκοπεί στη μελλοντική βελτίωση του μαθήματος. Μπορείτε εναλλακτικά (i) να το προμηθευτείτε σε έντυπη μορφή από το Εργαστήριο Λογισμικού ή να το εκτυπώσετε (PDF, 240ΚΒ), να το συμπληρώσετε και να το ρίξετε στη γραμματοθυρίδα του διδάσκοντα, ή κάτω από την πόρτα του γραφείου του, ή (ii) να το συμπληρώσετε ηλεκτρονικά (ZIP, 19KB, περιέχει αρχείο Microsoft Word) και να το στείλετε με e-mail στο διδάσκοντα.

Παλαιότερες ανακοινώσεις

Υλικό

Γενικά

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

Δείτε επίσης τις διαφάνειες "διαφήμισης" του μαθήματος.

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

Εργασία

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

1η ανεξάρτητη εργασία
- Να κατασκευάσετε λεκτικό και συντακτικό αναλυτή για τη γλώσσα Llama, η περιγραφή της οποίας δίνεται παραπάνω. Να συμπεριληφθούν και τα τμήματα που χαρακτηρίζονται στο φυλλάδιο της γλώσσας ως προαιρετικά.
- Το πρόγραμμα που θα παραδώσετε θα πρέπει (κατ' ελάχιστον) να διαβάζει ένα πρόγραμμα Llama από το stdin και να απαντά "Success" αν η λεκτική και συντακτική ανάλυση ήταν επιτυχείς. Σε αντίθετη περίπτωση, θα πρέπει να εμφανίζει κατάλληλο επεξηγηματικό μήνυμα για το πρώτο σφάλμα που συναντά.

2η ανεξάρτητη εργασία
- Να κατασκευάσετε σημασιολογικό αναλυτή για τη γλώσσα Llama, η περιγραφή της οποίας δίνεται παραπάνω (συμπεριλαμβανομένων των τμημάτων που χαρακτηρίζονται στο φυλλάδιο της γλώσσας ως προαιρετικά). Ο σημασιολογικός αναλυτής θα πρέπει να κάνει εξαγωγή τύπων στην περίπτωση που αυτοί δεν έχουν δοθεί από τον προγραμματιστή.
- Πρέπει να παραδώσετε μια συνάρτηση που να δέχεται ως παράμετρο το συντακτικό δέντρο ενός προγράμματος Llama, στη μορφή που δίνεται στα αρχεία bonus και να απαντά "Success" αν η σημασιολογική ανάλυση ήταν επιτυχής. Σε αντίθετη περίπτωση, θα πρέπει να εμφανίζει κατάλληλο επεξηγηματικό μήνυμα για το πρώτο σφάλμα που συναντά.
- Μπορείτε να χρησιμοποιήσετε ένα έτοιμο εμπρόσθιο τμήμα (front-end) του μεταγλωττιστή, για την κατασκευή του συντακτικού δέντρου που θα δώσετε ως παράμετρο στη συνάρτησή σας: (ZIP, 28KB) ή (TGZ, 28KB), version 0.1 (7/4/2005).

3η ανεξάρτητη εργασία
- Να κατασκευάσετε γεννήτορα τελικού κώδικα για τη γλώσσα των τετράδων που περιγράφεται στο βιβλίο του μαθήματος. Η τελική γλώσσα πρέπει να είναι η assembly για επεξεργαστές της οικογένειας Intel x86.
- Μπορείτε να χρησιμοποιήσετε ένα έτοιμο αναγνώστη ενδιάμεσου κώδικα σε μορφή τετράδων: (ZIP, 16KB) ή (TGZ, 11KB), version 0.2 (24/6/2005).

Υλοποίηση της γλώσσας Llama, version 1.4 (23/8/2005)

Θα χρειαστείτε επίσης το μεταγλωττιστή της OCaml (3.08.3), διαθέσιμο από το: http://www.ocaml.org/

Λόγω της ομοιότητας μεταξύ OCaml και Llama, ίσως σας φανούν χρήσιμα τα ακόλουθα:

[Chai00]		E. Chailloux, P. Manoury and B. Pagano, Developing Applications with Objective Caml, O' Reilly and Associates, 2000. Available online from: http://caml.inria.fr/oreilly-book/.
[Hick02]		J. Hickey, Introduction to the Objective Caml Programming Language, course notes, 2002. Available online from: http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf.

Υλοποίηση της γλώσσας Llama χωρίς type inference, version 0.11 (27/5/2005)
- Εκτελέσιμο για Windows (ZIP, 90KB)
- Εκτελέσιμο για Linux (TGZ, 221KB)

Βοηθητικά αρχεία που θα σας είναι χρήσιμα στην υλοποίηση, version 0.2 (25/4/2005)
- Πηγαίος κώδικας σε C: (ZIP, 18KB) ή (TGZ, 11KB)
- Θα χρειαστείτε επίσης το συλλέκτη σκουπιδιών (garbage collector) του Hans Boehm, διαθέσιμο από τη σελίδα του ή από το τοπικό αντίγραφο (TGZ, 761KB), version 6.4.

Περιβάλλον εκτέλεσης, version 0.4 (14/10/2005)
- Περιβάλλον συμβολομετάφρασης (ZIP, 186KB) αποτελούμενο από τον Microsoft Macro Assembler 5.10, τον Microsoft Linker 5.10, τον Microsoft Library Manager 3.17 και το πρόγραμμα exe2bin.
- Βιβλιοθήκη χρόνου εκτέλεσης (LIB, 12 KB) και ο κώδικας των συναρτήσεων σε x86 assembly (ZIP, 223 KB) που περιέχει όλα τα παραπάνω.

Εγχειρίδιο χρήσης του flex (PDF, 334KB).
Εγχειρίδιο χρήσης του bison (PDF, 621KB).

Διαφάνειες

Σε μορφή για παρουσίαση (PDF, 1074KB), μία διαφάνεια ανά σελίδα.
Σε μορφή για εκτύπωση (PDF, 940KB), έξι διαφάνειες ανά σελίδα.
Τελευταία ενημέρωση των διαφανειών: 03/06/2005 (τελική έκδοση).

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

Διαλέξεις

Παράδοση 23/2/2005

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

Διαφάνειες: 1 έως 10

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

Τυπικές γλώσσες
- Γεννητικά και αναγνωριστικά μοντέλα
- Γραμματικές
- Ιεραρχία Chomsky
- Αναγνωριστές
Κανονικές γλώσσες
- Κανονικές εκφράσεις
- Πεπερασμένα αυτόματα
- Αναγωγές και ισοδυναμίες
Λεκτική ανάλυση
- Διαγράμματα μετάβασης
- Κατασκευή του λεκτικού αναλυτή
- Υλοποίηση ΛΑ με το flex

Διαφάνειες: 11 έως 33

Παράδοση 8/3/2005

Λεκτική ανάλυση (συνέχεια)
- Υλοποίηση ΛΑ με το flex
- Δύο προγράμματα επεξεργασίας κειμένου: tp1.l και tp2.l

Διαφάνειες: 33 έως 38

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

Γλώσσες χωρίς συμφραζόμενα
- Διφορούμενες γλώσσες
- Συμβολισμός BNF/EBNF
Συντακτική ανάλυση
- Από πάνω προς τα κάτω και από κάτω προς τα πάνω
- Υλοποίηση ΣΑ με το bison

Διαφάνειες: 39 έως 61

Παράδοση 22/3/2005

Συντακτική ανάλυση
- Υλοποίηση ΣΑ με το bison (συνέχεια)
- Πρόγραμμα #1, απλή συντακτική ανάλυση εκφράσεων: simple.l και simple.y
- Πρόγραμμα #2, ομοίως με προτεραιότητες τελεστών: lesssimp.l και lesssimp.y
- Πρόγραμμα #3, ομοίως με υπολογισμό αποτελέσματος: eval.l και eval.y
Κατηγορικές γραμματικές
Πίνακας συμβόλων

Διαφάνειες: 56 έως 72 και 81 έως 87

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

Σημασιολογική ανάλυση
- Στατική σημασιολογία
- Δυναμική σημασιολογία
- Σημασιολογικός έλεγχος
Περιγραφή του κώδικα bonus

Διαφάνειες: 88 έως 96

Παράδοση 12/4/2005

Σημασιολογική ανάλυση (συνέχεια)
- Έλεγχος τύπων
- Εξαγωγή τύπων (type inference)

Διαφάνειες: 97 έως 105

Παράδοση 20/4/2005

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

Διαφάνειες: 106 έως 142

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

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

Διαφάνειες: 143 έως 184

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

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

Διαφάνειες: 73 έως 80 και 185 έως 202

Τελευταία αλλαγή: 10/3/06, 20:11.