Efficient sharing in ambiguous parsing

Abstract

At the outbreak, interest in non-deterministic parsing was due to the fact that it is the context free backbone of some natural language analyzers. In effect, several of them start with a purely context-free parsing phase which generates all possible parses as some kind of sharing structure usually called shared forest. Later, in a second phase, a more elaborate analyzer that takes into account the finer grammatical structure of the language is applied in order to filter out undesirable parses. That implies the existence of a disambiguation process, from which a single tree is to be chosen in the resulting shared forest. In this paper, we study the structure of these forests with respect to optimality of syntactic sharing, in relation to the parsing schema used to produce them and to the number of computations to be applied during the parse process. Finally, we give the guideline to design efficient context-free parsers in relation to both the performance and the implementation techniques.