Next: The codepoint-per-earleme model, Previous: The dense variable-length token model, Up: Advanced input models [Contents][Index]
In the
sparse variable-length model of input,
zero or more successful
calls of
marpa_r_alternative()
must be immediately previous
to every call to
marpa_r_earleme_complete().
The sparse model is the dense variable-length model,
with its only restriction lifted —
the sparse variable-length input model
allows calls to
marpa_r_earleme_complete()
that are not immediately preceded by successful calls to
marpa_r_alternative().
Since it is unrestricted, the sparse input model is Libmarpa’s fully general input model. Because of this, it may be useful for us to state the effect of mutators on the earleme variables in detail, even at the expense of some repetition.
In the sparse input model,
empty earlemes
are now possible.
An empty earleme is an earleme
with no tokens and no Earley set.
An empty earleme occurs iff
marpa_r_earleme_complete()
is called when there is no immediately previous
successful call to
marpa_r_alternative().
The sparse model takes its name
from the fact that there may be earlemes with no
Earley set.
In the sparse model, Earley sets are “sparsely”
distributed among the earlemes.
The latest earleme is the most recent non-empty earleme. In other words, the latest earleme is the most recent earleme with an Earley set at it. In the dense input models, the current earleme and the latest earleme were always the same. Because the sparse input models allow empty earlemes, it becomes possible for the latest earleme and the current earleme to differ. The latest earleme must always be the earleme of an Earley set. The current earleme is not necessarily the earleme of an Earley set.
In the sparse model of input,
the effect on the earleme variables of
a successful call of the
marpa_r_alternative() mutator
is the same as for the dense model of input:
max(old_f, old_c+length),
old_f is the furthest earleme
before the call to marpa_r_alternative(),
old_c is the value of the current earleme
before the call to marpa_r_alternative(), and
length is the length of the token read.
marpa_r_alternative() never changes the
latest or current earleme.
In the sparse model,
when the earleme is not empty,
the effect of
a call to
marpa_r_earleme_complete()
on the earleme variables is the same as
in the dense and the basic models of input.
Specifically, the following will be true:
old_c+1,
where old_c is the current earleme before the call.
old_c+1, and therefore
will be equal to the current earleme.
marpa_r_earleme_complete().
For the sparse input model,
in the case of an empty earleme,
the effect of the
marpa_r_earleme_complete()
mutator on the earleme variables
is the following:
old_c+1,
where old_c is the current earleme before the call.
old_l,
where the latest earleme before the call is old_l.
This implies that the latest earleme will be less than
the current earleme.
marpa_r_earleme_complete().
Next: The codepoint-per-earleme model, Previous: The dense variable-length token model, Up: Advanced input models [Contents][Index]