World Library  
Flag as Inappropriate
Email this Article

Backus-Naur form

Article Id: WHEBN0005396032
Reproduction Date:

Title: Backus-Naur form  
Author: World Heritage Encyclopedia
Language: English
Subject: C (programming language), List of computer scientists, Chomsky normal form, EDIF, Forth (programming language), List of programmers, Yacc, Greibach normal form, Peter Naur, Verilog
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Backus-Naur form

Not to be confused with BCNF or Boyce–Codd normal form.

In computer science, BNF (Backus Normal Form or Backus–Naur Form) is one of the two[1] main notation techniques for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocol; the other main technique for writing context-free grammars is the van Wijngaarden form. They are applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory.

Many extensions and variants of the original Backus–Naur notation are used; some are exactly defined, including Extended Backus–Naur Form (EBNF) and Augmented Backus–Naur Form (ABNF).

History

The idea of describing the structure of language with rewriting rules can be traced back to at least the work of Pāṇini (about the 4th century BC), who used it in his description of Sanskrit word structure. American linguists such as Leonard Bloomfield and Zellig Harris took this idea a step further by attempting to formalize language and its study in terms of formal definitions and procedures (around 1920–60).

Meanwhile, string rewriting rules as formal, abstract systems were introduced and studied by mathematicians such as Axel Thue (in 1914), Emil Post (1920s–40s) and Alan Turing (1936). Noam Chomsky, teaching linguistics to students of information theory at MIT, combined linguistics and mathematics, by taking what is essentially Thue's formalism as the basis for the description of the syntax of natural language; he also introduced a clear distinction between generative rules (those of context-free grammars) and transformation rules (1956).[2][3]

John Backus, a programming language designer at IBM, proposed "metalinguistic formulas"[4][5] to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959), using the BNF notation.

Further development of ALGOL led to ALGOL 60; in its report (1963), Peter Naur named Backus's notation Backus Normal Form, and simplified it to minimize the character set used. However, Donald Knuth argued that BNF should rather be read as Backus–Naur Form, as it is "not a normal form in the conventional sense",[6] unlike, for instance, Chomsky Normal Form. The name Pāṇini Backus form has also been suggested in view of the facts that the expansion Backus Normal Form may not be accurate, and that Pāṇini had independently discovered a similar notation earlier. [7]

Introduction

A BNF specification is a set of derivation rules, written as

  ::= __expression__

where <symbol> is a nonterminal, and the __expression__ consists of one or more sequences of symbols; more sequences are separated by the vertical bar, '|', indicating a choice, the whole being a possible substitution for the symbol on the left. Symbols that never appear on a left side are terminals. On the other hand, symbols that appear on a left side are non-terminals and are always enclosed between the pair <>.

The '::=' means that the symbol on the left must be replaced with the expression on the right.

Example

As an example, consider this possible BNF for a U.S. postal address:

  ::=   
 
       ::=     
                    |  
 
   ::=  |  "." 
 
  ::=    
 
        ::=  ","   
 
 ::= "Sr." | "Jr." |  | ""
    ::=  | ""

This translates into English as:

  • A postal address consists of a name-part, followed by a street-address part, followed by a zip-code part.
  • A name-part consists of either: a personal-part followed by a last name followed by an optional suffix (Jr., Sr., or dynastic number) and end-of-line, or a personal part followed by a name part (this rule illustrates the use of recursion in BNFs, covering the case of people who use multiple first and middle names and/or initials).
  • A personal-part consists of either a first name or an initial followed by a dot.
  • A street address consists of a house number, followed by a street name, followed by an optional apartment specifier, followed by an end-of-line.
  • A zip-part consists of a town-name, followed by a comma, followed by a state code, followed by a ZIP-code followed by an end-of-line.
  • A opt-suffix-part consists of a suffix, such as "Sr.", "Jr." or a roman-numeral, or an empty string (i.e. nothing).
  • A opt-apt-num consists of a apartment number or an empty string (i.e. nothing).

Note that many things (such as the format of a first-name, apartment specifier, ZIP-code, and Roman numeral) are left unspecified here. If necessary, they may be described using additional BNF rules.

Further examples

BNF's syntax itself may be represented with a BNF like the following:

          ::=  |  
            ::=  "<"  ">"  "::="   
  ::= " "  | ""
      ::=  |  "|" 
        ::=   |  
            ::=  |   
            ::=  | "<"  ">"
         ::= '"'  '"' | "'"  "'"

Note that "" is empty string, i.e. no whitespace.

The original BNF did not use quotes as shown in rule.

This assumes that no whitespace is necessary for proper interpretation of the rule. represents the appropriate line-end specifier (in ASCII, carriage-return and/or line-feed, depending on the operating system). and are to be substituted with a declared rule's name/label or literal text, respectively.

In the U.S. postal address example above, the entire block-quote is a syntax. Each line or unbroken grouping of lines is a rule; for example one rule begins with " ::=". The other part of that rule (aside from a line-end) is an expression, which consists of two lists separated by a pipe "|". These two lists consists of some terms (three terms and two terms, respectively). Each term in this particular rule is a rule-name.

Variants

There are many variants and extensions of BNF, generally either for the sake of simplicity and succinctness, or to adapt it to a specific application. One common feature of many variants is the use of protocols.

Parsing expression grammars build on the BNF and regular expression notations to form an alternative class of formal grammar, which is essentially analytic rather than generative in character.

Many BNF specifications found online today are intended to be human readable and are non-formal. These often include many of the following syntax rules and extensions:

  • Optional items enclosed in square brackets: [].
  • Items repeating 0 or more times are enclosed in curly brackets or suffixed with an asterisk ('*'), such as " ::= {}" or " ::= *", respectively.
  • Items repeating 1 or more times are suffixed with an addition (plus) symbol ('+').
  • Terminals may appear in bold rather than italics, and nonterminals in plain text rather than angle brackets.
  • Alternative choices in a production are separated by the ‘|’ symbol: | .
  • Where items are grouped, they are enclosed in simple parentheses.

See also

Software using BNF

  • ANTLR, another parser generator written in Java
  • BNF Converter (BNFC[8])
  • Coco/R, compiler generator accepting an attributed grammar in EBNF
  • DMS Software Reengineering Toolkit, program analysis and transformation system for arbitrary languages
  • GOLD BNF parser
  • GNU bison, GNU version of yacc
  • RPA BNF parser.[9] Online (PHP) demo parsing: JavaScript, XML
  • XACT X4MR System,[10] a rule-based expert system for programming language translation
  • Yacc parser generator (used with Lex pre-processor)
  • bnfparser2,[11] a universal syntax verification utility
  • bnf2xml Markup input with XML tags using advanced BNF matching.
  • JavaCC Java Compiler Compiler tm (JavaCC tm) - The Java Parser Generator

References

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

External links

  • explains some of the history of the two names.
  • .
  • .
  • .
  • ISO/IEC 14977:1996(E) Information technology – Syntactic metalanguage – Extended BNF, available from or from (the latter is missing the cover page, but is otherwise much cleaner)

Language grammars

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.