Editing Backus–Naur form (section)

==History==
The concept of using [[Rewrite rule|rewriting rules]] to describe language structure traces back to at least [[Pāṇini]], an ancient Indian Sanskrit grammarian who lived sometime between the 6th and 4th centuries [[Before Christ|BC]].<ref>{{cite web |title=Panini biography |url=http://www-gap.dcs.st-and.ac.uk/~history/Biographies/Panini.html |access-date=2014-03-22 |publisher=School of Mathematics and Statistics, University of St Andrews, Scotland}}</ref> His notation for describing [[Sanskrit]] word structure is equivalent in power to that of BNF and exhibits many similar properties.<ref>{{cite journal |last=Ingerman |first=Peter Zilahy |date=March 1967 |title="Pāṇini-Backus Form" Suggested |journal=Communications of the ACM |volume=10 |issue=3 |page=137 |doi=10.1145/363162.363165 |s2cid=52817672 |doi-access=free}}</ref>

In Western society, grammar was long regarded as a subject for teaching rather than scientific study; descriptions were informal and targeted at practical usage. This perspective shifted in the first half of the 20th century, when linguists such as [[Leonard Bloomfield]] and [[Zellig Harris]] began attempts to formalize language description, including [[Phrase structure rules|phrase structure]]. Meanwhile, mathematicians explored related ideas through [[Semi-Thue system|string rewriting rules]] as [[formal logical systems]], such as [[Axel Thue]] in 1914, [[Emil Post]] in the 1920s–40s,<ref>{{cite journal |last=Post |first=Emil L. |year=1943 |title=Formal Reductions of the General Combinatorial Decision Problem |journal=American Journal of Mathematics |volume=65 |issue=2 |pages=197–215 |doi=10.2307/2371804}}</ref> and [[Vertical bar|Alan Turing]] in 1936. [[Noam Chomsky]], teaching linguistics to students of [[information theory]] at [[MIT]] combined linguistics and mathematics, adapting Thue's formalism to describe natural language syntax. In 1956, he introduced a clear distinction between generative rules (those of [[Context-free grammar|context-free grammars]]) and transformation rules.<ref>{{cite journal |last=Chomsky |first=Noam |year=1956 |title=Three models for the description of language |journal=IRE Transactions on Information Theory |volume=2 |issue=3 |pages=113–24 |doi=10.1109/TIT.1956.1056813 |s2cid=19519474}}</ref><ref name="Chomsky19573">{{cite book |last=Chomsky |first=Noam |title=Syntactic Structures |title-link=Syntactic Structures |publisher=Mouton |year=1957 |location=The Hague}}</ref>

BNF itself emerged when [[John Backus]], a programming language designer at [[IBM]], proposed a [[metalanguage]] of ''metalinguistic formulas'' to define the syntax of the new programming language IAL, known today as [[ALGOL 58]], in 1959.<ref name="Backus.19695">{{Cite book |last=Backus |first=J. W. |title=Proceedings of the International Conference on Information Processing |publisher=UNESCO |year=1959 |pages=125–132 |contribution=The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference}}</ref> This notation was formalized in the [[ALGOL 60]] report, where [[Peter Naur]] named it ''Backus normal form'' in the committee's 1963 report.<ref name="ALGOL60RPT3">Revised ALGOL 60 report section 1.1. {{cite web |title=ALGOL 60 |url=http://www.masswerk.at/algol60/report.htm |access-date=April 18, 2015}}</ref> Whether Backus was directly influenced by Chomsky's work is uncertain.<ref>{{cite web |last=Fulton |first=Scott M., III |date=20 March 2007 |title=John W. Backus (1924 - 2007) |url=http://betanews.com/2007/03/20/john-w-backus-1924-2007 |access-date=Jun 3, 2014 |publisher=BetaNews, Inc.}}</ref><ref>{{cite report |url=https://archive.computerhistory.org/resources/text/Oral_History/Backus_John/Backus_John_1.oral_history.2006.102657970.pdf |title=Oral History of John Backus |author=John Backus |date=Sep 2006 |publisher=Computer History Museum |editor=Grady Booch}} Here: p.25</ref>

[[Donald Knuth]] argued in 1964 that BNF should be read as ''Backus–Naur form'', as it is "not a [[Normal form (term rewriting)|normal form]] in the conventional sense," unlike [[Chomsky normal form]].<ref>{{cite journal |last=Knuth |first=Donald E. |year=1964 |title=Backus Normal Form vs. Backus Naur Form |journal=Communications of the ACM |volume=7 |issue=12 |pages=735–736 |doi=10.1145/355588.365140 |s2cid=47537431 |doi-access=free}}</ref> In 1967, Peter Zilahy Ingerman suggested renaming it ''Pāṇini Backus form'' to acknowledge Pāṇini's earlier, independent development of a similar notation.<ref>{{cite journal |last=Ingerman |first=P. Z. |year=1967 |title="Pāṇini Backus Form" suggested |journal=Communications of the ACM |volume=10 |issue=3 |page=137 |doi=10.1145/363162.363165 |s2cid=52817672 |doi-access=free}}</ref>

In the ALGOL 60 report, Naur described BNF as a ''metalinguistic formula'':<ref name=ALGOL60RPT>Revised ALGOL 60 report section. 1.1.{{cite web|url=http://www.masswerk.at/algol60/report.htm|title=ALGOL 60|access-date=April 18, 2015}}</ref>

{{blockquote|Sequences of characters enclosed in the brackets <> represent metalinguistic variables whose values are sequences of symbols. The marks "::{{=}}" and "{{pipe}}" (the latter with the meaning of "or") are metalinguistic connectives. Any mark in a formula, which is not a variable or a connective, denotes itself. Juxtaposition of marks or variables in a formula signifies juxtaposition of the sequence denoted.}}

This is exemplified in the report's section 2.3, where comments are specified:<blockquote>For the purpose of including text among the symbols of a program the following "comment" conventions hold:

{| class="wikitable" 
! The sequence of basic symbols:
! is equivalent to
|----
| ''';''' '''comment''' &lt;any sequence not containing ';'&gt;;
| ''';'''
|----
| '''begin''' '''comment''' &lt;any sequence not containing ';'&gt;;
| '''begin'''
|----
| '''end''' &lt;any sequence not containing 'end' or ';' or 'else'&gt;
| '''end'''
|}

Equivalence here means that any of the three structures shown in the left column may be replaced, in any occurrence outside of strings, by the symbol shown in the same line in the right column without any effect on the action of the program.</blockquote>

Naur altered Backus's original symbols for ALGOL 60, changing <code>:≡</code> to <code>::=</code> and the overbarred "{{overline|or}}" to <code>|</code>, using commonly available characters.<ref name="Backus.1969">
{{Cite book |last=Backus |first=J. W. |author-link=John W. Backus |title=Proceedings of the International Conference on Information Processing |publisher=UNESCO |year=1959 |pages=125–132 |contribution=The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference |contribution-url=http://www.softwarepreservation.org/projects/ALGOL/paper/Backus-Syntax_and_Semantics_of_Proposed_IAL.pdf/view}}</ref>{{rp|14}} 

BNF is very similar to [[Canonical form (Boolean algebra)|canonical-form]] [[Boolean algebra]] equations (used in logic-circuit design), reflecting Backus's mathematical background as a FORTRAN designer.<ref name="class2">{{cite web |last=Naur |first=Peter |date=1961 |title=A COURSE OF ALGOL 60 PROGRAMMING with special reference to the DASK ALGOL system |url=http://archive.computerhistory.org/resources/text/algol/ACM_Algol_bulletin/1064048/frontmatter.pdf |access-date=26 March 2015 |publisher=Regnecentralen |publication-place=Copenhagen}}</ref> Studies of Boolean algebra were commonly part of a mathematics curriculum, which may have informed Backus's approach. Neither Backus nor Naur described the names enclosed in <code>&lt; &gt;</code> as non-terminals—Chomsky's terminology was not originally used in describing BNF. Naur later called them "classes" in 1961 course materials.<ref name="class2" /> In the ALGOL 60 report, they were "metalinguistic variables," with other symbols defining the target language.

[[Saul Rosen]], involved with the [[Association for Computing Machinery]] since 1947, contributed to the transition from IAL to ALGOL and edited Communications of the ACM. He described BNF as a metalanguage for ALGOL in his 1967 book.<ref>{{cite book |author=Saul Rosen |title=Programming Systems and Languages |location=New York |publisher=McGraw Hill |series=McGraw Hill Computer Science Series |date=Jan 1967 |isbn=978-0070537088 |url=https://archive.org/details/programmingsyste0000unse/mode/1up |url-access=registration}}</ref> Early ALGOL manuals from IBM, Honeywell, Burroughs, and Digital Equipment Corporation followed this usage.