Next: A performance model based
Up: The Goals of the
Previous: The Goals of the
is presented that can be used for
efficient parsing and generation of constraint-based grammars without
the need for compilation. The most important properties of the
algorithm are:
- Earley deduction. The control logic of the new algorithm is
based on Earley deduction, i.e., it realizes a mixed top-down/bottom-up
behaviour. The new algorithm is the first one that is able to apply
this strategy for parsing and generation in a real symmetric and
balanced way and consequently will terminate on a larger class of
reversible grammars.
- Dynamic selection function. The uniform algorithm uses a
dynamic selection function to determine the element to process next
on the basis of the current portion of the input - a string for
parsing and a semantic expression for generation.
This enables us, for example, to obtain a left-to-right
control regime in the case of parsing and a semantic functor driven
regime in the case of generation when processing the same grammar by means
of the same underlying algorithm.
- Uniform indexing technique. The same basic mechanism is
used for parsing and generation, but parameterized with respect to the
information used for indexing partial results. The kind of
index causes completed information to be placed in the different
state sets. Using this
mechanism we can benefit from a table-driven view of generation,
similar to that of parsing. For example, using a
semantics-oriented indexing mechanism during generation massive
redundancies are avoided, because once a phrase is generated, we are
able to use it in any position within a sentence.
- Item sharing.
We present a new method of grammatical processing which we term
item sharing. The basic idea is that items computed in
one direction are automatically made available for the other direction
as well. The item sharing approach is based on the uniform indexing technique
mentioned above and is realized as a straightforward extension
of the uniform tabular algorithm. The relevance of this novel method
is demonstrated when the new performance model is presented.
Since the only relevant parameter our uniform tabular algorithm has
with respect to parsing and generation is the difference in input
structures the basic differences between parsing and generation are
simply the different input structures. This seems to be trivial, however our
approach is the first uniform algorithm that is able to adapt
dynamically to the data, achieving a maximal degree of uniformity
for parsing and generation under a task-oriented view.
Next: A performance model based
Up: The Goals of the
Previous: The Goals of the
Guenter Neumann
Mon Oct 5 14:01:36 MET DST 1998