Μετάβαση στο περιεχόμενο

Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Ιούνιος 2025 — Παραλλαγή Α

Μεταγραφή από τις φωτογραφίες 1000000765.jpg και 1000000764.jpg· τα 1.png, 2.png, content.png είναι αντίγραφα ή μερικές φωτογραφίες και το Themata_2025.pdf είναι ανακατασκευή.

1000000765.jpg

ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΚΑΙ ΜΕΤΑΦΡΑΣΤΩΝ Εξέταση Περιόδου Ιουνίου 2025

ΘΕΜΑ 1 – Συντακτική Ανάλυση (25%) Δίνεται η παρακάτω απλή BNF γραμματική, με τερματικά σύμβολα τα: ( ) [ ] ::= () | [] | \(\epsilon\)

(a) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky και γιατί; (b) Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική; Περιγράψτε τα χαρακτηριστικά των συμβολοσειρών αυτών. Δώστε σχετικά παραδείγματα, καθώς και όλα τα μικρότερα μέλη της γλώσσας με μήκος έως και 4 χαρακτήρες. (c) Ελέγξτε αν η συμβολοσειρά είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ταιριάσματος – Πρόβλεψης Top-Down συντακτικής ανάλυσης. (d) Είναι ή όχι η γραμματική LL(1) και γιατί; Αν όχι, μετασχηματίστε την σε μια ισοδύναμη LL(1) γραμματική.

ΘΕΜΑ 2 – Λεξική Ανάλυση (15%) (a) Παρουσιάστε το διάγραμμα καταστάσεων – μεταβάσεων για το πεπερασμένο αυτόματο που αναγνωρίζει όλους τους δυαδικούς αριθμούς οι οποίοι περιέχουν το πολύ τρία 1. Το \(\epsilon\) είναι αποδεκτός αριθμός. (b) Γράψετε μια κανονική έκφραση που αντιστοιχεί στο παραπάνω αυτόματο.

ΘΕΜΑ 3 – Εμβέλεια και Μεταβίβαση Παραμέτρων (25%) Δίνεται το παρακάτω πρόγραμμα σε μια γλώσσα τύπου Pascal στην οποία ισχύει ο στατικός κανόνας εμβέλειας:

program MAIN;
  var a: array[1..2] of integer; i, j: integer;

  procedure P(x: integer; y: integer);
  begin
    a[i] := a[i] + x;
    i := 2;
    x := x + 1;
    j := 1;
    y := y + x;
  end;

begin
  a[1] := 3; a[2] := 5;
  i := 1; j := 2;
  P(a[i], a[j]);
  writeln('output: ', a[1], ' ', a[2]);
end.

Μορφή εξόδου του προγράμματος:

[Σχήμα: Πλαίσιο που γράφει "output: a1 a2"]

Πίνακας αποτελεσμάτων | Κλήση με | a[1] | a[2] | | --- | --- | --- | | 1. τιμή | | | | 2. αναφορά | | | | 3. τιμή-αποτέλεσμα | | | | 4. όνομα | | |

(a) Ποια είναι τα περιβάλλοντα αναφοράς όλων των τμημάτων του προγράμματος; (b) Ποιες τιμές θα τυπωθούν στο τέλος για τα a[1] και a[2] στις παρακάτω περιπτώσεις μεταβίβασης παραμέτρων; Συμπληρώστε τον πίνακα και παρουσιάστε συνοπτικά τους υπολογισμούς σας. 1. Κλήση με τιμή (call by value) 2. Κλήση με αναφορά (call by reference) 3. Κλήση με τιμή-αποτέλεσμα (call by value) 4. Κλήση με όνομα (call by name)

ΘΕΜΑ 4 – Μεταβλητές και Διαχείριση Μνήμης (10%) Ποιες θα είναι οι τελικές τιμές του πίνακα data που θα τυπώσει το παρακάτω πρόγραμμα; Αναφέρετε και εξηγήστε τους υπολογισμούς σας.

| 1 | void main() { | | 2 | int *p, data[] = {2, 4, 6}; | | 3 | p = &data[1]; | | 4 | *(p+1) -= 1; | | 5 | p = &p[1]; | | 6 | *(p-1) -= 1; | | 7 | p += ((p-2))++; | | 8 | printf("%d %d %d\n", data[0], data[1], data[2]); | | 9 | } |

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

1000000764.jpg

ΘΕΜΑ 5 – Python (15%) Δίνεται η παρακάτω λίστα που περιέχει τα στοιχεία φοιτητών και τους βαθμούς τους σε δύο μαθήματα: 

students = [
    {'Όνομα': 'Γιώργος', 'Μάθημα1': 7.5, 'Μάθημα2': 8.0},
    {'Όνομα': 'Μαρία', 'Μάθημα1': 9.0, 'Μάθημα2': 9.5},
    {'Όνομα': 'Κώστας', 'Μάθημα1': 6.0, 'Μάθημα2': 5.5},
    {'Όνομα': 'Άννα', 'Μάθημα1': 8.5, 'Μάθημα2': 9.0},
    {'Όνομα': 'Πέτρος', 'Μάθημα1': 5.0, 'Μάθημα2': 6.5},
]
(a) Χρησιμοποιώντας κατάλληλο βρόχο επανάληψης, εκτυπώστε για κάθε φοιτητή τα εξής στοιχεία: Όνομα — Μέσος Όρος Βαθμών. (b) Δημιουργήστε ένα DataFrame από τη λίστα students, με τη βιβλιοθήκη Pandas. (c) Προσθέστε μία νέα στήλη στο DataFrame με όνομα Μέσος_Όρος, η οποία θα περιέχει το μέσο όρο των στηλών Μάθημα1 και Μάθημα2. (d) Εκτυπώστε όλους τους φοιτητές που έχουν Μέσο Όρο \(\ge\) 8. (e) Ταξινομήστε το DataFrame κατά τη στήλη Μέσος_Όρος σε φθίνουσα σειρά και εκτυπώστε το αποτέλεσμα. (f) Τέλος, διαγράψτε τη στήλη Μάθημα2 από το DataFrame.

ΘΕΜΑ 6 – Functional Programming και Γλώσσες ΒΔ (20%) (α) Κάνοντας χρήση της Python lambda map function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα της k-στής δύναμης των ακεραίων αριθμών μιας λίστας L, όπου το k το δίνει ο χρήστης. (β) Κάνοντας χρήση της Python lambda reduce function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα της k-στής δύναμης των ακεραίων αριθμών μιας λίστας L, όπου το k το δίνει ο χρήστης. (γ) Τι τυπώνει το παρακάτω πρόγραμμα; 

import functools
numbers = [1, 2, 3, 4]
result = functools.reduce(lambda x, y: x * y, numbers)
print(result)
(δ) Τι αλλαγές πρέπει να κάνω στο παραπάνω πρόγραμμα, ώστε να τυπωθεί το γινόμενο των k-στών δυνάμεων; Η τιμή του k δίνεται από τον χρήστη. (ε) Συμπληρώστε όλα τα στάδια αποτίμησης της παρακάτω έκφρασης σε \(\lambda\)-λογισμό: $\((\lambda x.\ \lambda y.\ \lambda z.\ x^3 + y^3 + z^3)\ 3\ 2\ 1\)$ (στ) Έστω μία βάση δεδομένων με δύο πίνακες (σχέσεις) R1(A,B,C,D) και R2(B,E,F,H) οι οποίοι συσχετίζονται στην κοινή στήλη (γνώρισμα) B και έστω ο παρακάτω κώδικας σε γλώσσα SQL: 
Select A, B, E
From R1, R2
Where R1.B=R2.B and C<200
Περιγράψτε όλα τα ενδιάμεσα πλάνα εκτέλεσης που παράγει ο SQL Compiler για το παραπάνω ερώτημα μέχρι την εύρεση του τελικού πλάνου που είναι και το βέλτιστο. Θυμίζουμε την ύπαρξη ενσωματωμένου βελτιστοποιητή (embedded optimizer) ο οποίος μετατρέπει τον SQL κώδικα σε ισοδύναμη μορφή σχεσιακής άλγεβρας και στη συνέχεια εφαρμόζει τους γνωστούς ευριστικούς κανόνες βελτιστοποίησης. Σημειώνουμε ότι η στήλη C δέχεται αριθμητικές τιμές.

ΚΑΛΗ ΕΠΙΤΥΧΙΑ!!!

  • Τα θέματα επιστρέφονται μαζί με το γραπτό
  • Απαντήστε σε όλα τα θέματα
  • Η διάρκεια της εξέτασης είναι 2,5 ώρες
Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)

Προσοχή

Θέμα 1 (γ): η λύση ελέγχει τη συμβολοσειρά [][()], ενώ η μεταγραφή της εκφώνησης γράφει [][([()])· να ελεγχθεί στη φωτογραφία 1000000765.jpg. Θέμα 4: η λύση υπολογίζει με += 1 στη γραμμή *(p+1), ενώ η εκφώνηση γράφει *(p+1) -= 1 και *(p-1) -= 1. Με τον κώδικα της εκφώνησης οι τελικές τιμές είναι data[0] = 3, data[1] = 3, data[2] = 7 (και όχι 9 όπως στη λύση). Θέμα 6 (α): το reduce της λύσης εφαρμόζεται στη λίστα numbers και όχι στις k-στές δυνάμεις, άρα δεν υπολογίζει το άθροισμα των k-στών δυνάμεων που ζητά η εκφώνηση. Θέμα 6: τα υποκεφάλαια (β) και (γ) της λύσης αντιστοιχούν στα ερωτήματα (γ) και (ε) της εκφώνησης. Τα ερωτήματα (β) (reduce για k-στές δυνάμεις), (δ) (αλλαγές στο πρόγραμμα) και (στ) (SQL) δεν καλύπτονται από τη λύση. Θέμα 3 και Θέμα 5 της εκφώνησης δεν καλύπτονται: η λύση που υπήρχε στο παλιό αρχείο αφορά άλλο πρόγραμμα ή άλλα δεδομένα και δεν μεταφέρθηκε.

Λύσεις — Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Ιούνιος 2025 — Παραλλαγή Α

Λύσεις που μεταφέρθηκαν από το παλιό συγκεντρωτικό αρχείο. Δεν έχουν επαληθευτεί· οι ασυμφωνίες με την εκφώνηση σημειώνονται στα warnings του αρχείου.

(α) Τύπος στην Ιεραρχία Chomsky: - Απάντηση: Η γραμματική είναι Τύπου 2 (Context-Free Grammar / Γραμματική Χωρίς Συμφραζόμενα). - Αιτιολόγηση: Στην αριστερή πλευρά κάθε κανόνα παραγωγής υπάρχει ακριβώς ένα μη-τερματικό σύμβολο (\(\langle S \rangle\)), ενώ στη δεξιά πλευρά υπάρχει οποιαδήποτε συμβολοσειρά αποτελούμενη από τερματικά και μη-τερματικά σύμβολα (συμπεριλαμβανομένου του κενού \(\epsilon\)). Δεν είναι Τύπου 3 (Κανονική) διότι δεν είναι δεξιά ούτε αριστερά γραμμική (έχει παρενθέσεις που κλείνουν και φωλιάζουν αναδρομικά).

(β) Είδος Συμβολοσειρών & Μικρότερα Μέλη: - Περιγραφή Γλώσσας: Παράγει όλες τις ισοζυγισμένες και ορθά φωλιασμένες ακολουθίες στρογγυλών () και τετράγωνων [] παρενθέσεων (η γνωστή γλώσσα Dyck 2 τύπων παρενθέσεων \(D_2\)). - Μικρότερα σε μήκος μέλη (\(\le 4\) χαρακτήρες): - Μήκος 0: \(\epsilon\) - Μήκος 2: (), [] - Μήκος 4: ()(), [][], ()[], [](), (()), [[]], ([]), [()]

(γ) Έλεγχος Συμβολοσειράς [][()] μέσω Στοίβας Ολίσθησης - Ελάττωσης (Bottom-Up Shift-Reduce): - Θεωρούμε είσοδο [][()]$. Επειδή \(\langle S \rangle \to \epsilon\), μπορούμε να εισάγουμε αναγωγές κενού (ή να αναγνωρίσουμε \(S \to S[S]\) και \(S \to S(S)\)): 1. Αρχική κατάσταση: Στοίβα: $, Είσοδος: [][()]$ 2. Αναγωγή: \(\epsilon \to S \implies\) Στοίβα: $ S 3. Ολίσθηση (Shift) [: Στοίβα: $ S [ 4. Αναγωγή: \(\epsilon \to S \implies\) Στοίβα: $ S [ S 5. Ολίσθηση (Shift) ]: Στοίβα: $ S [ S ] 6. Ελάττωση (Reduce) \(S[S] \to S \implies\) Στοίβα: $ S 7. Ολίσθηση (Shift) [: Στοίβα: $ S [ 8. Ολίσθηση (Shift) (: Στοίβα: $ S [ ( 9. Αναγωγή: \(\epsilon \to S \implies\) Στοίβα: $ S [ ( S 10. Ολίσθηση (Shift) ): Στοίβα: $ S [ ( S ) 11. Ελάττωση (Reduce) \(S(S) \to S \implies\) Στοίβα: $ S [ S 12. Ολίσθηση (Shift) ]: Στοίβα: $ S [ S ] 13. Ελάττωση (Reduce) \(S[S] \to S \implies\) Στοίβα: $ S 14. Είσοδος $: Αποδοχή (Accept)! Η συμβολοσειρά ανήκει στη γλώσσα.

(δ) Είναι η γραμματική LL(1); Μετασχηματισμός σε LL(1): - Έλεγχος LL(1): ΟΧΙ, δεν είναι LL(1). - Αιτιολόγηση: Περιέχει άμεση αριστερή αναδρομή (οι κανόνες ξεκινούν με \(\langle S \rangle\)), γεγονός που οδηγεί σε άπειρη αναδρομή σε LL(1) αναλυτή. Επιπλέον, είναι ασαφής (ambiguous). - Μετασχηματισμός σε LL(1): Εξαλείφουμε την αριστερή αναδρομή παράγοντας το πρώτο σύμβολο και το υπόλοιπο της ουράς: $\(S \to (S) S \mid [S] S \mid \epsilon\)$ - Υπολογισμός συνόλων: - \(\text{FIRST}((S)S) = \{ ( \}\) - \(\text{FIRST}([S]S) = \{ [ \}\) - \(\text{FIRST}(\epsilon) = \{ \epsilon \}\) - \(\text{FOLLOW}(S) = \{ ), ], \$ \}\) - Τα \(\text{FIRST}\) σύνολα των εναλλακτικών είναι ξένα μεταξύ τους, και \(\text{FIRST} \cap \text{FOLLOW} = \emptyset\). Συνεπώς, η νέα γραμματική είναι LL(1).

(α) Πεπερασμένο Αυτόματο (DFA) για δυαδικούς αριθμούς με το πολύ τρία '1' (0 έως 3 άσσους): - Καταστάσεις: \(q_0, q_1, q_2, q_3\) (αποδεκτές καταστάσεις που καταμετρούν 0, 1, 2, 3 άσσους) και \(q_4\) (κατάσταση παγίδα / dead state για \(\ge 4\) άσσους). - Αρχική κατάσταση: \(q_0\). - Τελικές καταστάσεις: \(F = \{q_0, q_1, q_2, q_3\}\). - Μεταβάσεις: - \(\delta(q_0, 0) = q_0, \quad \delta(q_0, 1) = q_1\) - \(\delta(q_1, 0) = q_1, \quad \delta(q_1, 1) = q_2\) - \(\delta(q_2, 0) = q_2, \quad \delta(q_2, 1) = q_3\) - \(\delta(q_3, 0) = q_3, \quad \delta(q_3, 1) = q_4\) - \(\delta(q_4, 0) = q_4, \quad \delta(q_4, 1) = q_4\)

(β) Κανονική Έκφραση (Regular Expression): $\(0^* (1 0^* + \epsilon) (1 0^* + \epsilon) (1 0^* + \epsilon)\)$ ή ισοδύναμα: $\(0^* (\epsilon \mid 1) 0^* (\epsilon \mid 1) 0^* (\epsilon \mid 1) 0^*\)$

Ανάλυση γραμμή-γραμμή: 1. p = &data[1];: Ο δείκτης p δείχνει στο στοιχείο data[1] (τιμή 4). 2. *(p+1) += 1;: Το p+1 δείχνει στο data[2]. Η τιμή του αυξάνεται κατά 1: data[2] = 6 + 1 = 7. 3. p = &p[1];: Ισοδύναμο με p = p + 1. Ο δείκτης p πλέον δείχνει στο data[2]. 4. *(p-1) -= 1;: Το p-1 δείχνει στο data[1]. Η τιμή του μειώνεται κατά 1: data[1] = 4 - 1 = 3. 5. *p += (*(p-2))++;: - Το p-2 δείχνει στο data[0] (τρέχουσα τιμή 2). - Λόγω του μετα-αυξητικού τελεστή ++, διαβάζεται πρώτα η παλιά τιμή (2) για την πρόσθεση: *p += 2 \(\implies\) data[2] = 7 + 2 = 9. - Στη συνέχεια, αυξάνεται το data[0]: data[0] = 2 + 1 = 3.

Τελικές τιμές πίνακα data: - data[0] = 3 - data[1] = 3 - data[2] = 9

(α) Lambda Map & Reduce: - Υπολογισμός \(k\)-οστών δυνάμεων: 

powers = list(map(lambda x: x**k, numbers))
- Άθροιση λίστας με reduce: 
from functools import reduce
total = reduce(lambda a, b: a + b, numbers)

(β) Αποτέλεσμα Εκτέλεσης functools.reduce: 

import functools
numbers = [1, 2, 3, 4]
result = functools.reduce(lambda x, y: x * y, numbers)
print(result)
- Βήμα 1: (1 * 2) = 2 - Βήμα 2: (2 * 3) = 6 - Βήμα 3: (6 * 4) = 24 - Τυπώνει: 24.

(γ) \(\lambda\)-Λογισμός (\(\ eta\)-Reductions): $\((\lambda x. \lambda y. \lambda z. x^3 + y^3 + z^3) \; 3 \; 2 \; 1\)$ 1. Αντικατάσταση \(x = 3\): $\((\lambda y. \lambda z. 3^3 + y^3 + z^3) \; 2 \; 1 = (\lambda y. \lambda z. 27 + y^3 + z^3) \; 2 \; 1\)$ 2. Αντικατάσταση \(y = 2\): $\((\lambda z. 27 + 2^3 + z^3) \; 1 = (\lambda z. 27 + 8 + z^3) \; 1 = (\lambda z. 35 + z^3) \; 1\)$ 3. Αντικατάσταση \(z = 1\): $\(35 + 1^3 = 35 + 1 = 36\)$ - Τελικό αποτέλεσμα: 36.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή