Παρουσίαση/Προβολή

Περιεχόμενο μαθήματος - Module Description

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

Λέξεις Κλειδιά: Μεταγλωττιστές, Διερμηνευτές, Λεκτική Ανάλυση, Συντακτική Ανάλυση, Σημασιολογική Ανάλυση, Αναπαραστάσεις Ενδιάμεσης Μορφής Προγραμμάτων, Βελτιστοποίηση Προγραμμάτων, Παραγωγή Τελικού Κώδικα

The course aims to introduce students to translation technology and compilers. The course material aims at understanding and acquiring fundamental knowledge in the translation of programs expressed in programming languages ​​and relevant optimization techniques. An additional goal is to link introductory programming courses and data structures with the most specialized courses in the fields, because it requires global infrastructure knowledge and the offered knowledge can be used in a wide range of applications, such as information retrieval, communication protocols, hardware description languages, microprocessors , natural language processing etc. In particular, it aims:

Keywords: Compilers, Interpreters, Lexical Analysis, Syntactic Analysis, Semantic Analysis, Intermediate Program Representation, Program Optimization, Target Code Generation

Προαπαιτούμενα - PREREQUISITE COURSES

Οι φοιτητές/τριες θα πρέπει κατέχουν καλή γνώση Διαδικασιακού Προγραμματισμού (Κ-260) και Δομών Δεδομένων & Αλγορίθμων (Κ-320). Προαιρετικά, επιθυμητή είναι η γνώση Αντικειμενοστρεφούς προγραμματισμού (Κ-430). 

No. Students should have good knowledge of Procedural Programming (ECE_K260) or Object-Oriented Programming (ECE_K430) and Data Structures & Algorithms (ECE_K320)

Διδάσκοντας - Lecturer

Διδάσκων: Παναγιώτης Αλεφραγκής, Αναπληρωτής Καθηγητής, Εmail: alefrag@go.uop.gr

Lecturer: Panayiotis Alefragis, Associate Professor, Εmail: alefrag@go.uop.gr

Μαθησιακοί στόχοι - Learning outcomes

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής θα είναι σε θέση:

Σε επίπεδο Γνώσεων:

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

Σε επίπεδο Δεξιοτήτων:

• να μετασχηματίζει γραμματικές για να είναι κατάλληλες για υλοποίηση
• να υλοποιεί αλγόριθμους και δομές δεδομένων για κάθε φάσης μεταγλώττισης
• να χρησιμοποιεί εργαλεία και βιβλιοθήκες για τη ανάπτυξη μεταγλωττιστών
• να υλοποιεί προγράμματα που πραγματοποιούν ανάλυση κειμένου
• να υλοποιεί σύνθετες εφαρμογές στη γλώσσα υλοποίησης C
• να παράγει προγράμματα χαμηλού επιπέδου από προγράμματα σε μια γλώσσα υψηλού επιπέδου
• να μπορεί να συγκρίνει κώδικα επιπέδου γλώσσας μηχανής και τον ίδιο κώδικα σε γλώσσες υψηλού επιπέδου

Σε επίπεδο Ικανοτήτων:

• να σχεδιάζει μία καινούργια γλώσσα προγραμματισμού
• να συντάσσει τη γραμματική μιας γλώσσας προγραμματισμού
• να οργανώνεται σε ομάδες εργασίας
• να υλοποιεί χρονοδιάγραμμα ανάπτυξης έργου λογισμικού με ενδιάμεσα παραδοτέα
• να επιλέγει και να συνδυάζει τα κατάλληλα εργαλεία / βιβλιοθήκες για την επίλυση προβλημάτων μετάφρασης ή/και ανάλυση κειμένων

Upon successful completion of the course, student will be able to:

At the Knowledge level:

• know the basic concepts of translators' theory
• know the structure of programming languages
• know the stages of interpreting and compiling programs of programming languages
• understand the need to use tools to implement the process of lexical and syntactic analysis
• understand the forms of intermediate representations
• know algorithms to improve the intermediate and final representation of programs
• know the concept of Instruction Set Architecture through optimizations and final code generation
• understand the differences in computer architectures through the study of the execution mechanisms of the final code

At the Skill level:

• be able to transform grammars to make them eligible for implementation
• implement algorithms and data structures for each compilation phase
• use tools and libraries to develop compilers
• implement programs that perform text analysis
• implement complex applications in the C programming language
• produce low-level programs from programs in a high-level language
• be able to compare code in machine language to the same code in a high-level languages

At the level of Abilities:

• design a new programming language
• write the grammar of a programming language
• participate and collaborate into working groups
• implement a software project development schedule with intermediate deliverables
• select and combine the appropriate tools / libraries for solving translation problems and / or textual analysis

Περιεχόμενο μαθήματος - SYLLABUS

1. Εισαγωγή στου μεταγλωττιστές και στα συστήματα μετάφρασης. Η Δομή ενός Μεταγλωττιστή: Γλώσσες, ανάπτυξη μεταγλωττιστών, εργαλεία ανάπτυξης, σύνθεση από τμήματα λογισμικού, ορολογία, απαιτήσεις, φάσεις μεταγλώττισης, οργάνωση μεταγλωττιστή
2. Λεκτική Ανάλυση: αυτόματα, κανονικές εκφράσεις, εσωτερική λειτουργία λεκτικού αναλυτή
3. Εργαλεία Κατασκευής Μεταγλωττιστών: Παρουσίαση flex, bison, antlr
4. Συντακτική Ανάλυση Ι: Λειτουργία συντακτικού αναλυτή, top down συντακτικοί αναλυτές, γραμματικές (LL(1), LL(k)), μετασχηματισμοί γραμματικών
5. Συντακτική Ανάλυση ΙΙ: συντακτικά κατευθυνόμενη μετάφραση, bottom up συντακτικοί αναλυτές, γραμματικές (LR(0), SLR(1), LR(k) και LALR(1))
6. Διαχείριση Πίνακα Συμβόλων: Οργάνωση του πίνακα συμβόλων, εγγράφημα δραστηριοποίησης, ανάκτηση πληροφορίας από τον πίνακα συμβόλων, διαφορετικές μορφές και υλοποιήσεις ανάλογα με τις απαιτήσεις της γλώσσας, Πίνακες κατακερματισμού, βιβλιοθήκες
7. Σημασιολογική Ανάλυση: Σημασιολογικός έλεγχος, σημασιολογικά χαρακτηριστικά, σημασιολογικοί κανόνες.
8. Παραγωγή Ενδιάμεσου Κώδικα Ι: ενδιάμεση γλώσσα, αριθμητικές πράξεις, λογικές παραστάσεις, λογικές πράξεις
9. Παραγωγή Ενδιάμεσου Κώδικα ΙΙ: Δομές απόφασης, δομές επανάληψης, συναρτήσεις διαδικασίες
10. Βελτιστοποίηση Κώδικα I: Οργάνωση μεταφραστή βελτιστοποίησης, ανάλυση ελέγχου ροής και δεδομένων, αλγεβρικοί μετασχηματισμοί
11. Βελτιστοποίηση Κώδικα II: Μετασχηματισμοί βρόχων, μετασχηματισμοί χαμηλού επιπέδου, μετασχηματισμοί υποπρογραμμάτων
12. Παραγωγή Τελικού Κώδικα Ι: Βασικές εντολές γλώσσας μηχανής, παραγωγή κώδικα για αριθμητικών πράξεων, εντολές αλμάτων και εντολές εισόδου/εξόδου
13. Παραγωγή Τελικού Κώδικα ΙΙ: Οργάνωση μνήμης, Παραγωγή κώδικα για εντολές εγγραφής και ανάγνωσης προς και από τη μνήμη, κλήσεις συναρτήσεων και διαδικασιών, πέρασμα παραμέτρων

Το μάθημα παρέχει στους φοιτητές όλες τις βασικές γνώσεις στο αντικείμενο των μεταγλωττιστών. Το μάθημα περιλαμβάνει επίλυση ασκήσεων καθώς και υποχρεωτική προγραμματιστική εργασία σε ομάδες με θέμα την πλήρη κατασκευή με χρήση γλώσσας υψηλού επιπέδου (C,Java) και εργαλείων ανάπτυξης μεταγλωττιστών ενός πλήρους μεταγλωττιστή κάποιας απλοποιημένης γλώσσας προγραμματισμού.

1. Introduction to compilers and translation systems. The Structure of a Compiler: Languages, compiler development, development tools, composition of software components, terminology, requirements, compilation phases, compiler organization
2. Lexical Analysis: automata, regular expressions, internal lexical analyser functionality
3. Compiler Construction Tools: Flex, bison, antlr
4. Syntactic Analysis I: Syntax analyser functionality, top down parsers, grammars (LL(1), LL(k)), grammatical transformations
5. Syntactic Analysis ΙΙ: Syntax Directed Translation, bottom up parsers, grammars (LR(0), SLR(1), LR(k) και LALR(1))
6. Symbol Table Management: Organization of the symbol table, activity chart, retrieval of information from the symbol table, different formats and implementations depending on language requirements, Hash tables, libraries
7. Semantic Analysis: Semantic checks, semantic properties, semantic rules.
8. Intermediate Code Production I: intermediate languages, arithmetic operations, logical representations, logical operations
9. Intermediate Code Production II : Decision structures, repetition structures, functions and processes
10. Code Optimization I: Organization of an optimization translator, control flow and data analysis, algebric transformations
11. Code Optimization II: Loop transformations, low-level transformations, subprogram transformations
12. Final Code I Production: Basic machine language commands, code output for arithmetic operations, jump commands and I/O commands
13. Final Code II Production: Memory Organization, Code generation for write and read commands to/from memory, Function and Process Calls, Parameter Passing

The course provides students with all required knowledge in the subject of compilers. The course includes solving exercises as well as mandatory group programming project to implement a complete compiler for some simplified programming language using a high-level language (C,Java) and compiler development tools.

Μέθοδοι διδασκαλίας

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

Μέθοδοι αξιολόγησης - evaluation methods

Η αξιολόγηση γίνεται στην Ελληνική γλώσσα. Μπορεί να πραγματοποιηθεί και στην Αγγλική γλώσσα αν υπάρχουν αλλοδαποί φοιτητές.

Παρουσίαση υλοποίησης ομαδικής εργασίας και ατομική προφορική αξιολόγηση κάθε φοιτητή σε τέσσερις διακριτές φάσεις (40%).

Γραπτή τελική εξέταση (60%) που περιλαμβάνει:

1. Επίλυση ασκήσεων ανάπτυξης
2. Ερωτήσεις πολλαπλής επιλογής
3. Ερωτήσεις σύντομης απάντησης

Βαθμολογική κλίμακα: 1 έως 10

Ελάχιστος βαθμός επιτυχίας: 5

Βαθμοί < 5 αντιστοιχούν σε βαθμό ECTS F.

Για τους υπόλοιπους βαθμούς η αντιστοίχιση έχει ως εξής:

>= 9: ECTS A

>= 8: ECTS B

>= 7: ECTS C

>= 6: ECTS D

>= 5: ECTS E

Παρατηρήσεις:

Τα κριτήρια αξιολόγησης ορίζονται σαφώς στην πρώτη διάλεξη του εξαμήνου καθώς και τα επιμέρους ποσοστά και οι κανόνες που διέπουν τη βαθμολόγηση, τόσο των παραπάνω τριών μεθόδων αξιολόγησης, όσο και των επιμέρους ποσοστών των διαφόρων φάσεων της προγραμματιστικής άσκησης. Τα κριτήρια αξιολόγησης και τα επιμέρους ποσοστά αναρτώνται στην εκπαιδευτική πλατφόρμα με την ανάρτηση της προγραμματιστικής άσκησης

Language of evaluation: Greek (English if required)

Presentation of project and oral examination for each student (40% of final mark).

Final examination (60% of final mark): Written exam that might include multiple choice questionnaires, short-answer questions, problem solving.

Grading scale: 1 to 10

Minimum passing mark: 5

Grades < 5 correspond to ECTS grade F.

For the rest of the grades the correspondence is as follows:

>= 9: ECTS A

>= 8: ECTS B

>= 7: ECTS C

>= 6: ECTS D

>= 5: ECTS E

Note:

The evaluation criteria are clearly announced during the first lecture of the semester as well as the individual percentages and the rules governing the grading, both of the above evaluation methods and of the individual percentages of the different phases of the work. The project evaluation criteria and the individual percentages are posted on the asynchronous educational platform with the project announcement.

Βιβλιογραφία

-Προτεινόμενη Βιβλιογραφία :

• Μεταγλωττιστές, A.V. Aho-M.S. Lam-R.Sethi-J.D.Ullman, Εκδόσεις Νέων Τεχνολογιών Μον. ΕΠΕ, 2011 [12713790]
• Μεταγλωττιστές Γλωσσών Προγραμματισμού, ΘΕΩΡΙΑ ΚΑΙ ΠΡΑΞΗ, Κ. ΛΑΖΟΣ, Π. ΚΑΤΣΑΡΟΣ, Ζ. ΚΑΡΑΪΣΚΟΣ, 3η έκδοση, 2004 [3873]
• Engineering: A Compiler, Keith D. Cooper, Linda Torczon, ISBN 978-012-088-478-0, Morgan Kaufmann, 2011
• Introduction to Compiler Design, Torben Aegidius Mogensen, 978-331-966-966-3, HEAL-Link Springer ebooks, 2017
• A Practical Approach to Compiler Construction, Des Watson, ISBN 978-331-952-789-5, HEAL-Link Springer ebooks, 2017

-Συναφή επιστημονικά περιοδικά:

• IEEE Transactions on Computers
• IEEE Transactions on Parallel and Distributed Systems
• ACM Transactions on Embedded Computing Systems
• ACM Transactions on Design Automation of Electronic Systems
• Programming Language Design and Implementation (PLDI) Conference Proceedings
• Languages, Compilers, and Tools for Embedded Systems (LCTES) Conference Proceedings

- Suggested bibliography:

• Compilers 2ed, A.V. Aho-M.S. Lam-R.Sethi-J.D.Ullman,ISBN 032-148-681-1, Addison Wesley, 2006
• Engineering: A Compiler, Keith D. Cooper, Linda Torczon, ISBN 978-012-088-478-0, Morgan Kaufmann, 2011
• Introduction to Compiler Design, Torben Aegidius Mogensen, 978-331-966-966-3, HEAL-Link Springer ebooks, 2017
• A Practical Approach to Compiler Construction, Des Watson, ISBN 978-331-952-789-5, HEAL-Link Springer ebooks, 2017

- Related academic journals:

• IEEE Transactions on Computers
• IEEE Transactions on Parallel and Distributed Systems
• ACM Transactions on Embedded Computing Systems
• ACM Transactions on Design Automation of Electronic Systems
• Programming Language Design and Implementation (PLDI) Conference Proceedings
• Languages, Compilers, and Tools for Embedded Systems (LCTES) Conference Proceedings