Indexing of rules

It is possible to use a more clever indexing of rules. Firstly, it is possible to extract the rules from the grammar that can be used to parse some given sentence, before the parser starts properly. That is, for each sentence the parser first selects those rules that possibly could be used in the analysis of that sentence. The parsing algorithm proper then only takes these rules into account when it searches for an applicable rule.

Furthermore, we can get rid of the $\mbox{\it consume\_guide}/3$ predicate. Given the pre-compilation step mentioned above, we can use a slightly different representation of bags where the elements of the bag are not explicitly mentioned, but are implicitly represented by the position in the bag. To make this work we also allow bags where elements occur zero times. For example, given the sentence `a b b c a a', the corresponding bag will simply be:

$$\langle 3, 2, 1 \rangle$$
Furthermore, the bag that consists of two a's is given the representation

$$\langle 2,0,0 \rangle$$
with respect to that sentence. The idea is that each rule which has been found to be a possible candidate for a given sentence is asserted either as a clause

$$\mbox{\it predict\_cr}(\mbox{\rm Head},\mbox{\rm M},\mbox{\rm Ds},\mbox{\rm InBag},\mbox{\rm OutBag})$$
or $$\mbox{\it predict\_ncr}(\mbox{\rm M},\mbox{\rm Ds},\mbox{\rm InBag},\mbox{\rm OutBag})$$
where the predicates which made up the body of that predicate are already partially evaluated. For example, given the sentence `a b b c a a' the indexing step of the parser may find that the (non-chain-rules) `a', `b' and `c' are applicable. These entries are then asserted as:

The guide is instantiated as follows. The in-part will simply be the bag representation shown above. More precisely for this example:

$$\langle s(s(s(0))), s(s(0)), s(0) \rangle$$
and the out-part now simply is:

$$\langle 0,0,0\rangle$$
Note that the `predict_ncr' and `head_corner' clauses remain as before.

[81] discusses two-step parsing algorithms for lexicalized grammars. In the first step the parser selects the rules which might be applicable in order to parse the given sentence. In the second step the sentence is actually parsed using these rules. Thus, for a LTAG we first select all the initial and auxiliary trees of which the anchors occur in the sentence. This technique is thus quite easily incorporated, using the technique discussed above.