Elamur Research⌕
☰
home / papers / 1988 / Parsing Strategies with ‘Lexicalized' Grammars: Application to Tree Adjoining Grammars

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

Paper · 1988 · Yves Schabes, Anne Abeille and Aravind K. Joshi

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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.
  • I5. 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 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputational Theory and Mathematics · 116 works

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

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

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
  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
  3. Gross, Manriee, 1984. Lexicon-Grammar and the Syntactic Analysis of French. In Proceeding of the 10 th International Conference on Computational Linguistics. find
  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
  5. Joshi, A. K.; Levy, L. S.; and Ta~ahashi, M, 1975. Tree Adjunct Grammars. J. Comput. Syst. Sci. 10(1). find
  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
  7. Lambek, Joachim, 1958. The Mathematics of Sentence Structure. American Mathematical Monthly 65:154-170. find
  8. Lambek, Joachim, 1961. On the Calculus of Syntactic Types. In Proceedings of the Symposium on Applied Mathematics, pages 166-178. find
  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
  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
  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
  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
  13. Shieber, Stuart M., 1986. An Introduction to Unification-Based Approaches to Grammar. Center for the Study of Language and Information, Stanford, CA. find
  14. Vijay-Shanker, K., 1987. A Study of Tree Adjoining Grammars. PhD thesis, Department of Computer and Information Science, University of Pennsylvania. find
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/schabes-1988-parsing-strategies-lexicalized-grammars-application/