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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Ρομπότ: Προσθήκη: ca:Gramàtica formal; διακοσμητικές αλλαγές
μΧωρίς σύνοψη επεξεργασίας
Γραμμή 16:
:* η πορεία είναι από τις λέξεις της γλώσσας προς την γραμματική της,
:* εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.
 
 
== Γενετικές γραμματικές ==
Γραμμή 28 ⟶ 27 :
 
Κάνοντας διάφορες επιλογές κανόνων κατά την διαδικασία δημιουργίας στοιχειοσειράς, παράγουμε μιά συγκεκριμένη στοιχειοσειρά. Αν αυτή η στοιχειοσειρά μπορεί να δημιουργηθεί και με διαφορετική σειρά επιλογών, τότε λέμε ότι η γραμματική είναι [[Ασαφής γραμματική|ασαφής]] ή ότι παράγει ''αμφισημίες''.
 
 
=== Τυπικός ορισμός ===
Γραμμή 62 ⟶ 60 :
 
Είναι φανερό ότι αυτή η γραμματική ορίζει την γλώσσα, (''έστω ότι την ονομάζουμε γλώσσα-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 ====
Γραμμή 71 ⟶ 68 :
 
Τυπικά, κάθε στοιχειοσειρά σχετίζεται με ένα ''σύνολο σημείων του χώρου'', και το εξαγόμενο ενός συστήματος-L ορίζεται ότι είναι το ''όριο'' αυτών των συνόλων.
 
 
=== Η Ιεραρχία του Τσόμσκι ===
Γραμμή 77 ⟶ 73 :
 
Δυο σημαντικοί τύποι είναι η [[Γραμματική χωρίς συμφραζόμενα]] (context-free grammar) και η [[Κανονική γραμματική]] (regular grammar), και οι γλώσσες που παράγονται από τέτοιες γραμματικές ονομάζονται αντίστοιχα ''[[Γλώσσα χωρίς συμφραζόμενα]]'' και ''[[Κανονική γλώσσα]]''. Αν και δεν είναι τόσο δυνατές γραμματικές, όσο είναι η ''απεριόριστη γραμματική'' (unrestricted grammar) που μπορεί να εκφράσει οποιαδήποτε γλώσσα μπορεί να γίνει αποδεκτή από μια [[Μηχανή Τούρινγκ]] (Turing machine), αυτοί οι δυο τύποι περιορισμένων γραμματικών χρησιμοποιούνται πολύ συχνά επειδή μπορούν να δημιουργηθούν εύκολα [[Συντακτική ανάλυση (προγραμματισμός)|συντακτικοί αναλυτές]] γι’ αυτές. Πράγματι, για τις γραμματικές χωρίς συμφραζόμενα υπάρχουν πολύ γνωστοί αλγόριθμοι για την δημιουργία αποδοτικών συντακτικών αναλυτών, που είναι γραμμικοί [[Συντακτική ανάλυση (προγραμματισμός)#Συντακτικός αναλυτής LL|από αριστερά]] ή [[Συντακτική ανάλυση (προγραμματισμός)#Συντακτικός αναλυτής LR|από δεξιά]].
 
 
==== Γραμματικές χωρίς συμφραζόμενα ====
Γραμμή 86 ⟶ 81 :
: 1. <math>S \longrightarrow aSb</math>
: 2. <math>S \longrightarrow ab</math>
 
 
==== Κανονικές γραμματικές ====
Γραμμή 102 ⟶ 96 :
 
Πρακτικά, οι κανονικές γραμματικές συνήθως ορίζονται με [[Κανονική έκφραση|κανονικές εκφράσεις]].
 
 
==== Σύγκριση Κανονικής γλώσσας με Γλώσσα χωρίς συμφραζόμενα ====
Γραμμή 112 ⟶ 105 :
 
Για περισσότερες λεπτομέρειες, δείτε [[Γλώσσα χωρίς συμφραζόμενα]] και [[Κανονική γλώσσα]].
 
 
=== Άλλοι τύποι γενετικών γραμματικών ===
Γραμμή 133 ⟶ 125 :
* [[Δένδρο αφηρημένης σύνταξης]] (Abstract syntax tree)
* [[Ασαφής γραμματική]] (ambiguous grammar)
 
 
== Πηγές ==
* Το άρθρο είναι μεταφορά στα ελληνικά του άρθρου [[w:en:Formal_grammar]] της αγγλικής Βικιπαίδειας.
 
 
<table align="center" border="0" cellpadding="2" cellspacing="0" class="toccolours">