next up previous contents
Next: Linguistic and Formal Foundations Up: Problems with Existing Approaches Previous: Gerdemann's Earley Style Processing

Summary

We can summarize the discussion of current approaches in grammar uniformity as follows: Based on the pioneering work of [Pereira and Warren1983] who demonstrate that parsing can be modelled as deduction introducing an Earley deduction method, [Shieber1988] generalizes their work to be applicable also for generation. However, Shieber's approach depends too strongly on a parsing view, so that in his approach the generation mode is less efficient than the parsing mode. To overcome this problem, [Shieber et al. 1989] introduce a new generation algorithm, which exhibits goal-directed generation behaviour by introducing a semantic-head first selection strategy, instead of the left-to-right one used by [Shieber1988]. However, applying this approach also for parsing, it seemed to be the case that parsing now, loses efficiency. Furthermore, the algorithm of [Shieber et al. 1989] has to face problems of nondeterminism and nontermination in the case of the top-down processing of non-chain rules, basically because they use the simple backtracking mechanism known from Prolog. To overcome these problems, Gerdemann adapts the idea of using a head-driven strategy in the case of generation but ``backtracks'' to Shieber's Earley style approach. He then shows that he obtains the same goal-directedness as Shieber et al., but without the problems of unnecessary re-computation and by avoiding recursion loops. However, the generator he developed on top of Earley's approach fundamentally altered this algorithm (which Gerdemann uses for parsing) and hence loses a certain degree of uniformity.

   figure550
Figure 2.2: A summary of the approaches discussed in relationship to the new approach. The arrows indicate the relationship of most direct influence.

The uniform approach that we are going to describe in this thesis is more strictly based on Pereira and Warren's approach. It is the first real generalization of their work with respect to parsing and generation, because our algorithm is able to adopt itself for the specific tasks at hand. Thus we can take advantage of a left-to-right selection strategy for parsing and a semantic head-driven selection strategy for generation using the same algorithm. Furthermore, because we use uniform indexing techniques we can define prediction and completion in a truly uniform way, thus avoiding the use of global structures like the one defined in Gerdemann's approach. Hence, our approach seems to be the most general view on parsing and generation which combines the advantages of most of the current approaches in one place. Furthermore, because we can choose any selection function, we easily can take advantage of a strict data-driven view. Thus, we can put in perspective our new approach using the figure 2.2.

Finally it is important to note that in none of the current uniform approaches neither interleaving of parsing and generation nor the possibility of sharing items between parsing and generation as the basis of a performance-oriented model has been discussed. Since we demonstrate that such a method is necessary in order to interleave parsing and generation in a practical way our approach has superior power than all of the todays uniform approaches.


next up previous contents
Next: Linguistic and Formal Foundations Up: Problems with Existing Approaches Previous: Gerdemann's Earley Style Processing

Guenter Neumann
Mon Oct 5 14:01:36 MET DST 1998