A novel uniform tabular algorithm

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.