Μορφή Μπάκους-Νάουρ

Στη θεωρητική πληροφορική, η BNF (Κανονική μορφή του Μπάκους, αγγλ. Backus Normal Form ή Μορφή Μπάκους-Νάουρ, αγγλ. Backus–Naur Form) είναι μια τεχνική συμβολισμού (μετασύνταξη) για γραμματικές χωρίς συμφραζόμενα (context-free grammars),που συχνά χρησιμοποιείται για να περιγράψει τη σύνταξη μιας γλώσσας της πληροφορικής, όπως οι γλώσσες προγραμματισμού υπολογιστών, οι τύποι εγγράφων (document formats), τα σύνολα εντολών (instruction sets) και τα πρωτόκολλα επικοινωνιών.
Εφαρμόζεται όπου χρειάζονται ακριβείς περιγραφές γλωσσών, για παράδειγμα σε επίσημους ορισμούς γλωσσών, σε εγχειρίδια, ή σε βιβλία για θεωρία γλωσσών προγραμματισμού.
Υπάρχουν πολλές επεκτάσεις και παραλλαγές της αρχικής BNF, κάποιες από αυτές είναι αυστηρά ορισμένες, όπως η Εκτεταμένη Μορφή Μπάκους-Νάουρ (Extended Backus–Naur Form, EBNF) και η Επαυξημένη Μορφή Μπάκους-Νάουρ (Augmented Backus–Naur Form, ABNF).

Ιστορία

Η ιδέα της περιγραφής της δομής μιας γλώσσας μέσα από κανόνες αναγραφής (rewriting rules) εντοπίζεται μάλλον για πρώτη φορά στο έργο του Pāṇini (περ. 4ος αιώνας π.Χ.), που τη χρησιμοποίησε για την περιγραφή της δομής των λέξεων της Σανσκριτικής γλώσσας. Αμερικανοί γλωσσολόγοι όπως ο Λέοναρντ Μπλούμφιλντ και ο Zellig Harris ανέπτυξαν την ιδέα προσπαθώντας να τυποποιήσουν τη γλώσσα και τη μελέτη αυτής με όρους τυπικών ορισμών και διαδικασιών (μεταξύ 1920-1960).
Στο μεταξύ, οι κανόνες αναγραφής συμβολοσειρών (string rewriting rules), όπως τα τυπικά αφηρημένα συστήματα εμφανίστηκαν και μελετήθηκαν από μαθηματικούς όπως ο Axel Thue (το 1914), ο Emil Post (δεκαετίες 1920-1940) και ο Άλαν Τούρινγκ (και η μηχανή Τούρινγκ του, 1936). Ο Νόαμ Τσόμσκι, διδάσκοντας γλωσσολογία σε φοιτητές της θεωρίας πληροφοριών (information theory) στο MIT, συνδύασε τη γλωσσολογία και τα μαθηματικά, πρακτικά βασίζοντας τη σύνταξη της φυσικής γλώσσας στο φορμαλισμό του Thue - εισήγαγε επίσης τον καθαρό διαχωρισμό μεταξύ κανόνων παραγωγής (generative rules, των γραμματικών χωρίς συμφραζόμενα) και κανόνων μετασχηματισμού (transformation rules), το 1956.
Ο John Backus, σχεδιαστής γλωσσών στην IBM, πρότεινε "μεταγλωσσολογικούς τύπους" ("metalinguistic formulas")
για την περιγραφή της τότε καινούριας γλώσσας προγραμματισμού IAL, γνωστής σήμερα σαν ALGOL 58 (1959), χρησιμοποιώντας το σμβολισμό BNF.
Η ανάπτυξη της ALGOL που ακολούθησε οδήγησε στην ALGOL 60· στην αναφορά του (1963), ο Peter Naur ονόμασε το συμβολισμό του Backus Κανονική Μορφή Backus και τον απλοποίησε ώστε να χρησιμοποιεί το ελάχιστο σύνολο χαρακτήρων.
Ο Ντόναλντ Κνουθ υποστήριξε όμως ότι τα αρχικά BNF θα έπρεπε να διαβάζονται σαν Backus–Naur Form (Μορφή Μπάκους-Νάουρ), γιατί "δεν πρόκειται σε καμία περίπτωση για κανονική μορφή",
σε αντίθεση, για παράδειγμα, με την Κανονική Μορφή Τσόμσκι (Chomsky Normal Form).

Εισαγωγή

Ένας ορισμός BNF είναι ένα σύνολο από κανόνες συνεπαγωγής (derivation rules) και γράφεται σαν
 <σύμβολο> ::= __έκφραση__
όπου το <σύμβολο> μπορεί να είναι μη τερματικό (non-terminal), με την έκφραση να αποτελείται από μια ή περισσότερες ακολουθίες συμβόλων. Οι περισσότερες ακολουθίες χωρίζονται μεταξύ τους με μια κάθετο, '|', που δείχνει την επιλογή. Τα σύμβολα που δεν εμφανίζονται ποτέ στα αριστερά ονομάζονται τερματικά (terminals). Αντίθετα, τα σύμβολα που εμφανίζονται στην αριστερή πλευρά είναι τα μη τερματικά, τα οποία και πάντα βρίσκονται μέσα σε <>.

Άλλα παραδείγματα

Η σύνταξη της BNF μπορεί να παρασταθεί σε BNF ως εξής:
 <σύνταξη>     ::= <κανόνας> | <κανόνας> <σύνταξη>
 <κανόνας>     ::= <προαιρ-κενό> "<" <όνομα-κανόνα> ">" <προαιρ-κενό> "::=" 
                   <προαιρ-κενό> <έκφραση> <τέλος-γραμμής>
 <προαιρ-κενό> ::= " " <προαιρ-κενό> | ""  ("" είναι η κενή συμβολοσειρά, χωρίς κενά)
 <έκφραση>     ::= <λίστα> | <λίστα> "|" <έκφραση>
 <line-end>    ::= <προαιρ-κενό> <EOL> | <τέλος-γραμμής> <τέλος-γραμμής>
 <λίστα>       ::= <όρος> | <όρος> <προαιρ-κενό> <λίστα>
 <όρος>        ::= <σταθερά> | "<" <όνομα-κανόνα> ">"
 <σταθερά>     ::= '"' <κείμενο> '"' | "'" <κείμενο> "'" (αν και η αρχική BNF δε χρησιμοποιούσε εισαγωγικά)
Η παραπάνω σύνταξη προϋποθέτει ότι δε χρειάζονται κενά για τη σωστή ερμηνεία ενός κανόνα. Το τέλος γραμμής ορίζει τον αντίστοιχο χαρακτήρα του ASCII, επιστροφή στην αρχή της γραμμής (carriage-return) και/ή νέα γραμμή (line-feed), ανάλογα με το λειτουργικό σύστημα. Το <όνομα-κανόνα> και το <κείμενο> αντικαθιστώνται με το όνομα και το κείμενο αντίστοιχα του κανόνα που ορίζεται.