Εισαγωγή

Καλώς ήρθατε

Υλικό και Λογισμικό Ι

• Τμήμα Πληροφοριακών και Επικοινωνιακών συστημάτων
• Πανεπιστήμιο του Αιγαίου (http://www.aegean.gr)
• Διομήδης Σπινέλλης <dspin@aegean.gr (mailto:dspin@aegean.gr)>
• Η σχέση του υλικού με το λογισμικό
• Προγραμματισμός σε επίπεδο μηχανής
• Μεταγλωττιστές
• Διερμηνευτές
• Θεωρία και ασκήσεις:
  • Τρίτη 16:00-18:00
  • Τετάρτη 09:00-11:00
• Εργαστήρια:
  • Δευτέρα 16:00-18:00
  • Πέμπτη 16:00-18:00
  • Υπεύθυνος: Π. Τσόπελας pts@aegean.gr (mailto:pts@aegean.gr)
• Ώρες γραφείου:
  • Τρίτη 10:00-11:00
  • (στείλτε email μέχρι τις 09:00 της ίδιας μέρας)

Τι περιλαμβάνει το μάθημα

1. Εισαγωγή
2. Προγραμματισμός σε επίπεδο μηχανής
3. Αυτόματα
4. Γραμματικές
5. Λεκτική ανάλυση
6. Το μεταεργαλείο lex
7. Συντακτική ανάλυση
8. Το μεταεργαλείο yacc
9. Πίνακες συμβόλων
10. Διερμηνευτές
11. Σημασιολογική ανάλυση
12. Παραγωγή ενδιάμεσου κώδικα
13. Βελτιστοποίηση κώδικα
14. Παραγωγή τελικού κώδικα

Οι σημειώσεις

• Δε θα μοιράζονται
• Βασίζονται στο βιβλίο
  • Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές. Συμμετρία 1993.

• Προσβάσιμες από το WWW:http://kerkis.math.aegean.gr/~dspin/comp (http://kerkis.math.aegean.gr/~dspin/comp)
• Δεν καλύπτουν όλο το μάθημα
• Πρόσθετες σημειώσεις:
  • ΕΜΠ: Καλωσήρθατε στους Μεταγλωττιστές On-Line http://webct.softlab.ntua.gr/SCRIPT/compilers/scripts/serve_home (http://guest:guest@webct.softlab.ntua.gr/SCRIPT/compilers/scripts/serve_home)
  • Πανεπιστήμιο Κρήτης: Τμήμα Επιστήμης Υπολογιστών: Γλώσσες και Μεταφράστες (ΗΥ 340) http://www.csd.uch.gr/~hy340/hy340.html (http://www.csd.uch.gr/~hy340/hy340.html)

Το χάσμα υλικού και λογισμικού

• ευκαμψία (flexibility) Το λογισμικό είναι πιο εύκαμπτο και εύπλαστο από το υλικό.
• απόδοση (performance) Ένας αλγόριθμος υλοποιημένος σε υλικό μπορεί να είναι ταχύτερος από τον αντίστοιχο υλοποιημένο σε λογισμικό.
• κόστος (cost) Το οριακό κόστος αναπαραγωγής του λογισμικού είναι, σε αντίθεση με αυτό του υλικού, μηδενικό. Από την άλλη πλευρά σε διαμορφωμένα εμπορικά συστήματα το κόστος του λογισμικού μπορεί να υπερβαίνει αυτό του υλικού.

Υλοποίηση γλωσσών προγραμματισμού

• από υλικό (π.χ. επεξεργαστές που προγραμματίζονται κατευθείαν στη γλώσσα FORTH)
• με ένα συμβολομεταφραστή (assembler) (προγραμματισμός σε συμβολικές γλώσσες)
• με ένα διερμηνευτή (interpreter) (συνήθως σε συνδυασμό με κάποια στάδια μεταγλώττισης για γλώσσες πολύ υψηλού επιπέδου όπως Prolog, Lisp, Haskell, ML, Basic, Perl, Python, TCL, sh, csh, awk)
• με ένα μεταγλωττιστή (compiler) (τυπικά για γλώσσες τρίτης γενιάς όπως Pascal, FORTRAN, Ada, C, C++)

Ο ορισμός ενός μεταγλωττιστή

• την αρχική γλώσσα (Α)
• την τελική γλώσσα (Τ)
• τη γλώσσα υλοποίησης (Υ)

Ο ίδιος συνδυασμός για ένα μεταγλωττιστή Μ συμβολίζεται και ως M^AT_Y.

Τελικός κώδικας

• συμβολική γλώσσα ενός συγκεκριμένου επεξεργαστή
• γλώσσα μηχανής ενός συγκεκριμένου επεξεργαστή
• γλώσσα μιας ιδεατής μηχανής (virtual machine)
• μια άλλη γλώσσα χαμηλότερου επιπέδου (π.χ. C για ένα μεταγλωττιστή C++)
• μια δομή δεδομένων η οποία θα εκτελεστεί από ένα διερμηνευτή

Παραδείγματα

Συμβολική γλώσσα Linux Intel 386

Γλώσσα μηχανής από δυαδικό αρχείο Linux Intel 386 σε μορφή δεκαεξαδική και ASCII

hello.o:     file format elf32-i386

Contents of section .text:
 0000 5589e568 00000000 e8fcffff ff83c404  U..h............
 0010 c9c3                                 ..              
Contents of section .data:
Contents of section .note:
 0000 08000000 00000000 01000000 30312e30  ............01.0
 0010 31000000                             1...            
Contents of section .rodata:
 0000 68656c6c 6f2c2077 6f726c64 0a00      hello, world..  
Contents of section .comment:
 0000 00474343 3a202847 4e552920 65676373  .GCC: (GNU) egcs
 0010 2d322e39 312e3636 20313939 39303331  -2.91.66 1999031
 0020 342f4c69 6e757820 28656763 732d312e  4/Linux (egcs-1.
 0030 312e3220 72656c65 61736529 00        1.2 release).   

Συμβολική γλώσσα της ιδεατής μηχανής Java Virtual Machine

Compiled from hello.java
class hello extends java.lang.Object {
    hello();
    public static void main(java.lang.String[]);
}

Method hello()
   0 aload_0
   1 invokespecial #9 <Method java.lang.Object()>
   4 return

Method void main(java.lang.String[])
   0 getstatic #12 <Field java.io.PrintStream out>
   3 ldc #2 <String "Hello ">
   5 invokevirtual #13 <Method void print(java.lang.String)>
   8 getstatic #12 <Field java.io.PrintStream out>
  11 new #7 <Class java.lang.StringBuffer>
  14 dup
  15 aload_0
  16 iconst_0
  17 aaload
  18 invokestatic #16 <Method java.lang.String valueOf(java.lang.Object)>
  21 invokespecial #10 <Method java.lang.StringBuffer(java.lang.String)>
  24 ldc #1 <String " ">
  26 invokevirtual #11 <Method java.lang.StringBuffer append(java.lang.String)>
  29 aload_0
  30 iconst_1
  31 aaload
  32 invokevirtual #11 <Method java.lang.StringBuffer append(java.lang.String)>
  35 invokevirtual #15 <Method java.lang.String toString()>
  38 invokevirtual #14 <Method void println(java.lang.String)>
  41 return

Απαιτήσεις

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

Σχεδίαση

• λεκτική ανάλυση (lexical analysis)
• συντακτική ανάλυση (syntax analysis)
• σημασιολογική ανάλυση (semantic analysis)
• παραγωγή ενδιάμεσου κώδικα (intermediate code generation)
• βελτιστοποίηση κώδικα (code optimisation)
• παραγωγή τελικού κώδικα (target code generation)

• διαχείριση πίνακα συμβόλων (symbol table management)
• διαχείριση λαθών (error management)

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

• Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 1-13. Συμμετρία 1993.

• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 1–24. Addison-Wesley, 1985.

Γενική βιβλιογραφία

• Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές. Συμμετρία 1993.

• Harold Abelson, Gerald Jay Sussman, and Jullie Sussman. Structure and Interpretation of Computer Programs. MIT Press, 1990.
• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools. Addison-Wesley, 1985.
• Keith Clarke. One-pass code generation using continuations. Software: Practice & Experience, 19(12):1175–1192, December 1989.
• Jack W. Davidson and David B. Whalley. Quick compilers using peephole optimization. Software: Practice & Experience, 19(1):79–97, January 1989.
• John M. Dedourek, Uday G. Gujar, and Marion E. McIntyre. Scanner design. Software: Practice & Experience, 10:959–972, 1980.
• H. Dobler and K. Pirklbauer. Coco-2: A new compiler compiler. ACM SIGPLAN Notices, 25(5):82–90, May 1990.
• Charles N. Fischer and Richard J. Jr. Leblanc. Crafting a Compiler With C. Addison-Wesley, 1991.
• Robert W. Gray, Vincent P. Heuring, Steven P. Levi, Anthony M. Sloane, and William M. Waite. Eli: A complete, flexible compiler construction system. Communications of the ACM, 35(2):121–131, February 1992.
• J. Grosch and H. Emmelmann. A tool box for compiler construction. In D. Hammer, editor, Compiler Compilers : Third International Workshop, CC '90, pages 106–116, Schwerin, Germany, October 1991. Springer-Verlag. Lecture Notes in Computer Science 477.
• J. Grosh. Ast — a generator for abstract syntax trees. Compiler Generation Report 15, GMD Forshungsstelle an der Universität Karlsruhe, Germany, August 1989. (Revised Version).
• Stephen C. Johnson. Yacc — yet another compiler-compiler. Computer Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, USA, July 1975.
• Stephen C. Johnson. A tour through the portable C compiler. Bell Telephone Laboratories, Murray Hill, NJ, USA (also available online http://plan9.bell-labs.com/7thEdMan/), seventh edition, 1979.
• Brian W. Kernighan and Rob Pike. The UNIX Programming Environment. Prentice-Hall, 1984.
• Michael E. Lesk. Lex — a lexical analyzer generator. Computer Science Technical Report 39, Bell Laboratories, Murray Hill, NJ, USA, October 1975.
• B. J. McKenzie. Fast peephole optimization techniques. Software: Practice & Experience, 19(12):1151–1162, December 1989.
• Frank G. Pagan. Converting interpreters into compilers. Software: Practice & Experience, 18(6):509–527, June 1988.
• Dennis M. Ritchie. A tour through the UNIX C compiler. In UNIX Programmer's Manual. Volume 2 — Supplementary Documents.
• Peter H. Salus, editor. Handbook of Programming Languages, volume III: Little Languages and Tools. Macmillan Technical Publishing, 1998.
• Ravi Sethi. Programming Languages: Convepts and Constructs. Addison-Wesley, 1989.
• Andrew S. Tanenbaum, M. Frans Kaashoek, Koen G. Langendoen, and Ceriel J. H. Jacobs. The design of very fast portable compilers. ACM SIGPLAN Notices, 24(11):125–131, November 1989.
• Ken Thompson. A new C compiler. In Proceedings of the Summer 1990 UKUUG Conference, pages 41–51, London, UK, July 1990. UKUUG.
• David H. D. Warren. Logic programming and compiler writing. Software: Practice & Experience, 10:97–125, 1980.

Ασκήσεις

Άσκηση 1 (προαιρετική)

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

   Παράδειγμα:

   Η υλοποίηση μιας γλώσσας με μεταγλωττιστή επηρεάζει ... την αποδοτικότητα του παραγώμενου κώδικα σε ταχύτητα διότι ...

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:27 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».