---
title: "Parsing Strategies with ‘Lexicalized' Grammars: Application to"
description: "On this basis they propose a two-stage parser. 15 references, cited by 66 papers here. Among them: 15."
authors: ["Yves Schabes", "Anne Abeille", "Aravind K. Joshi"]
year: 1988
venue: "Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics"
source: "https://aclanthology.org/C88-2121/"
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/schabes-1988-parsing-strategies-lexicalized-grammars-application/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/schabes-1988-parsing-strategies-lexicalized-grammars-application/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1988](https://md.research.elamur.ai/free/en/papers/1988/) / Parsing Strategies with ‘Lexicalized' Grammars: Application to Tree Adjoining Grammars

# Parsing Strategies with ‘Lexicalized' Grammars: Application to Tree Adjoining Grammars

**Authors:** [Yves Schabes](https://md.research.elamur.ai/free/en/authors/yves-schabes/), [Anne Abeille](https://md.research.elamur.ai/free/en/authors/anne-abeille/) and [Aravind K. Joshi](https://md.research.elamur.ai/free/en/authors/aravind-joshi/) · **Year:** 1988 · **Venue:** [Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 1988](https://md.research.elamur.ai/free/en/venues/coling/1988/)) · **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/C88-2121/) · [PDF](https://aclanthology.org/C88-2121.pdf) · [OpenAlex](https://openalex.org/W7051649268)

**Citations:** 15 citations (OpenAlex, 2026-10-14) · [66](https://md.research.elamur.ai/free/en/papers/schabes-1988-parsing-strategies-lexicalized-grammars-application/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper asks what it formally means for a grammar to be "lexicalized" and how this affects parsing. The authors call a formalism lexicalized when every elementary structure is anchored by a lexical item, usually its head, and the structures are combined by a fixed set of operations. They require the lexicalized grammar to keep the original tree set, not only the original language. They show that a CFG without recursive chain rules can be lexicalized with a substitution-only tree rewriting system. However, substitution alone can force linguistically odd head choices. Adding adjunction, as in Tree Adjoining Grammars (TAGs), lets the grammar writer pick heads freely. TAGs are therefore presented as lexicalized by design. On this basis they propose a two-stage parser. First, it collects the elementary structures selected by the words of the input. Second, it parses using only that finite set. Because this grammar is finite and tied to the sentence, recursion problems disappear and top-down search becomes viable. They show how their Earley-type TAG parser can be adapted to this strategy.

## Key points
- **Lexicalization criterion:** the lexicalized grammar must yield the same structures as the original grammar. Greibach normal form lexicalizes a CFG trivially, but it is rejected as a general method because it may change the tree set.
- **Substitution-only limits:** a tree rewriting grammar that uses only substitution generates exactly the context-free languages. It can lexicalize CFGs lacking recursive chain rules. In the paper's VP/adverb example, the adverb must be chosen as head instead of the verb.
- **TAG variant used:** three finite sets of elementary trees.
  - I: initial trees, rooted in S.
  - A: auxiliary trees, which have a foot node carrying the same label as the root.
  - L: lexical trees for arguments.
  
  Substitution is added alongside adjunction. It is mandatory on marked frontier nodes, and adjunction is blocked there. This addition does not alter TAG's formal properties.
- **Parser rules:** each parser rule is instantiated by one specific token at one input position, so it can be used only once.
- **Earley extension:** a new state component Γ tracks the trees not yet used. Once the Left Predictor uses one tree of a token, it removes that token's whole tree set. The scanner also checks the head's position, not just its word form.

## Interesting ideas
- **Filter the grammar per sentence before parsing.** Shrinking the grammar to the structures anchored by the actual input gives a search space that grows with sentence length. This idea underlies supertagging-style pre-filtering in any lexicalized parser.
- **Treat each token's structures as a use-once resource.** Removing a token's alternatives once one is consumed cleanly prevents reusing a word. It also guarantees termination, and resembles resource accounting in other chart or deduction-based parsers.
- **Judge grammar transformations by their trees.** Requiring that a conversion preserve trees, not just strings, is a useful standard for grammar or treebank conversions such as constituency-to-UD pipelines.
- **Separate recursion from local dependencies.** Adjunction lets a head keep its arguments local while modifiers attach recursively. This design choice helps any resource where head choice should follow linguistic motivation rather than formal convenience.
- **Use the whole input to guide search.** Since every structure is known up front, the parser can exploit information about words far ahead. This is useful for languages with flexible word order, such as Ukrainian.

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

📚 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

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 161 works

## Cite

Cite as: Yves Schabes, Anne Abeille and Aravind K. Joshi. 1988. Parsing Strategies with ‘Lexicalized' Grammars: Application to Tree Adjoining Grammars. Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics.

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

```bibtex
@inproceedings{schabes1988parsing,
  title = {{Parsing Strategies with ‘Lexicalized' Grammars: Application to Tree Adjoining Grammars}},
  author = {Yves Schabes, Anne Abeille and Aravind K. Joshi},
  booktitle = {Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics},
  year = {1988},
  url = {https://aclanthology.org/C88-2121/}
}
```

- [← previous An Architecture for Anaphora Resolution](https://md.research.elamur.ai/free/en/papers/rich-1988-architecture-anaphora-resolution/)
- [next → Anaphora Resolution: A Multi-Strategy Approach](https://md.research.elamur.ai/free/en/papers/carbonell-1988-anaphora-resolution-multi-strategy-approach/)
- [↑ back to papers of 1988](https://md.research.elamur.ai/free/en/papers/1988/)

## References

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

1. Abeilld, Anne, 1988. Parsing French with Tree Adjoining Grammar: some Linguistic Accounts. In Proceeding of the 12 °' International Conference on Computational Linguistics. van Benthem, Johns, 1985. [find](https://scholar.google.com/scholar?q=Abeilld%2C+Anne%2C+1988%2E+Parsing+French+with+Tree+Adjoining+Grammar%3A+some+Linguistic+Accounts%2E+In+Proceeding+of+the+12+%C2%B0%27+International+Conference+on+Computational+Linguistics%2E+van+Benthem%2C+Johns%2C+1985%2E)
2. Lambek Calculus. Manuscript, Filosofisch Instituut, Rijks Universiteit, Groningen. van Benthem, Johan, 1986. Essays on Logical Semantics, Chapter 7, pages 123-150. D. Reidel Publishing Company. [find](https://scholar.google.com/scholar?q=Lambek+Calculus%2E+Manuscript%2C+Filosofisch+Instituut%2C+Rijks+Universiteit%2C+Groningen%2E+van+Benthem%2C+Johan%2C+1986%2E+Essays+on+Logical+Semantics%2C+Chapter+7%2C+pages+123%2D150%2E+D%2E+Reidel+Publishing+Company%2E)
3. Gross, Manriee, 1984. Lexicon-Grammar and the Syntactic Analysis of French. In Proceeding of the 10 th International Conference on Computational Linguistics. [find](https://scholar.google.com/scholar?q=Gross%2C+Manriee%2C+1984%2E+Lexicon%2DGrammar+and+the+Syntactic+Analysis+of+French%2E+In+Proceeding+of+the+10+th+International+Conference+on+Computational+Linguistics%2E)
4. Joshi, Aravind K., 1985. How Much Context-Sensitivlty is Necessary for Characterizing Structural Descriptions--Tree Adjoining Grammars. In Dowry, D.; Karttunen, L.; and Zwicky, A. (editors), Natural Language Processing--Theoretical, Computational and Psychological Perspectives. Cambridge University… [find](https://scholar.google.com/scholar?q=Joshi%2C+Aravind+K%2E%2C+1985%2E+How+Much+Context%2DSensitivlty+is+Necessary+for+Characterizing+Structural+Descriptions%2D%2DTree+Adjoining+Grammars%2E+In+Dowry%2C+D%2E%3B+Karttunen%2C+L%2E%3B+and+Zwicky%2C+A%2E+%28editors%29%2C+Natural+L)
5. Joshi, A. K.; Levy, L. S.; and Ta~ahashi, M, 1975. Tree Adjunct Grammars. J. Comput. Syst. Sci. 10(1). [find](https://scholar.google.com/scholar?q=Joshi%2C+A%2E+K%2E%3B+Levy%2C+L%2E+S%2E%3B+and+Ta%7Eahashi%2C+M%2C+1975%2E+Tree+Adjunct+Grammars%2E+J%2E+Comput%2E+Syst%2E+Sci%2E+10%281%29%2E)
6. Kroch, A. and Joshi, A. K., 1985. Linguistic Relevance of Tree Adjoining Grammars. Technical Report MS-CIS-85-18, Department of Computer and Information Science, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Kroch%2C+A%2E+and+Joshi%2C+A%2E+K%2E%2C+1985%2E+Linguistic+Relevance+of+Tree+Adjoining+Grammars%2E+Technical+Report+MS%2DCIS%2D85%2D18%2C+Department+of+Computer+and+Information+Science%2C+University+of+Pennsylvania%2E)
7. Lambek, Joachim, 1958. The Mathematics of Sentence Structure. American Mathematical Monthly 65:154-170. [find](https://scholar.google.com/scholar?q=Lambek%2C+Joachim%2C+1958%2E+The+Mathematics+of+Sentence+Structure%2E+American+Mathematical+Monthly+65%3A154%2D170%2E)
8. Lambek, Joachim, 1961. On the Calculus of Syntactic Types. In Proceedings of the Symposium on Applied Mathematics, pages 166-178. [find](https://scholar.google.com/scholar?q=Lambek%2C+Joachim%2C+1961%2E+On+the+Calculus+of+Syntactic+Types%2E+In+Proceedings+of+the+Symposium+on+Applied+Mathematics%2C+pages+166%2D178%2E)
9. Schabes, Yves and Joshi, Aravind K., 1988 (a). An Earley-Type Parsing Algorithm for Tree Adjoining Grammars. In 26 th Meeting of the Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Schabes%2C+Yves+and+Joshi%2C+Aravind+K%2E%2C+1988+%28a%29%2E+An+Earley%2DType+Parsing+Algorithm+for+Tree+Adjoining+Grammars%2E+In+26+th+Meeting+of+the+Association+for+Computational+Linguistics%2E)
10. Schabes, Yves and Joshi, Aravind K., ]988 (b). An Earley-type Parser for Tree Adjoining Grammars. Technical Report, Department of Computer and Information Science, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Schabes%2C+Yves+and+Joshi%2C+Aravind+K%2E%2C+%5D988+%28b%29%2E+An+Earley%2Dtype+Parser+for+Tree+Adjoining+Grammars%2E+Technical+Report%2C+Department+of+Computer+and+Information+Science%2C+University+of+Pennsylvania%2E)
11. Shieber, Stuart M., 1984. The Design of a Computer Language for Linguistic Information. In 22 ~d Meeting of the Association for Computational Linguistics, pages 362-366. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E%2C+1984%2E+The+Design+of+a+Computer+Language+for+Linguistic+Information%2E+In+22+%7Ed+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+362%2D366%2E)
12. Shieber, Stuart M., 1985. Using Restriction to Extend Parsing Algorithms for Complex-feature-based Formalisms. In 23 rd Meeting of the Association for Computational Linguistics, pages 82-93. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E%2C+1985%2E+Using+Restriction+to+Extend+Parsing+Algorithms+for+Complex%2Dfeature%2Dbased+Formalisms%2E+In+23+rd+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+82%2D93%2E)
13. Shieber, Stuart M., 1986. An Introduction to Unification-Based Approaches to Grammar. Center for the Study of Language and Information, Stanford, CA. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E%2C+1986%2E+An+Introduction+to+Unification%2DBased+Approaches+to+Grammar%2E+Center+for+the+Study+of+Language+and+Information%2C+Stanford%2C+CA%2E)
14. Vijay-Shanker, K., 1987. A Study of Tree Adjoining Grammars. PhD thesis, Department of Computer and Information Science, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+1987%2E+A+Study+of+Tree+Adjoining+Grammars%2E+PhD+thesis%2C+Department+of+Computer+and+Information+Science%2C+University+of+Pennsylvania%2E)
15. Vijay-Shanker, K. and Joshi, A.K., 1988. Feature Structure Baaed Tree Adjoining Grammars. In Proceedings of the 12 th International Conference on Computational Linguistics. [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E+and+Joshi%2C+A%2EK%2E%2C+1988%2E+Feature+Structure+Baaed+Tree+Adjoining+Grammars%2E+In+Proceedings+of+the+12+th+International+Conference+on+Computational+Linguistics%2E)

*Updated 24 October 2026*