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

Μεταγραφή από τις φωτογραφίες IMG_1686.jpg, IMG_1689.jpg, IMG_1692.jpg, IMG_1694.jpg και IMG_1695.jpg.

IMG_1686.jpg¶

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

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

Δίνεται η παρακάτω BNF γραμματική, τμήμα της περιγραφής του συντακτικού μιας γλώσσας προγραμματισμού. Τα τερματικά σύμβολα της γραμματικής είναι τα: int float id , ; ένας χαρακτήρας κενού

<S> ::= int<κενό>id<A> | float<κενό>id<A>
<A> ::= ,<κενό>id<A> | ;
<κενό> ::= ένας χαρακτήρας κενού (μπορείτε να τον συμβολίζετε με _ )

(a) Να περιγράψετε τις κατασκευές που παράγονται από τη γραμματική. Τι θα μπορούσε να περιγράψει στη γλώσσα C η παραπάνω γραμματική, ως τμήμα της συνολικής γραμματικής της γλώσσας; Παρουσιάστε μερικά παραδείγματα νόμιμων εκφράσεων της γλώσσας. (b) Είναι LL(1) η γραμματική; Αιτιολογήστε την απάντησή σας. (c) Είναι το int m, p; μέλος της γλώσσας; Απαντήστε παρουσιάζοντας τη Στοίβα Ολίσθησης – Ελάττωση Bottom-Up συντακτικής ανάλυσης για το string. (d) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky; Αιτιολογήστε την απάντησή σας. (e) Μπορείτε να φτιάξετε μια κανονική έκφραση αντιστοιχη της γραμματικής και γιατί; Αν ναι, παρουσιάστε την. (f) Επιπλέον, υπάρχει ντετερμινιστικό πεπερασμένο αυτόματο αντιστοιχο της κανονικής έκφρασης; Αν ναι, παρουσιάστε το διάγραμμα καταστάσεων – μεταβάσεων του αυτόματου.

IMG_1689.jpg¶

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

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

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

Εξηγήστε γραμμή-γραμμή, για τις γραμμές 3-11, τους ορισμούς και τη λειτουργία του παραπάνω προγράμματος.
Τι θα τυπωθεί με την εκτέλεση του προγράμματος, δηλαδή ποιες θα είναι οι τελικές τιμές του πίνακα data;

IMG_1692.jpg¶

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

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

program MAIN;
var n: integer;
var A: array [1..5] of integer;
procedure F(k, b: integer);
begin
  writeln(k);
  n:= n + 1;
  writeln(k);
  k:= k + 4;
  writeln(n);
  b:= b + 5;
end;
BEGIN
  A[1]:= 10; A[2]:= 20; A[3]:= 30; A[4]:= 40; A[5]:= 50;
  n:= 1;
  F(n, a[n+2]);
  writeln(n);
  writeln(A[1], ' ', A[2], ' ', A[3], ' ', A[4], ' ', A[5]);
END.

[Σχήμα: πλαίσιο με τις ετικέτες X1, X2, X3, X4 σε στήλη και X5, X6, X7, X8, X9 σε γραμμή. Λεζάντα: «Μορφή εξόδου του προγράμματος για τις πέντε εντολές writeln.»]

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

IMG_1694.jpg¶

ΘΕΜΑ 4 – Functional Programming (20%)¶

(a) Είναι γνωστό ότι στις συναρτησιακές γλώσσες, η αναδρομή αντικαθιστά την επανάληψη. Κάντε ακριβώς το ίδιο (σώμα αναδρομικής συνάρτησης και πρώτη κλήση) για τον παρακάτω βρόχο (η εντολή j^2i σημαίνει ύψωση της μεταβλητής j σε δύναμη με εκθέτη 2*i):

K := 0; i := 0; j := 80;
while i < j do
    K := K + j^2i; i := i + 3;
            j := j - 3
end while
return K

(b) Με τι θα συμπληρώνατε τις αποτιμήσεις ?₁ και ?₂ των παρακάτω εκφράσεων συνθήκης σε γλώσσα scheme:

(if (< 4 5) 9 10) ⇒ ?₁
(cond
  ((< 12 11) 10)
  ((< 10 9) 11)
  (else 12)) ⇒ ?₂

(c) Έστω σε Lisp οι παρακάτω Map/Fold (Reduce) high-order functions:

(map (lambda (x) (^ x 3))
     '(1 2 3 4))  → ?₁

(fold + 0 '(1 2 3 4)) → ?₂
(fold [δυσανάγνωστο] 1 '(1 2 3 4)) → ?₃

(define (sum-of-cubes v)
  (fold + 0 (map (lambda (x) (^ x 3)) v)))
(sum-of-cubes '(1 2 3 4)) → ?₄

Με τι θα συμπληρώνατε τις αποτιμήσεις ?₁ των παραπάνω εκφράσεων; (Σημείωση: Η εντολή ^ σημαίνει ύψωση σε δύναμη)

(d) Παρουσιάστε όλα τα βήματα σταδιακής αποτίμησης της παρακάτω έκφρασης σε λ-λογισμό:

\[(\lambda x.\; \lambda y.\; \lambda z.\; x^2 + y^2 + z^2)\; 1\; 2\; 3\]

IMG_1695.jpg¶

ΘΕΜΑ 5 – Python (10%)¶

Υλοποιήστε πρόγραμμα σε Python που να εξομοιώνει τη λειτουργία ενός ηλεκτρονικού καλαθιού αγορών με χρήση πλειάδων ή λεξικού. Οι απαραίτητες συναρτήσεις που πρέπει – τουλάχιστον – να υλοποιήσετε, είναι οι παρακάτω: - Add_to_basket (προσθήκη προϊόντος στο καλάθι) - Remove_from_basket (αφαίρεση προϊόντος από το καλάθι) - Calculate_total_cost (υπολογισμός συνολικού κόστους του καλαθιού)

Πραγματοποιήστε την προσθήκη τουλάχιστον τριών προϊόντων, και εκτυπώστε το περιεχόμενο του καλαθιού και το συνολικό κόστος. Στη συνέχεια αφαιρέστε ένα προϊόν και εκτυπώστε πάλι το περιεχόμενο του καλαθιού.

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

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

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

Προσοχή

Θέμα 1 και Θέμα 2: η μεταγραφή της Παραλλαγής Β συμπίπτει με την Παραλλαγή Α, άρα η λύση μεταφέρθηκε και εδώ χωρίς δική της επαλήθευση· να ελεγχθεί στη φωτογραφία IMG_1689.jpg. Θέμα 2: η λύση δίνει μόνο τις τελικές τιμές του πίνακα· η ανάλυση γραμμή προς γραμμή δεν μεταφέρθηκε. Θέμα 3 και Θέμα 4 της Παραλλαγής Β δεν καλύπτονται από λύση: η λύση του παλιού αρχείου για το Θέμα 3 δεν μεταφέρθηκε εδώ, γιατί δεν έχει ελεγχθεί έναντι της εκφώνησης της Παραλλαγής Β.

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

Λύσεις που μεταφέρθηκαν από το παλιό συγκεντρωτικό αρχείο για τα Θέματα 1 και 2, των οποίων η εκφώνηση στη Παραλλαγή Β είναι ίδια με την Παραλλαγή Α. Δεν έχουν επαληθευτεί· οι ασυμφωνίες σημειώνονται στα warnings του αρχείου.

(α) Περιγραφή Κατασκευών: - Περιγράφει δηλώσεις μεταβλητών τύπου int ή float στη γλώσσα C με λίστα αναγνωριστικών χωρισμένων με κόμμα και τερματισμό με ερωτηματικό ;. - Παραδείγματα νόμιμων εκφράσεων: - int _ x ; - float _ temperature ; - int _ a , _ b , _ c ;

(β) Είναι LL(1) η γραμματική; - ΝΑΙ, η γραμματική είναι LL(1). - Τα $\text{FIRST}$ σύνολα των εναλλακτικών για το $\langle S \rangle$ είναι $\{\text{int}\}$ και $\{\text{float}\}$, τα οποία είναι ξένα. - Τα $\text{FIRST}$ σύνολα για το $\langle A \rangle$ είναι $\{,\}$ και $\{;\}$, τα οποία επίσης είναι ξένα. - Δεν υπάρχει αριστερή αναδρομή, ούτε κοινά προθέματα (είναι ήδη αριστερά παραγοντοποιημένη).

(γ) Έλεγχος του int m, p; με Στοίβα Ολίσθησης - Ελάττωσης (Bottom-Up): - Συμβολοσειρά εισόδου: int _ m , _ p ; $ 1. Shift int, Shift _, Shift m (id). 2. Shift ,, Shift _, Shift p (id). 3. Shift ;. 4. Reduce ; $\to A$. 5. Reduce , _ p A $\to A$. 6. Reduce int _ m A $\to S$. 7. Accept! Το string παράγεται νόμιμα.

(δ) Τύπος στην Ιεραρχία Chomsky: - Τύπου 3 (Κανονική Γραμματική - Regular Grammar), καθώς είναι δεξιά γραμμική (κάθε παραγωγή έχει τη μορφή $A \to w B$ ή $A \to w$, όπου $w$ τερματικά και $B$ μη-τερματικό στο τέλος).

(ε) Κανονική Έκφραση: $$(\text{int} \mid \text{float}) \_ \text{id} (, \_ \text{id})^* ;$$

(στ) DFA (Ντετερμινιστικό Πεπερασμένο Αυτόματο): - $q_0 \xrightarrow{\text{int, float}} q_1 \xrightarrow{\_} q_2 \xrightarrow{\text{id}} q_3$ - Από $q_3 \xrightarrow{;} q_{\text{final}}$ (αποδεκτή) - Από $q_3 \xrightarrow{,} q_4 \xrightarrow{\_} q_5 \xrightarrow{\text{id}} q_3$ (βρόχος πολλαπλών μεταβλητών).

Τελικές τιμές πίνακα data: - data[0] = 9 - data[1] = 10 - data[2] = 31 - data[3] = 33 - data[4] = 50 - data[5] = 59

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

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