Μεταγλωττιστές
Ιωάννης Σμαραγδάκης
Βασική δομή ενός μεταγλωττιστή. Τυπικές γλώσσες: κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, κατηγορικές γραμματικές. Λεκτική ανάλυση, χρήση μεταεργαλείων για τη δημιουργία λεκτικών αναλυτών. Συντακτική ανάλυση: συντακτικοί αναλυτές από πάνω προς τα κάτω (top-down) και από κάτω προς τα πάνω (bottom-up), ανάνηψη από σφάλματα, χρήση μεταεργαλείων για τη δημιουργία συντακτικών αναλυτών. Πίνακας συμβόλων. Σημασιολογική ανάλυση: είδη σημασιολογικών ελέγχων, συστήματα τύπων, δυναμικός έλεγχος τύπων. Παραγωγή ενδιάμεσου κώδικα. Βελτιστοποίηση κώδικα. Παραγωγή τελικού κώδικα. Μεταγλώττιση μη-κλασσικών γλωσσών προγραμματισμού.
ΛιγότεραΒασική δομή ενός μεταγλωττιστή. Τυπικές γλώσσες: κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, κατηγορικές γραμματικές. Λεκτική ανάλυση, χρήση μεταεργαλείων για τη δημιουργία λεκτικών αναλυτών. Συντακτική ανάλυση: συντακτικοί αναλυτές από πάνω προς τα κάτω (top-down) και από κάτω προς τα πάνω (bottom-up), ανάνηψη από σφάλματα, χρήση μεταεργαλείων για τη δημιουργία συντακτικών αναλυτών. Πίνακας συμβόλων. Σημασιολογική ανάλυση: είδη σημασιολογικών ελέγχων, συστήματα τύπων, δυναμικός έλεγχος τύπων. Παραγωγή ενδιάμεσου κώδικα. Βελτιστοποίηση κώδικα. Παραγωγή τελικού κώδικα. Μεταγλώττιση μη-κλασσικών γλωσσών προγραμματισμού.
Βασική δομή ενός μεταγλωττιστή. Τυπικές γλώσσες: κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, κατηγορικές γραμματικές. Λεκτική ανάλυση, χρήση μεταεργαλείων για τη δημιουργία λεκτικών αναλυτών. Συντακτική ανάλυση: συντακτικοί αναλυτές από πάνω προς τα κάτω (top-down) και από κάτω προς τα πάνω (bottom-up), ανάνηψη από σφάλματα, χρήση μεταεργαλείων για τη δημιουργία συντακτικών αναλυτών. Πίνακας συμβόλων. Σημασιολογική ανάλυση: είδη σημασιολογικών ελέγχων, συστήματα τύπων, δυναμικός έλεγχος τύπων. Παραγωγή ενδιάμεσου κώδικα. Βελτιστοποίηση κώδικα. Παραγωγή τελικού κώδικα. Μεταγλώττιση μη-κλασσικών γλωσσών προγραμματισμού.
Περίγραμμα
![CC - Αναφορά - Μη Εμπορική Χρήση - Παρόμοια Διανομή CC - Αναφορά - Μη Εμπορική Χρήση - Παρόμοια Διανομή](/template/default/img/cc/by-nc-sa.png)
Περιεχόμενο μαθήματος
- Εισαγωγή στους μεταγλωττιστές
- Επισκόπηση Μεταγλωττιστών
- Λεξική Ανάλυση
- Συντακτική Ανάλυση (top-down)
- Σημασιολογικήανάλυσηκαιέλεγχοςτύπων
- Visitor pattern
- Παραγωγή low level ενδιάμεσουκώδικα
- Ανάλυση προγραμμάτων, ροή δεδομένων, βελτιστοποίηση
- Συντακτική Ανάλυση (bottom-up)
- Δέσμευση Καταχωριστών
- Παραγωγή κώδικα (Επιλογή εντολών)
Διδάσκοντες
![Διδάσκον](/modules/document/file.php/DI111/images/smaragdakis.jpg)
Σμαραγδάκης Ιωάννης
Βαθμίδα: Αναπληρωτής Καθηγητής
Τομέας: Υπολογιστικά Συστήματα και εφαρμογές
Βιβλιογραφία
Official textbooks:
- Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman Compilers: Principles, Techniques, and Tools. 2nd edition. Addison-Wesley, 2007.
http://dragonbook.stanford.edu/
Published in translation by Newtech Publications (Νέων Τεχνολογιών) (http://www.newtech-publications.gr/)
- Nikolaos S. Papaspyrou and Emmanuel St. Skordalakis, Compilers, Symmetria, Athens, 2002.
(Νικόλαος Παπασπύρου και Εμμανουήλ Σκορδαλάκης. Μεταγλωττιστές, Εκδόσεις Συμμετρία.)
- K. Lazos, P. Katsaros, Z. Karaiskos, Compilers of Programming Languages: Theory and Practice, Thesaloniki 2004
Κ. Λάζος, Π. Κατσαρός, Ζ. Καραΐσκος. Μεταγλωττιστές Γλωσσών Προγραμματισμού: θεωρία και πράξη. Εκδόσεις Θεσσαλονίκη 2004.
http://delab.csd.auth.gr/~katsaros/CompilersBook.htm
Reference books:
- Andrew W. Appel, Modern Compiler Implementation in C. Cambridge University Press, 1998.
- Andrew W. Appel, Modern Compiler Implementation in Java. Cambridge University Press, 1998.
http://www.cs.princeton.edu/~appel/modern
- Charles N. Fischer and Richard J. LeBlanc, Jr. Crafting a Compiler with C, Benjamin/Cummings, 1991.
- Steven S. Muchnick, Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997.
- Allen I. Hollub, Compiler Design in C, Prentice Hall, 1990.
Ομάδα στόχος
Προπτυχιακοί φοιτητές του τμήματος Πληροφορικής και Τηλεπικοινωνιών - Φοιτητές του μαθήματος.
Προαπαιτούμενα
Προαπαιτούμενα Μαθήματα: Δομές Δεδομένων και Τεχνικές Προγραμματισμού, Αντικειμενοστραφής Προγραμματισμός
Συνιστώμενα Προαπαιτούμενα Μαθήματα: Αρχιτεκτονική Υπολογιστών Ι
Ηλεκτρονική σελίδα μαθήματος
Σημειώματα Δικαιωμάτων Πνευματικής Ιδιοκτησίας
Για το υλικό του παρόντος μαθήματος ισχύουν τα ακόλουθα σημειώματα.
Σημείωμα Ιστορικού Εκδόσεων Έργου
Το παρόν έργο αποτελεί την έκδοση 1.0.
Σημείωμα Αναφοράς
Copyright Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών, Γιάννης Σμαραγδάκης 2015. Γιάννης Σμαραγδάκης. Μεταγλωττιστές. Έκδοση: 1.0. Αθήνα 2015. Διαθέσιμο από τη δικτυακή διεύθυνση: http://opencourses.uoa.gr/courses/DI111.
Σημείωμα Αδειοδότησης
Το παρόν υλικό διατίθεται με τους όρους της άδειας χρήσης Creative Commons Αναφορά, Μη Εμπορική Χρήση Παρόμοια Διανομή 4.0 [1] ή μεταγενέστερη, Διεθνής Έκδοση. Εξαιρούνται τα αυτοτελή έργα τρίτων π.χ. φωτογραφίες, διαγράμματα κ.λ.π., τα οποία εμπεριέχονται σε αυτό και τα οποία αναφέρονται μαζί με τους όρους χρήσης τους στο «Σημείωμα Χρήσης Έργων Τρίτων».
[1] http://creativecommons.org/licenses/by-nc-sa/4.0/
Ως Μη Εμπορική ορίζεται η χρήση:
- που δεν περιλαμβάνει άμεσο ή έμμεσο οικονομικό όφελος από την χρήση του έργου, για το διανομέα του έργου και αδειοδόχο
- που δεν περιλαμβάνει οικονομική συναλλαγή ως προϋπόθεση για τη χρήση ή πρόσβαση στο έργο
- που δεν προσπορίζει στο διανομέα του έργου και αδειοδόχο έμμεσο οικονομικό όφελος (π.χ. διαφημίσεις) από την προβολή του έργου σε διαδικτυακό τόπο
Ο δικαιούχος μπορεί να παρέχει στον αδειοδόχο ξεχωριστή άδεια να χρησιμοποιεί το έργο για εμπορική χρήση, εφόσον αυτό του ζητηθεί.
Διατήρηση Σημειωμάτων
- Οποιαδήποτε αναπαραγωγή ή διασκευή του υλικού θα πρέπει να συμπεριλαμβάνει:
- το Σημείωμα Αναφοράς
- το Σημείωμα Αδειοδότησης
- τη δήλωση Διατήρησης Σημειωμάτων
- το Σημείωμα Χρήσης Έργων Τρίτων (εφόσον υπάρχει)
μαζί με τους συνοδευόμενους υπερσυνδέσμους.
- Εισαγωγή στους μεταγλωττιστές
- Επισκόπηση Μεταγλωττιστών
- Λεξική Ανάλυση
- Συντακτική Ανάλυση (top-down)
- Σημασιολογικήανάλυσηκαιέλεγχοςτύπων
- Visitor pattern
- Παραγωγή low level ενδιάμεσουκώδικα
- Ανάλυση προγραμμάτων, ροή δεδομένων, βελτιστοποίηση
- Συντακτική Ανάλυση (bottom-up)
- Δέσμευση Καταχωριστών
- Παραγωγή κώδικα (Επιλογή εντολών)
Σμαραγδάκης Ιωάννης
Βαθμίδα: Αναπληρωτής Καθηγητής
Τομέας: Υπολογιστικά Συστήματα και εφαρμογές
Official textbooks:
- Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman Compilers: Principles, Techniques, and Tools. 2nd edition. Addison-Wesley, 2007.
http://dragonbook.stanford.edu/
Published in translation by Newtech Publications (Νέων Τεχνολογιών) (http://www.newtech-publications.gr/)
- Nikolaos S. Papaspyrou and Emmanuel St. Skordalakis, Compilers, Symmetria, Athens, 2002.
(Νικόλαος Παπασπύρου και Εμμανουήλ Σκορδαλάκης. Μεταγλωττιστές, Εκδόσεις Συμμετρία.)
- K. Lazos, P. Katsaros, Z. Karaiskos, Compilers of Programming Languages: Theory and Practice, Thesaloniki 2004
Κ. Λάζος, Π. Κατσαρός, Ζ. Καραΐσκος. Μεταγλωττιστές Γλωσσών Προγραμματισμού: θεωρία και πράξη. Εκδόσεις Θεσσαλονίκη 2004.
http://delab.csd.auth.gr/~katsaros/CompilersBook.htm
Reference books:
- Andrew W. Appel, Modern Compiler Implementation in C. Cambridge University Press, 1998.
- Andrew W. Appel, Modern Compiler Implementation in Java. Cambridge University Press, 1998.
http://www.cs.princeton.edu/~appel/modern
- Charles N. Fischer and Richard J. LeBlanc, Jr. Crafting a Compiler with C, Benjamin/Cummings, 1991.
- Steven S. Muchnick, Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997.
- Allen I. Hollub, Compiler Design in C, Prentice Hall, 1990.
Προπτυχιακοί φοιτητές του τμήματος Πληροφορικής και Τηλεπικοινωνιών - Φοιτητές του μαθήματος.
Για το υλικό του παρόντος μαθήματος ισχύουν τα ακόλουθα σημειώματα.
Σημείωμα Ιστορικού Εκδόσεων Έργου
Το παρόν έργο αποτελεί την έκδοση 1.0.
Σημείωμα Αναφοράς
Copyright Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών, Γιάννης Σμαραγδάκης 2015. Γιάννης Σμαραγδάκης. Μεταγλωττιστές. Έκδοση: 1.0. Αθήνα 2015. Διαθέσιμο από τη δικτυακή διεύθυνση: http://opencourses.uoa.gr/courses/DI111.
Σημείωμα Αδειοδότησης
Το παρόν υλικό διατίθεται με τους όρους της άδειας χρήσης Creative Commons Αναφορά, Μη Εμπορική Χρήση Παρόμοια Διανομή 4.0 [1] ή μεταγενέστερη, Διεθνής Έκδοση. Εξαιρούνται τα αυτοτελή έργα τρίτων π.χ. φωτογραφίες, διαγράμματα κ.λ.π., τα οποία εμπεριέχονται σε αυτό και τα οποία αναφέρονται μαζί με τους όρους χρήσης τους στο «Σημείωμα Χρήσης Έργων Τρίτων».
[1] http://creativecommons.org/licenses/by-nc-sa/4.0/
Ως Μη Εμπορική ορίζεται η χρήση:
- που δεν περιλαμβάνει άμεσο ή έμμεσο οικονομικό όφελος από την χρήση του έργου, για το διανομέα του έργου και αδειοδόχο
- που δεν περιλαμβάνει οικονομική συναλλαγή ως προϋπόθεση για τη χρήση ή πρόσβαση στο έργο
- που δεν προσπορίζει στο διανομέα του έργου και αδειοδόχο έμμεσο οικονομικό όφελος (π.χ. διαφημίσεις) από την προβολή του έργου σε διαδικτυακό τόπο
Ο δικαιούχος μπορεί να παρέχει στον αδειοδόχο ξεχωριστή άδεια να χρησιμοποιεί το έργο για εμπορική χρήση, εφόσον αυτό του ζητηθεί.
Διατήρηση Σημειωμάτων
- Οποιαδήποτε αναπαραγωγή ή διασκευή του υλικού θα πρέπει να συμπεριλαμβάνει:
- το Σημείωμα Αναφοράς
- το Σημείωμα Αδειοδότησης
- τη δήλωση Διατήρησης Σημειωμάτων
- το Σημείωμα Χρήσης Έργων Τρίτων (εφόσον υπάρχει)
μαζί με τους συνοδευόμενους υπερσυνδέσμους.
Λέξεις Κλειδιά: Compiler, high level programming language, compilation problem, translation process, compiler structure
Λέξεις κλειδιά: Translation strategy, compilation strategy, basic compiler structure, Compiler front end, lexical analysis, specifications, parsing, using grammar, replication, semantic analysis, semantic analysis in programs, IR, IR-lowering, Optimization, back-end, finished program, runtime system.
Λέξεις κλειδιά: Lexical analysis, Scanner, hand coded scanner, scanner construction, lookahead, Regular Expressions, Formal languages, Finite Automata, Finite Automata state graphs, RE and DFA, Non-deterministic Finite Automata (NDF), Deterministic Finite Automata (DFA), Scanner constructions, Thomson construction, transitions, subset construction, DFA minimization, Hopcroft algorithm, DFA minimization, register specification, partitioning, lexer, building a lexer
Λέξεις κλειδιά: Parsing, parser, lexical analysis, derivation, context free grammar, top-down parser, Bottom up parser, LR parser, Backus Naur form (BNF), rewriting rules, expressions, language of expressions, Rightmost-, leftmost-derivation, derivations as parse trees, Abstract syntax tree, Ambiguous grammar, if-then-else ambiguity, removing ambiguity, Backtracking, Retrying , successful parse, Left recursion, Right recursion grammar, lookahead, First and Follow sets, computing First sets, Computing Follow sets, LL(1), left factoring, predictive parsing, recursive descent
Λέξεις κλειδιά: Hierarchy of Grammar classes, syntax directed translation, Errors, program checking, Semantic checking, Static checking, dynamic checking, Uniqueness check, type checking, flow-of-control-checks, scope, procedures, lexical scoping, shadowing, name spaces, compile-time, run-time, chained implementation, stack implementation, threaded stack implementation, symbol tables, type errors, type system, expressiveness, static type, conservative, properties of types, type expressions, type constructors, Arrays, products, records, pointers, function signatures, type equivalence, structural equivalence, representation, name equivalence, recursive types, coercions, integral promotions, overloading
Λέξεις κλειδιά: Visitor patterns for compiler, design pattern
Λέξεις κλειδία: Intermediate Representation (IR), Code generation, Structural-IR, linear-IR, Hybrid-IR, High level IR, Abstract syntax tree, Directed Acyclic Graph, Low level IR, abstract instructions, virtual registers, stack machines, lowering the code, linearizing the code, lowering scheme, Generation scheme, short circuit OR, short circuit AND, array access, statements, loops, assignment, l-values, nesting, code quality, leaves
Λέξεις κλειδιά: Optimization, constant propagation, constant folding, partial evaluation, algebraic simplifications, sub-expression elimination, dead code elimination, copy propagation, unreachable code elimination, loop optimization, strength reduction, induction variables, inlining, control flow, flow sensitive, control flow graph (CFG), node, Edge, basic blocks, program points, live variable analysis, liveness, computing liveness, analyzing instructions, liveness across instructions, analyzing control flow, system of equations, generalization, Lattice, confluence operator, Meet-, join-operator, termination, fixpoint, Knaster Tarski theorem
Λέξεις κλειδιά: Bottom up parser, LR-parsing, Right most derivation, shift, reduce, reductions, implications, DFA, closure operation, DFA transitions, shift/reduce conflicts, precedence, LALR(1) DFA, conversion LR(1) to LALR(1) DFA, LALR states
Λέξεις κλειδια: Register allocation, memory hierarchy, registers, graph coloring, K-coloring, optimal coloring, spilling, Chaitin’s algorithm, Chaitin-Briggs-algorithm, Bin packing, linear scan
Λέξεις κλειδιά: Instruction selection, IR, ISA, Tree representation, Tiles, tiling, dynamic programming, recursive algorithm, pseudocode, ad-hoc algorithm, RISC, code generator generators, tree notation, rewriting rules, rewriting process, implementation
Ανοικτό Ακαδ. Μάθημα
![Ανοικτά Ακαδημαϊκά Μαθήματα Ανοικτά Ακαδημαϊκά Μαθήματα](/template/default/img/open_courses_logo_small.png)
Αρ. Επισκέψεων : 0
Αρ. Προβολών : 0
Ημερολόγιο
Ανακοινώσεις
- - Δεν υπάρχουν ανακοινώσεις -