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

Μεταγραφή από τις φωτογραφίες IMG_1708.jpg, IMG_1710.jpg, IMG_1711.jpg, IMG_1712.jpg και IMG_1714.jpg. Η E81902F1-903F-4807-9CEE-5202C16D988F.jpeg είναι λύση του Θέματος 1 και δεν μεταγράφεται.

IMG_1708.jpg¶

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

ΘΕΜΑ 1 – Συντακτική Ανάλυση (25%)¶

Δίνεται η παρακάτω απλή BNF γραμματική, με τερματικά σύμβολα τα: ( ) [ ]

\[<S> ::= <S>(<S>) \mid <S>[<S>] \mid \epsilon\]

(α) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky και γιατί;

(β) Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική; Περιγράψτε τα χαρακτηριστικά των συμβολοσειρών αυτών. Δώστε σχετικά παραδείγματα, καθώς και όλα τα μικρότερα μέλη της γλώσσας με μήκος έως και 4 χαρακτήρες.

(γ) Ελέγξτε αν η συμβολοσειρά []([]()) είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ταιριάσματος – Πρόβλεψης Top-Down συντακτικής ανάλυσης.

(δ) Είναι ή όχι η γραμματική LL(1) και γιατί; Αν όχι, μετασχηματίστε την σε μια ισοδύναμη LL(1) γραμματική.

ΘΕΜΑ 2 – Λεξική Ανάλυση (15%)¶

(α) Παρουσιάστε το διάγραμμα καταστάσεων – μεταβάσεων για το πεπερασμένο αυτόματο που αναγνωρίζει όλους τους δυαδικούς αριθμούς οι οποίοι περιέχουν το πολύ τρία 1. Το \(\epsilon\) είναι αποδεκτός αριθμός.

(β) Γράψετε μια κανονική έκφραση που αντιστοιχεί στο παραπάνω αυτόματο.

ΘΕΜΑ 3 – Εμβέλεια και Μεταβίβαση Παραμέτρων (25%)¶

Δίνεται το παρακάτω πρόγραμμα σε μια γλώσσα τύπου Pascal στην οποία ισχύει ο στατικός κανόνας εμβέλειας:

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

  procedure P(x: integer; y: integer);
  begin
    a[1] := a[1] + 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: a_1 a_2

Πίνακας αποτελεσμάτων

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

(a) Ποια είναι τα περιβάλλοντα αναφοράς όλων των τμημάτων του προγράμματος;

(b) Ποιες τιμές θα τυπωθούν στο τέλος για τα a[1] και a[2] στις παρακάτω περιπτώσεις μεταβίβασης παραμέτρων; Συμπληρώστε τον πίνακα και παρουσιάστε συνοπτικά τους υπολογισμούς σας.

Κλήση με τιμή (call by value)
Κλήση με αναφορά (call by reference)
Κλήση με τιμή-αποτέλεσμα (call by value) > [sic: στο 3 γράφεται «call by value», ενώ ο όρος είναι value-result]
Κλήση με όνομα (call by name)

ΘΕΜΑ 4 – Μεταβλητές και Διαχείριση Μνήμης (10%)¶

Ποιες θα είναι οι τελικές τιμές του πίνακα data που θα τυπώσει το παρακάτω πρόγραμμα. Αναφέρετε και εξηγήστε τους υπολογισμούς σας.

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

Σημείωση: οι γραμμές 8 (printf) και 9 (}) του κώδικα δεν φαίνονται στο IMG_1708.jpg· μεταγράφονται από το IMG_1711.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) Εκτυπώστε όλους τους φοιτητές που έχουν Μέσο Όρο ≥ 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 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 δέχεται αριθμητικές τιμές.

IMG_1710.jpg¶

Συμπλήρωμα για το Θέμα 3 και το Θέμα 4 (βλ. επίσης IMG_1708.jpg και IMG_1711.jpg). Ο κώδικας και ο πίνακας του Θέματος 3 συμφωνούν με τις παραπάνω μεταγραφές.

IMG_1711.jpg¶

Επικαλύπτει τα IMG_1710.jpg και IMG_1708.jpg στο Θέμα 3 (end. και πίνακας) και στο Θέμα 4 (γραμμές 8–9). Τα Θέματα 5 και 6 μεταγράφονται ήδη παραπάνω.

IMG_1712.jpg¶

Επικαλύπτει τα IMG_1711.jpg και IMG_1714.jpg στο Θέμα 5 (a)–(f) και στο Θέμα 6 (α)–(γ). Οι συνδεδεμένες μεταγραφές βρίσκονται στην ενότητα του IMG_1708.jpg παραπάνω.

IMG_1714.jpg¶

Επικαλύπτει το IMG_1712.jpg στο Θέμα 6 (γ)–(στ). Οι συνδεδεμένες μεταγραφές βρίσκονται στην ενότητα του IMG_1708.jpg παραπάνω.

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης Θέματος 1 με χειρόγραφες απαντήσεις φοιτητή (E81902F1-903F-4807-9CEE-5202C16D988F.jpeg)

Προσοχή

Η λύση καλύπτει μόνο το ερώτημα (β) του Θέματος 1· δεν περιέχει απάντηση στο ερώτημα (α) (τερματικά και μη τερματικά σύμβολα). Η λύση σταματά στο βήμα 10 και δεν δίνει την τελική έκβαση της ανάλυσης (αποδοχή ή απόρριψη της συμβολοσειράς). Τα βήματα πρόβλεψης χρησιμοποιούν τον κανόνα <S> ::= <S>(<S>), που ξεκινά με το ίδιο μη τερματικό σύμβολο (αριστερή αναδρομή)· τα βήματα πρέπει να ελεγχθούν.

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

Λύση του Θέματος 1 από φωτογραφία με χειρόγραφες απαντήσεις φοιτητή. Η λύση δεν έχει επαληθευτεί από τον διδάσκοντα.

E81902F1-903F-4807-9CEE-5202C16D988F.jpeg¶

ΣΩΣΤΗ ΛΥΣΗ Θ1 ΙΟΥΝΙΟΣ 2025¶

Βήμα	Στοίβα	Είσοδος	Πράξη
0	\(<S>\)	`][][())` EOF	Πρόβλεψη \(<S> ::= <S>(<S>)\)
1	`)<S>(<S>`	`][][())` EOF	Πρόβλεψη \(<S> ::= <S>[<S>]\)
2	`)<S>(]<S>[<S>`	`][][())` EOF	Πρόβλεψη \(<S> ::= \epsilon\)
3	`)<S>(]<S>[`	`][][())` EOF	Ταίριασμα
4	`)<S>(]<S>`	`[][())` EOF	Πρόβλεψη \(<S> ::= \epsilon\)
5	`)<S>(]`	`[][())` EOF	Ταίριασμα
6	`)<S>(`	`[())` EOF	Ταίριασμα
7	`)<S>`	`())` EOF	Πρόβλεψη \(<S> ::= <S>(<S>)\)
8	`))<S>(<S>`	`())` EOF	Πρόβλεψη \(<S> ::= <S>[<S>]\)
9	`))<S>(]<S>[<S>`	`())` EOF	Πρόβλεψη \(<S> ::= \epsilon\)
10	`))<S>(]<S>[`	`())` EOF	Ταίριασμα

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

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

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