Context-Free Grammars and Constituency Parsing

Historical notes

1. How did American and European grammatical traditions differ?
   American structuralism (Bloomfield) developed immediate-constituent analysis; traditional European grammar defined relations between words, the root of dependency grammars.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, Historical notes, p. 446
2. What was Harris’s substitutability test for constituents?
   If a simple form (e.g. man) can substitute for a more complex sequence (intense young man) in a construction, the sequence is probably a constituent, an early idea of constituents as equivalence classes.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, Historical notes, pp. 446–447
3. Who discovered dynamic programming parsing?
   John Cocke implemented a parser with the roots of CKY in 1960, later formalized by Kasami (1965) and Younger (1967); Kuno’s well-formed substring table and Kay’s chart were related; Earley (1968) gave the top-down version.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, Historical notes, p. 447