Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Σεπτέμβριος 2024¶
Μεταγραφή από τις φωτογραφίες CamScanner_09-25-2024_18.23.jpg και CamScanner_09-25-2024_18.13_1_1.jpg.
CamScanner_09-25-2024_18.23.jpg¶
ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΚΑΙ ΜΕΤΑΦΡΑΣΤΩΝ Εξέταση Περιόδου Σεπτεμβρίου 2024
ΘΕΜΑ 1 – Λεξική και Συντακτική Ανάλυση (40%)
Σας δίνονται οι παρακάτω τρεις (3) απλές γραμματικές σε συμβολισμό BNF:
1. ::= | 0 | 1
2. ::= 0 | 1 | 0
3.
(a) Να περιγράψετε τις ακολουθίες δυαδικών αριθμών που παράγουν οι τρεις γραμματικές. Δώστε και παραδείγματα. (b) Αντιστοιχίστε τις ακολουθίες 10101, 011, 1, 000, 011100 στην/στις γραμματική/ές που τις παράγουν, ή σε καμία αν δεν μπορούν να παραχθούν. (c) Δείξτε αν η ακολουθία 01110 παράγεται ή όχι από την \(3^\eta\) γραμματική, κατασκευάζοντας τη Στοίβα Ταιριάσματος – Πρόβλεψης Top-Down συντακτικής ανάλυσης. (d) Ποια ή ποιες από τις γραμματικές είναι κανονική και γιατί; (e) Για την πρώτη κατά σειρά (με βάση με την παραπάνω αρίθμησή τους) από την/τις κανονικές γραμματικές που αναγνωρίσατε στο ερώτημα (d), παρουσιάστε αντίστοιχη κανονική έκφραση, καθώς και το διάγραμμα καταστάσεων – μεταβάσεων για το αντίστοιχο ντετερμινιστικό πεπερασμένο αυτόματο. (f) Ποια ή ποιες από τις τρεις γραμματικές δεν είναι LL(1) και γιατί; Μετασχηματίστε την πρώτη κατά σειρά (με βάση με την αρίθμησή τους) από τις γραμματικές αυτές, σε ισοδύναμη LL(1) γραμματική.
ΘΕΜΑ 2 – Εμβέλεια και Μεταβίβαση Παραμέτρων (20%) Δίνεται το παρακάτω πρόγραμμα σε μια γλώσσα τύπου Pascal που χρησιμοποιεί το στατικό κανόνα εμβέλειας:
program MAIN;
var i, c: integer; a: array[1..2] of integer;
procedure F(x, y: integer);
var d: integer;
procedure G(a: integer);
begin
a := a + d;
end;
begin
d := -1;
x := x - 1;
G(i);
G(y);
c := x * y;
end;
BEGIN
a[1] := 5; a[2] := 4; i:=2;
F(a[i], a[i]);
writeln('a[1]=', a[1]); writeln('a[2]=', a[2]); writeln('c=', c);
END.
Μορφή εξόδου του προγράμματος για τις τρεις εντολές writeln:
[Σχήμα: Πλαίσιο που γράφει: a[1]=V1 a[2]=V2 c=V3]
(a) Ποια είναι τα περιβάλλοντα αναφοράς (τοπικά, μη-τοπικά, καθολικά) όλων των τμημάτων του προγράμματος; (b) Ποιες τιμές (V1, V2, V3) θα τυπωθούν με την εντολή writeln, εφόσον οι διαδικασίες F και G καλούνται με τις παρακάτω περιπτώσεις τρόπου μεταβίβασης παραμέτρων; Εξηγήστε σύντομα τις διαδικασίες υπολογισμού σε όλες τις περιπτώσεις. 1. Όλες οι παράμετροι μεταβιβάζονται με κλήση με τιμή (call by value). 2. Όλες οι παράμετροι μεταβιβάζονται με κλήση με αναφορά (call by reference). 3. Όλες οι παράμετροι μεταβιβάζονται με τιμή – αποτέλεσμα (call by value-result). 4. Όλες οι παράμετροι μεταβιβάζονται με κλήση με όνομα (call by name).
ΘΕΜΑ 3 – Μεταβλητές και Διαχείριση Μνήμης (15%) Δίνεται το παρακάτω τμήμα προγράμματος σε γλώσσα C:
| 1 | void main(){ | | 2 | int data1[4] = {4, 3, 2, 1}; | | 3 | int data2[4] = {10, 20, 30, 40}; | | 4 | int *p1, *p2, a = 1, b = 2, c = 3; | | 5 | p1 = &data1[3]; | | 6 | p2 = &data2[*p1]; | | 7 | a = *(p2+1) + 1; | | 8 | p1 -= 2; | | 9 | b = p1[1] + *(p2-1); |
CamScanner_09-25-2024_18.13_1_1.jpg¶
10 *p2 /= 5;
11 c += *p1 + *p2 - 2;
12 printf("a=%d b=%d c=%d\n", a, b, c);
13 }
(a) Εξηγήστε συνοπτικά και γραμμή-γραμμή, για τις γραμμές 5-11, τη λειτουργία του παραπάνω προγράμματος. (b) Τι θα τυπωθεί με την εκτέλεση του προγράμματος, δηλ ποιες θα είναι οι τελικές τιμές των a, b, c;
ΘΕΜΑ 4 – Functional Programming και Γλώσσες ΒΔ (20%) (α) Είναι γνωστό ότι στις συναρτησιακές γλώσσες, η αναδρομή αντικαθιστά την επανάληψη. Κάντε ακριβώς το ίδιο (σώμα αναδρομικής συνάρτησης και πρώτη κλήση) για τον παρακάτω βρόχο (η εντολή j^i σημαίνει ύψωση της μεταβλητής j σε δύναμη με εκθέτη i):
R := 0; i := 1; j := 300;
while i < j do
R := R + j^i; i := i + 2;
j := j - 2
end while
return R
(β) Συμπληρώστε την αποτίμηση ? των παρακάτω εκφράσεων συνθήκης σε γλώσσα scheme:
(if (< 4 5) 0 1) => ?
(cond
((< 10 9) 1)
((< 8 7) 2)
(else 3)) => ?
(γ) Έστω σε Lisp οι παρακάτω Map/ Fold (Reduce) high-order functions. Συμπληρώστε τις αποτιμήσεις ? των εκφράσεων.
(map (lambda (x) (* x 3))
'(1 2 3 4 5)) => ?
(fold + 0 '(1 2 3 4 5)) => ?
(fold * 1 '(1 2 3 4 5)) => ?
(define (sum-of-triples v)
(fold + 0 (map (lambda (x) (* x 3)) v)))
(sum-of-triples '(1 2 3 4 5)) => ?
(δ) Συμπληρώστε όλα τα στάδια αποτίμησης της παρακάτω έκφρασης σε \(\lambda\)-λογισμό.
(ε) Σε μία γλώσσα συναρτησιακού προγραμματισμού, θεωρείστε τους κάτωθι κανόνες αναγωγής (reduction rules). - Built-in rules: addition, substraction, multiplication, division - User supplied rules: - square x = x * x - double x = x + x - sum [ ] = 0 - sum (x:xs) = x + sum [x+1:xs]
Δώστε όλα τα ενδιάμεσα βήματα αναγωγής μέχρι την τελική αποτίμηση της έκφρασης square (sum [1:10]) με πρόθυμη (eager evaluation) και οκνηρή (lazy evaluation) στρατηγική αποτίμησης. Πόσα βήματα (reductions) απαιτεί η κάθε στρατηγική; Ποια είναι η πιο αποδοτική;
ΘΕΜΑ 5 - Python (15%) Γράψτε ένα πρόγραμμα σε Python που να διαχειρίζεται μια λίστα αριθμών. Το πρόγραμμα θα πρέπει να χρησιμοποιεί τις κατάλληλες μεθόδους για την εκτέλεση των παρακάτω εργασιών: (α) Δημιουργήστε μια λίστα με τους εξής αριθμούς: - 5, 12, 8, 3, 25, 18, 22,25,30 (β) Πρόσθεσε στην αρχή της λίστας τον αριθμό 7 και στο τέλος της λίστας τον αριθμό 20. (γ) Διέγραψε τον αριθμό 8 από τη λίστα. (δ) Ταξινόμησε τη λίστα των αριθμών σε αύξουσα σειρά. (ε) Επίλεξε και τύπωσε τον δεύτερο και τον τέταρτο αριθμό από τη λίστα. (στ) Υπολόγισε και εμφάνισε το συνολικό πλήθος των αριθμών στη λίστα. (ζ) Επίλεξε και εμφάνισε τον αριθμό που βρίσκεται στη μέση της λίστας (αν το πλήθος είναι ζυγό, εμφάνισε τον μεσαίο αριθμό της κάτω μισής). (η) Αντικατάστησε τον τελευταίο αριθμό της λίστας με τον αριθμό 15.
ΚΑΛΗ ΕΠΙΤΥΧΙΑ!!!
- Τα θέματα επιστρέφονται μαζί με το γραπτό
- Απαντήστε σε όλα τα θέματα
- Η διάρκεια της εξέτασης είναι 2,5 ώρες
2
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(a)
1. \(A\to AA\mid0\mid1\): όλες οι μη κενές δυαδικές συμβολοσειρές (οποιουδήποτε μήκους ≥ 1), π.χ. 0, 1, 01, 1101. (Ασαφής γραμματική: πολλά δέντρα για την ίδια συμβολοσειρά.)
2. \(B\to0B\mid1B\mid0\): οι δυαδικές συμβολοσειρές που τελειώνουν σε 0 (μήκος ≥ 1): 0, 10, 110, 0100.
3. \(C\to0C0\mid1C1\mid0\mid1\): οι παλίνδρομες δυαδικές συμβολοσειρές περιττού μήκους (το μεσαίο ψηφίο 0 ή 1): 0, 1, 010, 101, 01110, 10101.
(b)
| Ακολουθία | Γραμματικές |
|---|---|
| 10101 | 1 και 3 (παλίνδρομο περιττού μήκους, τελειώνει σε 1 ⇒ όχι η 2) |
| 011 | μόνο 1 (δεν τελειώνει σε 0, δεν είναι παλίνδρομο) |
| 1 | 1 και 3 |
| 000 | 1, 2 και 3 |
| 011100 | 1 και 2 (άρτιο μήκος και όχι παλίνδρομο ⇒ όχι η 3) |
Καμία ακολουθία δεν είναι «σε καμία».
(c) Η 01110 παράγεται από την 3: \(C\Rightarrow0C0\Rightarrow01C10\Rightarrow01110\) (το κέντρο 1 από το \(C\to1\)). Στοίβα ταιριάσματος – πρόβλεψης (κορυφή αριστερά). Η επιλογή μεταξύ \(C\to0C0\) και \(C\to0\) (και αντίστοιχα για το 1) δεν προκύπτει από ένα σύμβολο κοιτάγματος· την αποφασίζουμε με βάση το πόσα σύμβολα απομένουν (κέντρο όταν ακολουθούν μόνο τα συμμετρικά σύμβολα).
| Στοίβα | Είσοδος | Ενέργεια |
|---|---|---|
| C$ | 01110$ | \(C\to0C0\) |
| 0C0$ | 01110$ | ταίριασμα 0 |
| C0$ | 1110$ | \(C\to1C1\) |
| 1C10$ | 1110$ | ταίριασμα 1 |
| C10$ | 110$ | \(C\to1\) (κέντρο) |
| 110$ | 110$ | ταίριασμα 1 |
| 10$ | 10$ | ταίριασμα 1 |
| 0$ | 0$ | ταίριασμα 0 |
| $ | $ | αποδοχή |
Η 01110 παράγεται από την 3η γραμματική.
(d) Μόνο η 2η είναι κανονική γραμματική (Τύπου 3): δεξιά γραμμική (τερματικό + το πολύ ένα μη τερματικό στο τέλος). Η 1η έχει \(A\to AA\) (δύο μη τερματικά, όχι γραμμική μορφή· η γλώσσα της είναι όμως κανονική, \((0|1)^+\)). Η 3η έχει το μη τερματικό ανάμεσα σε τερματικά και περιγράφει παλίνδρομα, που δεν είναι κανονική γλώσσα.
(e) Η 2η γραμματική: κανονική έκφραση \((0\mid1)^*\,0\). DFA με δύο καταστάσεις:
| Κατάσταση | με 0 | με 1 | Τελική |
|---|---|---|---|
| q0 (αρχή / τελευταίο ψηφίο 1) | q1 | q0 | όχι |
| q1 (τελευταίο ψηφίο 0) | q1 | q0 | ναι |
Αρχική q0, τελική q1.
(f) Καμία από τις τρεις δεν είναι LL(1):
1. \(A\to AA\mid0\mid1\): αριστερή αναδρομή, και FIRST(\(AA\))={0,1} επικαλύπτεται με τις 0, 1.
2. \(B\to0B\mid1B\mid0\): οι \(0B\) και \(0\) έχουν κοινό πρόθεμα 0 (FIRST και των δύο {0}).
3. \(C\to0C0\mid1C1\mid0\mid1\): κοινά προθέματα \(0C0\)/\(0\) και \(1C1\)/\(1\).
Μετασχηματισμός της πρώτης (απαλοιφή αριστερής αναδρομής):
\(A\to0A'\mid1A'\), \(A'\to AA'\mid\epsilon\)
Έλεγχος LL(1): FIRST(\(0A'\))={0}, FIRST(\(1A'\))={1} ξένα. Για το \(A'\): FIRST(\(AA'\))={0,1}, FOLLOW(\(A'\))=FOLLOW(\(A\))={$}· ξένα ⇒ LL(1). Ισοδύναμα, απλούστερα: \(A\to0A'\mid1A'\), \(A'\to0A'\mid1A'\mid\epsilon\) (παράγει \((0|1)^+\)).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(a) Περιβάλλοντα αναφοράς (στατικός κανόνας):
- MAIN: τοπικά {i, c, a, F}· μη τοπικά κανένα· καθολικά {i, c, a, F}.
- F: τοπικά {x, y, d, G}· μη τοπικά {i, c, a (πίνακας), F}.
- G: τοπικά {a (παράμετρος)}· μη τοπικά {x, y, d, G (από την F), i, c, F (από το MAIN)}· ο πίνακας a του MAIN κρύβεται από την τοπική a της G.
(b) Αρχικά \(a[1]=5\), \(a[2]=4\), \(i=2\), κλήση F(a[2], a[2]).
-
Κλήση με τιμή: \(x=4\), \(y=4\) (αντίγραφα), \(d=-1\), \(x=3\).
G(i): τοπικό \(a=2+(-1)=1\) (χωρίς επίδραση).G(y): τοπικό \(a=4-1=3\) (χωρίς επίδραση). \(c=x\cdot y=3\cdot4=12\). a[1]=5, a[2]=4, c=12. -
Κλήση με αναφορά: \(x\) και \(y\) είναι και τα δύο ψευδώνυμα του \(a[2]\) (ο δείκτης \(i=2\) αποτιμήθηκε στην κλήση). \(x:=x-1\) ⇒ \(a[2]=3\) (το \(y\) επίσης 3).
G(i): \(a_G\)≡\(i\) ⇒ \(i:=2-1=1\).G(y): \(a_G\)≡\(a[2]\) ⇒ \(a[2]:=3-1=2\). \(c=x\cdot y=2\cdot2=4\). a[1]=5, a[2]=2, c=4. -
Τιμή–αποτέλεσμα: \(x=4\), \(y=4\) (αντίγραφα), \(d=-1\), \(x=3\).
G(i): \(a=2\to1\), στην έξοδο \(i:=1\).G(y): \(a=y=4\to3\), στην έξοδο \(y:=3\). \(c=x\cdot y=3\cdot3=9\). Στο τέλος της F γίνεται αντιγραφή πίσω: \(x=3\) και \(y=3\) στο \(a[2]\) (διεύθυνση καθορισμένη στην κλήση, με \(i=2\)) ⇒ \(a[2]=3\). a[1]=5, a[2]=3, c=9. (Η σειρά αντιγραφής δεν έχει σημασία εδώ, γιατί και τα δύο είναι 3.) -
Κλήση με όνομα: \(x\equiv a[i]\), \(y\equiv a[i]\) με νέα αποτίμηση σε κάθε χρήση. \(d=-1\). \(x:=x-1\) ⇒ \(a[2]:=a[2]-1=3\) (με \(i=2\)).
G(i): \(a_G\equiv i\) ⇒ \(i:=i+d=1\).G(y): \(a_G\equiv y\equiv a[i]\) και τώρα \(i=1\) ⇒ \(a[1]:=a[1]+d=4\). \(c=x\cdot y=a[i]\cdot a[i]=a[1]\cdot a[1]=4\cdot4=16\). a[1]=4, a[2]=3, c=16.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(a) (πίνακες: data1 = {4,3,2,1}, data2 = {10,20,30,40})
- Γρ. 5: p1 = &data1[3] ⇒ p1 δείχνει στο 1 (*p1 = 1).
- Γρ. 6: p2 = &data2[*p1] = &data2[1] ⇒ δείχνει στο 20.
- Γρ. 7: a = *(p2+1) + 1 = data2[2] + 1 = 30 + 1 = 31.
- Γρ. 8: p1 -= 2 ⇒ δείχνει στο data1[1] = 3.
- Γρ. 9: b = p1[1] + *(p2-1) = data1[2] + data2[0] = 2 + 10 = 12.
- Γρ. 10: *p2 /= 5 ⇒ data2[1] = 20/5 = 4.
- Γρ. 11: c += *p1 + *p2 - 2 = 3 + (3 + 4 − 2) = 3 + 5 = 8.
(b) a = 31, b = 12, c = 8 (επαληθεύτηκε με πρόγραμμα).
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
(α) Με ως ορίσματα τις μεταβλητές του βρόχου (\(R=0\), \(i=1\), \(j=300\), ενώ \(i<j\): \(R\mathrel{+}=j^i\), \(i\mathrel{+}=2\), \(j\mathrel{-}=2\)):
(define (loop R i j)
(if (< i j)
(loop (+ R (expt j i)) (+ i 2) (- j 2))
R))
(loop 0 1 300)
(Python: def loop(R,i,j): return loop(R+j**i, i+2, j-2) if i<j else R, κλήση loop(0,1,300).)
(β) (if (< 4 5) 0 1) ⇒ 0. Στο cond: (< 10 9) και (< 8 7) ψευδή ⇒ else ⇒ 3.
(γ) map ⇒ (3 6 9 12 15). (fold + 0 '(1 2 3 4 5)) ⇒ 15. (fold * 1 '(1 2 3 4 5)) ⇒ 120. (sum-of-triples '(1 2 3 4 5)) ⇒ 45 (3·15).
(δ) \((\lambda x.\lambda y.\lambda z.\,x+y+z)\;4\;5\;6\to(\lambda y.\lambda z.\,4+y+z)\;5\;6\to(\lambda z.\,4+5+z)\;6\to4+5+6\to\mathbf{15}\).
(ε) Η εκφώνηση ορίζει \(sum(x{:}xs)=x+sum[x{+}1{:}xs]\). Ερμηνεύω το \([m{:}n]\) ως λίστα ακεραίων από \(m\) έως \(n\) και \(sum[m{:}n]=m+sum[m{+}1{:}n]\) με \(sum=0\) όταν \(m>n\) (αλλιώς δεν τερματίζει)· η ερμηνεία είναι αβέβαιη.
Σύμβαση: κάθε εφαρμογή κανόνα (χρήστη ή ενσωματωμένου +, *) είναι μία αναγωγή. Για \(n=10\) το άθροισμα \(S\) έχει 10 εφαρμογές του \(sum\), 10 υπολογισμούς \(m+1\), 1 τερματισμό και 10 προσθέσεις: \(3\cdot10+1=31\) αναγωγές, αποτέλεσμα 55.
- Πρόθυμη: πρώτα το όρισμα: \(sum[1{:}10]\to1+sum[2{:}10]\to\cdots\to1+(2+\cdots+(10+0))\to55\) (31), μετά \(square\,55\to55\cdot55\to3025\) (2). Σύνολο 33.
- Οκνηρή (εξωτερικότερη, χωρίς διαμοιρασμό): \(square\,(sum[1{:}10])\to sum[1{:}10]*sum[1{:}10]\) (1), το \(sum\) υπολογίζεται δύο φορές (2·31), μετά ο πολλαπλασιασμός (1) ⇒ \(3025\). Σύνολο 64.
- Οκνηρή με διαμοιρασμό (graph reduction): \(1+31+1=33\).
Η πιο αποδοτική: η πρόθυμη (και η οκνηρή με διαμοιρασμό), 33 αναγωγές· η οκνηρή χωρίς διαμοιρασμό κάνει διπλή δουλειά (64).
Θέμα 5¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
Η εκφώνηση γράφει «- 5, 12, …»: το «-» θεωρείται σημείο λίστας και όχι αρνητικό πρόσημο.
# (α) δημιουργία λίστας
nums = [5, 12, 8, 3, 25, 18, 22, 25, 30]
# (β) 7 στην αρχή, 20 στο τέλος
nums.insert(0, 7)
nums.append(20)
# (γ) διαγραφή του 8 (πρώτη εμφάνιση)
nums.remove(8)
# (δ) αύξουσα ταξινόμηση
nums.sort()
# (ε) δεύτερος και τέταρτος αριθμός (δείκτες 1 και 3)
print(nums[1], nums[3])
# (στ) πλήθος
print(len(nums))
# (ζ) μεσαίος αριθμός (για ζυγό πλήθος: ο μεσαίος της κάτω μισής)
print(nums[(len(nums) - 1) // 2])
# (η) αντικατάσταση του τελευταίου
nums[-1] = 15
Ροή τιμών: μετά το (β) [7,5,12,8,3,25,18,22,25,30,20], μετά το (γ) [7,5,12,3,25,18,22,25,30,20], μετά το (δ) [3,5,7,12,18,20,22,25,25,30]. Τυπώνονται: (ε) 5 12, (στ) 10, (ζ) το πλήθος είναι ζυγό (10): κάτω μεσαίος = nums[4] = 18, και μετά το (η) η λίστα γίνεται [3,5,7,12,18,20,22,25,25,15].