A Right-to-Left Chart Parsing with Headable Paths for Korean Dependency Grammar
Changhyun Kim, Jae‐Hoon Kim, Jungyun Seo, Gil Chang Kim · 1995
In this paper, we propose a right-to-left dependency grammar parsing method for languages in which a governor appears after its modifier like Korean and Japanese. Unlike conventional left-to-right parsers, this parsing method can take advantage of the governor post-positioning property of such languages to reduce the size of search space by using the idea of a headable path. A headable path is a path which contains all candidate words which can be the governor of an input word during parsing. The experiments showed very promising results in reducing the number of intermediate dependency structures and actual parsing time. Keywords : Dependency Grammar, Governor Post-Positioning Property, No-Crossing Condition, Headable Path 1 Introduction The degree of freedom in word-order varies with each language. Languages like English, French or Chinese are relatively fixed word-order languages, while languages like German are less fixed ones. On the other hand, languages like Korean, Japanese, ...