---
title: "Semantic-Head-Driven Generation — Shieber 1990"
description: "It is a design-level contribution with no corpus evaluation. 26 references, cited by 63 papers here."
authors: ["Stuart M. Shieber", "Gertjan van Noord", "Fernando C. N. Pereira", "Robert C. Moore"]
year: 1990
venue: "Computational Linguistics"
source: "https://aclanthology.org/J90-1004/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/shieber-1990-semantic-head-driven-generation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/shieber-1990-semantic-head-driven-generation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1990](https://md.research.elamur.ai/free/en/papers/1990/) / Semantic-Head-Driven Generation

# Semantic-Head-Driven Generation

**Authors:** [Stuart M. Shieber](https://md.research.elamur.ai/free/en/authors/stuart-m-shieber/), [Gertjan van Noord](https://md.research.elamur.ai/free/en/authors/gertjan-van-noord/), [Fernando C. N. Pereira](https://md.research.elamur.ai/free/en/authors/fernando-c-n-pereira/) and [Robert C. Moore](https://md.research.elamur.ai/free/en/authors/robert-c-moore/) · **Year:** 1990 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1990](https://md.research.elamur.ai/free/en/venues/cl/1990/)) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J90-1004/) · [PDF](https://aclanthology.org/J90-1004.pdf) · [OpenAlex](https://openalex.org/W1792465007)

**Citations:** 142 citations (OpenAlex, 2026-10-14) · [63](https://md.research.elamur.ai/free/en/papers/shieber-1990-semantic-head-driven-generation/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper addresses tactical generation: producing a sentence from a logical-form encoding of its meaning using unification-based or logic grammars, such as DCG, PATR-II and HPSG-style grammars. Earlier generators each restricted which grammars they could handle. Top-down regimes, even with dynamic goal reordering, can loop forever on left-recursive rules. The authors show this with a possessive NP rule and with a PATR-II complements rule, where no ordering of subgoals avoids nontermination. The Earley-style bottom-up generator works only with semantically monotonic grammars and can be highly nondeterministic. Shieber, Pereira, van Noord and Moore propose a generator that walks the analysis tree from its semantic head: it picks a pivot node, generates it, and then connects it upward to the root through chain rules. The algorithm is presented as Prolog interpreters over a node-based DCG encoding. It is a design-level contribution with no corpus evaluation. Its value is that it accepts both nonmonotonic semantics and left recursion, which makes reversible, linguistically realistic grammars usable for generation.

## Key points
- The algorithm handles two cases that defeat earlier generators: semantically nonmonotonic grammars, which the Earley-based bottom-up generator cannot use, and left recursion, which top-down methods cannot handle.
- Dutch cross-serial verb constructions build subcategorization lists of unbounded length. This rules out ad hoc depth limits as a fix for top-down nontermination.
- Empty heads, such as the moved verb in Dutch/German verb-second clauses, are handled with a `head_gap` relation. The gap is introduced only after its antecedent has been built, so the gap's information is available in time.
- Reported uses include van Noord's BUG generator in the MiMo2 Teletext news translation system and the STREP project at CSLI for HPSG grammars. Calder et al. (1989) describe a UCG generator that seems to be a particular instance of this algorithm.
- Proposed future work:
  - a uniform parsing/generation architecture, linked to Kay's (1990) parser and van Noord's (1989b) Horn-clause proof procedure;
  - chart-style dynamic programming to remove redundant recomputation;
  - delayed evaluation for auxiliary conditions in rules.

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

## Institutions

- [Harvard University](https://md.research.elamur.ai/free/en/universities/harvard-university/) — University, Cambridge, United States · 73 works · 37,309 citations
- [AT&T](https://md.research.elamur.ai/free/en/companies/at-t/) — Company, Bedminster, United States · 29 works · 15,393 citations
- [SRI International](https://md.research.elamur.ai/free/en/labs/sri-international/) — Research institute, Menlo Park, United States · 9 works · 5,737 citations
- [Utrecht University](https://md.research.elamur.ai/free/en/universities/utrecht-university/) — University, Utrecht, Netherlands · 21 works · 1,281 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 116 works

## Cite

Cite as: Stuart M. Shieber, Gertjan van Noord, Fernando C. N. Pereira and Robert C. Moore. 1990. Semantic-Head-Driven Generation. Computational Linguistics.

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

```bibtex
@article{shieber1990semantic,
  title = {{Semantic-Head-Driven Generation}},
  author = {Stuart M. Shieber, Gertjan {van Noord}, Fernando C. N. Pereira and Robert C. Moore},
  journal = {Computational Linguistics},
  year = {1990},
  doi = {10.5555/89086.89097},
  url = {https://doi.org/10.5555/89086.89097}
}
```

- [← previous Constraint Grammar as a Framework for Parsing Running Text](https://md.research.elamur.ai/free/en/papers/karlsson-1990-constraint-grammar-as-framework-parsing/)
- [next → Automatic Processing of Large Corpora for the Resolution of Anaphora References](https://md.research.elamur.ai/free/en/papers/dagan-1990-automatic-processing-large-corpora-resolution/)
- [↑ back to papers of 1990](https://md.research.elamur.ai/free/en/papers/1990/)

## References

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

1. Calder, J.; Reape, M.; and Zeevat, H. 1989 "An Algorithm for Generation in Unification Categorial Grammar." In Proceedings of the 4th Conference of the European Chapter of the Association for Computational Linguistics, 233-240. [find](https://scholar.google.com/scholar?q=Calder%2C+J%2E%3B+Reape%2C+M%2E%3B+and+Zeevat%2C+H%2E+1989+%22An+Algorithm+for+Generation+in+Unification+Categorial+Grammar%2E%22+In+Proceedings+of+the+4th+Conference+of+the+European+Chapter+of+the+Association+for+Computat)
2. Colmerauer, A. 1982 PROLOG II: Manuel de R6ference et Mod61e Th6orique. Technical report, Groupe de'Intelligence Artificielle, Fa-cult6 des Sciences de Luminy, Marseille, France. [find](https://scholar.google.com/scholar?q=Colmerauer%2C+A%2E+1982+PROLOG+II%3A+Manuel+de+R6ference+et+Mod61e+Th6orique%2E+Technical+report%2C+Groupe+de%27Intelligence+Artificielle%2C+Fa%2Dcult6+des+Sciences+de+Luminy%2C+Marseille%2C+France%2E)
3. Cooper, R. 1983 "Quantification and Syntactic Theory," Volume 21 of Synthese Language Library. D. Reidel, Dordrecht, the Netherlands. [find](https://scholar.google.com/scholar?q=Cooper%2C+R%2E+1983+%22Quantification+and+Syntactic+Theory%2C%22+Volume+21+of+Synthese+Language+Library%2E+D%2E+Reidel%2C+Dordrecht%2C+the+Netherlands%2E)
4. Dymetman, M. and Isabelle, P. 1988 "Reversible Logic Grammars for Machine Translation." In Proceedings of the Second International Conference on Theoretical and Methodological Issues in Machine Translation of Natural Languages. [find](https://scholar.google.com/scholar?q=Dymetman%2C+M%2E+and+Isabelle%2C+P%2E+1988+%22Reversible+Logic+Grammars+for+Machine+Translation%2E%22+In+Proceedings+of+the+Second+International+Conference+on+Theoretical+and+Methodological+Issues+in+Machine+Transl)
5. Evers, A. 1975. The Transformational Cycle in German and Dutch. Ph.D. Thesis, University of Utrecht, Utrecht, the Netherlands. [find](https://scholar.google.com/scholar?q=Evers%2C+A%2E+1975%2E+The+Transformational+Cycle+in+German+and+Dutch%2E+Ph%2ED%2E+Thesis%2C+University+of+Utrecht%2C+Utrecht%2C+the+Netherlands%2E)
6. Fodor, J. D. In press. "Cross Serial Dependencies and Subcategorization Percolation." In R. Rieber (ed.), CUNYForum, Volume 15. City University of New York, New York. [find](https://scholar.google.com/scholar?q=Fodor%2C+J%2E+D%2E+In+press%2E+%22Cross+Serial+Dependencies+and+Subcategorization+Percolation%2E%22+In+R%2E+Rieber+%28ed%2E%29%2C+CUNYForum%2C+Volume+15%2E+City+University+of+New+York%2C+New+York%2E)
7. Halvorsen, P.-K. and Kaplan, R.M. 1988 "Projections and Semantic Description in Lexieal-Functional Grammar." In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, 1116-1122. [find](https://scholar.google.com/scholar?q=Halvorsen%2C+P%2E%2DK%2E+and+Kaplan%2C+R%2EM%2E+1988+%22Projections+and+Semantic+Description+in+Lexieal%2DFunctional+Grammar%2E%22+In+Proceedings+of+the+International+Conference+on+Fifth+Generation+Computer+Systems%2C+Tokyo%2C)
8. Hirsh, S. 1987 "P-PATR, a Compiler for Unification Based Grammars," In V. Dahl and P. Saint-Dizier (eds.), Natural Language Understanding and Logic Programming, H. Elsevier Science Publishers, New York, NY: 63-78. [find](https://scholar.google.com/scholar?q=Hirsh%2C+S%2E+1987+%22P%2DPATR%2C+a+Compiler+for+Unification+Based+Grammars%2C%22+In+V%2E+Dahl+and+P%2E+Saint%2DDizier+%28eds%2E%29%2C+Natural+Language+Understanding+and+Logic+Programming%2C+H%2E+Elsevier+Science+Publishers%2C+New+Yor)
9. Hobbs, J.R. and Shieber, S.M. 1987 An Algorithm for Generating Quantifier Scopings." Computational Linguistics, 13:47-63. [find](https://scholar.google.com/scholar?q=Hobbs%2C+J%2ER%2E+and+Shieber%2C+S%2EM%2E+1987+An+Algorithm+for+Generating+Quantifier+Scopings%2E%22+Computational+Linguistics%2C+13%3A47%2D63%2E)
10. Huybrechts, R.A.C. 1984 "The Weak Inadequacy of Context-Free Phrase Structure Grammars," In G. de Haan, M. Trommelen, and W. Zonneveld (eds.), Van Periferie naar Kern. Foris, Dordrecht, the Netherlands. [find](https://scholar.google.com/scholar?q=Huybrechts%2C+R%2EA%2EC%2E+1984+%22The+Weak+Inadequacy+of+Context%2DFree+Phrase+Structure+Grammars%2C%22+In+G%2E+de+Haan%2C+M%2E+Trommelen%2C+and+W%2E+Zonneveld+%28eds%2E%29%2C+Van+Periferie+naar+Kern%2E+Foris%2C+Dordrecht%2C+the+Netherland)
11. Kay, M. 1990 "Head-Driven Parsing." In M. Tomita (ed.), Currentlssues in Parsing Technology. Klumer Academic Publishers, Dordrecht, the Netherlands. [find](https://scholar.google.com/scholar?q=Kay%2C+M%2E+1990+%22Head%2DDriven+Parsing%2E%22+In+M%2E+Tomita+%28ed%2E%29%2C+Currentlssues+in+Parsing+Technology%2E+Klumer+Academic+Publishers%2C+Dordrecht%2C+the+Netherlands%2E)
12. Koster, J. 1975 "Dutch as an SOV Language." Linguistic Analysis, 1:(2):111-136. [find](https://scholar.google.com/scholar?q=Koster%2C+J%2E+1975+%22Dutch+as+an+SOV+Language%2E%22+Linguistic+Analysis%2C+1%3A%282%29%3A111%2D136%2E)
13. Matsumoto, Y.; Tanaka, H.; Hirakawa, H.; Miyoshi, H.; and Yasukawa, H. 1983 "BUP: A Bottom-Up Parser Embedded in Prolog." New Generation Computing, 1 (2): 145-158. [find](https://scholar.google.com/scholar?q=Matsumoto%2C+Y%2E%3B+Tanaka%2C+H%2E%3B+Hirakawa%2C+H%2E%3B+Miyoshi%2C+H%2E%3B+and+Yasukawa%2C+H%2E+1983+%22BUP%3A+A+Bottom%2DUp+Parser+Embedded+in+Prolog%2E%22+New+Generation+Computing%2C+1+%282%29%3A+145%2D158%2E)
14. Moortgat, M. 1984 "A Fregean Restriction on Meta-Rules" In Proceedings of New England Linguistic Society, 14:306-325. [find](https://scholar.google.com/scholar?q=Moortgat%2C+M%2E+1984+%22A+Fregean+Restriction+on+Meta%2DRules%22+In+Proceedings+of+New+England+Linguistic+Society%2C+14%3A306%2D325%2E)
15. Naish, L. 1986 "Negation and Control in Prolog," Volume 238 of Lecture Notes in Computer Science. [find](https://scholar.google.com/scholar?q=Naish%2C+L%2E+1986+%22Negation+and+Control+in+Prolog%2C%22+Volume+238+of+Lecture+Notes+in+Computer+Science%2E)
16. Springer-Verlag Berlin, F.R.G. van Noord, G. 1989a "BUG: A Directed Bottom-Up Generator for Unification Based Formalisms." Working Papers in Natural Language Processing 4, Katholieke Universiteit Leuven, Stichting Taaltechnolo-gie Utrecht, Utrecht, the Netherlands. van Noord, G. 1989b "An Overview o… [find](https://scholar.google.com/scholar?q=Springer%2DVerlag+Berlin%2C+F%2ER%2EG%2E+van+Noord%2C+G%2E+1989a+%22BUG%3A+A+Directed+Bottom%2DUp+Generator+for+Unification+Based+Formalisms%2E%22+Working+Papers+in+Natural+Language+Processing+4%2C+Katholieke+Universiteit+Leuv)
17. Pereira, F.C.N. and Shieber, S.M. 1985 "Prolog and Natural-Language Analysis," Volume 10 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford, CA. [find](https://scholar.google.com/scholar?q=Pereira%2C+F%2EC%2EN%2E+and+Shieber%2C+S%2EM%2E+1985+%22Prolog+and+Natural%2DLanguage+Analysis%2C%22+Volume+10+of+CSLI+Lecture+Notes%2E+Center+for+the+Study+of+Language+and+Information%2C+Stanford%2C+CA%2E)
18. Pereira, F.C.N. and Warren, D.H.D. 1983 "Parsing as Deduction." In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics, 137-144. [find](https://scholar.google.com/scholar?q=Pereira%2C+F%2EC%2EN%2E+and+Warren%2C+D%2EH%2ED%2E+1983+%22Parsing+as+Deduction%2E%22+In+Proceedings+of+the+21st+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+137%2D144%2E)
19. Pereira, F.C.N. 1981 "Extraposition Grammars." Computational Linguistics, 7(4):243-256. [find](https://scholar.google.com/scholar?q=Pereira%2C+F%2EC%2EN%2E+1981+%22Extraposition+Grammars%2E%22+Computational+Linguistics%2C+7%284%29%3A243%2D256%2E)
20. Po'ilard, C. 1988 "Categorial Grammar and Phrase Structure Grammar: An ]Excursion on the Syntax-Semantics Frontier," In R. Oehrle, E. Bach, and D. Wheeler (eds.), Categorial Grammars and Natural Language Structures. D. Reidel, Dordrecht, the Netherlands. [find](https://scholar.google.com/scholar?q=Po%27ilard%2C+C%2E+1988+%22Categorial+Grammar+and+Phrase+Structure+Grammar%3A+An+%5DExcursion+on+the+Syntax%2DSemantics+Frontier%2C%22+In+R%2E+Oehrle%2C+E%2E+Bach%2C+and+D%2E+Wheeler+%28eds%2E%29%2C+Categorial+Grammars+and+Natural+Langu)
21. Shieber, S.M. 1985a "An Introduction to Unification-Based Approaches to Grammar," Volume 4 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford, CA. [find](https://scholar.google.com/scholar?q=Shieber%2C+S%2EM%2E+1985a+%22An+Introduction+to+Unification%2DBased+Approaches+to+Grammar%2C%22+Volume+4+of+CSLI+Lecture+Notes%2E+Center+for+the+Study+of+Language+and+Information%2C+Stanford%2C+CA%2E)
22. Shieber, S.M. 1985b "Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms." In Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, 145-152. [find](https://scholar.google.com/scholar?q=Shieber%2C+S%2EM%2E+1985b+%22Using+Restriction+to+Extend+Parsing+Algorithms+for+Complex%2DFeature%2DBased+Formalisms%2E%22+In+Proceedings+of+the+23rd+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+1)
23. Shieber, S.M. 1988 "A Uniform Architecture for Parsing and Generation." In Proceedings of the 12th International Conference on Computational Linguistics, 614-619. [find](https://scholar.google.com/scholar?q=Shieber%2C+S%2EM%2E+1988+%22A+Uniform+Architecture+for+Parsing+and+Generation%2E%22+In+Proceedings+of+the+12th+International+Conference+on+Computational+Linguistics%2C+614%2D619%2E)
24. Stcedman, M. 1985 "Dependency and Coordination in the Grammar of Dutch and English." Language, 61 (3):523-568. [find](https://scholar.google.com/scholar?q=Stcedman%2C+M%2E+1985+%22Dependency+and+Coordination+in+the+Grammar+of+Dutch+and+English%2E%22+Language%2C+61+%283%29%3A523%2D568%2E)
25. Strzalkowski, T. 1989 Automated Inversion of a Unification Parser into a Unification Generator. Technical Report 465, Department of Computer Science, New York University, New York. [find](https://scholar.google.com/scholar?q=Strzalkowski%2C+T%2E+1989+Automated+Inversion+of+a+Unification+Parser+into+a+Unification+Generator%2E+Technical+Report+465%2C+Department+of+Computer+Science%2C+New+York+University%2C+New+York%2E)
26. Wedekind, J. 1988 "Generation as Structure Driven Derivation." In Proceedings of the 12th International Conference on Computational Linguistics, 732-737. [find](https://scholar.google.com/scholar?q=Wedekind%2C+J%2E+1988+%22Generation+as+Structure+Driven+Derivation%2E%22+In+Proceedings+of+the+12th+International+Conference+on+Computational+Linguistics%2C+732%2D737%2E)

*Updated 24 October 2026*