Περιεχόμενα

(Σε εκτυπώσιμη μορφή: PS, PDF.)


Πρόλογος					iii

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

1	Εισαγωγή				1
	1.1	Γλώσσες προγραμματισμού			1
	1.2	Μεταγλωττιστές			2
	1.3	Αναγκαιότητα και ιστορική αναδρομή			4
	1.4	Είδη μεταγλωττιστών και συναφή εργαλεία			5
	1.5	Κατασκευή ενός μεταγλωττιστή			10
		1.5.1	Ορισμός του προβλήματος		10
		1.5.2	Απαιτήσεις		10
		1.5.3	Φάσεις της μεταγλώττισης		12
			1.5.3.1	Λεκτική ανάλυση	14
			1.5.3.2	Συντακτική ανάλυση	14
			1.5.3.3	Σημασιολογική ανάλυση	14
			1.5.3.4	Παραγωγή ενδιάμεσου κώδικα	15
			1.5.3.5	Βελτιστοποίηση	16
			1.5.3.6	Παραγωγή τελικού κώδικα	16
		1.5.4	Επιλογές κατά την υλοποίηση		16
			1.5.4.1	Οργάνωση σε περάσματα	17
			1.5.4.2	Οργάνωση σε εμπρόσθιο και οπίσθιο τμήμα	18
		1.5.5	Έλεγχος ορθότητας		19
		1.5.6	Σφάλματα και ανάνηψη		19
	1.6	Ένας πειραματικός μεταγλωττιστής			21
	Ασκήσεις				23

2	Τυπικές γλώσσες				25
	2.1	Ορισμοί			25
		2.1.1	Γλώσσες		26
	2.2	Γεννητικά και αναγνωριστικά μοντέλα			28
		2.2.1	Γραμματικές		28
		2.2.2	Ιεραρχία Chomsky		30
		2.2.3	Αναγνωριστές		30
	2.3	Κανονικές γλώσσες			32
		2.3.1	Κανονικές εκφράσεις		33
		2.3.2	Πεπερασμένα αυτόματα		34
			2.3.2.1	Ντετερμινιστικά πεπερασμένα αυτόματα	35
			2.3.2.2	Μη-ντετερμινιστικά πεπερασμένα αυτόματα	35
			2.3.2.3	Μη-ντετερμινιστικά πεπερασμένα αυτόματα με μηδενικές μεταβάσεις	36
			2.3.2.4	Τρόποι παράστασης πεπερασμένων αυτομάτων	37
			2.3.2.5	Καταστάσεις παγίδευσης	39
			2.3.2.6	Ισοδυναμία πεπερασμένων αυτομάτων	39
			2.3.2.7	Ελαχιστοποίηση ΝΠΑ	40
		2.3.3	Αναγωγές		42
			2.3.3.1	Αναγωγή κανονικής γραμματικής σε ΜΠΑ-ε	43
			2.3.3.2	Αναγωγή κανονικής έκφρασης σε ΜΠΑ-ε	44
	2.4	Γλώσσες χωρίς συμφραζόμενα			47
		2.4.1	Γραμματικές χωρίς συμφραζόμενα		47
			2.4.1.1	Ισοδύναμες γραμματικές	49
			2.4.1.2	Διφορούμενες γραμματικές	49
			2.4.1.3	Τρόποι παράστασης γραμματικών	52
		2.4.2	Αυτόματα στοίβας		54
			2.4.2.1	Τρόποι παράστασης αυτομάτων στοίβας	56
			2.4.2.2	Είδη αυτομάτων στοίβας	59
		2.4.3	Οι γλώσσες χωρίς συμφραζόμενα στην κατασκευή μεταγλωττιστών		60
	2.5	Κατηγορικές γραμματικές			61
		2.5.1	Χρήση κατηγορικών γραμματικών		62
		2.5.2	Κατηγορικές γραμματικές και μεταγλωττιστές		65
	Ασκήσεις				65

3	Λεκτική ανάλυση				69
	3.1	Λεκτικές μονάδες			69
	3.2	Αναγνώριση λεκτικών μονάδων			70
		3.2.1	Μια γενική μέθοδος		71
		3.2.2	Μια ειδική μέθοδος με βάση τα διαγράμματα μετάβασης		73
	3.3	Ανάνηψη από σφάλματα			74
	3.4	Σχεδίαση και υλοποίηση ενός λεκτικού αναλυτή με βάση τα διαγράμματα μετάβασης			76
		3.4.1	Καταγραφή και ταξινόμηση των χαρακτήρων		77
		3.4.2	Καταγραφή και ταξινόμηση των λεκτικών μονάδων		78
		3.4.3	Ενδιάμεση μνήμη και ανάνηψη από σφάλματα		79
		3.4.4	Σχεδίαση του διαγράμματος μετάβασης		80
		3.4.5	Υλοποίηση του λεκτικού αναλυτή		81
	3.5	Υλοποίηση ενός λεκτικού αναλυτή με το μεταεργαλείο flex			84
		3.5.1	Περιγραφή κανονικών εκφράσεων στο flex		86
		3.5.2	Ένα παράδειγμα χρήσης του flex		86
		3.5.3	Ορισμός αρχικών καταστάσεων		89
		3.5.4	Το περιβάλλον εκτέλεσης του flex		90
	Ασκήσεις				91

4	Συντακτική ανάλυση				93
	4.1	Εισαγωγή			93
		4.1.1	Βοηθητικές έννοιες: FIRST και FOLLOW		94
	4.2	Συντακτικοί αναλυτές από πάνω προς τα κάτω			97
		4.2.1	Γραμματικές LL(1)		98
			4.2.1.1	Αντικατάσταση	99
			4.2.1.2	Αριστερή παραγοντοποίηση	99
			4.2.1.3	Απαλοιφή αριστερής αναδρομής	100
		4.2.2	Συντακτικοί αναλυτές αναδρομικής κατάβασης		101
		4.2.3	Συντακτικοί αναλυτές LL(1)		103
			4.2.3.1	Κατασκευή του πίνακα συντακτικής ανάλυσης LL(1)	104
			4.2.3.2	Λειτουργία συντακτικού αναλυτή LL(1)	105
	4.3	Συντακτικοί αναλυτές από κάτω προς τα πάνω			106
		4.3.1	Συντακτικοί αναλυτές LR(k)		109
			4.3.1.1	Λειτουργία συντακτικού αναλυτή LR(1)	110
			4.3.1.2	Κατασκευή των πινάκων ελέγχου LR(1)	111
		4.3.2	Συντακτικοί αναλυτές SLR(1)		112
			4.3.2.1	Στοιχεία	112
			4.3.2.2	Η συνάρτηση CLOSURE	112
			4.3.2.3	Η συνάρτηση GOTO	113
			4.3.2.4	Εύρεση του συνόλου καταστάσεων	114
			4.3.2.5	Κατασκευή των πινάκων ελέγχου SLR(1)	115
		4.3.3	Συντακτικοί αναλυτές LALR(1) με το μεταεργαλείο bison		119
			4.3.3.1	Περιγραφή κανόνων παραγωγής στο bison	122
			4.3.3.2	Επίλυση συγκρούσεων στο bison	124
			4.3.3.3	Χειρισμός συντακτικών σφαλμάτων στο bison	125
			4.3.3.4	Το περιβάλλον εκτέλεσης του bison	125
	4.4	Ανάνηψη από σφάλματα			126
		4.4.1	Στρατηγικές για ανάνηψη από σφάλματα		127
		4.4.2	Ανάνηψη από σφάλματα σε συντακτικό αναλυτή LL(1)		129
		4.4.3	Ανάνηψη από σφάλματα σε συντακτικό αναλυτή LR(1)		130
	Ασκήσεις				131

5	Πίνακες συμβόλων				137
	5.1	Εισαγωγή			137
	5.2	Χαρακτηριστικά των ονομάτων			138
	5.3	Περιεχόμενα του πίνακα συμβόλων			140
	5.4	Οργάνωση του πίνακα συμβόλων			141
		5.4.1	Γραμμικές λίστες		142
		5.4.2	Δέντρα δυαδικής αναζήτησης		142
		5.4.3	Πίνακες κατακερματισμού		143
		5.4.4	Πολλαπλές εμβέλειες		144
	Ασκήσεις				146

6	Σημασιολογική ανάλυση				147
	6.1	Σύνταξη και σημασιολογία			147
		6.1.1	Στατική σημασιολογία		147
		6.1.2	Δυναμική σημασιολογία		150
	6.2	Είδη σημασιολογικών ελέγχων			150
	6.3	Συστήματα τύπων και σημασιολογικός έλεγχος			152
		6.3.1	Βασικοί και σύνθετοι τύποι		152
		6.3.2	Απλές εκφράσεις και έλεγχοι βασικών τύπων		154
		6.3.3	Μετατροπές τύπων		156
		6.3.4	Υπερφόρτωση τελεστών		156
		6.3.5	Πολυμορφικοί τελεστές		157
		6.3.6	Συνώνυμα τύπων		158
		6.3.7	Ισοδυναμία τύπων		158
			6.3.7.1	Δομική ισοδυναμία τύπων	159
			6.3.7.2	Ονομαστική ισοδυναμία τύπων	159
		6.3.8	Υποσύνολα τύπων και υποτύποι		160
		6.3.9	Πολυμορφικά συστήματα τύπων		161
		6.3.10	Αντιστοίχιση τύπων σε ονόματα		161
		6.3.11	Εξαγωγή τύπων		162
	6.4	Δυναμικός έλεγχος τύπων			164
	Ασκήσεις				165

7	Παραγωγή ενδιάμεσου κώδικα				167
	7.1	Ενδιάμεσος κώδικας			167
		7.1.1	Μετάφραση οδηγούμενη από τη σύνταξη		168
		7.1.2	Ενδιάμεση γλώσσα		169
			7.1.2.1	Τετράδες	170
			7.1.2.2	Τριάδες	171
			7.1.2.3	Αφηρημένα συντακτικά δέντρα	171
			7.1.2.4	Προθεματικός και επιθεματικός κώδικας	172
			7.1.2.5	Κατευθυνόμενοι ακυκλικοί γράφοι	172
	7.2	Παραγωγή ενδιάμεσου κώδικα σε μορφή τετράδων			173
		7.2.1	Η γλώσσα των τετράδων		173
			7.2.1.1	Τελούμενα	174
			7.2.1.2	Τελεστές	175
		7.2.2	Μεταγλώσσα μετάφρασης και μεταβλητές ιδιοτήτων		178
		7.2.3	Ένα απλό σχέδιο παραγωγής τετράδων		180
			7.2.3.1	Απλές εκφράσεις	180
			7.2.3.2	Αριθμητικές εκφράσεις	181
			7.2.3.3	L-values και δείκτες	182
			7.2.3.4	Λογικές εκφράσεις	184
			7.2.3.5	Απλές εντολές	189
			7.2.3.6	Σύνθετη εντολή	190
			7.2.3.7	Εντολή if	191
			7.2.3.8	Εντολή while	193
			7.2.3.9	Χρήση υποπρογραμμάτων	194
			7.2.3.10	Δυναμική παραχώρηση μνήμης	196
			7.2.3.11	Δηλώσεις δομικών μονάδων	198
			7.2.3.12	Ένα ολοκληρωμένο παράδειγμα	199
	7.3	Διερμηνείς			199
	Ασκήσεις				201

8	Βελτιστοποίηση κώδικα				205
	8.1	Εισαγωγή			205
		8.1.1	Κριτήρια εφαρμογής μετασχηματισμών βελτιστοποίησης		206
		8.1.2	Επίτευξη καλύτερης απόδοσης		207
		8.1.3	Οργάνωση ενός βελτιστοποιητικού μεταγλωττιστή		208
	8.2	Ανάλυση ροής ελέγχου και ροής δεδομένων			209
	8.3	Βελτιστοποιητικοί μετασχηματισμοί			212
		8.3.1	Μετασχηματισμοί υψηλού επιπέδου		213
			8.3.1.1	Αποτίμηση σταθερών εκφράσεων	213
			8.3.1.2	Αλγεβρικοί μετασχηματισμοί	214
			8.3.1.3	Απαλοιφή κοινών υποεκφράσεων	215
			8.3.1.4	Διάδοση αντιγράφων	216
			8.3.1.5	Ενοποίηση κώδικα	218
		8.3.2	Μετασχηματισμοί βρόχων		220
			8.3.2.1	Μετακίνηση κώδικα	220
			8.3.2.2	Απαλοιφή επαγωγικών μεταβλητών και υποβιβασμός ισχύος	221
			8.3.2.3	Αναδιοργάνωση βρόχων	224
			8.3.2.4	Απαλοιφή ελέγχου ορίων πίνακα	226
		8.3.3	Μετασχηματισμοί χαμηλού επιπέδου		228
			8.3.3.1	Απαλοιφή άχρηστου κώδικα	228
			8.3.3.2	Ευθυγράμμιση	228
			8.3.3.3	Απλοποίηση συνθηκών και αλμάτων	230
		8.3.4	Μετασχηματισμοί υποπρογραμμάτων		230
			8.3.4.1	Ενσωμάτωση υποπρογράμματος	233
			8.3.4.2	Κλήσεις ουράς και συνένωση	234
			8.3.4.3	Υποπρογράμματα φύλλα	237
		8.3.5	Παράδειγμα: Η βελτιστοποίηση του quicksort		237
	Ασκήσεις				238

9	Παραγωγή τελικού κώδικα				239
	9.1	Γεννήτορας τελικού κώδικα			239
	9.2	Τελικός υπολογιστής			240
		9.2.1	Καταχωρητές		241
		9.2.2	Διαχείριση μνήμης		242
		9.2.3	Εντολές		243
			9.2.3.1	Εντολές μεταφοράς	243
			9.2.3.2	Εντολές ακεραίων αριθμητικών πράξεων	244
			9.2.3.3	Εντολές λογικών πράξεων	245
			9.2.3.4	Εντολές άλματος	245
			9.2.3.5	Εντολές διαχείρισης στοίβας	246
			9.2.3.6	Εντολές υποπρογραμμάτων	246
			9.2.3.7	Εντολές αριθμητικών πράξεων κινητής υποδιαστολής	247
	9.3	Περιβάλλον εκτέλεσης			249
		9.3.1	Παράσταση δεδομένων		249
		9.3.2	Εγγραφήματα δραστηριοποίησης		251
		9.3.3	Οργάνωση της μνήμης		252
		9.3.4	Δομή ενοτήτων και μη τοπικά δεδομένα		254
			9.3.4.1	Σύνδεσμοι προσπέλασης	255
			9.3.4.2	Πίνακες δεικτών	258
		9.3.5	Πέρασμα παραμέτρων		259
	9.4	Παραγωγή αποδοτικού τελικού κώδικα			262
		9.4.1	Δέσμευση καταχωρητών		262
		9.4.2	Επιλογή εντολών		264
	9.5	Το τελικό πρόγραμμα			270
		9.5.1	Η βιβλιοθήκη χρόνου εκτέλεσης		271
		9.5.2	Σταθερές συμβολοσειρές		272
		9.5.3	Σταθερές κινητής υποδιαστολής		272
	9.6	Ένας γεννήτορας τελικού κώδικα για την ενδιάμεση γλώσσα τετράδων			273
		9.6.1	Βοηθητικές ρουτίνες		273
			9.6.1.1	Βοηθητική ρουτίνα getΑR	273
			9.6.1.2	Βοηθητική ρουτίνα updateΑL	273
			9.6.1.3	Βοηθητική ρουτίνα load	274
			9.6.1.4	Βοηθητική ρουτίνα loadReal	274
			9.6.1.5	Βοηθητική ρουτίνα loadΑddr	275
			9.6.1.6	Βοηθητική ρουτίνα store	275
			9.6.1.7	Βοηθητική ρουτίνα storeReal	277
			9.6.1.8	Βοηθητική ρουτίνα name	277
			9.6.1.9	Βοηθητική ρουτίνα endof	277
			9.6.1.10	Βοηθητική ρουτίνα label	278
		9.6.2	Παραγωγή κώδικα		278
			9.6.2.1	Ανάθεση και στοιχεία πίνακα	279
			9.6.2.2	Αριθμητικές πράξεις και συγκρίσεις	279
			9.6.2.3	Δομικές μονάδες, κλήσεις και άλματα	282
		9.6.3	Ένα ολοκληρωμένο παράδειγμα		284
	Ασκήσεις				287

10	Αντικειμενοστρεφείς γλώσσες				289
	10.1	Αντικειμενοστρεφής προγραμματισμός			289
	10.2	Αντικείμενα και μέθοδοι			290
	10.3	Κατασκευαστές και καταστροφείς			291
	10.4	Απλή κληρονομικότητα			293
	10.5	Πολυμορφισμός υποτύπων			296
	10.6	Πολλαπλή κληρονομικότητα			299
	10.7	Έλεγχος υποτύπων και μετατροπές			303
	10.8	Διαπροσωπείες			306
	Ασκήσεις				309

ΠΑΡΑΡΤΗΜΑΤΑ

Α	Η γλώσσα προγραμματισμού PCL				311
	Α.1	Λεκτικές μονάδες			311
	Α.2	Τύποι δεδομένων			313
	Α.3	Δομή του προγράμματος			314
		Α.3.1	Μεταβλητές		315
		Α.3.2	Υποπρογράμματα		315
	Α.4	Εκφράσεις			316
		Α.4.1	L-values		316
		Α.4.2	Σταθερές		317
		Α.4.3	Τελεστές		317
		Α.4.4	Κλήση συναρτήσεων		319
	Α.5	Εντολές			319
	Α.6	Βιβλιοθήκη χρόνου εκτέλεσης			321
		Α.6.1	Είσοδος και έξοδος		321
		Α.6.2	Μαθηματικές συναρτήσεις		322
		Α.6.3	Συναρτήσεις μετατροπής		322
	Α.7	Πλήρης γραμματική της PCL			322

Β	Παραδείγματα μεταγλώττισης				325
	Β.1	Πες γεια!			325
	Β.2	Οι πύργοι του Hanoi			327
	Β.3	Πρώτοι αριθμοί			336
	Β.4	Ταξινόμηση με τη μέθοδο της φυσαλίδας			341
	Β.5	Μέση τιμή τυχαίας μεταβλητής			346

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

Ευρετήριο					355

Νικόλαος Σ. Παπασπύρου (nickie@softlab.ntua.gr)

Τελευταία ενημέρωση: 21/01/2003, 4:24 .