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,
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