ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ
ΤΜΗΜΑ ΗΛΕΚΤΡΟΛΟΓΩΝ ΜΗΧΑΝΙΚΩΝ ΚΑΙ ΜΗΧΑΝΙΚΩΝ
ΥΠΟΛΟΓΙΣΤΩΝ
ΤΟΜΕΑΣ ΠΛΗΡΟΦΟΡΙΚΗΣ
ΕΞΕΤΑΣΕΙΣ ΣΤΟ ΜΑΘΗΜΑ: ΜΕΤΑΓΛΩΤΤΙΣΤΕΣ
ΔΙΔΑΣΚΩΝ: Ε. ΣΚΟΡΔΑΛΑΚΗΣ
27 ΙΟΥΝΙΟΥ 2000
ΘΕΜΑ 1
(1.0 μονάδες)
Δίνεται:
Θεωρούμε τη γλώσσα η οποία αποτελείται από συμβολοσειρές
που σχηματίζονται από τα σύμβολα 0 και 1 αλλά κάθε μια συμβολοσειρά περιέχει
υποχρεωτικά μια και μόνο μια φορά την υποσυμβολοσειρά 000. Με άλλα λόγια, να
μην υπάρχουν περισσότερα από τρία 0 συνεχόμενα, και να υπάρχουν τρία 0
συνεχόμενα ακριβώς μια φορά. Ως παράδειγμα, οι συμβολοσειρές: 10001011, 010110001, 000 ανήκουν σ' αυτή τη γλώσσα, ενώ οι
συμβολοσειρές: 101000011, 111, 10100 δεν ανήκουν σ' αυτήν.
Ζητείται:
1α) Να
δοθεί ένα πεπερασμένο ντεντερμινιστικό αυτόματο σε μορφή γράφου μετάβασης
(σελίδα 18) που να αναγνωρίζει τις συμβολοσειρές αυτής της γλώσσας.
1β) Να δοθεί το διάγραμμα μετάβασης (σελίδα 58)
που αντιστοιχεί σ' αυτό το γράφο μετάβασης
1γ) Να περιγραφεί η γλώσσα αυτή με μιά κανονική
έκφραση (σελίδα 21).
Λύση:
1α)
1β)
Στο παραπάνω σχήμα, όπου $ εννοούμε ‘όχι 0 ή 1’.
1γ) Μία κανονική έκφραση που περιγράφει τη
γραμματική είναι:
(1 | 01
| 001) * 000 (1 | 10 | 100) *
ΘΕΜΑ 2
(1.0 μονάδες)
Δίνεται:
Θεωρούμε τη γλώσσα η οποία αποτελείται από
συμβολοσειρές που σχηματίζονται από τα σύμβολα a και b αλλά σε κάθε μια
συμβολοσειρά το πλήθος των b είναι
διπλάσιο του πλήθους των a. Ως
παράδειγμα, οι συμβολοσειρές: abb,
babbba ανήκουν σ' αυτή τη γλώσσα, ενώ οι συμβολοσειρές : baab,
aab, ba δεν ανήκουν σ' αυτήν.
Ζητείται:
2α) Να δοθεί σε μορφή BNF η γραμματική αυτής της γλώσσας.
2β) Να δοθεί το συντακτικό δένδρο αναγνώρισης της
συμβολοσειράς : baabbb με αυτή τη γραμματική.
Λύση:
2α)
<S> ::= ε
<S>
::= a <S> b <S> b <S>
<S>
::= b a <S> b <S>
<S>
::= b b <S> a <S>
2β)
ΘΕΜΑ 3
(1.5 μονάδες)
Για το πρόγραμμα
Pascal που δίνεται παρακάτω να παραχθεί ο ενδιάμεσος κώδικας.
1. program excj2000;
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:=x*z+a
7.
end; {of proc1}
8. begin {of excj2000}
9. if
y<a*x then while i<=n do begin i:=i+1; s:=s+i end
else if x>y and
x<z then z:=3
else proc1(r,r)
10. end. {of excj2000}
Λύση:
1.
unit,
proc1, -, -
2.
*,
x, z, $1
3.
+,
$1, a, $2
4.
:=,
$2, -, y
5.
endu,
proc1, -, -
6.
unit,
excj2000, -, -
7.
*,
a, x, $3
8.
<,
y, $3, 10
9.
jump,
-, -, 18
10.
<=,
i, n, 12
11.
jump,
-, -, 27
12.
+,
i, 1, $4
13.
:=,
i, -, $4
14.
+,
s, i, $5
15.
:=,
s, -, $5
16.
jump,
-, -, 10
17.
jump,
-, -, 27
18.
>,
x, y, 20
19.
jump,
-, -, 24
20.
<,
x, z, 22
21.
jump,
-, -, 24
22.
:=
3, -, z
23.
jump,
-, -, 27
24.
par,
r, V, -
25.
par,
r, R, -
26.
call,
-, -, proc1
27.
endu,
excj2000, -, -
ΘΕΜΑ 4
(1.5
μονάδες)
Για το πρόγραμμα
Pascal που δίνεται παρακάτω να παραχθεί ο τελικός κώδικας για τις τετράδες 9 έως
15. Ο κώδικας αυτός να παραχθεί με τη μέθοδο της κατ’ ευθείαν
εντολής-προς-εντολή παραγωγής. Να περιγραφούν και τα εγγραφήματα δραστηριοποίησης.
1. progam p; 1: unit,p,-,-
2.
var c,a,b:integer;
3.
procedure p1; 2: unit,p1,-,-
4.
var c,b: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+c,b,c); 10: +, a, c, $3
11: par,$3,V,-
12: par,b,V,-
13: par,c,R,-
14: call,-,-,p21
15. end; {p22}
15: endu,p22,-,-
16. begin
17. p22;
16: call,-,-,p22
18.
end;
{p1} 17: endu,p1,-,-
19
begin
20.
p1;
18: call.-,-,p1
21.
end..
{p} 19: endu,p,-,-
Λύση:
Εγγραφήματα δραστηριοποίησης:
|
|
p1 |
p21 |
p22 |
p |
|
bp+12 |
|
x |
|
|
|
bp+10 |
|
y |
|
|
|
bp+8 |
|
z |
|
|
|
bp+6 |
Διεύθυνση αποτελέσματος |
Διεύθυνση αποτελέσματος |
Διεύθυνση αποτελέσματος |
Διεύθυνση αποτελέσματος |
|
bp+4 |
Σύνδεσμος προσπέλασης |
Σύνδεσμος προσπέλασης |
Σύνδεσμος προσπέλασης |
Σύνδεσμος προσπέλασης |
|
bp+2 |
Διεύθυνση επιστροφής |
Διεύθυνση επιστροφής |
Διεύθυνση επιστροφής |
Διεύθυνση επιστροφής |
|
bp |
Προηγούμενο bp |
Προηγούμενο bp |
Προηγούμενο bp |
Προηγούμενο bp |
|
bp-2 |
c |
c |
c |
c |
|
bp-4 |
b |
$1 |
$3 |
a |
|
bp-6 |
|
$2 |
|
b |
Κώδικας:
;9:
unit,p22,-,-
@9:
_p22_3: proc near
push bp
mov bp, sp
sub sp, 4
;10:
+, a, c, $3
@10:
mov si, word ptr [bp+4]
mov si, word ptr [si+4]
mov ax, word ptr[si-4]
mov dx, word ptr[bp-2]
add ax, dx
mov word ptr [bp-4], ax
;11:
par,$3,V,-
@11:
mov ax, word ptr [bp-4]
push ax
;12:
par,b,V,-
@12:
mov si, word ptr [bp+4]
mov ax, word ptr [si-4]
push ax
;13:
par,c,R,-
@13:
lea si, word ptr [bp-2]
push si
;14:
call,-,-,p21
@14:
sub sp, 2
push word ptr [bp+4]
call near ptr _p_21_2
add sp, 10
;15:
endu,p22,-,-
@15:
mov sp, bp
pop bp
ret
_p_22_3 endp