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

Στη θεωρητική πληροφορική, η 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.[1][2]

Ο John Backus, σχεδιαστής γλωσσών στην IBM, πρότεινε "μεταγλωσσολογικούς τύπους" ("metalinguistic formulas")[3][4] για την περιγραφή της τότε καινούριας γλώσσας προγραμματισμού IAL, γνωστής σήμερα σαν ALGOL 58 (1959), χρησιμοποιώντας το σμβολισμό BNF.

Η ανάπτυξη της ALGOL που ακολούθησε οδήγησε στην ALGOL 60· στην αναφορά του (1963), ο Peter Naur ονόμασε το συμβολισμό του Backus Κανονική Μορφή Backus και τον απλοποίησε ώστε να χρησιμοποιεί το ελάχιστο σύνολο χαρακτήρων. Ο Ντόναλντ Κνουθ υποστήριξε όμως ότι τα αρχικά BNF θα έπρεπε να διαβάζονται σαν Backus–Naur Form (Μορφή Μπάκους-Νάουρ), γιατί "δεν πρόκειται σε καμία περίπτωση για κανονική μορφή",[5] σε αντίθεση, για παράδειγμα, με την Κανονική Μορφή Τσόμσκι (Chomsky Normal Form).

άλλες γλώσσες