Το χάσμα υλικού και λογισμικού
Οι δυνατότητες που προσφέρει το υλικό και το λογισμικό έρχονται συχνά
σε αντίθεση ή αλληλοσυμπληρώνονται.
- ευκαμψία (flexibility)
Το λογισμικό είναι πιο εύκαμπτο και εύπλαστο από το υλικό.
- απόδοση (performance)
Ένας αλγόριθμος υλοποιημένος σε υλικό μπορεί να είναι ταχύτερος από τον
αντίστοιχο υλοποιημένο σε λογισμικό.
- κόστος (cost)
Το οριακό κόστος αναπαραγωγής του λογισμικού είναι, σε αντίθεση με αυτό του
υλικού, μηδενικό.
Από την άλλη πλευρά σε διαμορφωμένα εμπορικά συστήματα το κόστος του
λογισμικού μπορεί να υπερβαίνει αυτό του υλικού.
Οι γλώσσες προγραμματισμού και τα λειτουργικά συστήματα είναι δύο τεχνολογίες
που επιτρέπουν τη βέλτιστη συνύπαρξη του υλικού με το λογισμικό.
Υλοποίηση γλωσσών προγραμματισμού
Μια γλώσσα προγραμματισμού μπορεί - ανάλογα με τη γλώσσα -
να υλοποιηθεί με τους παρακάτω τρόπους:
- από υλικό
(π.χ. επεξεργαστές που προγραμματίζονται κατευθείαν στη γλώσσα FORTH)
- με ένα συμβολομεταφραστή (assembler)
(προγραμματισμός σε συμβολικές γλώσσες)
- με ένα διερμηνευτή (interpreter)
(π.χ. Python, JavaScript, Ruby, Lisp, Haskell, PHP, bash)
- με ένα μεταγλωττιστή (compiler)
(π.χ. C, C++, Java, C#, Go, Rust, Fortran)
καθώς και με συνδυασμούς τους.
Αρχιτεκτονική του μεταγλωττιστή
Η διεργασία της μεταγλώττισης μπορεί να διαχωριστεί στις παρακάτω
ξεχωριστές λειτουργίες οι οποίες εκτελούνται σε διαδοχικές φάσεις:
- λεκτική ανάλυση (lexical analysis)
- συντακτική ανάλυση (syntax analysis)
- σημασιολογική ανάλυση (semantic analysis)
- παραγωγή ενδιάμεσου κώδικα (intermediate code generation)
- βελτιστοποίηση κώδικα (code optimisation)
- παραγωγή τελικού κώδικα (target code generation)
Λεκτική ανάλυση
Ο λεκτικός αναλυτής παρέχει τις παρακάτω λειτουργίες:
- Διαχωρίζει το εισερχόμενο κείμενο σε
λεκτικές μονάδες (tokens) και το μεταφέρει
με τον τρόπο αυτό στο συντακτικό αναλυτή.
- Αποθηκεύει τα σύμβολα που διαβάζει σε πίνακα συμβόλων.
- Αποθηκεύει άλλα στοιχεία όπως τις συμβολοσειρές.
- Αναγνωρίζει λεκτικά λάθη στην είσοδο (π.χ. σύμβολα που δεν
επιτρέπονται στη γλώσσα).
- Αφαιρεί τα σχόλια
- Συσχετίζει αριθμούς γραμμών με στοιχεία της εισόδου του.
Με τον τρόπο αυτό διαχωρίζονται οι εργασίες της λεκτικής και της
συντακτικής ανάλυσης και κάθε μια υλοποιείται με τον πιο αποδοτικό τρόπο.
Λεκτικές μονάδες
- Τα στοιχεία μιας γλώσσας χωρίζονται σε λεκτικές μονάδες.
- Τυπικές λεκτικές μονάδες που ορίζονται είναι:
- Οι δεσμευμένες λέξεις (reserved words)
- Τα ονόματα (identifiers)
- Οι σταθερές (constants)
- Οι τελεστές (operators)
- Οι διαχωριστές (delimiters)
Χρήση λεκτικών μονάδων
- Κάθε λεκτική μονάδα συσχετίζεται από το λεκτικό αναλυτή με τον τύπο
της (π.χ. ακέραια σταθερά) και την τιμή της (π.χ. 42).
- Μη προκαθορισμένες λεκτικές μονάδες
(που δεν είναι δεσμευμένες λέξεις της γλώσσας)
αποθηκεύονται σε πίνακα συμβόλων.
- Οι δεσμευμένες λέξεις τυπικά διαχωρίζονται μεταξύ τους κατά το στάδιο της
λεκτικής ανάλυσης.
- Συχνά η αναγνώριση των δεσμευμένων λέξεων γίνεται με τη χρήση
συναρτήσεων κατακερματισμού.
Ο συντακτικός αναλυτής
Ο συντακτικός αναλυτής:
- υλοποιεί τη συντακτική ανάλυση μιας συγκεκριμένης γλώσσας,
- δέχεται ως είσοδο ένα πρόγραμμα με τη μορφή ακολουθίας λεκτικών
μονάδων,
- ελέγχει αν το πρόγραμμα είναι σύμφωνο με τη γραμματική
της γλώσσας που υλοποιεί (αν ανήκει στη συγκεκριμένη γλώσσα),
- σε περίπτωση συντακτικού λάθους ενημερώνει το χρήστη,
- παράγει το συντακτικό δένδρο που αντιστοιχεί στην ακολουθία εισόδου.
Παράδειγμα
i = 0;
while ( i < 10) {
System.out.println(i);
i = i + 1;
}
(Το δέντρο μπορεί να κατασκευαστεί και ζωντανά από 17 άτομα.)
Συντακτικό δένδρο
Παραγωγή κώδικα
Η παραγωγή κώδικα αποτελεί το πιο ενδιαφέρον και σύνθετο στάδιο της
μεταγλώττισης.
Κατά το στάδιο αυτό μπορούν να υλοποιηθούν τεχνικές βελτιστοποίησης
προσανατολισμένες στη συγκεκριμένη γλώσσα ή αρχιτεκτονική και να
υλοποιηθούν αλγόριθμοι βέλτιστης χρήσης των στοιχείων της αρχιτεκτονικής.
Η παραγωγή του τελικού εκτελέσιμου
κώδικα μπορεί να διακριθεί στα παρακάτω στάδια:
- παραγωγή ενδιάμεσου κώδικα (intermediate code)
- βελτιστοποίηση του ενδιάμεσου κώδικα
- παραγωγή τελικού κώδικα
- βελτιστοποίηση του τελικού κώδικα
- σύνδεση (linking)
Βελτιστοποίηση του ενδιάμεσου κώδικα
Η βελτιστοποίηση του κώδικα μετασχηματίζει τον κώδικα σε μια μορφή που
παράγει τα ίδια αποτελέσματα με τον αρχικά αλλά βελτιωμένα κάποια
κριτήρια απόδοσης.
Τέτοια κριτήρια μπορεί να είναι:
- η ταχύτητα εκτέλεσης του προγράμματος (συχνότερα)
- η μνήμη που καταλαμβάνει το πρόγραμμα (π.χ. όταν το πρόγραμμα
πρέπει να εκτελεστεί σε ενσωματωμένες (embeded)
συσκευές με περιορισμένη μνήμη),
- η ενέργεια που καταναλώνει το πρόγραμμα (π.χ. όταν το
πρόγραμμα θα εκτελεστεί σε φορητές συσκευές με μπαταρίες),
- η δυνατότητα εκμετάλλευσης της αρχιτεκτονικής του τελικού
επεξεργαστή (π.χ. καταχωρητών, πολλαπλών υπολογιστικών στοιχείων).
Πλεονεκτήματα βελτιστοποίησης
Η βελτιστοποίηση μπορεί να απαλλάξει τον προγραμματιστή από
αντιπαραγωγικές αλλαγές του κώδικα που έχουν ως στόχο να
ικανοποιήσουν τα κριτήρια αυτά και να του επιτρέψει να
συγκεντρωθεί σε άλλα ποιοτικά στοιχεία του παραγόμενου
κώδικα όπως την ορθότητα, την ασφάλεια, τη διαθεσιμότητα,
τη συντηρησιμότητα, και τη μεταφερσιμότητα.
Συχνά βελτιστοποιήσεις που γίνονται από τον προγραμματιστή
έρχονται σε αντίθεση με τα παραπάνω ποιοτικά στοιχεία.
Παράδειγμα βελτιστοποίησης
- Απαλοιφή κοινών υποεκφράσεων (common subexpression elimination)
- Εκφράσεις με κοινά στοιχεία υπολογίζονται
μόνο μια φορά.
Η ακολουθία:
x = b / c;
y = 42 + b / c;
μετασχηματίζεται στην ακολουθία:
Παράδειγμα βελτιστοποίησης
- Μετακίνηση κώδικα βρόχων (loop code motion)
-
Εκφράσεις που δεν αλλάζουν μέσα σε ένα βρόχο μετακινούνται έξω από αυτόν.
Η ακολουθία:
{
int a, b, z;
a = 8; b = 4;
for (i = 0; i < 10; i++) {
z = a / b;
System.out.println(z);
}
}
μετασχηματίζεται στην ακολουθία:
{
int a, b, z;
a = 8; b = 4;
z = a / b;
for (i = 0; i < 10; i++) {
System.out.println(z);
}
}
Παράδειγμα βελτιστοποίησης
- Απαλοιφή άχρηστου κώδικα (dead code removal)
-
Κώδικας που δεν εκτελείται ποτέ απαλείφεται.
Η ακολουθία:
{
int a, q;
q = 48;
return (q);
a = q / 2;
}
μετασχηματίζεται στην ακολουθία:
{
int a, q;
q = 48;
return (q);
}
Παράδειγμα βελτιστοποίησης
- Απαλοιφή κλήσεων σε συναρτήσεις (function inlining)
-
Κλήσεις σε συναρτήσεις μετασχηματίζονται σε απευθείας χρήση του αντίστοιχου
κώδικα.
Η ακολουθία:
static int
square(int a) {
return (a * a);
}
public static void main(String args[]) {
System.out.println(square(12));
}
μετασχηματίζεται στην ακολουθία:
public static void main(String args[]) {
System.out.println(12 * 12);
}
Παράδειγμα βελτιστοποίησης
- Απαλοιφή αναδρομής από το τέλος συνάρτησης (tail recursion elimination)
-
Αναδρομή στο τέλος μιας συνάρτησης μετασχηματίζεται σε βρόχο.
Η ακολουθία:
foo() {
System.out.println("foo");
foo();
}
μετασχηματίζεται στην ακολουθία:
foo() {
for (;;)
System.out.println("foo");
}
Βελτιστοποίηση του τελικού κώδικα
Συχνά ο τελικός κώδικας που παράγεται μπορεί να περιέχει ακολουθίες
εντολών
οι οποίες να μπορούν να βελτιστοποιηθούν για το συγκεκριμένο επεξεργαστή.
Οι ακολουθίες αυτές μπορούν να βρεθούν εξετάζοντας ένα μικρό παράθυρο
του τελικού κώδικα, όπως αυτό θα φαίνονταν κοιτάζοντας τον
κώδικα από μια κλειδαρότρυπα.
Για το λόγο αυτό οι βελτιστοποιήσεις αυτές λέγονται και
βελτιστοποιήσεις κλειδαρότρυπας (peephole optimizations).
Παράδειγμα βελτιστοποίησης τελικού κώδικα
Η ακολουθία:
mov $12, %rax
mov %rax, %rbx
mov $20, %rax
μετασχηματίζεται στην ακολουθία:
mov $12, %rbx
mov $20, %rax
Επίσης η διάταξη των εντολών μπορεί να βελτιωθεί για να γίνεται
καλύτερη χρήση πολλαπλών υπολογιστικών στοιχείων που διαθέτει ο
επεξεργαστής.
Για παράδειγμα σε ορισμένους επεξεργαστές η εναλλαγή εντολών κινητής
υποδιαστολής με εντολές ακεραίων επιτρέπει στις δύο λειτουργικές
μονάδες να δουλεύουν παράλληλα.
Σύνδεση
Κατά τη σύνδεση τα ανεξάρτητα μεταγλωττισμένα τμήματα του προγράμματος
συνδέονται μεταξύ τους και με τις βιβλιοθήκες της γλώσσας για να
δημιουργηθεί το τελικό εκτελέσιμο πρόγραμμα.
Συχνά οι βιβλιοθήκες που χρησιμοποιούνται είναι κοινές ανάμεσα σε
προγράμματα και φορτώνονται δυναμικά κατά το στάδιο εκτέλεσης του
προγράμματος (Unix shared libraries, Windows DLLs).
Κατά τη φάση της σύνδεσης γίνεται έλεγχος πως όλες οι συναρτήσεις
και μεταβλητές που χρησιμοποιούνται έχουν οριστεί και, για ορισμένες
γλώσσες όπως η C++, πως οι τύποι των συμβόλων που έχουν οριστεί σε
διαφορετικά αρχεία είναι συμβατοί μεταξύ τους.
Ορισμένες γλώσσες όπως η Java υλοποιούν μεγάλο μέρος της σύνδεσης κατά
τη φόρτωση του προγράμματος στη μνήμη για εκτέλεση.
Ιδεατές μηχανές
Μια
ιδεατή μηχανή (virtual machine)
εμφανίζει στο λογισμικό που τρέχει πάνω σε αυτήν
μια διαφορετική διεπαφή από αυτή στην οποία βασίζεται η μηχανή
για την υλοποίησή της.
- Ο
μικροκώδικας (microcode)
στο εσωτερικό του επεξεργαστή επιτρέπει στο υλικό του να
εκτελεί σύνθετες εντολές.
- Το λειτουργικό σύστημα εμφανίζει τους υλικούς φορείς αποθήκευσης
ως ένα ιδεατό σύστημα φύλαξης αρχείων.
- Εξειδικευμένο υλικό και λογισμικό παρέχει σε κάθε διεργασία
του συστήματος πλήρη χρήση μιας μεγάλης περιοχής ιδεατής μνήμης.
- Η ιδεατή μηχανή της Java επιτρέπει στον ίδιο κώδικα να εκτελείται
με ασφάλεια σε διαφορετικά υπολογιστικά περιβάλλοντα.
Συχνά οι ιδεατές μηχανές υλοποιούνται σε ιεραρχία.
Πλεονεκτήματα και προβλήματα ιδεατών μηχανών
- + Μεταφερσιμότητα
- + Ευελιξία διαχείρισης
- + Υλοποίηση πολιτικών ασφαλείας
- Σύστημα αρχείων
- Προστασία μνήμης
- Πόροι της μηχανής της Java
- - Απόδοση
- - Περιπλοκότητα
Διαχείριση μνήμης
Κατά τη διάρκεια ζωής του προγράμματος υπάρχουν απαιτήσεις για
τη φύλαξη δεδομένων με διαφορετική διάρκεια ζωής.
Συγκεκριμένα, πρέπει να υπάρχει υποστήριξη για
δεδομένα που διατηρούνται:
- σε όλη τη διάρκεια ζωής του προγράμματος
(π.χ. μεταβλητές με τον προσδιοριστή static)
- όσο εκτελείται μια
ενότητα (block)
του προγράμματος
(π.χ. μεταβλητές τοπικές σε ενότητες)
- για συγκεκριμένο πεπερασμένο χρονικό διάστημα με τυχαία αρχή και τέλος
(π.χ. αντικείμενα της Java)
Παράδειγμα διάταξης μνήμης
Στοίβα (stack) ...
...
Σωρός (heap) (Δυναμική μνήμη) |
... Στατικά δεδομένα (static data) |
... Μεταγλωττισμένος κώδικας (code (text)) |
Τρόποι διαχείρισης μνήμης
Όταν ο όγκος της κύριας μνήμης του υπολογιστή δεν επαρκεί
μπορεί να χρησιμοποιηθεί:
- ιδεατή μνήμη (virtual memory)
σε δευτερεύουσα αποθήκευση (secondary storage)
- εξωτερικό αρχείο υπό τον έλεγχο του προγράμματος
- βάση δεδομένων
Τέλος, για οικονομία στο χώρο που απαιτεί ο κώδικας των προγραμμάτων
σε δευτερεύουσα αποθήκευση, χρησιμοποιούνται συχνά
μοιρασμένες βιβλιοθήκες (shared libraries)
(π.χ. .DLL, .so).
Άσκηση: ορίσματα, εκφράσεις, βρόχοι και αποφάσεις
Άσκηση 2
Μπορείτε να κατεβάσετε το αντίστοιχο αρχείο και να στείλετε τους
βαθμούς σας από τους δεσμούς που βρίσκονται στη
σελίδα των ασκήσεων.
Βιβλιογραφία
- Rogers CadenheadΠλήρες εγχειρίδιο της Java 12Όγδοη έκδοση. Εκδόσεις Μ. Γκιούρδας, Αθήνα 2023. Κεφ. 1, 2.
- Herbert Schildt. Οδηγός της Java 7. 5η έκδοση. Εκδόσεις Γκιούρδας Μ., Αθήνα 2012. Κεφ. 1.
- Harvey M. Deitel και Paul J. Deitel. Java Προγραμματισμός, 6η έκδοση. Εκδόσεις Μ. Γκιούρδας, Αθήνα 2005. Κεφάλαιο 1.
- Εμμ. Σ. Σκορδαλάκης.
Εισαγωγή στους Μεταγλωττιστές.
Συμμετρία 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.
- Andrew W. Appel and Maia
Ginsburg.
Modern Compiler Implementation in C.
Cambridge University Press, 1998.
- Andrew W. Appel.
Simple generational garbage collection and fast allocation.
Software: Practice and Experience, 19(2):171–183, February
1989.
- Hans-Juergen
Boehm.
Garbage collection in an uncooperative environment.
Software: Practice and Experience, 18(9):807–820, September
1988.
- Keith Clarke.
One-pass code generation using continuations.
Software: Practice and Experience, 19(12):1175–1192, December
1989.
- Jack W. Davidson and David B.
Whalley.
Quick compilers using peephole optimization.
Software: Practice and Experience, 19(1):79–97, January
1989.
- John M. Dedourek, Uday G.
Gujar, and Marion E. McIntyre.
Scanner design.
Software: Practice and 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.
- James
Gosling, Bill Joy, Guy Steele, and
Gilad Bracha.
The Java Language Specification.
Addison-Wesley, third edition, 2005.
- BNF
index of the Java language grammar.
Available online:
http://cui.unige.ch/db-research/Enseignement/analyseinfo/JAVA/ (http://cui.unige.ch/db-research/Enseignement/analyseinfo/JAVA/).
- 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.
In UNIX Programmer's Manual. Volume 2 — Supplementary
Documents. Bell Telephone Laboratories, Murray Hill, NJ, USA (also
available online http://plan9.bell-labs.com/7thEdMan/), seventh edition,
1979.
- The Java language
specification, Java SE 7 edition.
Available online: http://docs.oracle.com/javase/specs/ (http://docs.oracle.com/javase/specs/).
- 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 and Experience, 19(12):1151–1162, December
1989.
- Frank G. Pagan.
Converting interpreters into compilers.
Software: Practice and 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. Bell Telephone Laboratories, Murray Hill, NJ, USA (also
available online http://plan9.bell-labs.com/7thEdMan/), seventh edition,
1979.
- 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 and Experience, 10:97–125, 1980.
Περιεχόμενα