A parsing algorithm for Korean implemented in Prolog

ABSTRACT

This paper presents a parsing algorithm for a partial free-word-order language, Korean. It is based on dependency grammar, unification-based grammar, and implemented in Prolog. The dependency grammar accepts free order of the words in a sentence. Unification-based features separate the grammar from the parsing algorithm, and as a result, the parser can easily be applied to parse other languages by modifying only the lexicon and the grammar. Also, the features check syntactic, morphological, and semantic dependency. The parser provides a structure of a natural language sentence of Korean with dependency pairs. It constrains totally free-word-order languages, recognizes subcategorization features, restricts the order of dependents for a single head, and matches long-distance dependencies.

REFERENCES

• 1: H. Chung and H. Rim. Unlexicalized dependency parser for variable word order languages based on local contextual pattern. CICLing, pages 112--123, 2004.
• 2: Michael A. Covington, Parsing discontinuous constituents in dependency grammar, Computational Linguistics, v.16 n.4, December 1990
• 3: M. A. Covington. Gulp 3.1: An extension of prolog for unification-based grammar. Research Report AI-1994-06, Artificial Intelligence Programs, University of Georgia, 1994.
• 4: M. A. Covington. A fundamental algorithm for dependency parsing. In Proceedings OF 39th Annual ACM Southeast Conference, 2001.
• 5: R. Hudson. Word Grammar. Basil Blackwell, 1984.
• 6: C. Kim, J. Kim, J. Seo, and G. Kim. A right-to-left chart parsing with headable paths for korean dependency grammar. ICCPOL-94, pages 175--180, 1994.
• 7: M. Kim, S. Kang, and J. Lee. Resolving ambiguity in inter-chunk dependency parsing. NLPRS, pages 263--270, 2001.
• 8: H. Kwon and A. Yoon. Unification-based dependency parsing of governor-final languages. In Proceedings of the Second International Workshop on Parsing Technologies, pages 182--192, 1989.
• 9: I. Mel'čuk. Levels of dependency in linguistic description: Concepts and problems. V. Agel, L. Eichinnger, H.-W. Eroms, P. Hellwig, H. J. Herringer, H. Lobin (eds): Dependency and Valency. An International Handbook of Contemporary Research, 1:188--229, 2003.
• 10: H. Sohn. The Korean Language. Cambridge University Press, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Language parsing and understanding

General Terms:
Algorithms, Languages

Keywords:
Prolog, dependency grammar, parsing, unification-based grammar