[go: up one dir, main page]

Skip to main content

Left Corner Parser for Tree Insertion Grammars

  • Conference paper
  • First Online:
Artificial Intelligence: Methodology, Systems, and Applications (AIMSA 2002)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2443))

  • 535 Accesses

Abstract

Tree Adjoining Grammar (TAG) is a grammar formalism that has become very popular for the description of natural languages, however, this context-sensitive formalism entails important computation costs (O(n6)-time). Tree Insertion Grammar (TIG) is a compromise between Context Free Grammar (CFG) and TAG that can be parsed in O(n3) - time. In the literature, just two Earley-like parsers for TIGs have been defined. In this paper, we define a new variant of Earley-like parser for TIGs. In order to improve the performance of this parser,w e show how the left corner relation for CFG can be generalized to the case of TIG and we present an efficient parser for TIG that uses this relation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alonso, M.A., Cabrero, D., de la Clergerie, E., Vilares, M.: Tabular algorithms for TAG parsing. In Proc. of EACL’99 (1999) 150–157

    Google Scholar 

  2. Diaz, V., Carrillo, V., Alonso, M.A.: A left corner parser for tree adjoining grammars. In Proc. of TAG+6 (2002) 90–95

    Google Scholar 

  3. Diaz, V., Carrillo, V., Toro, M.: A review of Earley-based parser for TIG. Lecture Notes in Artificial Intelligence. Subseries of LNCS 1415 (1998) 732–738

    Google Scholar 

  4. Joshi, A.K., Schabes, Y.: Tree-adjoining grammars. Handbook of Formal Languages 3 (1997) 69–123

    MathSciNet  Google Scholar 

  5. Nederhof, M.: The computational complexity of the correct-prefix property for TAGs. Computational Linguistics 25(3) (1999) 345–360

    MathSciNet  Google Scholar 

  6. Schabes, Y., Waters, R.C.: Tree insertion grammar: A cubic-time parsable formalism that lexicalizes context-free grammar without changing the trees produced. Computational Linguistics 21(4) (1995) 479–513

    MathSciNet  Google Scholar 

  7. Schabes, Y., Waters, R.C.: Stochastic lexicalized tree-insertion grammar. Recent Advances in Parsing Technology (1996) 281–294

    Google Scholar 

  8. Shieber, S.M., Schabes, Y., Pereira, F.C.N.: Principles and implementation of deductive parsing. Journal of Logic Programming 24(1–2) (1995) 3–36

    Article  MATH  MathSciNet  Google Scholar 

  9. Sikkel, K.: Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms (1997)

    Google Scholar 

  10. XTAG Research Group: A Lexicalized Tree Adjoining Grammar for English. Technical Report IRCS-01-03, University of Pennsylvania,USA (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Carrillo, V., Díaz, V.J. (2002). Left Corner Parser for Tree Insertion Grammars. In: Scott, D. (eds) Artificial Intelligence: Methodology, Systems, and Applications. AIMSA 2002. Lecture Notes in Computer Science(), vol 2443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46148-5_15

Download citation

  • DOI: https://doi.org/10.1007/3-540-46148-5_15

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-44127-4

  • Online ISBN: 978-3-540-46148-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics