Εθνικό Μετσόβιο Πολυτεχνείο
Τμήμα Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών
Τομέας Πληροφορικής

Εξέταση στο μάθημα : Μεταγλωττιστές (8ο εξάμηνο)

Καθηγητής : Εμμ. Σκορδαλάκης

Ημερομηνία εξέτασης : 7 Σεπτεμβρίου 2001 (Εξέταση κανονικής περιόδου)

Διάρκεια εξέτασης : 3 ώρες

Θέμα 1 [10%]

Να σχεδιαστεί ένα ντετερμινιστικό πεπερασμένο αυτόματο σε μορφή γράφου μετάβασης, που να αναγνωρίζει τους φυσικούς αριθμούς (στο δεκαδικό σύστημα αρίθμησης) που διαιρούνται ακριβώς με το 3. Υπενθυμίζεται ότι ένας φυσικός αριθμός διαιρείται ακριβώς με το 3, αν και μόνο αν το άθροισμα των ψηφίων του (στο δεκαδικό σύστημα αρίθμησης) διαιρείται ακριβώς με το 3. Για παράδειγμα, το αυτόματο θα πρέπει να αναγνωρίζει τις συμβολοσειρές: 51, 9993711, 8361, 0034008, ενώ θα πρέπει να απορρίπτει τις συμβολοσειρές: 92, 007700, 112.

Το αλφάβητο εισόδου είναι το σύνολο των δεκαδικών ψηφίων {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Το αυτόματο δεν πρέπει να αναγνωρίζει την κενή συμβολοσειρά. Επίσης, για αποφυγή πολυπλοκότητας, επιτρέπεται η ύπαρξη μηδενικών στην αρχή ενός φυσικού αριθμού.

Θέμα 2 [10%]

Δίνεται η παρακάτω γραμματική σε συμβολισμό EBNF που περιγράφει, χωρίς πολλές λεπτομέρειες, τους ορισμούς συναρτήσεων της C και ένα μικρό υποσύνολο των εντολών της. (Παραλείπονται οι ορισμοί των μη τερματικών συμβόλων simple, formals και expr.)

decl ::= result id “(” formals “)” “{” ( stmt )^* “}”

result ::= type | “void”

stmt     ::= simple | “break” “;” | “continue” “;” | “return” [ expr ] “;”
              |    “while” “(” expr “)” “{” ( stmt )^* “}”
              |    “switch” “(” expr “)” “{” ( stmt )^* “}”

Στη γραμματική αυτή, δεν είναι εμφανείς οι εξής περιορισμοί που επιβάλλει η γλώσσα C:

· Στο εσωτερικό μιας συνάρτησης που επιστρέφει void δεν μπορεί να εμφανίζεται η εντολή “return” συνοδευόμενη από έκφραση.

· Στο εσωτερικό μιας συνάρτησης που δεν επιστρέφει void, αν εμφανίζεται η εντολή “return” θα πρέπει να συνοδεύεται από έκφραση.

· Η εντολή “break” μπορεί να εμφανίζεται μόνο στο εσωτερικό μιας εντολής “while” ή μιας εντολής “switch”.

· Η εντολή “continue” μπορεί να εμφανίζεται μόνο στο εσωτερικό μιας εντολής “while”.

Να τροποποιήσετε κατάλληλα την παραπάνω γραμματική ώστε οι παραγόμενες συμβολοσειρές να πληρούν αυτούς τους περιορισμούς.

Θέμα 3 [15%]

Δίνεται το παρακάτω πρόγραμμα Pascal. Ζητούνται: (α) ο ενδιάμεσος κώδικας που θα παραχθεί, χωρίς βελτιστοποίηση, και (β) τα εγγραφήματα δραστηριοποίησης για κάθε δομική μονάδα.

program main;

function f (var x : integer; y : integer) : integer;

begin

while (x < y) or (y <= 0) do

begin

y := 2 * y - x - 1;

if 3 * x + 2 * y = 999 then

f := 42

else

x := x + 1

end;

f := y

end;

var n : integer;

begin

n := 9;

writeInteger(f(n, 100))

end.

Θέμα 4 [15%]

Δίνεται το παρακάτω πρόγραμμα Pascal (αριστερά) και ο αντίστοιχος ενδιάμεσος κώδικας (δεξιά). Ζητούνται: (α) τα εγγραφήματα δραστηριοποίησης για κάθε δομική μονάδα, και (β) ο τελικός κώδικας που θα παραχθεί για τις τετράδες: 2, 3, 5, 6, 7, 10, 11, 13, 20.

program main;

var x, y, z : integer;

procedure p (var x : integer; y : integer);

var i : integer;

function f (n : integer) : integer;

begin

f := 2 * n

end;

1: unit, f, -, -

2: *, 2, n, $1

3: retv, $1, -, -

4: endu, f, -, -

begin

i := x + y + z;

x := f(2 * i)

end;

5: unit, p, -, -

6: +, x, y, $2

7: +, $2, z, $3

8: :=, $3, -, i

9: *, 2, i, $4

10: par, $4, V, -

11: par, $5, RET, -

12: call, -, -, f

13: :=, $5, -, x

14: endu, p, -, -

begin

x := 5;

y := 7;

p(y, x)

end.

15: unit, main, -, -

16: :=, 5, -, x

17: :=, 7, -, y

18: par, y, R, -

19: par, x, V, -

20: call, -, -, p

21: endu, main, -, -

Καλή Επιτυχία

Λύσεις