Creating Parse Forests.

The Alpino parser takes the result of lexical analysis as its input, and produces a parse forest: a compact representation of all parse trees. The Alpino parser is a left-corner parser with selective memoization and goal-weaking. It is a variant of the parsers described in [20]. We generalized some of the techniques described there to take into account relational constraints, which are delayed until sufficiently instantiated [22].

As described in [23] and [21], the parser can be instructed to find all occurrences of the start category anywhere in the input. This feature is added to enhance robustness as well. In case the parser cannot find an instance of the start category from the beginning of the sentence to the end, then the parser produces parse trees for large chunks of the input. A best-first search procedure then picks out the best sequence of such chunks. Depending on the application, such chunks might be very useful. In the past, we successfully employed this strategy in a spoken dialogue system [24].