Backus-Naur Form

From Conservapedia
(Redirected from BNF)
Jump to: navigation, search

In the late 1950's, John Backus and Peter Naur developed a notation for describing the syntax (grammar) of programming languages. This notation is known as Backus-Naur Form (or BNF), and was first used in the Algol 60 Report [1] to specify the syntax of Algol 60, and has since been used for specifying the syntax of other programming languages.

A few years earlier, in 1956, the linguist Chomsky had published [2] an article about a hierarchy of formal grammatical systems for describing various classes of languages. Even though expressed very differently, and developed independently, it turns out that BNF is logically equivalent to Chomsky's level 2 grammar (often referred to as a context-free grammar).

References

  1. Revised Report on the Algorithmic Language Algol 60. Retrieved on 2012-05-11.
  2. Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory 2: 113–124. http://www.chomsky.info/articles/195609--.pdf. Retrieved 2012-05-11.