---
title: "Parsing Some Constrained Grammar Formalisms (1993)"
description: "They develop a pure bottom-up, CKY-style recognizer for LIG in a binary normal form. 16 references, cited by 37 papers here."
authors: ["K Vijay-Shanker", "David J. Weir"]
year: 1993
venue: "Computational Linguistics"
source: "https://aclanthology.org/J93-4002/"
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/shanker-1993-parsing-some-constrained-grammar-formalisms/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/shanker-1993-parsing-some-constrained-grammar-formalisms/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1993](https://md.research.elamur.ai/free/en/papers/1993/) / Parsing Some Constrained Grammar Formalisms

# Parsing Some Constrained Grammar Formalisms

**Authors:** [K Vijay-Shanker](https://md.research.elamur.ai/free/en/authors/k-vijay-shanker/) and [David J. Weir](https://md.research.elamur.ai/free/en/authors/david-weir/) · **Year:** 1993 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1993](https://md.research.elamur.ai/free/en/venues/cl/1993/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **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/J93-4002/) · [PDF](https://aclanthology.org/J93-4002.pdf)

**Citations:** [37](https://md.research.elamur.ai/free/en/papers/shanker-1993-parsing-some-constrained-grammar-formalisms/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Vijay-Shanker and Weir carry context-free recognition techniques over to a few mildly context-sensitive formalisms, namely Tree Adjoining Grammars (TAG), Linear Indexed Grammars (LIG), and a variant of Combinatory Categorial Grammars (CCG). These formalisms control derivations with unbounded stacks, either explicitly or implicitly. Storing whole stacks in a parse table would make recognition exponential. The authors observe that in LIG and CCG, different branches of a derivation never share a stack. So the context-freeness property still holds, and a bounded amount of information per table cell is enough.

They develop a pure bottom-up, CKY-style recognizer for LIG in a binary normal form. Each table cell stores only the top part of a stack plus a pointer to the cell where the rest of that stack can be recovered. They prove the algorithm correct by induction, then adapt it to CCG and TAG. The result is a reusable recipe for polynomial-time recognition of stack-controlled grammars. At the time, it gave the only known polynomial-time recognizer for CCG.

## Key points
- The central problem is unbounded stacks. Path sets of CFG, HG, and TAG derivation trees are regular languages, while those of LIG and CCG are context-free. Naive stack storage therefore leads to exponential time and space.
- The LIG normal form allows at most two right-hand-side symbols, split into a primary and a secondary constituent. The primary constituent always yields the distinguished child, which inherits the stack.
- The table P[i, d] for input a₁…aₙ (an n × n array) records that an object derives the substring starting at position i with length d. Entries keep the nonterminal and top stack symbols, plus "terminator" pointers to other entries for the rest of the stack.
- The pointer trick only works directly when at least two stack symbols are recorded (k ≥ 2). The authors handle the remaining cases with a threshold on stack length (TTC) and a "TC-property" in the correctness proof.
- The scheme builds on equivalence proofs linking LIG, TAG, CCG, and Head Grammars. The authors note it could be adapted to Earley-style parsing or Lang's (1990) framework.

*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 (2): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works

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

## Cite

Cite as: K Vijay-Shanker and David J. Weir. 1993. Parsing Some Constrained Grammar Formalisms. Computational Linguistics.

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

```bibtex
@article{vijayshanker1993parsing,
  title = {{Parsing Some Constrained Grammar Formalisms}},
  author = {K Vijay-Shanker and David J. Weir},
  journal = {Computational Linguistics},
  year = {1993},
  url = {https://aclanthology.org/J93-4002/}
}
```

- [← previous Book Reviews: Corpus Linguistics and the Automatic Analysis of English](https://md.research.elamur.ai/free/en/papers/briscoe-1993-book-reviews-corpus-linguistics-automatic/)
- [next → A Principle-based Parser for Foreign Language Training in German and Arabic](https://md.research.elamur.ai/free/en/papers/garman-1993-principle-based-parser-foreign-language/)
- [↑ back to papers of 1993](https://md.research.elamur.ai/free/en/papers/1993/)

## References

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

1. Aho, A. V. (1968). "Indexed grammars--An extension to context free grammars." J. ACM, 15, 647-671. [find](https://scholar.google.com/scholar?q=Aho%2C+A%2E+V%2E+%281968%29%2E+%22Indexed+grammars%2D%2DAn+extension+to+context+free+grammars%2E%22+J%2E+ACM%2C+15%2C+647%2D671%2E)
2. Duske, J., and Parchmann, R. (1984). "Linear indexed languages." Theoretical Comput. Sci., 32, 47-60. [find](https://scholar.google.com/scholar?q=Duske%2C+J%2E%2C+and+Parchmann%2C+R%2E+%281984%29%2E+%22Linear+indexed+languages%2E%22+Theoretical+Comput%2E+Sci%2E%2C+32%2C+47%2D60%2E)
3. Gazdar, G. (1988). "Applicability of indexed grammars to natural languages." In Natural Language Parsing and Linguistic Theories, edited by U. Reyle and C. Rohrer. D. Reidel, 69-94. [find](https://scholar.google.com/scholar?q=Gazdar%2C+G%2E+%281988%29%2E+%22Applicability+of+indexed+grammars+to+natural+languages%2E%22+In+Natural+Language+Parsing+and+Linguistic+Theories%2C+edited+by+U%2E+Reyle+and+C%2E+Rohrer%2E+D%2E+Reidel%2C+69%2D94%2E)
4. Joshi, A. K. (1985). "How much context-sensitivity is necessary for characterizing structural descriptions--tree adjoining grammars." In Natural Language Processing--Theoretical, Computational and Psychological Perspective, edited by D. Dowty, L. Karttunen, and A. Zwicky. Cambridge University Press,… [find](https://scholar.google.com/scholar?q=Joshi%2C+A%2E+K%2E+%281985%29%2E+%22How+much+context%2Dsensitivity+is+necessary+for+characterizing+structural+descriptions%2D%2Dtree+adjoining+grammars%2E%22+In+Natural+Language+Processing%2D%2DTheoretical%2C+Computational+and+Psy)
5. Joshi, A. K.; Levy, L. S.; and Takahashi, M. (1975). "Tree adjunct grammars." ]. Comput. Syst. Sci., 10(1), 136-163. [find](https://scholar.google.com/scholar?q=Joshi%2C+A%2E+K%2E%3B+Levy%2C+L%2E+S%2E%3B+and+Takahashi%2C+M%2E+%281975%29%2E+%22Tree+adjunct+grammars%2E%22+%5D%2E+Comput%2E+Syst%2E+Sci%2E%2C+10%281%29%2C+136%2D163%2E)
6. Kasami, T. (1965). "An efficient recognition and syntax algorithm for context-free languages." Technical Report AF-CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA. [find](https://scholar.google.com/scholar?q=Kasami%2C+T%2E+%281965%29%2E+%22An+efficient+recognition+and+syntax+algorithm+for+context%2Dfree+languages%2E%22+Technical+Report+AF%2DCRL%2D65%2D758%2C+Air+Force+Cambridge+Research+Laboratory%2C+Bedford%2C+MA%2E)
7. Lang, B. (1990). "Towards a uniform formal framework for parsing." In Current Issues in Parsing Technology, edited by M. Tomita. Kluwer Academic Publishers, 153-171. [find](https://scholar.google.com/scholar?q=Lang%2C+B%2E+%281990%29%2E+%22Towards+a+uniform+formal+framework+for+parsing%2E%22+In+Current+Issues+in+Parsing+Technology%2C+edited+by+M%2E+Tomita%2E+Kluwer+Academic+Publishers%2C+153%2D171%2E)
8. Pareschi, R., and Steedman, M. J. (1987). "A lazy way to chart-parse with categorial grammars." In Proceedings, 25th Meeting of the Association for Computational Linguistics, 81-88. [find](https://scholar.google.com/scholar?q=Pareschi%2C+R%2E%2C+and+Steedman%2C+M%2E+J%2E+%281987%29%2E+%22A+lazy+way+to+chart%2Dparse+with+categorial+grammars%2E%22+In+Proceedings%2C+25th+Meeting+of+the+Association+for+Computational+Linguistics%2C+81%2D88%2E)
9. Pollard, C. (1984). Generalized Phrase Structure Grammars, Head Grammars and Natural Language. Doctoral dissertation, Stanford University. [find](https://scholar.google.com/scholar?q=Pollard%2C+C%2E+%281984%29%2E+Generalized+Phrase+Structure+Grammars%2C+Head+Grammars+and+Natural+Language%2E+Doctoral+dissertation%2C+Stanford+University%2E)
10. Steedman, M. (1986). "Combinators and grammars." In Categorial Grammars and Natural Language Structures, edited by R. Oehrle, E. Bach, and D. Wheeler. Foris, 417-442. [find](https://scholar.google.com/scholar?q=Steedman%2C+M%2E+%281986%29%2E+%22Combinators+and+grammars%2E%22+In+Categorial+Grammars+and+Natural+Language+Structures%2C+edited+by+R%2E+Oehrle%2C+E%2E+Bach%2C+and+D%2E+Wheeler%2E+Foris%2C+417%2D442%2E)
11. Steedman, M. J. (1985). "Dependency and coordination in the grammar of Dutch and English." Language, 61:523-568. [find](https://scholar.google.com/scholar?q=Steedman%2C+M%2E+J%2E+%281985%29%2E+%22Dependency+and+coordination+in+the+grammar+of+Dutch+and+English%2E%22+Language%2C+61%3A523%2D568%2E)
12. Tomita, M. (1988). "Graph-structured stack and natural language parsing." In Proceedings, 26th Meeting of the Association for Computational Linguistics, 248-257. [find](https://scholar.google.com/scholar?q=Tomita%2C+M%2E+%281988%29%2E+%22Graph%2Dstructured+stack+and+natural+language+parsing%2E%22+In+Proceedings%2C+26th+Meeting+of+the+Association+for+Computational+Linguistics%2C+248%2D257%2E)
13. Vijay-Shanker, K. (1987). A study of tree adjoining grammars. Doctoral dissertation, University of Pennsylvania, Philadelphia, PA. [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E+%281987%29%2E+A+study+of+tree+adjoining+grammars%2E+Doctoral+dissertation%2C+University+of+Pennsylvania%2C+Philadelphia%2C+PA%2E)
14. Vijay-Shanker, K., and Joshi, A. K. (1985). "Some computational properties of tree adjoining grammars." In Proceedings, 23rd Meeting of the Association for Computational Linguistics, 82-93. [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Joshi%2C+A%2E+K%2E+%281985%29%2E+%22Some+computational+properties+of+tree+adjoining+grammars%2E%22+In+Proceedings%2C+23rd+Meeting+of+the+Association+for+Computational+Linguistics%2C+82%2D93%2E)
15. Vijay-Shanker, K., and Weir, D. J. (In press). "The equivalence of four extensions of context-free grammars." Mathematical Systems Theory. [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Weir%2C+D%2E+J%2E+%28In+press%29%2E+%22The+equivalence+of+four+extensions+of+context%2Dfree+grammars%2E%22+Mathematical+Systems+Theory%2E)
16. Vijay-Shanker, K., and Weir, D. J. (1990). [find](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Weir%2C+D%2E+J%2E+%281990%29%2E)

*Updated 30 October 2026*