Backus Normal Form vs. Backus Naur Form (long)

Kelly Morrison <morrison@eng.auburn.edu>
Fri, 2 Jul 1993 05:04:18 GMT

          From comp.compilers

Related articles
Representations of grammars morrison@eng.auburn.edu (Kelly Morrison) (1993-06-25)
Backus Normal Form vs. Backus Naur Form (long) morrison@eng.auburn.edu (Kelly Morrison) (1993-07-02)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Kelly Morrison <morrison@eng.auburn.edu>
Keywords: history, parse, algol60
Organization: Compilers Central
References: 93-06-063
Date: Fri, 2 Jul 1993 05:04:18 GMT
Full-Name: Kelly Morrison

      Since I brought up the topic, I thought I'd clear it up. :)


      The book "History of Programming Languages", edited by Richard L.
Wexelblat, contains papers and transcripts of talks given by Alan J.
Perlis and Peter Naur about the development of ALGOL {58-60} language.


Here are some brief and relevant quotes:


{Naur is describing his participation in the December 1959 meeting of the
European part of the ALGOL committee}


"The use of Backus's notation could only be mentioned
in passing; my recommendation to that effect appears as
one of 55 brief notes on revisions of the Zurich report
as follows: '15) Change the syntactical description'"


"The decisive action concerning the development of the
new style of description was taken during the weeks
following the Mainz meeting, when I worked out the
results of the meeting according to the notions of
language description that I had formed. In order to
press the matter forward as much as possible, on January
2 I sent all other committee members a document...
[which] contains the first appearance of my slightly
revised form of Backus's notation."


{In an appendix, Naur discusses how he modified Backus's notation by
giving a brief example. Personally, I was stunned at how trivial the
changes were: basically, he modified the language so that it included only
symbols you could type at a standard keyboard. Naur concludes with this
comment:}


"Thus the modified notation uses ::= instead of [can't type
this symbol: it's a colon followed by an equals sign with
a third line above it] and | instead of [another symbol
that can't be typed: it's the keyword or with a line above
it]. In addition, in the modified form the designations of
the syntactic constituents, such as 'basic statement,' are
chosen to be exactly the same as those used for the same
items in describing the semantics, without abbreviation."


{In a later appendix, F. L. Bauer responds to Naur's statements:}


"It is amusing to see how Peter Naur looks at the use of
the Backus notation from his personal point of view.
Among [other members of the committee] there was no
question that we would like... a form similar to the one
Backus had used for its ICIP paper... If Peter Naur had
seen this a result of his "plan" to make an appeal to the
members of the ALGOL committee concerning the style of
the language description, he was running into open doors."


"... Peter Naur speaks of 'my slightly revised form of
Backus's notation' and 'my slightly modified form of
Backus's notation.' I think the minor notation difference
is not worth mentioning. If some people speak of Backus-
Naur form instead of the original Backus Normal Form,
then they indicate that Peter Naur, as the editor of the
ALGOL 60 report, brought this notation to a wide attention.
Backus-ALGOL Form would be more appropriate anyhow."


{Here are K. Samuelson's comments on Naur's statements:}


"On the subject of BNF (which to me has always meant Backus
Normal Form, since John Backus quite alone introduced it in
his Paris '59 paper) for the ALGOL 60 report, I can only
contradict him. As far as I, or even the entire GAMM group,
is concerned no persuasion whatsoever was necessary to use
it. Rather, BNF just needed to be presented by John to be
accepted as a superior means of syntax description."


{The following exchange comes from a transcript given at the 1978
conference which the book documents:}


CHEATHAM: The next question is from Bernie Galler of the
University of Michigan, and he asks: "BNF is sometimes
pronounced Backus-Naur-Form and sometimes Backus-Normal-
Form. What was the original intention?


NAUR: I don't know where BNF came from in the first
place. I don't know -- surely BNF originally meant Backus
Normal Form. I don't know who suggested it. Perhaps
Ingerman. [This is denied by Peter Z. Ingerman.] I don't
know.


CHEATHAM: It was a suggestion that Peter Ingerman proposed
then?


NAUR: ... Then the suggestion to change that I think was
made by Don Knuth in a letter to the Communications of the
ACM, and the justification -- well, he has the justification
there. I think I made reference to it, so there you'll find
whatever justification was originally made. That's all I
would like to say.
--


Post a followup to this message

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