Backus-Naur vs. Backus-Normal
Mark Price
I'll don my asbestos underwear and ask anyway.
My computer science prof told us that BNF originally stood for
Backus-Naur Form but then was changed to Backus Normal Form. For extra
credit, he said, find out why Naur got dropped. After looking up BNF in
FOLDOC, however, it appears that BNF originally stood for Backus Normal
and then, at Donald Knuth's suggestion, was changed to Backus-Naur.
According to this version, then, Naur got added, not dropped.
So does anyone know why Knuth thought Naur should get credit? I see
references to a 1959 paper by Backus, followed by a 1960 paper by Naur.
Did Naur come up with a metasyntax similar to but independently of
Backus', or did Naur make additions to one already developed by Backus,
or both or neither or what?
Thanks in advance for scanning your memory banks on this one.
Mark
Charles Richmond
what I (think) that I do know.
BNF was one of the first systems for formally describing the syntax of a
programming language. And Algol 60 was the first computer language to be
formally described by BNF. And Peter Naur was the chairman of the Algol 60
committee that designed the language. Mr. Nauer also edited the Algol 60 report.
So perhaps this is why Knuth thought that Naur's name should be attached to BNF.
Now for extra credit, why was the Algol 60 Report dedicated to the memory
of William Turanski? (I got the answer to this from a.f.c before, but I bet
your professor does *not* know the answer.)
--
+-------------------------------------------------------------+
| Charles and Francis Richmond <rich...@plano.net> |
+-------------------------------------------------------------+
Douglas W. Jones,201H MLH,3193350740,3193382879
>
> So does anyone know why Knuth thought Naur should get credit? I see
> references to a 1959 paper by Backus, followed by a 1960 paper by Naur.
John Backus was the inventor of FORTRAN, and he was a member of the IFIP
working committee that developed ALGOL. Peter Naur edited the Algol 60
Report. The Algol 60 report used BNF to describe the syntax of that
elegant little language, and the details of the notation were largely
developed by Peter Naur, with many details determined by, for example,
Naur's European background (where angle braces are used as quote marks,
from whence we get the <metasymbol> notation) or by, for example, the
limited character set of his typewriter, which forced him into ::= where
his manuscript had an arrow or somesuch mark.
People on the committee started calling it Naur's notation, but Naur
said no, this was a notation he got from Backus, so at Naur's suggestion,
people started calling it Backus Normal Form.
However, as Knuth pointed out, Naur had quite a bit to do with this form,
and furthermore, it's not really a normal form, since there are an
infinite number of different ways to construct a BNF grammar for any
given context free language. So, we get BNF standing for Backus-Naur
Form.
Doug Jones
jo...@cs.uiowa.edu
(who's first 3 high-level programming
languages were CAL, FORTRAN II and Algol 60)
Neil Franklin
>
> My computer science prof told us that BNF originally stood for
> Backus-Naur Form but then was changed to Backus Normal Form. For extra
> credit, he said, find out why Naur got dropped. After looking up BNF in
> FOLDOC, however, it appears that BNF originally stood for Backus Normal
> and then, at Donald Knuth's suggestion, was changed to Backus-Naur.
> According to this version, then, Naur got added, not dropped.
Well you have beaten your CS prof.
From "A History of Programming Languages", Richard L Wexelblat (Ed),
Conference proceeding of same named conference, ACM Press
Paper: "European Side of Last Phase of Development of Algol", Peter Naur
------
Page 99:
.. I was led to the conviction that the formulisatin of a clear and
complete description was more important than any particular
language. Only on October 1959, during a second phase of studying
Backus's Paris report, did I penetrate through the formal, syntactic
description. This made me realize that his notation would be a highly
valuable tool ...
Page 131:
On the subject of BNF (which to me has allways meant Backus Normal
Form, since John Backus quite allone introduced it in his Paris '59
paper) ...
Page 162: (Q&A session)
2. The Meaning of the Acronym BNF
Chetham: The next question ... "BNF is sometimes pronounced
Backus-Naur-Form and sometimes Backus-Normal-Form. What was the
original intention?"
Naur: I do not know where BNF came from in the first place. [It was
not used during the ALGOL 60 conference in Paris in January 1060.] I
don't know - surely BNF originally meant BAckus-Normal-Form. I don't
know who suggested it. Perhaps Ingermen. [This is denied by Peter
Z. Ingerman (1978).] I don't know.
Chetham: ...
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
[Knuth (1964) in references to Naur's paper], so there ypu'll finf
whatever justification was originally made. That's all I would like to
say.
Page 139: (References)
Knuth, D. E. (1964). Backus Normal Form vs Backus Naur Form. Comm. ACM
7(12): 735-736.
------
> So does anyone know why Knuth thought Naur should get credit? I see
So it seems you need Knuths CACM paper.
--
Neil Franklin, Nerd, Geek, Unix Wizzard and Guru, Hacker, Mystic
ne...@franklin.ch.remove http://neil.franklin.ch/
Computer: toy that speeds work, so you have more time to play with it
Bernie Cosell
} From article <3773B4...@teleportcutthisout.com>, by Mark Price <pri...@teleportcutthisout.com>:
} >
} > So does anyone know why Knuth thought Naur should get credit? I see
} > references to a 1959 paper by Backus, followed by a 1960 paper by Naur.
}
} People on the committee started calling it Naur's notation, but Naur
} said no, this was a notation he got from Backus, so at Naur's suggestion,
} people started calling it Backus Normal Form.
}
} However, as Knuth pointed out, Naur had quite a bit to do with this form,
} and furthermore, it's not really a normal form, since there are an
} infinite number of different ways to construct a BNF grammar for any
} given context free language. So, we get BNF standing for Backus-Naur
} Form.
This matched my memory, and seems to be exactly backwards from the fellow's
homework assignment: I _first_ heard of it as "Backus _Normal_ Form", and
it was only some years later when I was told that the acronym was
henceforth to be expanded as "Backus _Naur_ Form". If there was a flip
back in the other direction [*back* to "normal" form] then it happened way
after my time...
/Bernie\
--
Bernie Cosell Fantasy Farm Fibers
ber...@fantasyfarm.com Pearisburg, VA
--> Too many people, too few sheep <--
Janne Rinta-Manty
NF> Naur: I do not know where BNF came from in the first place. [It
NF> was not used during the ALGOL 60 conference in Paris in January
NF> 1060.] I don't know - surely BNF originally meant
NF> BAckus-Normal-Form. I don't know who suggested it. Perhaps
NF> Ingermen. [This is denied by Peter Z. Ingerman (1978).] I don't
NF> know.
Peter Z. Ingerman suggested "Panini-Backus Form" in CACM 10, 3 (1967),
137 - Panini had used similar notation for the grammar of Sanskrit.
"Not only does it give due credit, but it also avoids the misuse of
the word ``Normal.''"
Apparently the suggestion didn't have much influence.
--
Janne Rinta-Mänty
Mark Price
look up Panini's Sanskrit grammar and why the Algol 60 Report is
dedicated to the memory of William Turanski, or at least toss them out
with a knowing air in class and make my classmates feel dumb for not
knowing about them either. :)
Mark
Carl R. Friend
>
> I will try to look up Panini's Sanskrit grammar and why the Algol 60
If I recall correctly, the Algol '60 report is dedicated to Mr.
Turanski as he was instrumental in getting the language specified and
subsequently lost his life in an automobile accident in the weeks
before the report was published.
I have a copy of the report upstairs, but to get it at the moment
would be difficult (it'd wake the wife). If anybody's interested, I'll
look it up and post the text of the memorial.
--
+------------------------------------------------+---------------------+
| Carl Richard Friend (UNIX Sysadmin) | West Boylston |
| Minicomputer Collector / Enthusiast | Massachusetts, USA |
| mailto:carl....@stoneweb.com | |
| http://www.ultranet.com/~crfriend/museum | ICBM: N42:22 W71:47 |
+------------------------------------------------+---------------------+
David K. Bryant
>Now for extra credit, why was the Algol 60 Report dedicated to the memory
>of William Turanski?
And for double-coupons, who is Frank Borland and what is
his claim to fame?
No, he doesn't appear with Tim Allen on "Tool Time".