Parsing method for the translation grammar

This paper proposes a new parsing method based on Dynamic Programming (DP). In Natural Language Processing, the proper syntactic tree of a sentence can be selected as the one with the best score, which is represented the likelihood of the tree. In case that a score of a syntactic tree depends on only that tree itself, the proper syntactic tree can be obtained by an effective parsing method based on DP. However, in Translation Grammar which was proposed for Machine Translation, a score of a syntactic tree depends on a translation of the head word in a phrase which corresponds to the tree. Moreover, in a bottom up parsing, a translation of a head word in a phrase may be determined only provisionally, and a score of a subtree is not estimated until parsing is finished. The new method proposed in this paper preserves every subtree effectively which has the prospect of finally constructing the tree with the best score, and can realize an effective parsing based on DP.