Head-driven parsing

This paper presents a novel top-down headdriven parsing algorithm for data-driven projective dependency analysis. This algorithm handles global structures, such as clause and coordination, better than shift-reduce or other bottom-up algorithms. Experiments on the English Penn Treebank data and the Chinese CoNLL-06 data show that the proposed algorithm achieves comparable results with other data-driven dependency parsing algorithms.

9p nghetay_1 07-04-2013 32 1   Download

We study the problem of finding the best headdriven parsing strategy for Linear ContextFree Rewriting System productions. A headdriven strategy must begin with a specified righthand-side nonterminal (the head) and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing.

10p hongdo_1 12-04-2013 26 1   Download

On the basis of work in [8] for nondeterministic left-to-right parsing, we trace here a theory of head-driven parsing going from crude top-down and head-corner to more sophisticated solutions, in the attempt to successively make more deterministic the behaviour of head-driven methods. Finally, we propose an original generalization of headdriven parsing, allowing a more detailed specification of the order in which elements of a right-hand side are to be processed.

8p bunmoc_1 20-04-2013 26 1   Download