In Greibach's survey Formal Languages: Origins and Directions, she writes the following paragraph on page 19 about the term "context-free":

The theory of context-free languages was being developed during the same period [late 1950s-early 1960s]. I have not been able to pinpoint the initial appearance of the term context-free [...]; perhaps some reader can help. It was not used by Chomsky in 1958 or 1959, by Bar-Hillel, Perles, and Shamir (1961), or by Ginsburg and Rice (1962). It was, however, used by Scheinberg (1960) [...] The term context-free was also used by Chomsky in "On the notion 'rule of grammar'" (1961).

Are there any other papers from this era that make use of the term "context-free", and can the earliest usage of this term be pinned down?

More generally, how has the use of the related terms "context-free", "phrase structure", and "ALGOL-like" varied over the 1950s and 1960s? Clearly, one term has won out over the others, but can their relative usage be measured?


1 Answer 1


In the following paper, Chomsky announced the new nomenclature:

In Chomsky (1959)$^1$ a class of grammars is studied each of which contains a finite number of "rules" of the form $A\rightarrow\phi$, where $A$ is a single symbol and $\phi$ is not null. Such grammars (there called type 2 grammars) we will now call context-free (CF) phrase structure grammars.

(Some minor typographical changes from the original, as HSM uses a different greek font for $\phi$.)

The precise detail of the interaction of Chomsky's ideas with Backus's work on defining ALGOL's syntax find the following description in this source:

To address this problem, Backus applied a formalism called context-free languages that had just been invented by linguist Noam Chomsky. [..] Chomsky’s work in turn had its roots in Emil Post’s theoretical work on general rewriting grammars. How Backus came to this synthesis promises to keep historians busy for some time.

There’s a strange confusion here. I swore that the idea for studying syntax came from Emil Post because I had taken a course with Martin Davis at the Lamb Estate [an IBM think tank on the Hudson].... So I thought if you want to describe something, just do what Post did. Martin Davis tells me he did not teach the course until long afterward [1960-61 according to Davis’s records]. So I don’t know how to account for it. I didn’t know anything about Chomsky. I was a very ignorant person$^2$.

$^2$ Martin Davis speculates that Richard Goldberg, a Harvard-trained logician and part of the Fortran team, may have discussed Post's or Chomsky's work with Backus.

To see the confusion compare also an earlier quote by Backus in Wexelblat, R. L. (ed.) (1978). History of programming languages. Association for Computing Machinery, p. 162 when asked about the influence of formal linguistics:

As to where the idea came from - it came from a class that I took from Martin Davis. He was giving it at Atlanta State, talking about the work of Emil Post and the idea of a production. It was only in trying to describe ALGOL 58 that I realized that there was trouble about syntax description. It was obvious that Post's productions were just the thing, and I hastily adapted them to that use. And I'd just like to add that the main thing was simply the recognition that syntax needed carefuld escription that really brought it about. It was Peter Naur's recognition of exactly the same fact independently - I just happen to have written this funny little paper that he happened to read - that caused him to use it. But I would say it was a parallel discovery, namely, that syntax had to be accurately described; that was the real thing.

There are certainly various folklore histories around these interactions, some giving Chomsky full credit and claiming Backus was aware, some claiming the above independence of discovery as articulated by Backus himself. See for example Cleaveland J.C. and Uzgalis, R., (1977) Grammars for Programming Languages, Elsevier, p.1 for an example of the latter.

I cannot speak to a more detailed historical tracing of changes and adoption of nomenclature, though I suspect that google scholar and google ngram will offer a good first stab pursuing it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.