Elamur Research⌕
☰
home / papers / 1993 / Parsing Some Constrained Grammar Formalisms

Parsing Some Constrained Grammar Formalisms

Paper · 1993 · K Vijay-Shanker and David J. Weir

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.

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 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.

@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/}
}

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
  2. Duske, J., and Parchmann, R. (1984). "Linear indexed languages." Theoretical Comput. Sci., 32, 47-60. find
  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
  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
  5. Joshi, A. K.; Levy, L. S.; and Takahashi, M. (1975). "Tree adjunct grammars." ]. Comput. Syst. Sci., 10(1), 136-163. find
  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
  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
  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
  9. Pollard, C. (1984). Generalized Phrase Structure Grammars, Head Grammars and Natural Language. Doctoral dissertation, Stanford University. find
  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
  11. Steedman, M. J. (1985). "Dependency and coordination in the grammar of Dutch and English." Language, 61:523-568. find
  12. Tomita, M. (1988). "Graph-structured stack and natural language parsing." In Proceedings, 26th Meeting of the Association for Computational Linguistics, 248-257. find
  13. Vijay-Shanker, K. (1987). A study of tree adjoining grammars. Doctoral dissertation, University of Pennsylvania, Philadelphia, PA. find
  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
  15. Vijay-Shanker, K., and Weir, D. J. (In press). "The equivalence of four extensions of context-free grammars." Mathematical Systems Theory. find
  16. Vijay-Shanker, K., and Weir, D. J. (1990). find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shanker-1993-parsing-some-constrained-grammar-formalisms/