Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Ιούνιος 2021¶
Μεταγραφή από τα στιγμιότυπα Screenshot_20210630_141314.png, Screenshot_20210630_143512.png και Screenshot_20210630_151036.png.
Screenshot_20210630_141314.png¶
ΘΕΜΑ 1¶
a. Να παρουσιάσετε τον Πίνακα Καταστάσεων – Μεταβάσεων (εναλλακτικός τρόπος παρουσίασης του διαγράμματος καταστάσεων – μεταβάσεων), για το ντετερμινιστικό πεπερασμένο αυτόματο που αναγνωρίζει όλους τους δυαδικούς αριθμούς οι οποίοι: Περιέχουν ένα τουλάχιστον 0, ενώ τα 1 (αν υπάρχουν) εμφανίζονται ένα τη φορά και έχουν δεξιά και αριστερά τους δύο ή περισσότερα 0. Παραδείγματα: 0, 0000, 001000100001000. Πόσες καταστάσεις έχει το αυτόματο; Ποιες από αυτές είναι τελικές καταστάσεις; b. Δείξτε σε Πίνακα τη λειτουργία και το αποτέλεσμα του αυτόματου, για την είσοδο 001000. c. Γράψετε μια κανονική έκφραση που αντιστοιχεί στο παραπάνω αυτόματο.
ΣΗΜΕΙΩΣΗ: Αν και δεν ζητείται, θα σας βοηθήσει στις απαντήσεις σας να κατασκευάσετε στην αρχή για δική σας χρήση, το διάγραμμα καταστάσεων – μεταβάσεων του αυτόματου.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_20210630_143512.png¶
Ερώτηση 1 (Ελεύθερου Κειμένου — 0 βαθμοί)
ΘΕΜΑ 2¶
Μία συνθηματική γλώσσα απλών προτάσεων, περιγράφεται από την παρακάτω BNF γραμματική, με τερματικά σύμβολα τα: a b d S όπου το S συμβολίζει τον χαρακτήρα «κενό» (space).
a. Τι είδους συμβολοσειρές περιγράφει η γραμματική; Περιγράψτε τη δομή και μερικά βασικά χαρακτηριστικά των συμβολοσειρών αυτών, παρουσιάζοντας και παραδείγματα. b. Δημιουργώντας τη Στοίβα Ολίσθησης – Ελάττωσης Bottom-Up συντακτικής ανάλυσης, να αποφανθείτε αν η πρόταση da ad (ή αλλιώς daSad) είναι μέλος της συνθηματικής γλώσσας. c. Είναι η γραμματική LL(1); Αιτιολογήστε την απάντησή σας, υποδεικνύοντας όλα τα σημεία της γραμματικής που δικαιολογούν τον ισχυρισμό σας. Αν η γραμματική δεν είναι LL(1), τι είδους μετασχηματισμοί και σε ποια σημεία πρέπει να γίνουν, ώστε να δημιουργηθεί μια ισοδύναμη LL(1) γραμματική; (δεν χρειάζεται να παρουσιάσετε τους ίδιους τους μετασχηματισμούς, ούτε την ισοδύναμη γραμματική)
Screenshot_20210630_151036.png¶
ΘΕΜΑ 3¶
Δίνονται τα παρακάτω δύο προγράμματα μιας γλώσσας προγραμματισμού η οποία όσον αφορά το συντακτικό και τη γενική δομή των προγραμμάτων της είναι τύπου Pascal, ενώ υιοθετεί τις τεχνικές μεταβίβασης παραμέτρων καθώς και τη σημειογραφία και τη λειτουργικότητα δεικτών (pointers) της C. Τα προγράμματα εκτελούνται σε έναν compiler ο οποίος στην εντολή ανάθεσης προσδιορίζει πρώτα την l-value (αν χρειάζεται να προσδιοριστεί).
a. Ποιες είναι οι ομοιότητες και οι διαφορές των δύο προγραμμάτων, ιδιαίτερα όσον αφορά τον τρόπο μεταβίβασης παραμέτρων, τις μεταβλητές και τις σχέσεις τους; b. Ποια είναι τα περιβάλλοντα αναφοράς των P και MAIN στο Πρόγραμμα A; c. Στα παραπάνω δύο προγράμματα υπάρχει μία εντολή η οποία δεν είναι σωστή από σημασιολογική άποψη και θα προκαλέσει error. Ποια είναι και γιατί; Σβήστε την εντολή από τον κώδικα. d. Ποια είναι η έξοδος των δύο προγραμμάτων κατά την εκτέλεσή τους; Εξηγείστε τις αλλαγές τιμών όλων των μεταβλητών κατά τη διαδικασία υπολογισμού. e. Ποια θα ήταν η έξοδος του Προγράμματος A κατά την εκτέλεσή του, αν υποθέταμε ότι η μεταβίβαση παραμέτρων γινόταν με τους παρακάτω δύο τρόπους (παρουσιάστε και εξηγείστε τις αλλαγές τιμών όλων των μεταβλητών κατά τη διαδικασία υπολογισμού): i. Κλήση με τιμή – αποτέλεσμα (call by value – result) ii. Κλήση με όνομα (call by name)
Πρόγραμμα A¶
program MAIN;
var n: integer;
a: array [0..10] of integer;
function P(x: integer): integer;
begin
write(x);
n:= n + 2;
write(x);
x:= x + 8;
P:= x;
end;
BEGIN
n:= 1;
a[0]:= x; a[1]:= 100; a[2]:= 200;
a[3]:= 300; a[4]:= 400; a[5]:= 500;
a[6]:= 600;
a[n+3]:= P(a[n+2]);
write(a[1]);
write(a[2]);
write(a[3]);
write(a[4]);
write(a[5]);
END.
Πρόγραμμα B¶
program MAIN;
var n: integer;
a: array [0..10] of integer;
function P(*x: integer): integer;
begin
write(*x);
n:= n + 2;
write(*x);
*x:= *x + 8;
P:= *x;
end;
BEGIN
n:= 1;
a[0]:= x; a[1]:= 100; a[2]:= 200;
a[3]:= 300; a[4]:= 400; a[5]:= 500;
a[6]:= 600;
a[n+3]:= P(&a[n+2]);
write(a[1]);
write(a[2]);
write(a[3]);
write(a[4]);
write(a[5]);
END.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η γλώσσα: συμβολοσειρές \(0^{a_0}\,1\,0^{a_1}\,1\cdots1\,0^{a_k}\) όπου, αν \(k=0\) (καθόλου 1) αρκεί \(a_0\ge1\), ενώ αν \(k\ge1\) όλα τα \(a_i\ge2\) (κάθε 1 έχει τουλάχιστον δύο 0 δεξιά και αριστερά· τα ενδιάμεσα 0 μοιράζονται).
a. Πίνακας καταστάσεων – μεταβάσεων (ν = νεκρή/παγίδα κατάσταση):
| Κατάσταση | Σημασία | με 0 |
με 1 |
Τελική |
|---|---|---|---|---|
| q0 | αρχή, τίποτα διαβασμένο | q1 | ν | όχι |
| q1 | ακριβώς ένα 0 από την αρχή |
q2 | ν | ναι |
| q2 | δύο ή περισσότερα 0 στη σειρά |
q2 | q3 | ναι |
| q3 | μόλις διαβάστηκε 1 |
q4 | ν | όχι |
| q4 | 1 και μετά ένα 0 |
q2 | ν | όχι |
| ν | νεκρή | ν | ν | όχι |
Το αυτόματο έχει 6 καταστάσεις (5 χρήσιμες + η νεκρή· αν δεν μετράμε τη νεκρή, 5). Τελικές: q1 και q2. (Η q2 χρησιμεύει και ως «έχω ≥2 μηδενικά μετά από 1»: οι συνέχειες είναι ίδιες με τις αρχικά διαβασμένα ≥2 0, γι' αυτό δεν χρειάζεται ξεχωριστή κατάσταση.)
Έλεγχος: το αυτόματο συγκρίθηκε με πρόγραμμα με τον ορισμό της εκφώνησης για όλες τις συμβολοσειρές μέχρι μήκος 14.
b. Λειτουργία για την είσοδο 001000:
| Βήμα | Σύμβολο | Από | Σε |
|---|---|---|---|
| 1 | 0 | q0 | q1 |
| 2 | 0 | q1 | q2 |
| 3 | 1 | q2 | q3 |
| 4 | 0 | q3 | q4 |
| 5 | 0 | q4 | q2 |
| 6 | 0 | q2 | q2 |
Τέλος εισόδου στην q2 (τελική) ⇒ αποδοχή.
c. Κανονική έκφραση: με \(Z = 00\,0^*\) (δύο ή περισσότερα μηδενικά):
δηλαδή ή ένα μόνο 0, ή ≥2 μηδενικά ακολουθούμενα από ομάδες «1 και ≥2 μηδενικά». Π.χ. το 001000100001000 ταιριάζει: 00·1·000·1·0000·1·000.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Η γραμματική (ονόματα συντομογραφίας): πρόταση = Π, λέξη = Λ, συλλαβή = Σ, βάση = B, σύμφωνο = C. Κανόνες: \(\Pi\to\Lambda\mid\Pi\,S\,\Lambda\), \(\Lambda\to\Sigma\mid\Sigma\Lambda\Sigma\), \(\Sigma\to B\mid BC\mid aB\mid aC\), \(B\to Ca\), \(C\to b\mid d\).
a. Επεκτείνοντας: οι βάσεις είναι ba, da. Συλλαβές: \(B\) = ba/da, \(BC\) = ba+(b/d) κ.λπ. (π.χ. bab, dad), \(aB\) = aba/ada, \(aC\) = ab/ad. Δηλαδή κάθε συλλαβή είναι Cᵃ(C), δηλ. ba, da, bab, bad, dab, dad, aba, ada, ab, ad. Η λέξη είναι περιττό πλήθος συλλαβών (\(\Sigma\), \(\Sigma\Sigma\Sigma\), …) με φωλιασμένη δομή (συλλαβή, λέξη, συλλαβή). Η πρόταση είναι μία ή περισσότερες λέξεις χωρισμένες από ένα κενό S. Παραδείγματα: da, ad, ba da, da ad, bab, ab ba ad.
b. Bottom-up για daSad (στοίβα, είσοδος, ενέργεια):
| Στοίβα | Είσοδος | Ενέργεια |
|---|---|---|
| $ | daSad$ | ολίσθηση |
| $d | aSad$ | ελάττωση C→d |
| $C | aSad$ | ολίσθηση |
| $Ca | Sad$ | ελάττωση B→Ca |
| $B | Sad$ | ελάττωση Σ→B (επόμενο S, όχι σύμφωνο) |
| $Σ | Sad$ | ελάττωση Λ→Σ |
| $Λ | Sad$ | ελάττωση Π→Λ |
| $Π | Sad$ | ολίσθηση S |
| $ΠS | ad$ | ολίσθηση a |
| $ΠSa | d$ | ολίσθηση d |
| $ΠSad | $ | ελάττωση C→d |
| $ΠSaC | $ | ελάττωση Σ→aC |
| $ΠSΣ | $ | ελάττωση Λ→Σ |
| $ΠSΛ | $ | ελάττωση Π→ΠSΛ |
| $Π | $ | αποδοχή |
Η da ad ανήκει στη γλώσσα. Στο τέταρτο βήμα η απόφαση «Σ→B» αντί για ολίσθηση (για Σ→BC) βασίστηκε στο ότι ο επόμενος χαρακτήρας είναι S και όχι σύμφωνο.
c. LL(1): όχι. Σημεία:
1. \(\Pi\to\Pi S\Lambda\) είναι αριστερά αναδρομικός κανόνας: ο προβλέπων αναλυτής θα έμπαινε σε άπειρη αναδρομή· επιπλέον οι δύο εναλλακτικές της Π έχουν κοινό FIRST.
2. \(\Lambda\to\Sigma\mid\Sigma\Lambda\Sigma\): κοινό πρόθεμα Σ (ίδιο FIRST).
3. \(\Sigma\to B\mid BC\): κοινό πρόθεμα B· και \(\Sigma\to aB\mid aC\): κοινό πρόθεμα a. Επίσης FIRST(B)={b,d} αλλά και FIRST(\(BC\))={b,d}.
Μετασχηματισμοί: (i) απαλοιφή αριστερής αναδρομής στην Π (Π→ΛΠ′, Π′→SΛΠ′|ε)· (ii) αριστερή παραγοντοποίηση στις Λ, Σ (π.χ. Λ→ΣΛ′, Σ→BΣ′ | aΣ″ κ.λπ.). Προσοχή: ακόμη και μετά από αυτά, η Λ→ΣΛΣ (φωλιασμένη δομή με ίδιο αρχικό και τελικό μέρος) μπορεί να παραμένει μη LL(1), γιατί το FOLLOW της Λ περιέχει τα ίδια σύμβολα με το FIRST της· δεν το έχω ελέγξει πλήρως (χαμηλή βεβαιότητα για αυτή τη λεπτομέρεια).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Σημείωση: η εντολή a[0]:= x στο MAIN χρησιμοποιεί την x, που δεν δηλώνεται στο MAIN (είναι παράμετρος της P και δεν φαίνεται εκεί). Αυτή είναι η σημασιολογικά λανθασμένη εντολή (αδήλωτη μεταβλητή) και στα δύο προγράμματα διαγράφεται. Άρα \(a[1..6]=100,200,300,400,500,600\), \(n=1\).
Η ανάθεση a[n+3]:= P(...) ορίζει πρώτα την l-value: με \(n=1\) είναι το \(a[4]\), πριν εκτελεστεί η P (που αλλάζει το \(n\)).
a. Ομοιότητες/διαφορές: Ίδια δομή, καθολικά n, a, ίδιες εντολές στη συνάρτηση, ίδια κλήση ως προς το στοιχείο \(a[n+2]=a[3]\). Στο Α η παράμετρος x περνά με τιμή (αντίγραφο), άρα η \(x:=x+8\) δεν αλλάζει τον πίνακα. Στο Β περνά η διεύθυνση &a[n+2] (εξομοίωση κλήσης με αναφορά) και το *x είναι ο ίδιος ο \(a[3]\), άρα η αλλαγή φαίνεται στον πίνακα. Το \(n\) και ο πίνακας είναι κοινά (καθολικά) και στα δύο.
b. Περιβάλλοντα αναφοράς (Πρόγραμμα Α): - MAIN: τοπικά {n, a, P}, μη τοπικά κανένα, καθολικά {n, a, P}. - P: τοπικά {x}, μη τοπικά {n, a, P} (από το MAIN), καθολικά {n, a, P}.
c. Η εντολή a[0]:= x (και στα δύο προγράμματα), όπως παραπάνω.
d. Εκτέλεση.
Πρόγραμμα Α (τιμή): \(x=a[3]=300\) (αντίγραφο). write(x)→300. \(n:=3\). write(x)→300. \(x:=308\). \(P:=308\). Ανάθεση στην προκαθορισμένη l-value: \(a[4]:=308\). Μετά γράφονται \(a[1..5]=100,200,300,308,500\).
Έξοδος: 300 300 100 200 300 308 500 (ως ένα συνεχές κείμενο: 300300100200300308500).
Πρόγραμμα Β (δείκτης): x=&a[3]. write(*x)→300. \(n:=3\). write(*x)→300 (ο δείκτης έχει ήδη δεσμευτεί στο \(a[3]\)). *x:=308 ⇒ \(a[3]=308\). \(P:=308\). \(a[4]:=308\) (l-value από πριν). Γράφονται \(a[1..5]=100,200,308,308,500\).
Έξοδος: 300 300 100 200 308 308 500.
e. Πρόγραμμα Α με άλλες μεταβιβάσεις:
i. Τιμή–αποτέλεσμα: η διεύθυνση του πραγματικού (\(a[n+2]=a[3]\)) υπολογίζεται κατά την κλήση. \(x=300\) → write:300, \(n=3\), write:300, \(x=308\). Στην έξοδο της P αντιγράφεται το \(x\) πίσω στο \(a[3]\) ⇒ \(a[3]=308\). \(a[4]:=308\). Γράφονται 100, 200, 308, 308, 500.
Έξοδος: 300 300 100 200 308 308 500. (Αν η διεύθυνση επανυπολογιζόταν κατά την έξοδο με \(n=3\), θα έβγαινε \(a[5]=308\)· η συνήθης σύμβαση είναι κατά την κλήση.)
ii. Κλήση με όνομα: το x αντικαθίσταται κειμενικά από a[n+2] και υπολογίζεται κάθε φορά που χρησιμοποιείται. write(x) με \(n=1\): \(a[3]=300\). \(n:=3\). write(x): \(a[5]=500\). x:=x+8 ⇒ \(a[5]:=508\). \(P:=x=a[5]=508\). \(a[4]:=508\). Γράφονται \(a[1..5]=100,200,300,508,508\).
Έξοδος: 300 500 100 200 300 508 508.