Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Ιούνιος 2015 — Θέμα 3¶
Μεταγραφή από το στιγμιότυπο Screenshot_2.jpg (μόνο η εκφώνηση του θέματος).
Screenshot_2.jpg¶
3.10.8 Θέμα 3 Ιούνιος 2015
ΘΕΜΑ 3 (25%)¶
Δίνεται η παρακάτω BNF γραμματική, με τερματικά σύμβολα τα: a b \(\epsilon\) $\(<S> ::= b<S> \mid a<M>\)$ $\(<M> ::= b<S> \mid a<F>\)$ $\(<F> ::= b<F> \mid a<F> \mid \epsilon\)$
(a) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky; Αιτιολογήστε την απάντησή σας. (b) Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική; (c) Ελέγξτε αν η συμβολοσειρά baaaba είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ολίσθησης - Ελάττωσης Bottom-Up συντακτικής ανάλυσης.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2015-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Κανόνες: \(S \to bS \mid aM\), \(M \to bS \mid aF\), \(F \to bF \mid aF \mid \epsilon\).
(a) Κάθε κανόνας έχει τη μορφή (τερματικό)(το πολύ ένα μη τερματικό στο δεξί άκρο) ή \(\epsilon\): η γραμματική είναι δεξιά γραμμική, άρα Τύπου 3 (κανονική) στην ιεραρχία Chomsky.
(b) Διαβάζοντας τις καταστάσεις ως αυτόματο: στο \(S\) το b μένει στο \(S\), το a πάει στο \(M\) (είδαμε ένα a). Στο \(M\) το b γυρίζει στο \(S\), ενώ το a πάει στο \(F\) (είδαμε aa). Το \(F\) δέχεται τα πάντα και τελειώνει με \(\epsilon\). Άρα:
η γλώσσα είναι όλες οι συμβολοσειρές {a,b}* που περιέχουν τουλάχιστον μία φορά τη διαδοχή aa· κανονική έκφραση \((b\mid ab)^*\,aa\,(a\mid b)^*\). Ελάχιστη: aa. Παραδείγματα: aa, baa, abaab, baaaba. (Επαληθεύτηκε με πλήρη έλεγχο όλων των συμβολοσειρών μέχρι μήκος 12.)
(c) Παραγωγή: \(S \Rightarrow bS \Rightarrow baM \Rightarrow baaF \Rightarrow baaaF \Rightarrow baaabF \Rightarrow baaabaF \Rightarrow baaaba\). Το bottom-up κάνει τις αναγωγές με την αντίστροφη σειρά. Επειδή η γραμματική είναι δεξιά αναδρομική, γίνονται πρώτα όλες οι ολισθήσεις.
| Στοίβα | Είσοδος | Ενέργεια |
|---|---|---|
| $ | baaaba$ | ολίσθηση b |
| $b | aaaba$ | ολίσθηση a |
| $ba | aaba$ | ολίσθηση a |
| $baa | aba$ | ολίσθηση a |
| $baaa | ba$ | ολίσθηση b |
| $baaab | a$ | ολίσθηση a |
| $baaaba | $ | ελάττωση \(F\to\epsilon\) |
| $baaabaF | $ | ελάττωση \(F\to aF\) |
| $baaabF | $ | ελάττωση \(F\to bF\) |
| $baaaF | $ | ελάττωση \(F\to aF\) |
| $baaF | $ | ελάττωση \(M\to aF\) |
| $baM | $ | ελάττωση \(S\to aM\) |
| $bS | $ | ελάττωση \(S\to bS\) |
| $S | $ | αποδοχή |
Είσοδος άδεια και στοίβα $S ⇒ αποδοχή: η baaaba ανήκει στη γλώσσα (περιέχει aa). Το F→ε εφαρμόζεται πρώτο (δεξιά αναδρομή), γι' αυτό όλες οι ολισθήσεις προηγούνται των αναγωγών.