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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alonso, M.A., Cabrero, D., de la Clergerie, E., Vilares, M.: Tabular algorithms for TAG parsing. In Proc. of EACL’99 (1999) 150–157
Diaz, V., Carrillo, V., Alonso, M.A.: A left corner parser for tree adjoining grammars. In Proc. of TAG+6 (2002) 90–95
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
Joshi, A.K., Schabes, Y.: Tree-adjoining grammars. Handbook of Formal Languages 3 (1997) 69–123
Nederhof, M.: The computational complexity of the correct-prefix property for TAGs. Computational Linguistics 25(3) (1999) 345–360
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
Schabes, Y., Waters, R.C.: Stochastic lexicalized tree-insertion grammar. Recent Advances in Parsing Technology (1996) 281–294
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
Sikkel, K.: Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms (1997)
XTAG Research Group: A Lexicalized Tree Adjoining Grammar for English. Technical Report IRCS-01-03, University of Pennsylvania,USA (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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