next up previous contents
Next: An Object-Oriented Architecture Up: Item Sharing Between Parsing Previous: The Basic Idea

Adaptation of the Uniform Tabular Algorithm

In order to adapt the uniform algorithm for the item sharing method we change the structure of an item such that it contains different slots IN and FROM for parsing and generation. Thus, we have

displaymath12257

where L denotes the lemma of an item, i the (position of the) selected element. During parsing the slots in and from are used and during generation the slots in and from.

If we are in one of the two possible directions, say parsing, then for active items only the corresponding IN and FROM slots are filled with values of the essential feature. The other slots are unbounded which will be denoted by using the symbol NONE. We will use the notation PHON(I) to denote the value of the essential argument used during parsing and SEM(I) to denote the value of the essential argument used during generation. Then the general structure of active and passive items is as follows. In the case of parsing, active items are of form

displaymath12258

and for passive items we have

displaymath12259

where al is an active lemma with selected element at position i in the body of al, phon(i) is the index of the item al is a member, and phon(k) is the backward pointer. pl is a passive item with no selected element, and m the pointer to the head of the passive lemma. Note that in the case of passive items, the value of the essential arguments for both parsing and generation are determined on the basis of the constraints of the passive lemma's head. This is consistent with respect to the definition of item sets.

Analogously, for generation active items are of the form

displaymath12260

and for passive items we have

displaymath12259

Now the inference rules can easily be adapted to handle such item structure. Firstly, the uniform algorithm only considers one IN-FROM pair, depending on the major mode, for example parsing. If a new re-solved lemma (determined through prediction or completion) is active, only the IN-FROM pair of the major mode is filled with the value of the essential argument. The value of the generation slots are by default NONE. However, if a passive lemma is re-solved the slots used by generation receive values determined on the basis of the essential feature specified for this direction (i.e., the value of the SEM path). However, this is actually only done, if the essential argument is indeed instantiated, otherwise the default value NONE is used. This guarantees that for passive items, where only the essential feature of one direction (for parsing this is the string feature) is instantiated are not shared, which is necessary, if empty rules are involved. As a consequence, we forbid that empty elements (like gaps) are not shared unless they are filled with some value.


next up previous contents
Next: An Object-Oriented Architecture Up: Item Sharing Between Parsing Previous: The Basic Idea

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