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

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

Μεταγραφή από τις φωτογραφίες IMG_6178.jpg και IMG_6179.jpg. Το IMG_6178.png επιβεβαιώθηκε ως αντίγραφο του IMG_6178.jpg. Το Themata_2023.pdf είναι ανακατασκευή από μη επαληθευμένο κείμενο και δεν αντιγράφεται.

IMG_6178.jpg

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

ΘΕΜΑ 1 – Λεξική και Συντακτική Ανάλυση (40%) Δίνεται η παρακάτω BNF γραμματική, τμήμα της περιγραφής του συντακτικού μιας γλώσσας προγραμματισμού. Τα τερματικά σύμβολα της γραμματικής είναι τα: int float id , ; ένας χαρακτήρας κενού

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

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

Η αρχή του ΘΕΜΑΤΟΣ 2 φαίνεται και σε αυτή τη φωτογραφία (γραμμές 1–6 του κώδικα), αλλά ολόκληρο το Θέμα 2 μεταγράφεται από το IMG_6179.jpg.

IMG_6179.jpg

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

ΘΕΜΑ 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 }
1. Εξηγήστε γραμμή-γραμμή, για τις γραμμές 3-11, τους ορισμούς και τη λειτουργία του παραπάνω προγράμματος. 2. Τι θα τυπωθεί με την εκτέλεση του προγράμματος, δηλαδή ποιες θα είναι οι τελικές τιμές του πίνακα data;

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

ΘΕΜΑ 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.

[Λείπει από τη φωτογραφία: τα ερωτήματα του ΘΕΜΑΤΟΣ 3]

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

[Λείπει από τη φωτογραφία: Θέματα 4 και άνω]

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

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

Προσοχή

Θέμα 3: τα ερωτήματα του θέματος δεν φαίνονται στις φωτογραφίες. Η λύση εξετάζει και κλήση με αναφορά (var k, b), που δεν υπάρχει στην κεφαλίδα F(k, b: integer) του κώδικα. Θέμα 2: η λύση δίνει μόνο τις τελικές τιμές του πίνακα· η ανάλυση γραμμή προς γραμμή που ζητά η εκφώνηση δεν μεταφέρθηκε.

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

Λύσεις που μεταφέρθηκαν από το παλιό συγκεντρωτικό αρχείο. Δεν έχουν επαληθευτεί· οι ασυμφωνίες με την εκφώνηση σημειώνονται στα 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

  • Στην κλήση F(n, A[n+2]), με \(n=1\), το όρισμα είναι A[1+2] = A[3] = 30.
  • Εφόσον οι παράμετροι \(k, b\) είναι call-by-value (δεν υπάρχει var στην κεφαλίδα):
  • writeln(k) \(\implies\) τυπώνει 1
  • n := n + 1 \(\implies n = 2\) (η \(n\) είναι καθολική)
  • writeln(k) \(\implies\) τυπώνει 1 (η τοπική \(k\) δεν επηρεάζεται από την \(n\))
  • k := k + 4 \(\implies k = 5\)
  • writeln(n) \(\implies\) τυπώνει 2
  • b := b + 5 \(\implies b = 35\) (τοπική, δεν αλλάζει το \(A[3]\))
  • Μετά την έξοδο από την \(F\):
  • writeln(n) \(\implies\) τυπώνει 2
  • writeln(A[1], ' ', A[2], ' ', A[3], ' ', A[4], ' ', A[5]) \(\implies\) τυπώνει 10 20 30 40 50
  • Αν οι παράμετροι ήταν Call by Reference (var k, b):
  • writeln(k) \(\implies\) 1
  • \(n := n + 1 \implies n = 2\) (και άρα \(k = 2\), αφού \(k \equiv n\))
  • writeln(k) \(\implies\) 2
  • \(k := k + 4 \implies k = 6\) (και \(n = 6\))
  • writeln(n) \(\implies\) 6
  • \(b := b + 5 \implies A[3] = 35\)
  • writeln(n) \(\implies\) 6
  • Τελικός πίνακας: 10 20 35 40 50

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

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