ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ
ΤΜΗΜΑ
ΗΛΕΚΤΡΟΛΟΓΩΝ ΜΗΧΑΝΙΚΩΝ ΚΑΙ ΜΗΧΑΝΙΚΩΝ ΥΠΟΛΟΓΙΣΤΩΝ
ΤΟΜΕΑΣ
ΠΛΗΡΟΦΟΡΙΚΗΣ
ΕΞΕΤΑΣΕΙΣ ΣΤΟ
ΜΑΘΗΜΑ: ΜΕΤΑΓΛΩΤΤΙΣΤΕΣ
ΔΙΔΑΣΚΩΝ: Ε.
ΣΚΟΡΔΑΛΑΚΗΣ
28 ΙΟΥΝΙΟΥ 1999
ΘΕΜΑ 1
(0.5 μονάδες)
Να σχεδιασθεί ένα διάγραμμα μετάβασης για την αναγνώριση δεκαδικών
σταθερών οι
οποίες αποτελούνται από
μηδέν ή περισσότερα
δεκαδικά ψηφία
που ακολουθούνται από μία τελεία η οποία ακολουθείται από μηδέν ή
περισσότερα
δεκαδικά ψηφία αλλά κάθε τέτοια σταθερά έχει τουλάχιστο ένα
δεκαδικό ψηφίο.
ΘΕΜΑ 2
(1.5 μονάδες)
Να δοθεί ο συντακτικός
ανάλυτής αναδρομικής κατάβασης,
συμπεριλαμβανομένου του λεκτικού αναλυτή, για τη γραμματική με κανόνες:
1. Ε->-Ε
2. Ε->(E)
3. E->VE'
4. E'->-E
5. E'->ε
6. V->iV'
7. V'->(E)
8. V'->ε
Μετά να δοθεί το συντακτικό δένδρο αναγνώρισης της συμβολοσειράς
i--i((i))
ΘΕΜΑ 3
(1.5 μονάδες)
Για το πρόγραμμα Pascal που δίνεται παρακάτω να παραχθεί ο ενδιάμεσος
κώδικας.
1. program excj99;
2. var a,x,y,z,r,s,i,n:integer;
3. procedure proc1(x:integer;var y:integer);
4. var q:integer;
5. begin {of proc1}
6. y:=a+x*z
7. end; {of proc1}
8. begin {of excj99}
9.
if a+x>y then while i<=n
do begin s:=s+i; i:=i+1 end
else if x>y or x<z then z:=3
else proc1(x+y,r)
10. end. {of excj99}
ΘΕΜΑ 4
(1.5 μονάδες)
Για το πρόγραμμα Pascal που δίνεται παρακάτω να παραχθεί ο τελικός
κώδικας για τις τετράδες 9 έως 14. Ο κώδικας αυτός να παραχθεί με τη μέθοδο της
κατ ευθείαν
εντολής-προς-εντολή παραγωγής. Να περιγραφούν και τα εγγραφήματα δραστηριοποίησης.
1. progam p; 1: unit,p,-,-
2. var a,b,c:integer;
3. procedure p1; 2: unit,p1,-,-
4. var b,c:integer;
5. procedure p21( x,y:integer;var z:integer); 3: unit,p21,-,-
6. var c:integer;
7. begin
8. c:=3; 4: :=,3,-,c
9. z:=x+y+c; 5: +,x,y,$1
6: +,$1,c,$2
7: :=,$2,-,z
10 . end; {p21} 8: endu,p21,-,-
11. procedure p22; 9: unit,p22,-,-
12. var c:integer;
13. begin
14. p21(a,b,c); 10: par,a,V,-
11: par,b,V,-
12: par,c,R,-
13: call,-,-,p21
15. end; {p22} 14: endu,,p22,-,-
16. begin
17. p22; 15: call,-,-,p22
18. end; {p1} 16: endu,p1,-,-
19. begin
20. p1; 17: call.-,-,p1
21. end.. {p} 18: endu,p,-,-
Λύσεις
Θέμα 1
Θέμα 2
procedure main();
begin
la();
E();
if
next_token<>Eof then ERROR();
end;
procedure E();
begin
if next_token=Minus then begin la(); E()
end;
if next_token=LPar then begin
la(); E();
if next_token=RPar then la();
else ERROR()
end;
if next_token = 'i' then begin V();
EPRIME() end
end;
procedure EPRIME();
begin
if next_token=Minus then begin la(); E()
end
end;
procedure V();
begin
if next_token='i' then begin la(); VPRIME()
end;
else ERROR()
end;
procedure VPRIME();
begin
if next_token=LPar then begin
la(); E();
if next_token=RPar then la();
else ERROR
end
end;
procedure la();
begin
c=getnextchar();
if eof then return eof;
else return c
end
Θέμα 3
1.
unit, proc1, -,
-
2.
*, x, z, $1
3.
+, 1, $1, $2
4.
:=, $2, -, y
5.
endu, proc1, -,
-
6.
unit, excj99,
-, -
7.
+, a, x, $3
8.
>, $3, y, 10
9.
jmp, -, - , 18
10.
<=, i, n, 12
11.
jmp, -, -, 17
12.
+, s, i, $4
13.
:=, $4, -, s
14.
+, i, 1, $5
15.
:=, $5, -, i
16.
jmp, -, -, 10
17.
jmp, -, -, 29
18.
>, x, y, 22
19.
jmp, -, -, 20
20.
<, z, x, 22
21.
jmp, -, -, 24
22.
:=, 3, -, z
23.
jmp, -, -, 29
24.
+, x, y, $6
25.
par, V, $6, -
26.
par, V, r, -
27.
call, -, -,
proc1
28.
jmp, -, -, 29
29.
endu, excj99,
-, -
Θέμα 4
Τελικός κώδικας
για τις τετράδες 9-14:
_p_22_3 proc near ;unit,
p22, -, -
push bp
mov bp,sp
sub sp,2
mov si, word ptr[bp+4] ;par, a, V, -
mov si, word ptr[si+4]
mov
si, word ptr[si-2]
push
ax
mov
si, word ptr[bp+4] ;par, b, V, -
mov
si, word ptr[si-2]
push
ax
lea
si, word ptr[bp-2] ;par, c, R, -
push
si
sup
sp,2 ;call, -, -, p21
push
word ptr[bp+4]
call
near ptr _p_21_2
add
sp,10
@p22_2: mov
sp, bp ;endu, p22, -, -
pop bp
ret
_p22_p endp
Στον τελικό
κώδικα χρησιμοποιήθηκαν σύνδεσμοι προσπέλασης.
Εγγραφήματα
δραστηριοποίησης
|
Θέση |
Πρόγραμμα p |
Διαδικασία p1 |
Διαδικασία p21 |
Διαδικασία p22 |
|
bp+12 |
|
|
Παράμετρος x |
|
|
bp+10 |
|
|
Παράμετρος y |
|
|
bp+8 |
|
|
Παράμετρος z |
|
|
bp+6 |
Διεύθυνση
αποτελέσματος |
Διεύθυνση
αποτελέσματος |
Διεύθυνση
αποτελέσματος |
Διεύθυνση
αποτελέσματος |
|
bp+4 |
Σύνδεσμος
προσπέλασης |
Σύνδεσμος
προσπέλασης |
Σύνδεσμος
προσπέλασης |
Σύνδεσμος
προσπέλασης |
|
bp+2 |
Διεύθυνση
επιστροφής |
Διεύθυνση
επιστροφής |
Διεύθυνση
επιστροφής |
Διεύθυνση
επιστροφής |
|
bp |
Προηγούμενο bp |
Προηγούμενο bp |
Προηγούμενο bp |
Προηγούμενο bp |
|
bp-2 |
Τοπική a |
Τοπική b |
Τοπική c |
Τοπική c |
|
bp-4 |
Τοπική b |
Τοπική c |
Προσωρινή $1 |
|
|
bp-6 |
Τοπική c |
|
Προσωρινή $2 |
|