This chapter is organized as follows. In the next section 4.1 we give a short overview of Pereira and Warren's original Earley deduction scheme and introduce some basic notations. In sections 4.2 through section 4.6 we present a first version of the uniform tabular algorithm and give a parsing and generation example in section 4.7.
Although this version already realizes novel ideas (e.g., data-driven selection function, a new top-down semantic-driven generation strategy) it is not as efficient as it could be. Therefore we present in sections 4.8 and 4.9 a uniform but data-driven indexing mechanism that is used for efficient retrieval of re-solved lemmas. In section 4.10 we describe the necessary modifications of the uniform algorithm to be able to make use of the uniform indexing mechanism and give a parsing and generation example in section 4.11.
In the section 4.12 we show how to deal with verb second problems. After the description of important properties of the uniform algorithm in section 4.13 and of the implementation of the algorithm in section 4.14, we present the item sharing approach in section 4.15. We first present informally the basic ideas and then show how the method is integrated within the uniform tabular algorithm, and finally describe important implementational aspects.
Before we go on in actually doing the things just promised we would like to stress, that all methods developed in this thesis have been implemented. In order to abstract away from a concrete implementation using a specific programming language we present the methods in an abstract way (making use of a pseudo programming language). However, this abstract description is made in just a way that the underlying implementation will be transparent. Thus the way we are describing the methods and the way they are implemented converges.