In this chapter we have presented a uniform tabular algorithm for parsing and generation of constraint-based grammars and a method for sharing items between both processing directions.
The uniform tabular algorithm is based on Pereira and Warren's Earley deduction method. However, for obtaining an efficient and task-oriented behaviour of the uniform algorithm we use a data-driven selection function and a uniform indexing mechanism for efficient retrieval of partial results.
Both the selection function and the indexing mechanism are parameterized with respect to the input in question (a string for parsing and a semantics expression for generation). Since the only relevant parameter our 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 itself dynamically to the data, achieving a maximal degree of uniformity for parsing and generation under a task-oriented view.
Besides the facts that the new uniform tabular algorithm is data- and goal-directed and maintains partial results in a practical way, the uniformity of the indexing mechanism also makes possible that parsing and generation are able to share their results. We have - for the first time - presented such a technique, which we call item sharing. This method is in particular useful and important if parsing and generation have to be interleaved in solving specific problems like paraphrasing or revision. The item sharing approach developed in this thesis shows for the first time how a tight integration of parsing and generation can be done efficiently and effectively. In the next chapter we are going to explain in detail how the uniform tabular algorithm in combination with the item sharing approach is used to realize such a behaviour.