Difference between revisions of "Backus-Naur Form"
Jump to navigation
Jump to search
(create article and provide introduction; details to come) |
(add Category:Computer Science) |
||
| Line 23: | Line 23: | ||
==References== | ==References== | ||
<references/> | <references/> | ||
| + | |||
| + | [[Category:Computer Science]] | ||
Latest revision as of 19:38, May 14, 2012
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
- ↑ Revised Report on the Algorithmic Language Algol 60. Retrieved on 2012-05-11.
- ↑ 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.