Talk:Backus–Naur form

Other early grammar specifications

Around the same time as BNF was being used in Algol, Tony Brooker and others were using a very similar notation which was eventually used in the Compiler Compiler. The article says '"A Compiler Building System" Developed by Brooker and Morris, directly used BNF.' but in fact it did not, it used their own grammar format and although I can't offer proof, my understanding is that it was semi-independent invention of an idea that was floating around the community at the time. I'm not going to go as far as suggesting that Brooker invented BNF but certainly his contemporary work was on par with it. I note that in the publication "The Compiler Compiler" the name Backus is nowhere mentioned. Tony was not the sort of person to steal someone's credit so I think that omission indirectly supports the idea that the grammar format used in the Compiler Compiler was their own work. The 1963 date on that paper is not the date that the format was first used. I'm afraid I don't know when Tony first used a formal grammar when building parsers but it would be interesting to look in to. Note that BNF was only being used descriptively at that time by the Algol 60 project, whereas Tony was actually using it in parser creation. I mention all this solely as a Talk comment as I don't have hard references to put in the primary article. 70.124.38.160 (talk) 03:04, 17 April 2024 (UTC)

Algol 60 was well established by then. Why not just assume they took the approach from the Algol 60 report? Rp (talk) 20:29, 17 April 2024 (UTC)

Well, I'm fairly sure Tony Brooker was using this format before the Algol 60 report. I believe he was already using something similar by the time of the IAL proposal in 1958. Tony's Atlas Autocode was a response to the IAL proposal rather than a response to the Algol 60 report, and he was definitely already using a structured grammar of this general style before his Atlas Autocode implementation. Tony was notably not invited to the Zurich meeting in '58 (I'm pretty sure if he had been, Algol 60 would have had fewer of the idiosyncracies that Tony objected to, and avoided in his Atlas Autocode language) and I don't think much of what he did around then was influenced by the Algol 60 work or people - he was off in Manchester doing his own thing in his own way. He was definitely thinking about grammars in the BNF style in '58 when he started work on the compiler-compiler but whether he'd already used the format by then for any other project, I can't be 100% sure. If I can find a <= 1958 reference to Tony's use of grammars I'll add it here, and although I'm sure there are some, I don't have them to hand. It's possible he used a grammar when writing Mercury Autocode but I can't remember and haven't searched the net for the Mercury Autocode sources to check. 70.124.38.160 (talk) 22:25, 19 April 2024 (UTC)

A reference perhaps? https://www.sciencedirect.com/science/article/abs/pii/B9781483197791500069 - clearly shows he was using a phrase-structured grammar to implement Mercury Autocode. The paper was published in 1961 but I believe Mercury Autocode itself was written by 1958. Simon Lavington mentioned (my emphasis):

The next Manchester computer, the Ferranti Mercury, had floating-point hardware but the memory-management problems were still present. By 1958 Tony had developed Mercury Autocode, which extended the linguistic richness of Mark I Autocode whilst failing to provide a general solution to the problem of Mercury’s two levels of storage (core and drum). in https://curation.cs.manchester.ac.uk/atlas/docs/Brooker%20Atlas%20CC%20rev%20April%202016bb.pdf 70.124.38.160 (talk) 22:44, 19 April 2024 (UTC)

A General Translation Program for Phrase Structure Languages (Brooker and Morris): https://dl.acm.org/cms/asset/95e0a22b-1077-42c0-b156-54ca3509f3cd/321105.321106.fp.png ( https://dl.acm.org/doi/10.1145/321105.321106 )

An Assembly Program for a Phrase Structure Language (Brooker and Morris): https://academic.oup.com/comjnl/article/3/3/168/345484

Published in 1960 but referring to earlier work. These ideas were floating around in the community in the 58-60 timescale and the Compiler Compiler definitely implemented parsing based on the input of this style of grammar - the first use clearly sooner than the 1972 that Paul B Mann wrongly asserted in "A translational BNF grammar notation" https://dl.acm.org/doi/10.1145/1147214.1147218 "BNF grammar notation came into existence about 1960 for the specification of programming languages. It was first used for the automatic generation of parsers about 1972."

By the way, while giving Tony the credit he's due, I'll mention that the "PEG Parser" algorithm is the same algorithm Tony used in his parsers including the Compiler Compiler (with the exception of the memoization component, which is just a trivial application of Donald Michie's Memo Functions from 1967 https://stacks.stanford.edu/file/druid:kr445kk4694/kr445kk4694.pdf ). 70.124.38.160 (talk) 01:03, 20 April 2024 (UTC)

Similar software?

@ComputerUserUser and Smuckola: Smuckola, you changed the heading "Software that accepts BNF-like input" to "Similar software" claiming that the former was vague. The former heading was crystal clear but it is the new one that seems ambiguous and vague to me. I think it should be changed back. Jason Quinn (talk) 08:53, 7 July 2024 (UTC)

Special “delete” symbol

At the time of writing, the Overview section ends with the following sentence:

Applying rules in this manner can produce longer and longer sequences, so many BNF definitions allow for a special "delete" symbol to be included in the specification. We can specify a rule that allows us to replace some symbols with this "delete" symbol, which is meant to indicate that we can remove the symbols from our sequence and still have a syntactically correct sequence.

I’m unfamiliar with the “delete” symbol being referred to there, nor is it clear to me what problem it’s being said to solve for. That doesn’t mean it doesn’t exist, of course, but the citation given for this sentence (http://www.cs.umsl.edu/~janikow/cs4280/bnf.pdf) makes no mention of this concept at all (and it would seem to be a somewhat odd citation choice even if it did), so I remain unable to determine what it’s talking about.

Is the sentence describing something meaningful? If so:

1. Can a real citation be provided for it?
2. Does it really belong in the overview?

The sentence was added here: https://en.wikipedia.org/w/index.php?title=Backus%E2%80%93Naur_form&diff=next&oldid=1204483713 Bhathos (talk) 04:31, 21 September 2024 (UTC)

The citation does mention the symbol (p.2, 2nd item from below), but doesn't call it "delete symbol". Every grammar using the delete symbol can be transformed into a grammar not using it and describing the same language (except for the empty string; see Context-free_grammar#Reachability,_productiveness,_nullability). The sentence from the Overview section give the impression that the purpose of the delete symbol is to obtain shorter sequences, which is blatant nonsense. - Jochen Burghardt (talk) 05:39, 23 September 2024 (UTC)