Μεταγλωττιστές
Γλωσσών Προγραμματισμού
ΘΕΩΡΙΑ ΚΑΙ ΠΡΑΞΗ
Κ. ΛΑΖΟΣ
Καθηγητής Τμ. Πληροφορικής
Α.Π.Θ.
Π. ΚΑΤΣΑΡΟΣ
Λέκτορας
Τμ. Πληροφορικής Α.Π.Θ.
Ζ. ΚΑΡΑΪΣΚΟΣ
MSc Πληροφορικής TU Delft Ολλανδίας
Πίνακας Περιεχομένων
Πρόλογος 5
ΚΕΦΑΛΑΙΟ 1: ΒΑΣΙΚΕΣ ΕΙΣΑΓΩΓΙΚΕΣ ΕΝΝΟΙΕΣ 7
1.1 Η δομή του μεταγλωττιστή 8
1.2 Η διαδικασία μεταγλώττισης 9
Η Λεξική Ανάλυση 12
Η Συντακτική Ανάλυση 12
Η Σημασιολογική Ανάλυση 14
Η Βελτιστοποίηση του Πηγαίου Προγράμματος 15
Η Σύνθεση του Τελικού Προγράμματος 16
Η Βελτιστοποίηση του Τελικού Προγράμματος 16
Δομές Δεδομένων 17
1.3 Θέματα που σχετίζονται με τη λειτουργία των μεταγλωττιστών 18
Ο Διερμηνευτής 18
Ο Συμβολομεταφραστής 19
Ο Διασυνδέτης 19
Ο Προεπεξεργαστής 20
Ο Συντάκτης/Διορθωτής 20
Ο Ανιχνευτής Σφαλμάτων 21
Ο Καταγραφέας (profiler) 21
Τα Προγράμματα Διαχείρισης Έργου 21
Προαιρετικές Επιλογές και Μηχανισμοί Διεπαφής 22
1.4 Ανάπτυξη μεταγλωττιστών 22
1.5 Μεταγλωττιστές μεταγλωττιστών 26
1.6 Η υποδειγματική γλώσσα YAPL 26
Ασκήσεις 30
Αναφορές και Σχόλια 30
ΚΕΦΑΛΑΙΟ 2: ΛΕΞΙΚΗ ΑΝΑΛΥΣΗ 31
2.1 Η διαδικασία της λεξικής ανάλυσης 32
2.2 Κανονικές εκφράσεις 35
Ορισμός κανονικών εκφράσεων 35
Κανονικές εκφράσεις για λεξικές μονάδες γλωσσών προγρ/μού 39
2.3 Πεπερασμένα αυτόματα 42
Προσδιοριστικά πεπερασμένα αυτόματα 43
Προσομοίωση πεπερασμένων αυτόματων 46
Μη προσδιοριστικά πεπερασμένα αυτόματα 50
Μετατροπή κανονικών εκφράσεων σε πεπερασμένα αυτόματα 51
Ελαχιστοποίηση προσδιοριστικών πεπερασμένων αυτόματων 56
2.4 Γεννήτριες λεξικών αναλυτών 58
2.5 Η λεξική ανάλυση του μεταγλωττιστή της YAPL 64
Ασκήσεις 71
Αναφορές και Σχόλια 73
ΚΕΦΑΛΑΙΟ 3: ΣΥΝΤΑΚΤΙΚΗ ΑΝΑΛΥΣΗ 75
3.1 Η διαδικασία της συντακτικής ανάλυσης 78
3.2 Γραμματικές και κατηγορίες γραμματικών 79
Κατηγορίες γραμματικών κατά Chomsky 82
Ορισμός γραμματικών 84
3.3 Γραμματικές χωρίς συμφραζόμενα και αυτόματα στοίβας 86
3.4 Συμβολισμοί BNF και EBNF και συντακτικά διαγράμματα 93
3.5 Παράγωγα και συντακτικά δένδρα 98
3.6 Γραμματικές με ασάφειες 103
Προτεραιότητα και προσεταιριστικότητα 106
Το πρόβλημα του μετέωρου else 108
3.7 Η σύνταξη της γλώσσας YAPL σε EBNF 110
3.8 Καθοδική ανάλυση 112
Καθοδική ανάλυση με οπισθοδρόμηση χωρίς περιορισμούς 113
Ανάλυση προβλέπουσας αναδρομικής κατάβασης 116
Καθοδική ανάλυση με περιορισμένη οπισθοδρόμηση 126
Καθοδική ανάλυση LL(1) 131
Απομάκρυνση αριστερής αναδρομικότητας 136
Αριστερή παραγοντοποίηση 139
Ανάνηψη λαθών 142
3.9 Ανοδική ανάλυση 148
Ανάλυση LR 152
Κατασκευή πίνακα μεταβάσεων για τη διενέργεια ανάλυσης LR 159
Ανάλυση LR(0) και SLR(1) 164
Κανονική ανάλυση LR(1) και LALR(1) 168
Διαχείριση λαθών στην ανάλυση LR 177
3.10 Γεννήτριες κώδικα ανάλυσης 179
Διαδικασία παραγωγής κώδικα ανάλυσης από τη γεννήτρια byacc 180
Αρχεία περιγραφής για το byacc 181
Επισκόπηση χώρου καταστάσεων και εντοπισμός συγκρούσεων
ενεργειών ανάλυσης 204
Ανάνηψη συντακτικών λαθών στο byacc 211
3.11 Η συντακτική ανάλυση του μεταγλωττιστή της YAPL 214
Ασκήσεις 233
Αναφορές και Σχόλια 235
ΚΕΦΑΛΑΙΟ 4 : ΣΗΜΑΣΙΟΛΟΓΙΚΗ ΑΝΑΛΥΣΗ 237
4.1 Ιδιότητες και γραμματικές ιδιοτήτων 240
4.2 Πίνακας συμβόλων 245
Ο πίνακας συμβόλων του μεταγλωττιστή της YAPL 247
4.3 Έλεγχοι τύπων 250
Ασκήσεις 252
ΚΕΦΑΛΑΙΟ 5: ΕΝΔΙΑΜΕΣΗ ΑΝΑΠΑΡΑΣΤΑΣΗ ΚΑΙ
ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ 253
5.1 Το συντακτικό δένδρο του μεταγλωττιστή της YAPL 255
5.2 Κώδικας τριών διευθύνσεων 257
5.3 Βελτιστοποίηση κώδικα μη εξαρτώμενη από τη μηχανή εκτέλεσης 262
Βελτιστοποιητικοί μετασχηματισμοί 262
Ασκήσεις 269
ΚΕΦΑΛΑΙΟ 6: ΑΠΕΙΚΟΝΙΣΗ ΤΥΠΩΝ ΚΑΙ ΔΕΔΟΜΕΝΩΝ ΣΤΗ
ΜΝΗΜΗ 271
6.1 Bασικοί τύποι 273
6.1.1 Ο τύπος των ακεραίων αριθμών 273
Δήλωση 274
Εντολές 275
6.1.2 Ο τύπος των πραγματικών αριθμών 275
Δήλωση 277
Εντολές 278
6.1.3 Ο τύπος των λογικών τιμών 278
Εντολές 278
6.1.4 Ο τύπος των χαρακτήρων 279
Δήλωση 279
6.2 Δομημένοι τύποι 279
6.2.1 Πίνακες 281
Δήλωση μονοδιάστατου πίνακα 282
Προσπέλαση μονοδιάστατου πίνακα 283
Πίνακες πολλών διαστάσεων 285
Κατάταξη με πρώτη τη γραμμή 286
Κατάταξη με πρώτη τη στήλη 288
Δήλωση πίνακα πολλών διαστάσεων 289
Προσπέλαση πίνακα πολλών διαστάσεων 290
Δυναμικοί πίνακες 294
Υλοποίηση πινάκων με διανύσματα δεικτών 297
6.2.2 Εγγραφές 298
Δήλωση εγγραφής 299
Προσπέλαση εγγραφής 299
6.2.3 Περίπλοκες δομές 301
6.3 Τύποι προσπέλασης 305
ΚΕΦΑΛΑΙΟ 7: ΠΕΡΙΒΑΛΛΟΝ ΕΚΤΕΛΕΣΗΣ 309
7.1 Οργάνωση της μνήμης κατά την εκτέλεση προγράμματος 310
7.2 Κλήση υποπρογραμμάτων 314
7.3 Αποθήκευση των καταχωρητών 318
7.4 Τοπικές μεταβλητές 321
7.5 Παράμετροι 328
7.5.1 Τρόποι περάσματος παραμέτρων 329
7.5.2 Πέρασμα παραμέτρων μέσω στοίβας 330
Το πέρασμα αναφοράς 332
Το πέρασμα τιμής-αποτελέσματος 334
Το πέρασμα αποτελέσματος 336
Το πέρασμα ονόματος 337
Άλλοι μεταφραστές 339
7.5.3 Προσπέλαση μη-τοπικών μεταβλητών 347
Στατικοί δείκτες 347
Προσπέλαση μη-τοπικών μεταβλητών 355
ΚΕΦΑΛΑΙΟ 8: ΔΗΜΙΟΥΡΓΙΑ ΚΩΔΙΚΑ ΜΗΧΑΝΗΣ 359
8.1 Δημιουργία κώδικα μηχανής 360
8.1.1 Δημιουργία κώδικα για αριθμητικές παραστάσεις 363
8.1.2 Δημιουργία κώδικα για εκχώρηση τιμής 371
8.1.3 Δημιουργία κώδικα για λογικές παραστάσεις 374
8.2 Βελτιστοποίηση του κώδικα μηχανής 378
8.3 Άλλοι μεταφραστές 380
ΠΑΡΑΡΤΗΜΑ Α 399
Αρχείο κεφαλίδας με δηλώσεις για το μεταγλωττιστή της YAPL (defs.h) 399
Αρχείο κεφαλίδας με δηλώσεις προτύπων συναρτήσεων (protypes.h) 401
Βοηθητικές συναρτήσεις για το μεταγλωττιστή της YAPL (syd2) 403
ΠΑΡΑΡΤΗΜΑ Β 425
Σύνθεση κώδικα-στόχο του μεταγλωττιστή της YAPL (syd3.c) 425
Βελτιστοποίηση κώδικα για το μεταγλωττιστή της YAPL (optim1) 460
Βελτιστοποίηση κώδικα για το μεταγλωττιστή της YAPL (optim2) 461
Βελτιστοποίηση κώδικα για το μεταγλωττιστή της YAPL (optim3) 463
ΠΑΡΑΡΤΗΜΑ Γ: ΑΡΧΙΤΕΚΤΟΝΙΚΗ ΤΟΥ ΕΠΕΞΕΡΓΑΣΤΗ PENTIUM 471
Γ.1 Οι καταχωρητές της κεντρικής μονάδας επεξεργασίας 472
Γ.2 Διεύθυνση δεδομένων 476
Γ.2.1 Το δεδομένο περιέχεται σε καταχωρητή (register operand) 476
Γ.2.2 Το δεδομένο περιέχεται στην εντολή (immediate operand) 476
Γ.2.3 Το δεδομένο είναι αποθηκευμένο στη μνήμη 477
Γ.3 Εντολές 483
Γ.3.1 Εντολές αριθμητικών πράξεων 484
Γ.3.2 Εκχώρηση τιμής με την εντολή MOV 487
Γ.3.3 Λογικές πράξεις 488
Γ.3.4 Σύγκριση και άλματα 489
Γ.3.5 Κλήση υποπρογράμματος και επιστροφή 493
Γ.4 Διαχείριση στοίβας 495
ΒΙΒΛΙΟΓΡΑΦΙΑ - ΑΝΑΦΟΡΕΣ 497
ΠΙΝΑΚΑΣ ΠΕΡΙΕΧΟΜΕΝΩΝ 499
 |