Elamur Research⌕
☰
home / papers / 1992 / The Acquisition and Use of Context-Dependent Grammars for English

The Acquisition and Use of Context-Dependent Grammars for English

Paper · 1992 · Robert F. Simmons and Yeong-Ho Yu

Summary

Simmons and Yu tackle the difficulty of building broad, unambiguous sentence grammars for English. Hand-written augmented context-free grammars are large, hard to maintain and prone to ambiguity. The authors propose a Context-Dependent Grammar (CDG). Each rule pairs a fixed window of parser state with an action: the top five stack symbols plus the next five input symbols, mapped to either a shift or a labelled reduction. A deterministic, single-path shift/reduce parser applies these rules, combining at most two stack elements per reduction. Rules come from interactive sessions in which a linguist demonstrates the correct step for each successive constituent. The grammar sits in a hash table with a selection formula, replacing an earlier back-propagation network that became too costly to train. On 345 sentences, mostly newswire and 10–60 words long, phrase-structure and case analyses reached 99% accuracy. The work suggests that context-based rule grammars are computationally and conceptually manageable for large text subsets.

Key points

  • 16,275 taught example constituents compressed to 3,843 rules, and the compressed grammar parsed just as well.
  • Extrapolation suggests about 25,000 example rules would give near-complete phrase-structure coverage of AP Wire text.
  • An earlier neural version with 2,000 rules took ten days to train on a Symbolics Lisp Machine. Training cost grew faster than the square of the example count, so the authors moved to hash-table storage.
  • The rule left side is a 10-symbol window (5 stack + 5 input, with blanks for padding). The right side is S (shift) or a reduce with a label, such as (R pp).
  • The same machinery produces case analyses. Reduce actions attach relations such as AGT, OBJ, MOD, DET, AUX and NMOD between the top stack items.

Interesting ideas

  • I1. A fixed window over the parser stack and lookahead is enough context to choose deterministically between shift and a labelled reduce; shrinking it to two stack items and one input item collapses the system into a binary CFG.
  • I2. The grammar is acquired by having a teacher confirm or correct each successive parse step, and every step is stored as a reusable example.
  • I3. When a learned model becomes too expensive to retrain, a hash table of exact contexts plus a similarity-based selection formula can serve as a cheap replacement.
  • I4. Role labels are assigned inside the reduce action itself, so syntax and shallow case structure come out of one pass.
  • I5. Plotting coverage against the number of taught examples lets the authors estimate how much annotation full coverage would need.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tree): Each decision of the perceptron parser could log its stack/buffer window as the human-readable reason, giving an explainable trace of every attachment.
  • I2 (learn): LLM-teacher or human corrections to silver parses could be saved as window→action entries, forming self-induced repair rules that are easy to audit.
  • I3 (tree): A lookup table of frequent contexts could sit next to gparse as a fast, transparent fallback, or act as a disagreement check against the neural parser.
  • I4 (frames): Reductions that also emit VerbNet-style roles (agent, object, modifier) could feed who-did-what-to-whom frames directly from parser actions.
  • I5 (learn): Tracking how new rules or examples taper off per added text would help estimate how much silver data a new genre, such as fables or word problems, needs.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.English · 2,263 worksSyntax & grammar formalisms · 214 works

Cite

Cite as Robert F. Simmons and Yeong-Ho Yu. 1992. The Acquisition and Use of Context-Dependent Grammars for English. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{simmons1992acquisition,
  title = {{The Acquisition and Use of Context-Dependent Grammars for English}},
  author = {Robert F. Simmons and Yeong-Ho Yu},
  journal = {Computational Linguistics},
  year = {1992},
  url = {https://aclanthology.org/J92-4001/}
}

References

25 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alterman, Richard (1985). "A dictionary based on concept coherence," Artificial Intelligence, 25, 153-186. ↗
  2. Allen, James (1987). Natural Language Understanding. Benjamin Cummings. find
  3. Allen, Robert (1987). "Several studies on natural language and back propagation." In Proceedings, International Conference on Neural Networks. San Diego. find
  4. Berwick, Robert C. (1985). The Acquisition of Syntactic Knowledge, Vol. 2, 335-341. MIT Press. find
  5. Chomsky, Noam (1957). Syntactic Structures. Mouton. find
  6. Cook, Walter (1989). Case Grammar Theory. Georgetown University Press. find
  7. Gazdar, Gerald (1988). "Applicability of indexed grammars to natural languages." In Linguistic Theory and Computer Applications, edited by P. Whitelock, et al., Academic Press, 37–67. ↗
  8. Gazdar, Gerald, and Mellish, Chris (1989). Natural Language Processing in LISP. Addison-Wesley. find
  9. Gazdar, Gerald; Klein, E.; and Pullum, G.; and Sag, I. (1985). Generalized Phrase Structure Grammar. Harvard University Press. find
  10. Semantics and Cognition, MIT Press, Cambridge, Mass., 1983. find
  11. Joshi, Aravind (1987). "An introduction to tree-adjoining grammars" In Mathematics of Language, edited by A. Manaster-Ramer, 87-114. John Benjamins. find
  12. Leow, Wee-Keng, and Simmons, R. E (1990). "A constraint satisfaction network for case analysis," AI Technical Report AI90-129, Department of Computer Science, University of Texas, Austin. find
  13. Marcus, M. P. (1980). A Theory of Syntactic Recognition for Natural Language. MIT Press. find
  14. McClelland, J. L., and Kawamoto, A. H. (1986). "Mechanisms of sentence processing: Assigning roles to constituents." In Parallel Distributed Processing, Vol. 2, edited by J. L. McClelland and D. E. Rumelhart, MIT Press, 272-326. find
  15. Miikkulainen, Risto, and Dyer, M. (1989). "A modular neural network architecture for sequential paraphrasing of script-based stories," Artificial Intelligence Lab., Department of Computer Science, UCLA. find
  16. Rim, Hae-Chang (1990). Computing outlines from descriptive texts. Doctoral dissertation, University of Texas, Austin. find
  17. Rumelhart, David E.; Hinton, G. E.; and Williams, R. J. (1986). "Learning internal representations by error propagation." In Parallel Distributed Processing, edited by D. E. Rumelhart and J. L. McClelland, MIT Press, 318-362. ↗
  18. Schank, Roger C. (1980). "Language and memory," Cognitive Science, 4(3). ↗
  19. Seo, Jungyun (1990). Text driven construction of discourse structures for understanding descriptive texts. Doctoral dissertation, University of Texas, Austin. find
  20. Sejnowski, Xerrence J., and Rosenberg, C. (1988). "NETtalk: A parallel network that learns to read aloud." In Neurocomputing, edited by Anderson and Rosenfeld, MIT Press. find
  21. Shieber, Stuart M. (1986). An Introduction to Unification Based Approaches to Grammar. University of Chicago Press. find
  22. Simmons, Robert F. (1984). Computations from the English. Prentice Hall. find
  23. Simmons, Robert F., and Yu, Yeong-Ho (1990). "Training a neural network to be a context sensitive grammar." In Proceedings, 5th Rocky Mountain AI Conference. Las Cruces, NM. find
  24. Tomita, M. (1985). Efficient Parsing for Natural Language. Kluwer Academic Publishers. ↗
  25. Yu, Yeong-Ho, and Simmons, R. E (1990). "Descending epsilon in back-propagation: A technique for better generalization," in press, Proc. Int. Jt. Conf. Neural Networks, San Diego. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/simmons-1992-acquisition-use-context-dependent-grammars/