SUMMARY: BNF definition

Ronny De Winter <>
Wed, 18 May 1994 09:05:31 GMT

          From comp.compilers

Related articles
SUMMARY: BNF definition (Ronny De Winter) (1994-05-18)
Re: SUMMARY: BNF definition (EBNF acceptance) (Nathan K. Inada) (1994-05-18)
Re: SUMMARY: BNF definition (EBNF acceptance) (Terence Parr) (1994-05-20)
Re: SUMMARY: BNF definition (EBNF acceptance) (1994-05-22)
Re: SUMMARY: BNF definition (EBNF acceptance) (1994-05-23)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Ronny De Winter <>
Keywords: parse, summary
Organization: Compilers Central
Date: Wed, 18 May 1994 09:05:31 GMT

Here are the responses to the BNF definition question I asked a few weeks ago.
Thanks to anybody who replied !

Ronny De Winter
Alcatel Bell Telephone, dept.se141
F. Wellesplein 1
B-2018 Antwerpen, Belgium


From: Dinko Tenev <>

What do you mean by "formal definition"? BNF in terms of BNF is as

<grammar> -> <production>
| <grammar> '|' <production>
<production> -> <LHS> '->' <sentential form>
<sentential form> -> epsilon
| symbol
| <sentential form> symbol

"Epsilon" is used to denote an empty string, and "symbol" stands for
any symbol in the grammar, either terminal, or nonterminal. Terminal
symbols are those which do not appear on the left side of a
production. The notation

A -> B | C (1)

is an abbreviation for

A -> B (2)
A -> C (3)

Although in the formal specification above I use "production" to
denote rules like (1), in the formal theory "production" would rather
refer to rules (2) and (3), i.e., (1) stands for 2 productions.

There is also a form of BNF, called Extended BNF (EBNF), which
augments BNF as follows: [ ... ] is used to denote optional entries,
i.e., [abc] means "0 or 1 occurrences of the string 'abc'"; { ... } is
used to denote closure, i.e., 0 or more occurrences of the enclosed
string of symbols; parantheses can be used to change the precedence - for
example, in BNF, you would generally have the following:

C -> FOR <id> := <expr> TO <expr> DO <stmt>
C -> FOR <id> := <expr> DOWNTO <expr> DO <stmt>

which, in EBNF, can be expressed as follows:

C -> FOR <id> := <expr> (TO | DOWNTO) <expr> DO <stmt>

Note that those features were added only for one's convenience - they
do not add to the descriptive power of BNF and could be easily
expressed in its own terms. Although they can significantly improve
the readability of the grammar, they complicate the matter when it
comes to parser or code generation, so EBNF is generally unpopular in
compilers theory.

A thorough research on formal grammars was done by Chomsky. You can
also find some references in J.P. Tremblay's "The Theory and Practice
of Compiler Writing".



There have been numerous definitions of extensions to BNF, but I don't
know that the original was ever formally defined.

The definition is very minimal:
<text name...> non-terminal symbol
::= is-defined-as
| alternative definition

I believe terminal symbols appeared as themselves; possibly in a
different font.

A rule in BNF, as describd in BNF (with "'s around terminals) is

<rule> ::= <non-terminal-symbol> "::=" <right-side>
<right-side> ::= <item-sequence>
| <item-sequence> "|" <right-side>
<item-sequence> ::= <item>
| <item> <item-sequence>
<item> ::= <non-terminal-symbol> | <terminal-symbol>

<non-terminal-symbol> ::= "<" <letters-and-spaces> ">"
<terminal-symbol> ::= """ <characters> """

<letters-and-spaces> ::= <letter>
| " "
| <letter> <letters-and-spaces>
| " " <letters-and-spaces>
<letter> ::= "a" | "b" | ...
<character> ::= "?" | "*" | ...


From: "Wlodek M. Zuberek" <>

BNF is a "notational variant" of context-free grammars (in the Chomsky
hierarchy), so the (formal) definition of context-free grammars applies
to BNF (with the "notational" change).


From: "J. Steensgaard" <>

The Revised Report refers to

J.W.Backus, The syntax and semantics of the proposed international
algebraic language of the Zuerich ACM-GAMM conference. ICIP Paris,
June 1959.

J. Steensgaard-Madsen


From: (David Neubart)

      I believe there is a reference to the "origins" of BNF in
      Saul Rosen's (ed.) book _Programming Systems & Languages_ published
      by McGraw-Hill 1967.

      That's the best I could come up with. I've just taken BNF for granted.
      That is, something that's always been around like dirt.

      Hope this give you a starting point.

Dave Neubart Advanced Technology Systems, Inc.
Sr. Software Engineer 4801 University Sq., Suite 2
Internet: Huntsville, Alabama 35816
      Voice: (205) 890-2414


I can't supply a formal definition of BNF. (I suspect that

          author = {J. W. Backus},
          title = {The syntax and semantics of the proposed international
                algebraic language of the {Z{\"u}rich ACM-GAMM} conference},
          booktitle = {Proceedings of the International Conference on
                Information Processing (ICIP)},
          address = {Paris},
          month = jun,
          year = 1959

is really the first paper where BNF was introduced.) But since I
asked the same question not long ago -- in the mean time I finally
tracked down the definition of EBNF:

          author = {Niklaus Wirth},
          title = {What Can We Do About the Unnecessary Diversity of Notation
                for Syntactic Definitions?},
          journal = cacm,
          volume = 20,
          number = 11,
          month = nov,
          year = 1977,
          pages = {822-823},

Perhaps that's of help to the questioner.


Joachim Schrod Email:
Computer Science Department
Technical University of Darmstadt, Germany

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.