SUMMARY: BNF definition

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


Ronny De Winter rdwi@se.bel.alcatel.be
Alcatel Bell Telephone, dept.se141
F. Wellesplein 1
B-2018 Antwerpen, Belgium


-----------------------------------


From: Dinko Tenev <s396@aubg.bg>


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


<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".


-----------------------------------------------------------------------------


From: Wilfred.Hansen@cs.cmu.edu


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" <wlodek@cs.mun.ca>


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" <jsm@dina.kvl.dk>


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: davidn@rmf41.usace.army.mil (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: davidn@rfm41.usace.army.mil Huntsville, Alabama 35816
      Voice: (205) 890-2414


---------------------------------------------------------------------------


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


        @inproceedings{prog:backus:59.1,
          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:


        @article{prog:wirth:77.1,
          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.


Cheers,
                Joachim


--
Joachim Schrod Email: schrod@iti.informatik.th-darmstadt.de
Computer Science Department
Technical University of Darmstadt, Germany
--

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