Hostname: page-component-76fb5796d-25wd4 Total loading time: 0 Render date: 2024-04-26T00:47:43.564Z Has data issue: false hasContentIssue false
  • English
  • Français

Deterministic shift-reduce parsing for unification-based grammars

Published online by Cambridge University Press:  21 October 2010

TAKASHI NINOMIYA ,
TAKUYA MATSUZAKI ,
NOBUYUKI SHIMIZU  and
HIROSHI NAKAGAWA
TAKASHI NINOMIYA
Affiliation:
Graduate School of Science and Engineering, Ehime University, 3 Bunkyo-cho, Matsuyama, Ehime 790-8577, Japan e-mail: ninomiya@cs.ehime-u.ac.jp
TAKUYA MATSUZAKI
Affiliation:
Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan e-mail: matuzaki@is.s.u-tokyo.ac.jp
NOBUYUKI SHIMIZU
Affiliation:
Information Technology Center, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan e-mail: shimizu@r.dl.itc.u-tokyo.ac.jp, n3@dl.itc.u-tokyo.ac.jp
HIROSHI NAKAGAWA
Affiliation:
Information Technology Center, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan e-mail: shimizu@r.dl.itc.u-tokyo.ac.jp, n3@dl.itc.u-tokyo.ac.jp
Get access Rights & Permissions [Opens in a new window]

Abstract

Many parsing techniques assume the use of a packed parse forest to enable efficient and accurate parsing. However, they suffer from an inherent problem that derives from the restriction of locality in the packed parse forest. Deterministic parsing is one solution that can achieve simple and fast parsing without the mechanisms of the packed parse forest by accurately choosing search paths. We propose new deterministic shift-reduce parsing and its variants for unification-based grammars. Deterministic parsing cannot simply be applied to unification-based grammar parsing, which often fails because of its hard constraints. Therefore, this is developed by using default unification, which almost always succeeds in unification by overwriting inconsistent constraints in grammars.

Type
Articles
Information
Natural Language Engineering , Volume 17 , Issue 3 , July 2011 , pp. 331 - 365
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abney, S. P. 1997. Stochastic attribute-value grammars. Computational Linguistics 23 (4): 597–618.Google Scholar
Bouma, G. 1990. Defaults in unification grammar. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics, Pittsburgh, PA, pp. 165–172.CrossRefGoogle Scholar
Bresnan, J., and Kaplan, R. M. 1982. Introduction:grammars as mental representations of language. In Bresnan, J. (ed.), The Mental Representation of Grammatical Relations. Cambridge, MA: MIT Press.Google Scholar
Briscoe, T. 1993a. Introduction. In Briscoe, T., de Paiva, V. and Copestake, A. (eds.), Inheritance, Defaults and the Lexicon. Cambridge, UK: Cambridge University Press.Google Scholar
Briscoe, T., and Carroll, J. 1993b. Generalized probabilistic LR-parsing of natural language (corpora) with unification-based grammars. Computational Linguistics 19 (1): 25–59.Google Scholar
Butt, M., King, T. H., Niño, M.-E., and Segond, F. 1999. A Grammar Writer's Cookbook. Stanford, CA: CSLI Publications.Google Scholar
Carpenter, B. 1992. The Logic of Typed Feature Structures. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Carpenter, B. 1993. Skeptical and credulous default unification with applications to templates and inheritance. In Briscoe, T., de Paiva, V. and Copestake, A. (eds.), Inheritance, Defaults and the Lexicon. Cambridge, UK: Cambridge University Press.Google Scholar
Charniak, E., and Johnson, M. 2005. Coarse-to-fine n-best parsing and maxent discriminative reranking. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics, Ann Arbor, MI, pp. 173–180.Google Scholar
Clark, S., and Curran, J. R. 2004a The importance of supertagging for wide-coverage CCG parsing. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, pp. 282–288.Google Scholar
Clark, S., and Curran, J. R. 2004b. Parsing the WSJ using CCG and log-linear models. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 103–110.Google Scholar
Collins, M. 2000. Discriminative reranking for natural language parsing. In Proceedings of the 17th International Conference on Machine Learning, Stanford, CA, pp. 175–182.Google Scholar
Collins, M., and Roark, B. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 111–118.Google Scholar
Copestake, A. 1993. Defaults in lexical representation. In Briscoe, T., de Paiva, V., and Copestake, A. (eds.), Inheritance, Defaults and the Lexicon. Cambridge, UK: Cambridge University Press.Google Scholar
Daumé, H. III, and Marcu, D. 2005. Learning as search optimization: approximate large margin methods for structured prediction. In Proceedings of The 22nd International Conference on Machine Learning, Bonn, Germany, pp. 169–176.CrossRefGoogle Scholar
Frank, A., King, T. H., Kuhn, J., and Maxwell, J. T. III 2001. Optimality theory style constraint ranking in large-scale LFG grammars. In Sells, P. (ed.), Formal and Empirical Issues in Optimality-Theoretic Syntax. Stanford, CA: CSLI, pp. 367–397.Google Scholar
Geman, S., and Johnson, M. 2002. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, Philadelphia, PA, pp. 279–286.Google Scholar
Hockenmaier, J. 2003. Parsing with generative models of predicate–argument structure. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, Sapporo, Japan, pp. 359–366.Google Scholar
Hockenmaier, J., and Steedman, M. 2002. Acquiring compact lexicalized grammars from a cleaner treebank. In Proceedings of the Third International Conference on Language Resources and Evaluation, Las Palmas, Spain, pp. 1974–1981.Google Scholar
Huang, L. 2008. Forest reranking: discriminative parsing with non-local features. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Columbus, OH, pp. 586–594.Google Scholar
Johnson, M., Geman, S., Canon, S., Chi, Z., and Riezler, S. 1999. Estimators for stochastic “unification-based” grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, College Park, MD, pp. 535–541.Google Scholar
Kaplan, R. M., Riezler, S., King, T. H., Maxwell, J. T. III, and Vasserman, A. 2004. Speed and accuracy in shallow and deep stochastic parsing. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, Boston, MA, pp. 97–104.Google Scholar
Malouf, R. 2002. A comparison of algorithms for maximum entropy parameter estimation. In Proceedings of the Sixth Conference on Natural Language Learning, Taipei, Taiwan, pp. 49–55.Google Scholar
Malouf, R., and van Noord, G. 2004. Wide coverage parsing with stochastic attribute value grammars. In Proceedings of the IJCNLP-04 Workshop: Beyond Shallow Analyses - Formalisms and Statistical Modeling for Deep Analyses. Hainan Island, China.Google Scholar
Matsuzaki, T., Miyao, Y., and Tsujii, J. 2007. Efficient HPSG parsing with supertagging and CFG-filtering. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, pp. 1671–1676.Google Scholar
Miyao, Y., Ninomiya, T., and Tsujii, J. 2005. Corpus-oriented grammar development for acquiring a head-driven phrase structure grammar from the Penn Treebank. In Su, K.-Y., , J. T., Lee, J.-H., and Kwong, O. Y. (eds.), Natural Language Processing - IJCNLP 2004, pp. 684–693. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer- Verlag.CrossRefGoogle Scholar
Miyao, Y., and Tsujii, J. 2002. Maximum entropy estimation for feature forests. In Proceedings of the Second International Conference on Human Language Technology Research, San Diego, CA, pp. 292–297.Google Scholar
Miyao, Y., and Tsujii, J. 2005. Probabilistic disambiguation models for wide-coverage HPSG parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics, Ann Arbor, MI, pp. 83–90.Google Scholar
Nakagawa, T. 2007 Multilingual dependency parsing using global features. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, Prague, Czech Republic, pp. 952–956.Google Scholar
Ninomiya, T., Matsuzaki, T., Miyao, Y., and Tsujii, J. 2007. A log-linear model with an n-gram reference distribution for accurate HPSG parsing. In Proceedings of the 10th International Conference on Parsing Technologies, Prague, Czech Republic, pp. 60–68.Google Scholar
Ninomiya, T., Matsuzaki, T., Tsuruoka, Y., Miyao, Y., and Tsujii, J. 2006. Extremely lexicalized models for accurate and fast HPSG parsing. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, Sydney, Australia, pp. 155–163.Google Scholar
Ninomiya, T., Miyao, Y., and Tsujii, J. 2002. Lenient default unification for robust processing within unification-based grammar formalisms. In Proceedings of the 19th International Conference on Computational Linguistics, Taipei, Taiwan, pp. 744–750.Google Scholar
Nivre, J., and Scholz, M. 2004. Deterministic dependency parsing of English text. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, pp. 64–70.Google Scholar
O'Donovan, R., Burke, M., Cahill, A., van Genabith, J., and Way, A. 2004 Large-scale induction and evaluation of lexical resources from the Penn-II Treebank. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 367–374.Google Scholar
Perkins, S., Lacker, K., and Theiler, J. 2003. Grafting: fast, incremental feature selection by gradient decent in function space. Journal of Machine Learning Research 3: 1333–1356.Google Scholar
Pollard, C., and Sag, I. A. 1994. Head-Driven Phrase Structure Grammar. Chicago, IL and Stanford, CA: University of Chicago Press and CSLI Publications.Google Scholar
Ratnaparkhi, A. 1997, A linear observed time statistical parser based on maximum entropy models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, Providence, RI, pp. 1–10.Google Scholar
Riezler, S., Prescher, D., Kuhn, J., and Johnson, M. 2000. Lexicalized stochastic modeling of constraint-based grammars using log-linear measures and EM training. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics, Hong Kong, China, pp. 480–487.Google Scholar
Sagae, K., and Lavie, A. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of the 9th International Workshop on Parsing Technology, Vancouver, Canada, pp. 125–132.CrossRefGoogle Scholar
Sagae, K., and Lavie, A. 2006. A best-first probabilistic shift-reduce parser. In Proceedings of the COLING/ACL on Main Conference Poster Sessions, Sydney, Australia, pp. 691–698.CrossRefGoogle Scholar
Sagae, K., Miyao, Y., and Tsujii, J. 2007. HPSG parsing with shallow dependency constraints. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, Prague, Czech Republic, pp. 624–631.Google Scholar
Steedman, M. 2000. The Syntactic Process. Cambridge, MA: The MIT Press.Google Scholar
Toutanova, K., Manning, C. D., Shieber, S. M., Flickinger, D., and Oepen, S. 2002. Parse disambiguation for a rich HPSG grammar. In Proceedings of The First Workshop on Treebanks and Linguistic Theories (TLT2002), Sozopol, Bulgaria, pp. 253–263.Google Scholar
Tsuruoka, Y., and Tsujii, J. 2005. Iterative CKY parsing for probabilistic context-free grammars. In Su, K.-Y., Tsujii, J., Lee, J.-H., and Kwong, O. Y. (eds.), Natural Language Processing - IJCNLP 2004, pp. 52–60. Lecture Notes in Artificial Intelligence. Berlin¡ Germany: Springer-Verlag.CrossRefGoogle Scholar
Yamada, H., and Matsumoto, Y. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the 8th International Workshop on Parsing Technologies, Nancy, France, pp. 195–206.Google Scholar
Zhang, Y., and Clark, S. 2009. Transition-based parsing of the Chinese treebank using a global discriminative model. In Proceedings of the 11th International Conference on Parsing Technologies, Paris, France, pp. 162–171.Google Scholar
Zhang, Y., Oepen, S., and Carroll, J. 2007. Efficiency in unification-based N-best parsing. In Proceedings of the 10th International Conference on Parsing Technologies, Prague, Czech, pp. 48–59.Google Scholar