Abstract
We explore the concept of designing parsers for the specific problem at hand. We consider two different classes of problems. First, we consider designing parsers which perform well on a given evaluation metric. While many different metrics exist for evaluating parsing results, including Viterbi, Crossing Brackets Rate, Zero Crossing Brackets Rate, and several others, most existing algorithms attempt to optimize the same metric, namely the probability of getting the correct labelled tree. By choosing a parsing algorithm appropriate for the evaluation metric, better performance can be achieved. We present algorithms which maximize several different criteria, yielding theoretically and empirically better results on those criteria. One of the new algorithms allows precision and recall to be traded off, without changing the grammar.We also explore parsers tailored to parsing certain classes of grammars quickly. We present two new parsers, including one which works well for grammars with many rules for the number of non-terminals. It parses in time roughly O(n^3V^2), where V is the number of terminals and non-terminals in the grammar. The other new parser is designed for lexicalized grammars, and parses in time O(n^4), compared to time O(n^5) or O(n^6) for traditional algorithms.