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

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

Μεταγραφή από τις φωτογραφίες IMG_1698.jpg, IMG_1702.jpg, 9E8737A0-5219-4CED-AC12-84EE810D778A.jpg και IMG_1704.jpg.

IMG_1698.jpg

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

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

Δίνεται η παρακάτω BNF γραμματική, με τερματικά σύμβολα τα: a b c d

\[<S> ::= <A><B><C><S> \mid d$$ $$<A> ::= a<A> \mid \epsilon$$ $$<B> ::= b<B> \mid \epsilon$$ $$<C> ::= c\]

(a) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky; Είναι ή όχι η γραμματική LL(1); Αιτιολογήστε τις απαντήσεις σας.

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

(c) Ελέγξτε αν η συμβολοσειρά acd είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ολίσθησης – Ελάττωσης Bottom-Up συντακτικής ανάλυσης.

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

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

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

IMG_1702.jpg

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

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

program MAIN;
var a, b, c: integer;
procedure F(x, y, z: integer);
begin
    y:= y + 1;
    c:= x + z + 1;
    z:= z + c;
end;

BEGIN
    a:= 30;
    b:= 20;
    F(a+b, a, b);
    writeln('a=', a); writeln('b=', b); writeln('c=', c);
END.

[Σχήμα: πλαίσιο με τίτλο «Μορφή εξόδου του προγράμματος για τις τρεις εντολές writeln»: a=V1, b=V2, c=V3]

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

(b) Ποιες τιμές (V1, V2, V3) θα τυπωθούν με την εντολή writeln, εφόσον η διαδικασία F καλείται με τις παρακάτω περιπτώσεις τρόπου μεταβίβασης παραμέτρων; Εξηγήστε σύντομα τις διαδικασίες υπολογισμού σε όλες τις περιπτώσεις.

  1. Όλες οι παράμετροι μεταβιβάζονται με κλήση με τιμή (call by value).
  2. Το x μεταβιβάζεται με κλήση με τιμή και οι y και z με κλήση με αναφορά (call by reference).
  3. Το x μεταβιβάζεται με κλήση με τιμή και οι y και z με τιμή – αποτέλεσμα (call by value-result).
  4. Όλες οι παράμετροι μεταβιβάζονται με κλήση με όνομα (call by name).

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

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

9E8737A0-5219-4CED-AC12-84EE810D778A.jpg

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

Δίνεται το παρακάτω τμήμα προγράμματος σε γλώσσα C:

Γραμμή Κώδικας
1 int main()
2 {
3 int data[5] = {50, 40, 30, 20, 10};
4 int *p;
5 p = &data[3];
6 *(p-1) = (*(p-2))--;
7 *p -= 1;
8 p[1] = 33;
9 p-=2;
10 *(p-1) = (*p > 10)? *p-10: *p+10;
11 for (int i=0; i<5; i++) printf("%d\n", data[i]);
12 return 0;
13 }

(a) Εξηγήστε συνοπτικά και γραμμή-γραμμή, για τις γραμμές 5-10, τη λειτουργία του παραπάνω προγράμματος.

(b) Τι θα τυπωθεί με την εκτέλεση του προγράμματος, δλδ ποιες θα είναι οι τελικές τιμές του πίνακα data;

IMG_1704.jpg

ΘΕΜΑ 5 – Python (15%)

Γράψτε ένα πρόγραμμα σε Python που θα διαχειρίζεται και θα επεξεργάζεται μια λίστα από ακέραιους αριθμούς. Πιο συγκεκριμένα, εισάγετε 10 ακέραιους αριθμούς και αποθηκεύστε τους σε μια λίστα. Το πρόγραμμα θα πρέπει να εκτελεί τις παρακάτω λειτουργίες:

(1) Εμφανίστε την αρχική λίστα των αριθμών. (2) Βρείτε και εμφανίστε τον μέγιστο και τον ελάχιστο αριθμό της λίστας. (3) Υπολογίστε και εμφανίστε τον μέσο όρο των αριθμών της λίστας. (4) Αντιστρέψτε τη λίστα και εμφανίστε την αντεστραμμένη λίστα. (5) Δημιουργήστε μια νέα λίστα που περιέχει κάθε αριθμό της αρχικής διπλασιασμένο και εμφανίστε την. (6) Ταξινομήστε την αρχική λίστα σε αύξουσα σειρά και εμφανίστε την.

ΘΕΜΑ 6 – Functional Programming και Γλώσσες ΒΔ (20%)

(α) Κάνοντας χρήση της Python lambda map function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα των κύβων των ακεραίων αριθμών μιας λίστας L.

(β) Κάνοντας χρήση της Python lambda reduce function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα των τετραγώνων των ακεραίων αριθμών μιας λίστας L.

(γ) Τι τυπώνει το παρακάτω πρόγραμμα;

import functools
numbers = [1, 2, 3]
result= functools.reduce(lambda x, y: x * y, numbers)
print(result)

(δ) Τι αλλαγές πρέπει να κάνω στο παραπάνω πρόγραμμα, ώστε να τυπωθεί το γινόμενο των τετραγώνων;

(ε) Γράψτε πρόγραμμα που θα διαβάζει τους ακέραιους αριθμούς μιας λίστας της αρεσκείας σας και θα τυπώνει μόνο αυτούς που είναι ζυγοί αριθμοί κάνοντας εφαρμογή της συνάρτησης map(). Τι θα πάρετε σαν αποτέλεσμα στην έξοδο; Αν αντί για map() χρησιμοποιήσετε τη συνάρτηση filter(), πώς θα τροποποιηθεί το αποτέλεσμα;

(στ) Έστω μία βάση δεδομένων με δύο πίνακες (σχέσεις) R(A,B,C,D) και S(B, E, F, H) οι οποίοι συσχετίζονται στην κοινή στήλη (γνώρισμα) B και έστω ο παρακάτω κώδικας σε γλώσσα SQL:

Select A
From R,S
Where R.B=S.B and C<100

Περιγράψτε όλα τα ενδιάμεσα πλάνα εκτέλεσης που παράγει ο SQL Compiler για το παραπάνω ερώτημα μέχρι την εύρεση του τελικού πλάνου που είναι και το βέλτιστο. Θυμίζουμε την ύπαρξη ενσωματωμένου βελτιστοποιητή (embedded optimizer) ο οποίος μετατρέπει τον SQL κώδικα σε ισοδύναμη μορφή σχεσιακής άλγεβρας και στη συνέχεια εφαρμόζει τους γνωστούς ευριστικούς κανόνες βελτιστοποίησης. Σημειώνουμε ότι η στήλη C δέχεται αριθμητικές τιμές.

Επιπλέον πηγές (αντίγραφα της ίδιας εξέτασης, χωρίς νέο κείμενο): IMG_1703.jpg, IMG_1706.jpg, 899A29B5-D7E6-4113-95C1-983B3F07918F.jpg, Screenshot_20240916_214142_Adobe_Acrobat.jpg/.png, Screenshot_20240916_214153_Adobe_Acrobat.jpg, Screenshot_20240916_214157_Adobe_Acrobat.jpg, Screenshot_2024-06-18-19-16-30-673_com.discord-edit.jpg, themata_2022-25/Themata_2024.pdf (ανακατασκευή σε κείμενο).

Λύσεις (⚪ AI, μη επαληθευμένο)

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

Προσοχή

Θέμα 1 (α): η λύση δεν δίνει συμπέρασμα για το αν η γραμματική είναι LL(1). Θέμα 1 (γ): η ανάλυση bottom-up είναι συνοπτική, χωρίς πλήρη στοίβα σε κάθε βήμα. Θέμα 2: η περιγραφή του αυτομάτου δεν ορίζει τις μεταβάσεις για όλες τις καταστάσεις (λείπουν οι μεταβάσεις με 1 από τις q1, q2, q3). Θέμα 4: η λύση αντιστοιχεί στο (*(p-2))--, ενώ η εκφώνηση γράφει (*(p-2))++. Με τον κώδικα της εκφώνησης οι τελικές τιμές είναι data = {31, 41, 40, 19, 33}, όχι {29, 39, 40, 19, 33}. Θέμα 5: η λύση είναι περιγραφή των πράξεων χωρίς κώδικα ή τιμές εξόδου. Θέμα 6: το ερώτημα (γ) (γινόμενο της λίστας [1, 2, 3]) και το (δ) δεν καλύπτονται από τη λύση. Η λύση για το SQL του παλιού αρχείου δεν μεταφέρθηκε, γιατί το ερώτημα δεν υπάρχει στη συνεδρία.

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

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

  1. Ιεραρχία Chomsky: Τύπου 2 (Context-Free Grammar).
  2. LL(1) Έλεγχος: Εξέταση συνόλων First και Follow.
  3. Bottom-Up Parsing του string acd:
  4. Είσοδος: a c d $

  5. Ολίσθηση a, Αναγωγή \(a \to A\) (ή \(\epsilon \to A\)), Shift c, Reduce \(c \to B\), Shift c, Reduce \(c \to C\), Shift d, Reduce \(\dots \to S\), Accept!

  6. Γλώσσα: Δυαδικοί αριθμοί όπου κάθε 1 ακολουθείται από ακριβώς ένα 0, εκτός από το τελευταίο 1 που ακολουθείται από τουλάχιστον δύο 0.

  7. Κανονική έκφραση: $\(0^* (10)^* 100 0^*\)$
  8. DFA:
  9. \(q_0\) (αρχική, διαβάζει αρχικά μηδενικά \(0^*\)).
  10. Διαβάζει 1 \(\to q_1\).
  11. Από \(q_1\) με 0 \(\to q_2\) (διαβάστηκε '10').
  12. Από \(q_2\) με 0 \(\to q_3\) (διαβάστηκε '100' - τελική αποδεκτή κατάσταση).

  13. Στο \(q_3\) με 0 παραμένει στο \(q_3\).

  14. Τελικές τιμές πίνακα data: data[0] = 29, data[1] = 39, data[2] = 40, data[3] = 19, data[4] = 33.

Πρόγραμμα εισαγωγής 10 ακεραίων και υπολογισμοί: max, min, μέσος όρος, αντιστροφή λίστας, διπλασιασμός στοιχείων με list comprehension ([2*x for x in lst]), ταξινόμηση.

  • Lambda map για άθροισμα κύβων: sum(map(lambda x: x**3, L)).
  • Lambda reduce για άθροισμα τετραγώνων: reduce(lambda a, b: a + b**2, [0] + L).

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

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