Source of the Problems

next up previous
Next: The New Algorithm Up: Problems with Existing Previous: Problems with Bottom-up

Source of the Problems

We can think of a parsing or generation process as discovering an analysis tree,png one admitted by the grammar and satisfying certain syntactic or semantic conditions, by traversing a virtual tree and constructing the actual tree during the traversal. The conditions to be satisfied-possessing a given yield in the parsing case, or having a root node labeled with given semantic information in the case of generation-reflect the different premises of the two types of problem.

>From this point of view, a naïve top-down parser or generator performs a depth-first, left-to-right traversal of the tree. Completion steps in Earley's algorithm, whether used for parsing or generation, correspond to a post-order traversal (with prediction acting as a pre-order filter). The left-to-right traversal order of both of these methods is geared towards the given information in a parsing problem, the string, rather than that of a generation problem, the goal logical form. It is exactly this mismatch between structure of the traversal and structure of the problem premise that accounts for the profligacy of these approaches when used for generation.

Thus for generation, we want a traversal order geared to the premise of the generation problem, that is, to the semantic structure of the sentence. The new algorithm is designed to reflect such a traversal strategy respecting the semantic structure of the string being generated, rather than the string itself.

Gertjan van Noord
Thu Nov 24 18:39:44 MET 1994