Τυπική γραμματική: Διαφορά μεταξύ των αναθεωρήσεων

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

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

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

:* λειτουργεί ως δημιουργός νημάτωνστοιχειοσειρών της γλώσσας, δηλαδή ''γράφει την γλώσσα'',

:* η πορεία είναι από την γραμματική προς τις προτάσειςλέξεις της γλώσσας,

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

* ΑΛΗΘΗΣ, αν τοη νήμαστοιχειοσειρά ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική

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

:* σαρώνει τοτην νήμαστοιχειοσειρά, τεχνολογεί τα μέρη που τοτην αποτελούν και τα αναγνωρίζει, (είναι [[Συντακτική ανάλυση (προγραμματισμός)|συντακτικός αναλυτής]] (parser)), δηλαδή ''διαβάζει την γλώσσα'',

:* η πορεία είναι από τις προτάσειςλέξεις της γλώσσας προς την γραμματική της,

== Γενετικές γραμματικές ==

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

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

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

=== Τυπικός ορισμός ===

:: νήμαστοιχειοσειρά που ανήκει στο <math>(\Sigma \cup N)^{*} \longrightarrow</math> νήμαστοιχειοσειρά που ανήκει στο <math>(\Sigma \cup N)^{*} </math>

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

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

=== Παράδειγμα ===

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

* <math>\boldsymbol{S} \longrightarrow (2) abc</math>

* <math>\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (2) a\boldsymbol{Ba}bcc \longrightarrow (3) aa\boldsymbol{Bb}cc \longrightarrow (4) aabbcc</math>

* <math>\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (1) aBaB\boldsymbol{S}cc \longrightarrow (2) a\boldsymbol{Ba}Babccc</math> <math>\longrightarrow (3) aaB\boldsymbol{Ba}bccc \longrightarrow (3) aa\boldsymbol{Ba}Bbccc \longrightarrow (3) aaaB\boldsymbol{Bb}ccc</math> <math>\longrightarrow (4) aaa\boldsymbol{Bb}bccc \longrightarrow (4) aaabbbccc</math>

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

==== Συστήματα-L ====

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

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

=== Η Ιεραρχία του Τσόμσκι ===

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

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

==== Γραμματικές χωρίς συμφραζόμενα ====

==== Κανονικές γραμματικές ====

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

(όπου <math>\epsilon</math> συμβολίζει τοτην κενόκενή νήμαστοιχειοσειρά, δηλαδή έναμια νήμαστοιχειοσειρά μήκουςμε 0μήκος μηδενικό).

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

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

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

=== Άλλοι τύποι γενετικών γραμματικών ===

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

== Αναλυτικές γραμματικές ==

* [http://languagemachine.sourceforge.net Η γλωσσομηχανή] (The Language Machine) εφαρμόζει άμεσα απεριόριστες αναλυτικές γραμματικές. Χρησιμοποιούνται κανόνες αντικατάστασης για τον μετασχηματισμό μιας εισόδου σε εξόδους και συμπεριφορές. Το σύστημα μπορεί επίσης να παραγάγει [http://languagemachine.sourceforge.net/picturebook.html το διάγραμμα-lm] (the lm-diagram) που δείχνει τι συμβαίνει όταν εφαρμόζονται οι κανόνες της απεριόριστήςαπεριόριστης αναλυτικής γραμματικής.