Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Σεπτέμβριος 2020 — Θέμα 1

Μεταγραφή από το αρχείο sep20.pdf (μόνο η εκφώνηση του Θέματος 1).

sep20.pdf

1ο ΘΕΜΑ

Δίνεται η BNF γραμματική που φαίνεται στο τέλος της εκφώνησης ως εικόνα, με επτά κανόνες R1 – R7 και τερματικά σύμβολα τα 0 1

a. Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky; Αιτιολογήστε την απάντησή σας. b. Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική; c. Μπορείτε να φτιάξετε μια κανονική έκφραση αντίστοιχη της γραμματικής και γιατί; Αν ναι, παρουσιάστε την. d. Ελέγξτε αν η συμβολοσειρά 011101 είναι μέλος της γλώσσας, παρουσιάζοντας τη δημιουργία (derivation) της top-down συντακτικής ανάλυσης της συμβολοσειράς, με τον παρακάτω τρόπο (από το παράδειγμα των σελίδων 22 – 23 των διαφανειών):

\(S_0 \to \text{[R1]} \ 0 S_1 \to \text{[R2]} \ 0. S_2 \to \text{[R3]} \ 0.0 S_3 \to \text{[R6]} \ 0.01\)

όπου \(S_n\) είναι συντακτική κατηγορία και R1, R2, ... είναι παραγωγές (κανόνες).

[Σχήμα: R1, R2: ::= 0| 1 R3, R4: ::= 0| 1 R5, R6, R7: ::= 0| 1| \(\epsilon\)]

Ποιο το αποτέλεσμα της εκτέλεσης του προγράμματος Python:

for i in [2, 1]:
    for j in [1, 3]:
        if i + j > 3: break
        print (i + j, end = ' ')
    print (i - 1, end = ' ')
print (i - 1, end = ' ')

• [ ] 3 0 0
• [ ] 3 0
• [ ] 3 5 1 2 4 0
• [ ] 3 5 1 2 4 0 0
• [ ] 3 1 2 0
• [ ] 3 1 2 0 0

ΘΕΜΑ 1

Δίνεται η BNF γραμματική που φαίνεται στο τέλος της εκφώνησης, με πέντε κανόνες R1 – R5 και τερματικά σύμβολα τα x y

a. Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky; Είναι LL(1) η γραμματική; Αιτιολογήστε τις απαντήσεις σας. b. Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική; Δώστε παραδείγματα αποδεκτών συμβολοσειρών, καθώς και τη μικρότερη σε μήκος. c. Ελέγξτε αν η συμβολοσειρά xxyyyy είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ταιριάσματος – Πρόβλεψης Top-Down συντακτικής ανάλυσης της συμβολοσειράς.

[Σχήμα: R1: ::= R2, R3: ::= xy | \(\epsilon\) R4, R5: ::= y | y]

ΘΕΜΑ 2

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

I. Θεωρώντας ότι ισχύει ο στατικός κανόνας εμβέλειας: a. Ποια είναι τα Περιβάλλοντα Αναφοράς (Τοπικά, Μη-τοπικά, Καθολικά) όλων των τμημάτων του προγράμματος; b. Στο πρόγραμμα υπάρχει μία εντολή η οποία δεν είναι σωστή από σημασιολογική άποψη και θα προκαλέσει run-time error. Ποια είναι αυτή και γιατί; Θεωρήστε για τη συνέχεια, ότι δεν υπάρχει η εντολή αυτή. c. Παρουσιάστε τη στοίβα εκτέλεσης (run-time stack) των εγγραφών ενεργοποίησης (Activation Records – AR) μόλις έχει γίνει η κλήση της Y. Χρησιμοποιήστε την εξής σημειογραφία: AR-MAIN(x,y) -> AR-X(z,w) -> ... με τη χρονική σειρά δημιουργίας των AR και όπου μέσα στις παρενθέσεις είναι τα μέλη των Τοπικών Περιβαλλόντων Αναφοράς κάθε υποπρογράμματος αντίστοιχα. Τους τυχόν Static Chain Pointers, αναφέρετέ τους ξεχωριστά. d. Παρουσιάστε τα αποτελέσματα της εκτέλεσης του προγράμματος, με τη σειρά που θα εμφανιστούν. Εξηγείστε τη διαδικασία υπολογισμού των τιμών που θα εμφανιστούν.

II. Απαντήστε στα παραπάνω ερωτήματα, θεωρώντας ότι ισχύει ο δυναμικός κανόνας εμβέλειας. Αναλυτικά για το ερώτημα (d) και εξηγώντας μόνο σύντομα τις τυχόν διαφορές στα υπόλοιπα ερωτήματα.

program MAIN;
  procedure X;
    a: integer;
    procedure Y;
    begin
      a:= a*2;
      write("In Y:", a)
    end;
    procedure Z;
      a: integer;
    begin
      a:= 7;
      Y;
      write("In Z:", a)
    end;
  begin
    a:= 5;
    Z
    write("In X:", a)
  end;
BEGIN
  a:= 1;
  X;
END.

Τι θα τυπώσει το παρακάτω πρόγραμμα;

s = 'σήμερα είναι δευτέρα'
print(s.capitalize())

• [ ] Σήμερα είναι δευτέρα
• [ ] Σήμερα Είναι Δευτέρα
• [ ] ΣΗΜΕΡΑ ΕΙΝΑΙ ΔΕΥΤΕΡΑ
• [ ] StringError

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.40 βαθμοί)

Ποιο το αποτέλεσμα του παρακάτω κώδικα Python

d = {1:'a', 2:'v', 3:'t', 4:'e'}
for i in sorted(d, key =d.get):
    print(d[i],end='')
else: print(' γεια')

• [ ] αντε γεια
• [ ] αεντ γεια
• [ ] αεντγεια
• [ ] αντε

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.40 βαθμοί)

Ποιο θα είναι το αποτέλεσμα:

x = 3.0
y = ( 3 / x )/(x - 3) + x ** 3 / (x ** 6)

• [ ] 3.0
• [ ] ZeroDivisionError
• [ ] 3E8
• [ ] 3
• [ ] 2.132468

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.40 βαθμοί)

Τι θα τυπώσει το παρακάτω πρόγραμμα

def f():
    x = 2
    print(x, end = ' ')
x = 3
f()
print(x, end = ' ')

• [ ] 3 2
• [ ] 2
• [ ] 2 3
• [ ] 3

Ερώτηση 5 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.40 βαθμοί)

Ποιο είναι το αποτέλεσμα της εκτέλεσης του κώδικα Python:

b = 1
def x(n):
    b = 5
    print (b, n, end = ' ')
    return b
print (x(2), b )

• [ ] 1 2 5 5
• [ ] 5 3 1 1
• [ ] 5 2 5 1
• [ ] 5 2 1 5

Σημείωση: το αρχείο περιέχει απαντήσεις φοιτητή (στο πεδίο απάντησης της 1ης σελίδας και σε αντίγραφο εξόδου IDE της 7ης σελίδας), που δεν μεταφέρονται.

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

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.1-pro-preview, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2020-09

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

Θέμα 1Α

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Κανόνες: R1: \(S\to 0S\), R2: \(S\to 1A\), R3: \(A\to 0S\), R4: \(A\to 1B\), R5: \(B\to 0B\), R6: \(B\to 1B\), R7: \(B\to\epsilon\).

a. Όλοι οι κανόνες είναι της μορφής τερματικό + (το πολύ ένα μη τερματικό δεξιά) ή \(\epsilon\): δεξιά γραμμική, άρα Τύπου 3 (κανονική).

b. Από το \(S\) το 0 μένει στο \(S\), το 1 πάει στο \(A\) («είδαμε ένα 1»). Από το \(A\) το 0 γυρνά στο \(S\), το 1 πάει στο \(B\) («είδαμε 11»). Το \(B\) δέχεται οτιδήποτε και τερματίζει με \(\epsilon\). Άρα: οι δυαδικές συμβολοσειρές που περιέχουν τουλάχιστον μία φορά δύο διαδοχικά 1 (υποσυμβολοσειρά 11). Ελάχιστη: 11. Παραδείγματα: 11, 0110, 1011, 011101.

c. Ναι, γιατί η γλώσσα είναι κανονική (η γραμματική είναι Τύπου 3). Πριν το πρώτο 11 μπορούμε να έχουμε μόνο 0 ή 10 (κάθε 1 πρέπει να ακολουθείται από 0):

\[(0\mid 10)^*\,11\,(0\mid 1)^*\]

(Επαληθεύτηκε με πρόγραμμα για όλες τις συμβολοσειρές μέχρι μήκος 12.)

d. Για την 011101:

\(S_0 \to[R1]\ 0S_1 \to[R2]\ 01A_2 \to[R4]\ 011B_3 \to[R6]\ 0111B_4 \to[R5]\ 01110B_5 \to[R6]\ 011101B_6 \to[R7]\ 011101\)

Η παραγωγή τελειώνει στην είσοδο, άρα η 011101 είναι μέλος της γλώσσας (περιέχει 11).

Λύση 2: ### a. Τύπος γραμματικής στην ιεραρχία Chomsky Η γραμματική είναι Τύπου 3 (Κανονική Γραμματική / Regular Grammar), διότι είναι δεξιά γραμμική (right-linear). Όλοι οι κανόνες παραγωγής έχουν τη μορφή \(A \to aB\) ή \(A \to \epsilon\), δηλαδή στο δεξιό μέλος υπάρχει το πολύ ένα τερματικό σύμβολο ακολουθούμενο από το πολύ ένα μη-τερματικό σύμβολο (ή η κενή συμβολοσειρά \(\epsilon\)).

b. Είδος συμβολοσειρών που περιγράφει

Η γραμματική περιγράφει όλες τις συμβολοσειρές πάνω από το αλφάβητο \(\{0, 1\}\) οι οποίες περιέχουν τουλάχιστον δύο διαδοχικά «1» (δηλαδή την υποσυμβολοσειρά 11). - Η κατάσταση εκκίνησης \(\langle S \rangle\) και η \(\langle A \rangle\) δεν έχουν \(\epsilon\)-παραγωγή, επομένως για να τερματίσει μια παραγωγή πρέπει υποχρεωτικά να φτάσει στη συντακτική κατηγορία \(\langle B \rangle\). - Η μετάβαση στην \(\langle B \rangle\) γίνεται αποκλειστικά μέσω του κανόνα \(\text{R4}: \langle A \rangle \to 1\langle B \rangle\), στον οποίο φτάνουμε μόνο από τον κανόνα \(\text{R2}: \langle S \rangle \to 1\langle A \rangle\). Επομένως απαιτείται η εμφάνιση δύο διαδοχικών άσσων (11). Μετά την εμφάνιση του 11, η \(\langle B \rangle\) μπορεί να παραγάγει οποιαδήποτε ακολουθία από \(0\) και \(1\) και να τερματίσει μέσω του \(\text{R7}: \langle B \rangle \to \epsilon\).

c. Κανονική έκφραση

Ναι, είναι δυνατή η κατασκευή κανονικής έκφρασης, διότι κάθε γραμματική Τύπου 3 παράγει μια κανονική γλώσσα (θεώρημα Kleene).

Η αντίστοιχη κανονική έκφραση είναι: $\((0 \mid 10)^* 11 (0 \mid 1)^*\)$

d. Παραγωγή (derivation) της συμβολοσειράς 011101

\[\langle S \rangle \to \text{[R1]} \ 0\langle S \rangle \to \text{[R2]} \ 01\langle A \rangle \to \text{[R4]} \ 011\langle B \rangle \to \text{[R6]} \ 0111\langle B \rangle \to \text{[R5]} \ 01110\langle B \rangle \to \text{[R6]} \ 011101\langle B \rangle \to \text{[R7]} \ 011101\]

Η συμβολοσειρά είναι μέλος της γλώσσας.

---

Λύση 3 (τρίτη γνώμη): a. Η γραμματική ανήκει στον Τύπο 2 (Γραμματικές Χωρίς Συμφραζόμενα - Context-Free Grammars) της ιεραρχίας Chomsky. Αυτό ισχύει διότι όλοι οι κανόνες παραγωγής έχουν ακριβώς ένα μη τερματικό σύμβολο στο αριστερό τους μέλος και μια ακολουθία από τερματικά και μη τερματικά σύμβολα στο δεξί τους μέλος.

Η γραμματική δεν είναι LL(1). Για να είναι μια γραμματική LL(1), δεν πρέπει να υπάρχουν συγκρούσεις στα σύνολα FIRST για κανόνες που έχουν το ίδιο αριστερό μέλος. Για το μη τερματικό \(B\), έχουμε τους κανόνες \(B \to yB\) και \(B \to y\). Ισχύει ότι \(FIRST(yB) = \{y\}\) και \(FIRST(y) = \{y\}\). Επειδή \(FIRST(yB) \cap FIRST(y) = \{y\} \neq \emptyset\), υπάρχει σύγκρουση FIRST-FIRST, άρα η γραμματική δεν είναι LL(1).

b. Το μη τερματικό \(A\) παράγει συμβολοσειρές της μορφής \(x^n y^n\) για \(n \ge 0\). Το μη τερματικό \(B\) παράγει συμβολοσειρές της μορφής \(y^m\) για \(m \ge 1\). Συνεπώς, το αρχικό σύμβολο \(S\) παράγει συμβολοσειρές της μορφής \(x^n y^{n+m}\), όπου \(n \ge 0\) και \(m \ge 1\). Δηλαδή, περιγράφει συμβολοσειρές που ξεκινούν με \(n\) σύμβολα 'x' και ακολουθούνται από \(k\) σύμβολα 'y', με την προϋπόθεση ότι το πλήθος των 'y' είναι αυστηρά μεγαλύτερο από το πλήθος των 'x' (\(k > n \ge 0\)). - Παραδείγματα αποδεκτών συμβολοσειρών: \(y\), \(xyy\), \(xxyyyy\), \(xxxyyyyy\). - Μικρότερη σε μήκος συμβολοσειρά: \(y\) (προκύπτει για \(n=0\) και \(m=1\)).

c. Η Top-Down συντακτική ανάλυση (με τη στοίβα να έχει την κορυφή της στα αριστερά) για τη συμβολοσειρά \(xxyyyy\) παρουσιάζεται παρακάτω:

Στοίβα (Κορυφή αριστερά)	Είσοδος	Ενέργεια
\(S \ \$\)	\(xxyyyy \ \$\)	Πρόβλεψη \(S \to AB\)
\(A \ B \ \$\)	\(xxyyyy \ \$\)	Πρόβλεψη \(A \to xAy\)
\(x \ A \ y \ B \ \$\)	\(xxyyyy \ \$\)	Ταίριασμα \(x\)
\(A \ y \ B \ \$\)	\(xyyyy \ \$\)	Πρόβλεψη \(A \to xAy\)
\(x \ A \ y \ y \ B \ \$\)	\(xyyyy \ \$\)	Ταίριασμα \(x\)
\(A \ y \ y \ B \ \$\)	\(yyyy \ \$\)	Πρόβλεψη \(A \to \epsilon\)
\(y \ y \ B \ \$\)	\(yyyy \ \$\)	Ταίριασμα \(y\)
\(y \ B \ \$\)	\(yyy \ \$\)	Ταίριασμα \(y\)
\(B \ \$\)	\(yy \ \$\)	Πρόβλεψη \(B \to yB\)
\(y \ B \ \$\)	\(yy \ \$\)	Ταίριασμα \(y\)
\(B \ \$\)	\(y \ \$\)	Πρόβλεψη \(B \to y\)
\(y \ \$\)	\(y \ \$\)	Ταίριασμα \(y\)
\(\$\)	\(\$\)	Αποδοχή

Ερώτηση (Python, βρόχοι με break)

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Για \(i=2\): \(j=1\) → \(3\) (δεν είναι \(>3\)) τυπώνει 3· \(j=3\) → \(5>3\) break· μετά τυπώνει \(i-1=1\). Για \(i=1\): \(j=1\) → τυπώνει 2· \(j=3\) → \(4>3\) break· τυπώνει \(0\). Μετά το βρόχο \(i=1\) ⇒ τυπώνει \(0\). Έξοδος 3 1 2 0 0 (εκτελέστηκε).

Σωστή επιλογή: «3 1 2 0 0».

Λύση 3 (τρίτη γνώμη): Επιλογή: Σήμερα είναι δευτέρα

Αιτιολόγηση: Η μέθοδος capitalize() της Python επιστρέφει ένα αντίγραφο της συμβολοσειράς όπου μόνο το πρώτο γράμμα μετατρέπεται σε κεφαλαίο (εδώ το 'σ' γίνεται 'Σ') και όλα τα υπόλοιπα γράμματα μετατρέπονται σε πεζά.

Ερώτηση (capitalize)

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Η capitalize() κάνει κεφαλαίο μόνο τον πρώτο χαρακτήρα και πεζά τα υπόλοιπα. Σωστή επιλογή: «Σήμερα είναι δευτέρα».

Λύση 3 (τρίτη γνώμη): Επιλογή: Σήμερα είναι δευτέρα

Αιτιολόγηση: Η μέθοδος capitalize() της Python επιστρέφει ένα αντίγραφο της συμβολοσειράς όπου μόνο το πρώτο γράμμα μετατρέπεται σε κεφαλαίο (εδώ το 'σ' γίνεται 'Σ') και όλα τα υπόλοιπα γράμματα μετατρέπονται σε πεζά.

Ερώτηση 2 (λεξικό με sorted και for … else)

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

Η sorted(d, key=d.get) ταξινομεί τα κλειδιά ως προς τις τιμές. Αν οι τιμές είναι τα ελληνικά γράμματα α, ν, τ, ε (όπως υποδηλώνουν οι επιλογές), η σειρά των τιμών είναι α, ε, ν, τ, δηλαδή κλειδιά 1, 4, 2, 3 και τυπώνεται αεντ. Ο βρόχος δεν τερματίστηκε με break, οπότε εκτελείται το else και τυπώνει γεια. Σωστή επιλογή: «αεντ γεια». (Αν οι τιμές στην εκφώνηση ήταν λατινικοί χαρακτήρες θα έβγαινε aetv, που δεν υπάρχει στις επιλογές.)

Ερώτηση 3 (διαίρεση με μηδέν)

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Η 3 / x δίνει 1.0 και η x - 3 δίνει 0.0. Η διαίρεση 1.0 / 0.0 σε Python δεν δίνει inf αλλά σηκώνει εξαίρεση. Σωστή επιλογή: ZeroDivisionError.

Ερώτηση 4 (τοπική/καθολική μεταβλητή)

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Η x = 2 μέσα στη f δημιουργεί τοπική μεταβλητή: η f() τυπώνει 2. Η καθολική x παραμένει 3, άρα η τελευταία print τυπώνει 3. Σωστή επιλογή: «2 3».

Ερώτηση 5 (σειρά τιμών στην print)

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Πρώτα αποτιμώνται τα ορίσματα της print: η x(2) εκτελείται και τυπώνει 5 2 και επιστρέφει 5. Μετά η print τυπώνει 5 1 (η καθολική b είναι 1). Συνολικά 5 2 5 1. Σωστή επιλογή: «5 2 5 1».

Θέμα 1Β

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Κανόνες: R1: \(S\to AB\), R2: \(A\to xAy\), R3: \(A\to\epsilon\), R4: \(B\to yB\), R5: \(B\to y\).

a. Ο R2 έχει το \(A\) ανάμεσα σε τερματικά (αναδρομή στο κέντρο), άρα η γραμματική δεν είναι κανονική: Τύπου 2 (context-free).

LL(1): όχι. Για το \(A\) ο έλεγχος περνά: FIRST(\(xAy\))={x}, και για το \(\epsilon\) χρειάζεται FOLLOW(\(A\))={y} (από το \(S\to AB\) και το \(xAy\)), δηλαδή ξένα σύνολα. Για το \(B\) όμως οι \(B\to yB\) και \(B\to y\) ξεκινούν και οι δύο με y (κοινό πρόθεμα, FIRST δεν είναι ξένα) ⇒ δεν είναι LL(1). Διορθώνεται με παραγοντοποίηση: \(B\to yB'\), \(B'\to B\mid\epsilon\).

b. \(S\Rightarrow A B\) δίνει \(x^n y^n\cdot y^m\) με \(n\ge 0\), \(m\ge 1\): οι συμβολοσειρές x…xy…y με πρώτα \(n\) x και μετά \(k=n+m>n\) y, δηλαδή περισσότερα y από x, χωρίς άλλη ανάμειξη. Παραδείγματα: y, yy, xyy, xxyyy, xxyyyy. Ελάχιστη: y.

c. Είσοδος xxyyyy$. Για την επιλογή μεταξύ \(B\to yB\) και \(B\to y\) χρειάζεται κοίταγμα 2 χαρακτήρων (αν ακολουθεί ακόμα y ή τέλος εισόδου), αφού δεν είναι LL(1).

Στοίβα (κορυφή αριστερά)	Είσοδος	Ενέργεια
S$	xxyyyy$	R1
AB$	xxyyyy$	R2 (\(A\to xAy\))
xAyB$	xxyyyy$	ταίριασμα x
AyB$	xyyyy$	R2
xAyyB$	xyyyy$	ταίριασμα x
AyyB$	yyyy$	R3 (\(A\to\epsilon\), επόμενο y)
yyB$	yyyy$	ταίριασμα y
yB$	yyy$	ταίριασμα y
B$	yy$	R4 (\(B\to yB\), ακολουθεί και άλλο y)
yB$	yy$	ταίριασμα y
B$	y$	R5 (\(B\to y\), τελευταίο y)
y$	y$	ταίριασμα y
$	$	αποδοχή

Η xxyyyy ανήκει στη γλώσσα (\(n=2\), \(m=2\)).

Λύση 2: ### a. Τύπος γραμματικής στην ιεραρχία Chomsky Η γραμματική είναι Τύπου 3 (Κανονική Γραμματική / Regular Grammar), διότι είναι δεξιά γραμμική (right-linear). Όλοι οι κανόνες παραγωγής έχουν τη μορφή \(A \to aB\) ή \(A \to \epsilon\), δηλαδή στο δεξιό μέλος υπάρχει το πολύ ένα τερματικό σύμβολο ακολουθούμενο από το πολύ ένα μη-τερματικό σύμβολο (ή η κενή συμβολοσειρά \(\epsilon\)).

b. Είδος συμβολοσειρών που περιγράφει

Η γραμματική περιγράφει όλες τις συμβολοσειρές πάνω από το αλφάβητο \(\{0, 1\}\) οι οποίες περιέχουν τουλάχιστον δύο διαδοχικά «1» (δηλαδή την υποσυμβολοσειρά 11). - Η κατάσταση εκκίνησης \(\langle S \rangle\) και η \(\langle A \rangle\) δεν έχουν \(\epsilon\)-παραγωγή, επομένως για να τερματίσει μια παραγωγή πρέπει υποχρεωτικά να φτάσει στη συντακτική κατηγορία \(\langle B \rangle\). - Η μετάβαση στην \(\langle B \rangle\) γίνεται αποκλειστικά μέσω του κανόνα \(\text{R4}: \langle A \rangle \to 1\langle B \rangle\), στον οποίο φτάνουμε μόνο από τον κανόνα \(\text{R2}: \langle S \rangle \to 1\langle A \rangle\). Επομένως απαιτείται η εμφάνιση δύο διαδοχικών άσσων (11). Μετά την εμφάνιση του 11, η \(\langle B \rangle\) μπορεί να παραγάγει οποιαδήποτε ακολουθία από \(0\) και \(1\) και να τερματίσει μέσω του \(\text{R7}: \langle B \rangle \to \epsilon\).

c. Κανονική έκφραση

Ναι, είναι δυνατή η κατασκευή κανονικής έκφρασης, διότι κάθε γραμματική Τύπου 3 παράγει μια κανονική γλώσσα (θεώρημα Kleene).

Η αντίστοιχη κανονική έκφραση είναι: $\((0 \mid 10)^* 11 (0 \mid 1)^*\)$

d. Παραγωγή (derivation) της συμβολοσειράς 011101

\[\langle S \rangle \to \text{[R1]} \ 0\langle S \rangle \to \text{[R2]} \ 01\langle A \rangle \to \text{[R4]} \ 011\langle B \rangle \to \text{[R6]} \ 0111\langle B \rangle \to \text{[R5]} \ 01110\langle B \rangle \to \text{[R6]} \ 011101\langle B \rangle \to \text{[R7]} \ 011101\]

Η συμβολοσειρά είναι μέλος της γλώσσας.

---

Λύση 3 (τρίτη γνώμη): a. Η γραμματική ανήκει στον Τύπο 2 (Γραμματικές Χωρίς Συμφραζόμενα - Context-Free Grammars) της ιεραρχίας Chomsky. Αυτό ισχύει διότι όλοι οι κανόνες παραγωγής έχουν ακριβώς ένα μη τερματικό σύμβολο στο αριστερό τους μέλος και μια ακολουθία από τερματικά και μη τερματικά σύμβολα στο δεξί τους μέλος.

Η γραμματική δεν είναι LL(1). Για να είναι μια γραμματική LL(1), δεν πρέπει να υπάρχουν συγκρούσεις στα σύνολα FIRST για κανόνες που έχουν το ίδιο αριστερό μέλος. Για το μη τερματικό \(B\), έχουμε τους κανόνες \(B \to yB\) και \(B \to y\). Ισχύει ότι \(FIRST(yB) = \{y\}\) και \(FIRST(y) = \{y\}\). Επειδή \(FIRST(yB) \cap FIRST(y) = \{y\} \neq \emptyset\), υπάρχει σύγκρουση FIRST-FIRST, άρα η γραμματική δεν είναι LL(1).

b. Το μη τερματικό \(A\) παράγει συμβολοσειρές της μορφής \(x^n y^n\) για \(n \ge 0\). Το μη τερματικό \(B\) παράγει συμβολοσειρές της μορφής \(y^m\) για \(m \ge 1\). Συνεπώς, το αρχικό σύμβολο \(S\) παράγει συμβολοσειρές της μορφής \(x^n y^{n+m}\), όπου \(n \ge 0\) και \(m \ge 1\). Δηλαδή, περιγράφει συμβολοσειρές που ξεκινούν με \(n\) σύμβολα 'x' και ακολουθούνται από \(k\) σύμβολα 'y', με την προϋπόθεση ότι το πλήθος των 'y' είναι αυστηρά μεγαλύτερο από το πλήθος των 'x' (\(k > n \ge 0\)). - Παραδείγματα αποδεκτών συμβολοσειρών: \(y\), \(xyy\), \(xxyyyy\), \(xxxyyyyy\). - Μικρότερη σε μήκος συμβολοσειρά: \(y\) (προκύπτει για \(n=0\) και \(m=1\)).

c. Η Top-Down συντακτική ανάλυση (με τη στοίβα να έχει την κορυφή της στα αριστερά) για τη συμβολοσειρά \(xxyyyy\) παρουσιάζεται παρακάτω:

Στοίβα (Κορυφή αριστερά)	Είσοδος	Ενέργεια
\(S \ \$\)	\(xxyyyy \ \$\)	Πρόβλεψη \(S \to AB\)
\(A \ B \ \$\)	\(xxyyyy \ \$\)	Πρόβλεψη \(A \to xAy\)
\(x \ A \ y \ B \ \$\)	\(xxyyyy \ \$\)	Ταίριασμα \(x\)
\(A \ y \ B \ \$\)	\(xyyyy \ \$\)	Πρόβλεψη \(A \to xAy\)
\(x \ A \ y \ y \ B \ \$\)	\(xyyyy \ \$\)	Ταίριασμα \(x\)
\(A \ y \ y \ B \ \$\)	\(yyyy \ \$\)	Πρόβλεψη \(A \to \epsilon\)
\(y \ y \ B \ \$\)	\(yyyy \ \$\)	Ταίριασμα \(y\)
\(y \ B \ \$\)	\(yyy \ \$\)	Ταίριασμα \(y\)
\(B \ \$\)	\(yy \ \$\)	Πρόβλεψη \(B \to yB\)
\(y \ B \ \$\)	\(yy \ \$\)	Ταίριασμα \(y\)
\(B \ \$\)	\(y \ \$\)	Πρόβλεψη \(B \to y\)
\(y \ \$\)	\(y \ \$\)	Ταίριασμα \(y\)
\(\$\)	\(\$\)	Αποδοχή

Θέμα 2

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

Παρατηρήσεις για τον κώδικα όπως μεταγράφηκε: το πρόγραμμα MAIN δεν δηλώνει καμία μεταβλητή· η a δηλώνεται μόνο μέσα στη X (και στη Z). Λείπει επίσης ; μετά το Z στο σώμα της X (θεωρούμε τυπογραφικό).

I. Στατικός κανόνας εμβέλειας

a. Περιβάλλοντα αναφοράς (τοπικά = δηλώσεις του τμήματος, μη τοπικά = δηλώσεις εξωτερικών τμημάτων που φαίνονται, καθολικά = του κυρίως προγράμματος):

Τμήμα	Τοπικό	Μη τοπικό	Καθολικό
MAIN	X	—	X
X	a_X, Y, Z	— (η X φαίνεται ως καθολική)	X
Y	(κανένα)	a_X, Z, Y (από την X)	X
Z	a_Z,	Y (από X)· η a_X κρύβεται από την a_Z	X

b. Λάθος εντολή: η a:= 1 στο σώμα του MAIN. Στο MAIN δεν υπάρχει ορατή a (η a είναι τοπική της X και δεν φαίνεται προς τα έξω) ⇒ σημασιολογικό λάθος (αδήλωτη μεταβλητή). Την σβήνουμε.

c. Στοίβα μόλις γίνει η κλήση της Y:

AR-MAIN() -> AR-X(a_X=5) -> AR-Z(a_Z=7) -> AR-Y()

Static chain pointers: Y → AR-X (η Y δηλώνεται στη X), Z → AR-X, X → AR-MAIN.

d. Εκτέλεση: η X θέτει \(a_X=5\) και καλεί τη Z. Η Z θέτει \(a_Z=7\) και καλεί την Y. Στη Y το a λύνεται μέσω static chain στη X: \(a_X = 5\cdot 2 = 10\). Έξοδος με τη σειρά:

• In Y:10
• In Z:7 (η Z βλέπει δική της a)
• In X:10

II. Δυναμικός κανόνας εμβέλειας

Τα ονόματα λύνονται με τη σειρά κλήσης (dynamic chain), όχι με τη δομή του κώδικα.

• a. Τα μη τοπικά περιβάλλοντα εξαρτώνται από το ποιος καλεί: η Y, όταν καλείται από τη Z, βλέπει την a_Z. Δεν υπάρχουν static chain pointers, μόνο δυναμική αλυσίδα (Y → Z → X → MAIN).
• b. Η a:=1 στο MAIN είναι πάλι λάθος (δεν υπάρχει a στο MAIN ούτε πιο πάνω στην αλυσίδα), άρα σβήνεται.
• c. Η ίδια στοίβα AR-MAIN() -> AR-X(a_X) -> AR-Z(a_Z) -> AR-Y(), αλλά το a της Y συνδέεται στην πλησιέστερη στη στοίβα, δηλαδή στην a_Z.
• d. Στη Y: \(a_Z = 7\cdot2 = 14\). Έξοδος: In Y:14, In Z:14, In X:5 (η a_X δεν άλλαξε).

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

---

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