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

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

Εισαγωγή

Ένας ορισμός BNF είναι ένα σύνολο από κανόνες συνεπαγωγής (derivation rules) και γράφεται σαν

 <σύμβολο> ::= __έκφραση__

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

Παράδειγμα

Σαν παράδειγμα μπορούμε να θεωρήσουμε την παρακάτω πιθανή BNF για ταχυδρομικές διευθύνσεις:

 <ταχυδρομική-διεύθυνση> ::= <μέρος-ονόματος> <διεύθυνση-οδός> <περιοχή>
 
        <μέρος-ονόματος> ::= <προσωπικό> <επώνυμο> <EOL> 
                           | <προσωπικό> <μέρος-ονόματος> <EOL>
  
             <προσωπικό> ::= <μικρό-όνομα> | <αρχικό> "." 
 
        <διεύθυνση-οδός> ::= <αριθμός> <όνομα-οδού> <EOL>
 
               <περιοχή> ::= <όνομα-πόλης> "," <όνομα-νομού> <ταχ-κώδικας> <EOL>

Η περιγραφή αυτή μεταφράζεται ως εξής:

• Μια ταχυδρομική διεύθυνση αποτελείται από ένα όνομα, που ακολουθείται από μια διεύθυνση και μια οδό, που ακολουθείται από μια περιοχή.
• Ένα όνομα αποτελείται: είτε από ένα προσωπικό όνομα που ακολουθείται από το επώνυμο και το τέλος γραμμής, είτε από ένα προσωπικό όνομα που ακολουθείται από ένα όνομα (σε αυτήν την περίπτωση έχουμε αναδρομή στη BNF, για τους ανθρώπους που έχουν πολλά μικρά ονόματα ή αρχικά) και το τέλος γραμμής.
• Ένα προσωπικό όνομα αποτελείται είτε από ένα μικρό όνομα, είτε από ένα αρχικό γράμμα που ακολουθείται από μια τελεία.
• Μια διεύθυνση αποτελείται από τον αριθμό της οικίας, το όνομα της οδού, και τέλος το τέλος της γραμμής.
• Μια περιοχή αποτελείται από ένα όνομα πόλης, που ακολουθείται από κόμμα, που ακολουθείται από το όνομα του νομού, τον ταχυδρομικό κώδικα, και το τέλος της γραμμής.

Σε αυτό το παράδειγμα, φαίνεται ότι κάποια πράγματα (όπως το μικρό όνομα, το επώνυμο και ο αριθμός οδού) δεν ορίζονται - φυσικά μπορούν και αυτά να οριστούν με επιπλέον κανόνες BNF.

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

Η σύνταξη της BNF μπορεί να παρασταθεί σε BNF ως εξής:

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

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

Παραλλαγές

Υπάρχουν πολλές παραλλαγές και επεκτάσεις της BNF, συνήθως με σκοπό την απλότητα ή την οικονομία, ή για συγκεκριμένες εφαρμογές. Συνηθισμένο χαρακτηριστικό σε πολλές παραλλαγές είναι η χρήση τελεστών κανονικών εκφράσεων όπως ο * και ο +. Η Εκτεταμένη Μορφή Μπάκους-Νάουρ (Extended Backus–Naur Form, EBNF) είναι αρκετά συνηθισμένη - ακόμα και το παραπάνω παράδειγμα, δεν ήταν στην αρχική μορφή που χρησιμοποιήθηκε στην αναφορά της ALGOL 60. Η σημειογραφία με τις αγκύλες "[ ]" εισήχθηκε κάποια χρόνια αργότερα, από τον ορισμό της IBM για την PL/I αλλά σήμερα είναι ευρέως αποδεκτός. Η Επαυξημένη Μορφή Μάκους-Νάουρ (Augmented Backus–Naur Form, ABNF) και η RBNF είναι δύο άλλες επεκτάσεις που χρησιμοποιούνται συχνά για την περιγραφών πρωτοκόλλων της Internet Engineering Task Force (IETF).

Οι γραμματικές συντακτικής ανάλυσης εκφράσεων (parsing expression grammars) βασίζονται στη BNF και σε συμβολισμούς κανονικών εκφράσεων για το σχηματισμό μιας εναλλακτικής κλάσης τυπικών γραμματικών, που είναι αναλυτικές, αντί για παραγωγικές γραμματικές (generative grammars).

Πολλοί ορισμοί BNF που υπάρχουν διαθέσιμοι στο Διαδίκτυο σήμερα προσπαθούν να είναι ευανάγνωστοι και όχι τυπικοί. Συχνά περιλαμβάνουν τους εξής συντακτικούς κανόνες και επεκτάσεις:

• Προαιρετικά αντικείμενα μέσα σε τετράγωνες αγκύλες, π.χ. [<αντικείμενο-x>]
• Αντικείμενα που επαναλαμβάνονται 0 ή περισσότερες φορές τοποθετούνται σε αγκύλες ή στο τέλος τους προστίθεται ένας αστερίσκος, π.χ. <λέξη> ::= <γράμμα> {<γράμμα>}
• Αντικείμενα που επαναλαμβάνονται 1 ή περισσότερες φορές ακολουθούνται από '+'
• Τα τερματικά σύμβολα μπορούν να εμφανίζονται με έντονη γραφή και τα μη-τερματικά σε απλή γραφή (και όχι σε πλάγια γραφή και μέσα σε σύμβολα <, >)
• Η επιλογή μεταξύ εναλλακτικών σε μια παραγωγή δείχνεται με το σύμβολο ‘|’. Π.χ., <εναλλακτική-A> | <εναλλακτική-B>
• Η ομαδοποίηση αντικειμένων γίνεται με παρενθέσεις

Δείτε επίσης

• Εκτεταμένη Μορφή Μπάκους-Νάουρ
• Ψευδοκώδικας, μια παρόμοια έννοια

Λογισμικό που χρησιμοποιεί BNF

• Yacc, γεννήτρια συντακτικών αναλυτών (χρησιμοποιείται μαζί με το Lex).
• ANTLR, γεννήτρια συντακτικών αναλυτών γραμμένη σε Java.
• BNF Converter (BNFC) (BNFC).
• Coco/R, γεννήτρια μεταγλωττιστών που δέχεται γραμματικές χαρακτηριστικών (attributed grammars) σε EBNF.
• GNU bison, η έκδοση GNU του yacc.
• RPA, BNF συντακτική ανάλυση. Επίδειξη συντακτικής ανάλυσης με σελίδα PHP: JavaScript, XML.

Αναφορές

1. Chomsky, Noam (1956). «Three models for the description of language». IRE Transactions on Information Theory 2 (2): 113–124. doi:10.1109/TIT.1956.1056813. Αρχειοθετήθηκε από το πρωτότυπο στις 2010-09-19. https://web.archive.org/web/20100919021754/http://www.chomsky.info/articles/195609--.pdf. Ανακτήθηκε στις 2011-05-27. 
2. Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton. 
3. Backus, J.W. (1959). «The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference». Proceedings of the International Conference on Information Processing. UNESCO, σελ. 125–132. http://www.softwarepreservation.org/projects/ALGOL/paper/Backus-Syntax_and_Semantics_of_Proposed_IAL.pdf/view. 
4. Farrell, James A. (Αύγουστος 1995). «Extended Backus Naur Form». Extended Backus Naur Form. http://www.cs.man.ac.uk/~pjj/farrell/comp2.html#EBNF. Ανακτήθηκε στις 2011-05-11. 
5. "not a normal form in any sense", Knuth, Donald E. (1964). «Backus Normal Form vs. Backus Naur Form». Communications of the ACM 7 (12): 735–736. doi:10.1145/355588.365140. 

Εξωτερικοί σύνδεσμοι

• Μεταγλωττιστές (διαφάνειες), ΕΜΠ.
• Backus Normal Form vs. Backus-Naur Form - ιστορικά στοιχεία των δύο όρων. (Αγγλικά)
• BNF and EBNF: What are they and how do they work?, Lars Marius Garshol. (Αγγλικά)
• Comparison of different variants of BNF (Αγγλικά)

Γραμματικές γλωσσών

• Algol-60 BNF, η αρχική BNF.
• Γραμματικές BNF για την SQL-92, την SQL-99 και την SQL-2003 Αρχειοθετήθηκε 2010-04-14 στο Wayback Machine., ελεύθερα διαθέσιμες γραμματικές της SQL.
• BNF Web Club, ελεύθερα διαθέσιμες γραμματικές της SQL, της Ada και της Java.
• Free Programming Language Grammars for Compiler Construction, ελεύθερα διαθέσιμες γραμματικές των C/C++, της Pascal, της COBOL, της Ada 95 και της PL/I.