Θέματα Εξετάσεων - Ιούνιος 1997

Θέμα 1ο [10]

Να σχεδιαστεί ένα ντετερμινιστικό πεπερασμένο αυτόματο σε μορφή γράφου μετάβασης, που να αναγνωρίζει συμβολοσειρές αποτελούμενες από 0 και 1, οι οποίες δεν περιέχουν ως τμήματα τις συμβολοσειρές 00 ή 010. Για παράδειγμα, η συμβολοσειρά 1101101110110 αναγνωρίζεται, ενώ η συμβολοσειρά 11010111 δεν αναγνωρίζεται λόγω του τμήματος 010.

Λύση

Θέμα 2ο [15]

Να κατασκευαστεί ο πίνακας συντακτικής ανάλυσης LL(1) για τη γραμματική με τους ακόλουθους κανόνες:

1. P -> S T
2. T -> ; P
3. T -> ε
4. S -> i S E x
5. S -> w S x
6. S -> a
7. S -> b P x
8. E -> e S
9. E -> ε

Στη συνέχεια να περιγραφούν τα βήματα για τη συντακτική ανάλυση της συμβολοσειράς:

iax;ibaxewaxx$

Λύση

Θέμα 3ο [25]

Να μεταγλωττιστεί χειρωνακτικά το παρακάτω πρόγραμμα Russel.

var y, a, b, x : integer

function f (a : ref integer, y : integer) is
	if
	   x > y -> a := x
	end
end

f(b, a)

Ζητούνται ο ενδιάμεσος και ο τελικός κώδικας, καθώς και τα εγγραφήματα δραστηριοποίησης για όλες τις δομικές μονάδες.

Λύση