Backus Normal Form vs. Backus Naur Form

From compilers Fri Jul 2 16:33:34 EDT 1993
Newsgroups: comp.compilers Path: iecc!compilers-sender
From: Kelly Morrison Subject: Backus Normal Form vs. Backus Naur Form (long)
Keywords: history, parse, algol60
Organization: Compilers Central
References: <93-06-063@comp.compilers>
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.

Back to Spirit Home