Τυπική γραμματική

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Στην Επιστήμη Υπολογιστών μια τυπική γραμματική (formal grammar) είναι μια αφηρημένη δομή που περιγράφει μια Τυπική γλώσσα επακριβώς, δηλαδή είναι ένα σύνολο κανόνων που απεικονίζουν με μαθηματικά το σύνολο, (συνήθως απειροσύνολο), των πεπερασμένου μήκους στοιχειοσειρών που σχηματίζονται με διακριτά στοιχεία (π.χ. γράμματα), τα οποία ανήκουν σε ένα σύνολο, συνήθως πεπερασμένο, που το λέμε αλφάβητο.

Οι τυπικές γραμματικές ονομάστηκαν έτσι κατ’ αναλογία των γραμματικών των γλωσσών που μιλούν οι άνθρωποι, αλλά τα αλφάβητά τους δεν περιέχουν κατ’ ανάγκη γράμματα. Οι τυπικές γραμματικές διαχωρίζονται σε δυο κύριες κατηγορίες : γενετικές (generative) και αναλυτικές (analytic).

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

Συνοπτικά για την γενετική γραμματική :

λειτουργεί ως δημιουργός στοιχειοσειρών της γλώσσας, δηλαδή γράφει την γλώσσα,
η πορεία είναι από την γραμματική προς τις λέξεις της γλώσσας,
εφαρμόζεται παραγωγική (top-down) προσέγγιση, από το γενικό προς το μερικό.

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

ΑΛΗΘΗΣ, αν η στοιχειοσειρά ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική
ΨΕΥΔΗΣ, αν η στοιχειοσειρά δεν ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική.

Συνοπτικά για την αναλυτική γραμματική :

σαρώνει την στοιχειοσειρά, τεχνολογεί τα μέρη που την αποτελούν και τα αναγνωρίζει, (είναι συντακτικός αναλυτής (parser)), δηλαδή διαβάζει την γλώσσα,
η πορεία είναι από τις λέξεις της γλώσσας προς την γραμματική της,
εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.

[Επεξεργασία] Γενετικές γραμματικές

Μια γενετική γραμματική συνίσταται από ένα σύνολο κανόνων για μετασχηματισμό στοιχειοσειρών. Για να δημιουργηθεί μια στοιχειοσειρά της γλώσσας, αρχίζουμε με μια στοιχειοσειρά που περιέχει μόνο το προκαθορισμένο αρχικό σύμβολο δημιουργίας στοιχειοσειράς, (συνήθως το ' $S$ '), και εφαρμόζοντας διαδοχικά τους κανόνες (οσεσδήποτε φορές, με οποιαδήποτε σειρά) την τροποποιούμε. Η γλώσσα αποτελείται από όλες τις στοιχειοσειρές που μπορούν να δημιουργηθούν με αυτόν τον τρόπο.

Για παράδειγμα, υποθέτουμε ότι το αλφάβητο αποτελείται από ' $a$ ' και ' $b$ ', το σύμβολο έναρξης είναι ' $S$ ' και ισχύουν οι παρακάτω κανόνες (ή νόμοι) παραγωγής:

1. $S \longrightarrow aSb$

2. $S \longrightarrow ba$

και ξεκινάμε με την στοιχειοσειρά " $S$ ", και μπορούμε να επιλέξουμε έναν κανόνα για να τον εφαρμόσουμε στην στοιχειοσειρά. Αν επιλέξουμε τον κανόνα 1, αντικαθιστούμε το ' $S$ ' με ' $a S b$ ' και παίρνουμε την " $a S b$ ". Αν επιλέξουμε πάλι τον κανόνα 1, αντικαθιστούμε το ' $S$ ' με ' $a S b$ ' και παίρνουμε την " $a a S b b$ ". Η διαδικασία συνεχίζεται μέχρι η στοιχειοσειρά να περιέχει μόνο στοιχεία από το αλφάβητο (δηλαδή ' $a$ ' και ' $b$ '). Για να περαιωθεί το παράδειγμα, αν επιλέξουμε τώρα τον κανόνα 2, αντικαθιστούμε το ' $S$ ' με ' $b a$ ' και παίρνουμε την " $a a b a b b$ ", οπότε τελειώσαμε. Μπορούμε να γράψουμε αυτή την σειρά επιλογών πιο συνοπτικά, χρησιμοποιώντας σύμβολα : $S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow aababb$ . Η γλώσσα της γραμματικής είναι το σύνολο όλων των στοιχειοσειρών που μπορούν να παραχθούν με εφαρμογή αυτής της διαδικασίας : $\left \{ba, abab, aababb, aaababbb, ...\right \}$ .

Κάνοντας διάφορες επιλογές κανόνων κατά την διαδικασία δημιουργίας στοιχειοσειράς, παράγουμε μιά συγκεκριμένη στοιχειοσειρά. Αν αυτή η στοιχειοσειρά μπορεί να δημιουργηθεί και με διαφορετική σειρά επιλογών, τότε λέμε ότι η γραμματική είναι ασαφής ή ότι παράγει αμφισημίες.

[Επεξεργασία] Τυπικός ορισμός

Στην κλασσική τυποποίηση των γενετικών γραμματικών, που πρώτος παρουσίασε ο Νόαμ Τσόμσκι το 1956, μια γραμματική G αποτελείται από τα παρακάτω μέρη:

Ένα πεπερασμένο σύνολο $N$ μη–τελικών (nonterminal) συμβόλων.
Ένα πεπερασμένο σύνολο $Σ$ τελικών (terminal) συμβόλων, το οποίο έχει τομή με το $N$ το κενό σύνολο.
Ένα πεπερασμένο σύνολο $P$ κανόνων παραγωγής, όπου κάθε κανόνας έχει την μορφή

στοιχειοσειρά που ανήκει στο $(\Sigma \cup N)^{*} \longrightarrow$ στοιχειοσειρά που ανήκει στο $(\Sigma \cup N)^{*}$

(όπου

*

είναι Αστέρι Κλέινι και $\cup$ είναι ένωση συνόλων) με τον περιορισμό ότι η αριστερή πλευρά του κανόνα (δηλαδή το μέρος που βρίσκεται αριστερά από το $\longrightarrow$ ) πρέπει να περιέχει τουλάχιστον ένα μη–τελικό σύμβολο.

Ένα σύμβολο $S$ που ανήκει στο $N$ και προσδιορίζεται ως αρχικό σύμβολο δημιουργίας στοιχειοσειράς (ή απλούστερα αρχικό σύμβολο).

Συνήθως, η τυπική γραμματική δηλώνεται ως μια διατεταγμένη τετράδα

G

(N,Σ, P, S)

Η γλώσσα μιας τυπικής γραμματικής $G = (N,Σ, P, S)$ , που συμβολίζεται $\boldsymbol{L}(G)$ , ορίζεται ως το σύνολο όλων των στοιχειοσειρών του $Σ$ που μπορούν να παραχθούν ξεκινώντας από μια στοιχειοσειρά με περιεχόμενο το αρχικό σύμβολο $S$ και εφαρμόζοντας επαναληπτικά στην στοιχειοσειρά τους κανόνες παραγωγής του $P$ μέχρι να μη περιέχει η στοιχειοσειρά μη–τελικά σύμβολα.

[Επεξεργασία] Παράδειγμα

Για τα παραδείγματα αυτά, τα σχετικά με τις τυπικές γλώσσες σύνολα καθορίζονται με τον συμβολισμό δόμησης συνόλου.

Θεωρούμε, για παράδειγμα, την γραμματική $G 1$ με $N = \left \{S, B\right \}$ , $\Sigma = \left \{a, b, c\right \}$ , το $P$ να απαρτίζεται από τους ακόλουθους κανόνες παραγωγής

1. $S \longrightarrow aBSc$

2. $S \longrightarrow abc$

3. $Ba \longrightarrow aB$

4. $Bb \longrightarrow bb$

και το μη–τελικό σύμβολο $S$ ως αρχικό σύμβολο. Μερικά δείγματα παραγωγής στοιχειοσειρών της γλώσσας $\boldsymbol{L}(G1)$ ακολουθούν, (και σημειώνουμε σε παρένθεση τον αριθμό του κανόνα που χρησιμοποιείται, και με έντονη γραφή το τμήμα της στοιχειοσειράς που αντικαθίσταται):

$\boldsymbol{S} \longrightarrow (2) abc$
$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (2) a\boldsymbol{Ba}bcc \longrightarrow (3) aa\boldsymbol{Bb}cc \longrightarrow (4) aabbcc$
$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (1) aBaB\boldsymbol{S}cc \longrightarrow (2) a\boldsymbol{Ba}Babccc$ $\longrightarrow (3) aaB\boldsymbol{Ba}bccc \longrightarrow (3) aa\boldsymbol{Ba}Bbccc \longrightarrow (3) aaaB\boldsymbol{Bb}ccc$ $\longrightarrow (4) aaa\boldsymbol{Bb}bccc \longrightarrow (4) aaabbbccc$

Είναι φανερό ότι αυτή η γραμματική ορίζει την γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-1), $\left \{ a^{n}b^{n}c^{n} | n > 0 \right \}$ , όπου $a n$ είναι μια στοιχειοσειρά μήκους n αποτελούμενη από χαρακτήρες $a$ . Επομένως, η πλήρης γλώσσα συνίσταται από στοιχειοσειρές που έχουν στην αρχή τους ένα θετικό πλήθος από χαρακτήρες 'a', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'b', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'c'.

[Επεξεργασία] Συστήματα-L

Οι τυπικές γενετικές γραμματικές είναι παρόμοιες με τα συστήματα-L (συστήματα Lindenmayer), με τις εξής διαφορές:

τα συστήματα-L δεν έχουν διάκριση μεταξύ τελικών και μη–τελικών συμβόλων,
τα συστήματα-L έχουν περιορισμούς στην σειρά εφαρμογής των κανόνων,
τα συστήματα-L δεν έχουν πέρας εφαρμογής των κανόνων, και δημιουργούν μια άπειρη ακολουθία στοιχειοσειρών.

Τυπικά, κάθε στοιχειοσειρά σχετίζεται με ένα σύνολο σημείων του χώρου, και το εξαγόμενο ενός συστήματος-L ορίζεται ότι είναι το όριο αυτών των συνόλων.

[Επεξεργασία] Η Ιεραρχία του Τσόμσκι

Όταν πρώτος ο Νόαμ Τσόμσκι περιέγραψε τυπικά τις γενετικές γραμματικές το 1956, τις ταξινόμησε σε τέσσερις τύπους, που τώρα είναι γνωστοί ως Ιεραρχία του Τσόμσκι. Η διαφοροποίηση μεταξύ των τύπων έγκειται στο ότι διαδοχικά αυτοί έχουν κανόνες παραγωγής αυξανόμενης αυστηρότητας, οπότε μπορούν να εκφράσουν λιγότερες τυπικές γλώσσες.

Δυο σημαντικοί τύποι είναι η Γραμματική χωρίς συμφραζόμενα (context-free grammar) και η Κανονική γραμματική (regular grammar), και οι γλώσσες που παράγονται από τέτοιες γραμματικές ονομάζονται αντίστοιχα Γλώσσα χωρίς συμφραζόμενα και Κανονική γλώσσα. Αν και δεν είναι τόσο δυνατές γραμματικές, όσο είναι η απεριόριστη γραμματική (unrestricted grammar) που μπορεί να εκφράσει οποιαδήποτε γλώσσα μπορεί να γίνει αποδεκτή από μια Μηχανή Τούρινγκ (Turing machine), αυτοί οι δυο τύποι περιορισμένων γραμματικών χρησιμοποιούνται πολύ συχνά επειδή μπορούν να δημιουργηθούν εύκολα συντακτικοί αναλυτές γι’ αυτές. Πράγματι, για τις γραμματικές χωρίς συμφραζόμενα υπάρχουν πολύ γνωστοί αλγόριθμοι για την δημιουργία αποδοτικών συντακτικών αναλυτών, που είναι γραμμικοί από αριστερά ή από δεξιά.

[Επεξεργασία] Γραμματικές χωρίς συμφραζόμενα

Σε μια Γραμματική χωρίς συμφραζόμενα, το αριστερό μέρος του κανόνα παραγωγής περιέχει μόνο ένα μη–τελικό σύμβολο. Η γλώσσα-1 που ορίστηκε προηγουμένως δεν είναι «Γλώσσα χωρίς συμφραζόμενα», αλλά η επόμενη είναι:

Είναι «Γλώσσα χωρίς συμφραζόμενα» η γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-2), $\left \{ a^{n}b^{n} | n > 0 \right \}$ (οποιοδήποτε θετικό πλήθος χαρακτήρων 'a', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'b'), που ορίζεται με την γραμματική $G 2$ που έχει $N=\left \{S\right \}$ , $\Sigma=\left \{a,b\right \}$ , αρχικό σύμβολο $S$ , και τους παρακάτω κανόνες παραγωγής:

1. $S \longrightarrow aSb$

2. $S \longrightarrow ab$

[Επεξεργασία] Κανονικές γραμματικές

Σε μια Κανονική γραμματική, το αριστερό μέρος του κανόνα παραγωγής περιέχει μόνο ένα μη–τελικό σύμβολο, αλλά και το δεξιό μέρος του κανόνα έχει περιορισμό: Επιτρέπεται να είναι κενό, ή να περιέχει μόνο ένα μη–τελικό σύμβολο, ή να περιέχει μόνο ένα τελικό σύμβολο ακολουθούμενο από ένα μη–τελικό σύμβολο. (Ενίοτε χρησιμοποιείται ένας ευρύτερος ορισμός: επιτρέπονται μακρύτερες στοιχειοσειρές τελικών συμβόλων ή μόνο μη–τελικά σύμβολα, ώστε να είναι ευκολότερη η περιγραφή της γλώσσας, χωρίς να αλλάζει ο τύπος της γλώσσας). Η γλώσσα-2 που ορίσαμε προηγουμένως δεν είναι κανονική, αλλά η επόμενη είναι:

Είναι «Κανονική γλώσσα» η γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-3), $\left \{ a^{n}b^{m} | m, n > 0 \right \}$ (οποιοδήποτε θετικό πλήθος χαρακτήρων 'a', ακολουθούμενο από οποιοδήποτε θετικό πλήθος χαρακτήρων 'b', όπου τα δύο πλήθη μπορεί να διαφέρουν), καθώς μπορεί να οριστεί από την γραμματική $G 3$ με $N=\left \{S, A, B\right \}$ , $\Sigma=\left \{a, b\right \}$ , αρχικό σύμβολο $S$ , και τους ακόλουθους κανόνες παραγωγής:

1. $S \longrightarrow aA$

2. $A \longrightarrow aA$

3. $A \longrightarrow bB$

4. $B \longrightarrow bB$

5. $B \longrightarrow \epsilon$

(όπου $ε$ συμβολίζει την κενή στοιχειοσειρά, δηλαδή μια στοιχειοσειρά με μήκος μηδενικό).

Πρακτικά, οι κανονικές γραμματικές συνήθως ορίζονται με κανονικές εκφράσεις.

[Επεξεργασία] Σύγκριση Κανονικής γλώσσας με Γλώσσα χωρίς συμφραζόμενα

Πέρα από τις διαφορές στους κανόνες παραγωγής, που απαιτούνται για να παραχθούν οι δυο τύποι γλωσσών, η ουσιαστική διαφορά μεταξύ της χωρίς συμφραζόμενα γλώσσας-2

$\left \{ a^{n}b^{n} | n > 0 \right \}$

και της κανονικής γλώσσας-3

$\left \{ a^{n}b^{m} | n, m > 0 \right \}$

είναι η προδιαγραφή ότι το πλήθος των χαρακτήρων 'a' πρέπει να είναι ίσο με το πλήθος των χαρακτήρων 'b' στην χωρίς συμφραζόμενα γλώσσα-2. Επομένως, οποιοδήποτε αυτόματο που θα προσπαθήσει να αναλύσει συντακτικά τις στοιχειοσειρές της γλώσσας χωρίς συμφραζόμενα πρέπει κατ’ ανάγκη να κρατάει λογαριασμό για περισσότερες πληροφορίες από εκείνο το αυτόματο που θα αναλύσει συντακτικά την κανονική γλώσσα. Το τελευταίο δεν χρειάζεται να μετρήσει το πλήθος των 'a' και των 'b', αλλά το μόνο που απαιτείται είναι να βεβαιώσει ότι το πλήθος καθενός δεν είναι μηδενικό.

Για περισσότερες λεπτομέρειες, δείτε Γλώσσα χωρίς συμφραζόμενα και Κανονική γλώσσα.

[Επεξεργασία] Άλλοι τύποι γενετικών γραμματικών

Πολλές επεκτάσεις και παραλλαγές της πρωτότυπης ιεράρχησης, (Ιεραρχία Τσόμσκι), των τυπικών γραμματικών έχουν πρόσφατα αναπτυχθεί, και από γλωσσολόγους και από πληροφορικούς, είτε για αυξήσουν την εκφραστική ισχύ των γραμματικών, είτε για να τις κάνουν προσιτές σε συντακτική (ή άλλη) ανάλυση. Βέβαια αυτοί οι δυο στόχοι είναι αντιδιαμετρικοί : όσο περισσότερο εκφραστική είναι μια τυπική γραμματική, τόσο δυσκολότερο είναι να αναλυθεί, συντακτικά ή αλλιώς, με αυτοματοποιημένες μεθόδους. Μερικοί τύποι γραμματικών, που έχουν αναπτυχθεί πρόσφατα, είναι:

Η Γραμματική προσάρτησης δένδρων (Tree-adjoining grammar) αυξάνει την εκφραστικότητα της συμβατικής γενετικής γραμματικής με το να επιτρέπει στους κανόνες παραγωγής να επενεργούν σε δένδρα συντακτικής ανάλυσης και όχι μόνο σε στοιχειοσειρές.
Η Γραμματική παραθημάτων (Affix grammar) και η Γραμματική ιδιοτήτων (attribute grammar) επιτρέπουν την επαύξηση των παραγωγικών κανόνων με σημασιολογικές ιδιότητες και λειτουργίες, και είναι και οι δύο χρήσιμες στην αύξηση της εκφραστικότητας της γραμματικής και στην κατασκευή εύχρηστων εργαλείων μετάφρασης γλωσσών.

Ένα ετήσιο συνέδριο είναι αφιερωμένο στις τυπικές γραμματικές.

[Επεξεργασία] Αναλυτικές γραμματικές

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

Η γλωσσομηχανή (The Language Machine) εφαρμόζει άμεσα απεριόριστες αναλυτικές γραμματικές. Χρησιμοποιούνται κανόνες αντικατάστασης για τον μετασχηματισμό μιας εισόδου σε εξόδους και συμπεριφορές. Το σύστημα μπορεί επίσης να παραγάγει το διάγραμμα-lm (the lm-diagram) που δείχνει τι συμβαίνει όταν εφαρμόζονται οι κανόνες της απεριόριστης αναλυτικής γραμματικής.
Γλώσσα παραγωγικής συντακτικής ανάλυσης (Top-down parsing language, TDPL) : ένας εξαιρετικά μινιμαλιστικός φορμαλισμός αναλυτικών γραμματικών που αναπτύχθηκε στην αρχή της δεκαετίας 1970 για την μελέτη των παραγωγικών (top-down) συντακτικών αναλυτών (parser).
Γραμματική συντακτικής ανάλυσης εκφράσεων (Parsing expression grammar, PEG) : μια πρόσφατη γενίκευση της TDPL σχεδιασμένη να αντιμετωπίσει τις ανάγκες εκφραστικότητας (expressiveness) για συγγραφείς γλωσσών προγραμματισμού και συμβολομεταφραστών.
Γραμματική σύνδεσης (Link grammar) : μια μορφή αναλυτικής γραμματικής, σχεδιασμένη για την Γλωσσολογία, που εξετάζει τις σχέσεις θέσεων σε ζεύγη λέξεων και παράγει συντακτική δομή.

[Επεξεργασία] Δείτε επίσης

Δένδρο συντακτικής ανάλυσης (Parse tree)
Δένδρο αφηρημένης σύνταξης (Abstract syntax tree)
Ασαφής γραμματική (ambiguous grammar)

[Επεξεργασία] Πηγές

Το άρθρο είναι μεταφορά στα ελληνικά του άρθρου w:en:Formal_grammar της αγγλικής Βικιπαίδειας.

Θεωρία αυτομάτων: τυπικές γλώσσες και τυπικές γραμματικές
Ιεραρχία Τσόμσκι	Γραμματικές	Γλώσσες	Ελάχιστο αυτόματο
Τύπος-0	Απεριόριστες	Αναδρομικά αριθμήσιμη	Μηχανή Τούρινγκ
-	(χωρίς κοινό όνομα)	Αναδρομική	Αποφασιστής
Τύπος-1	Με συμφραζόμενα	Με συμφραζόμενα	Γραμμικό φραγμένο
Τύπος-2	Χωρίς συμφραζόμενα	Χωρίς συμφραζόμενα	Σωρού
Τύπος-3	Κανονική	Κανονική	Πεπερασμένο
Κάθε κατηγορία γλώσσας ή γραμματικής είναι γνήσιο υποσύνολο της κατηγορίας που είναι ακριβώς από πάνω της.

Ανακτήθηκε από "http://el.wikipedia.org../../../%CF%84/%CF%85/%CF%80/%CE%A4%CF%85%CF%80%CE%B9%CE%BA%CE%AE_%CE%B3%CF%81%CE%B1%CE%BC%CE%BC%CE%B1%CF%84%CE%B9%CE%BA%CE%AE.html"

Κατηγορίες: Τυπικές γλώσσες

We provide Linux to the World