Μεταγλωττιστές Γλωσσών Προγραμματισμού

ΘΕΩΡΙΑ ΚΑΙ ΠΡΑΞΗ

Κ. ΛΑΖΟΣ
Καθηγητής Τμ. Πληροφορικής Α.Π.Θ.

Π. ΚΑΤΣΑΡΟΣ
Λέκτορας Τμ. Πληροφορικής Α.Π.Θ.

Ζ. ΚΑΡΑΪΣΚΟΣ
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