<commit_before># When in Marpa linear?

This contains some theoretical notes
on the grammars for which Marpa is linear.
These notes are very rough and preliminary,
and not intended to be understand by anyone
but Jeffrey.

## Right recursions

A right recursion is a non-trivial sequence of derivations,
in which the the rightmost symbol of the first step
of the sequence is also the rightmost symbol of the
last step.

A right recursion derivation
step is a single step in a right recursion
which replaces the rightmost symbol,
call it `A`,
with `rhs`
where `A ::= rhs` must be a rule in `g`.
`A ::= rhs` is said to have been "used"
in the right recursive derivation step.
If a rule is used in a right recursive
derivation step,
it is called a right recursive rule.

A right recursion is *marked* if and only if
the only Earley set in an Earley parse where
it adds completions is the set built when
scanning its last symbol.

A right recursion is *Leo-memoable*
at a location,
or *memoable*,
if one of its recursion symbols
ends at that location,
and would produces a completion in the Earley set
at that location.
A right recursion is *fully memoable* if and only if
it is memoable at the location of all of its recursion
symbols.

A right recursion is *Leo-memoized*, or *memoized*,
at a location,
is if is Leo-memoable,
and the right recursion symbol is unique,
in the sense that it occurs as the postdot
symbol of exactly one Earley item.

A "skip" in a Leo-memoization is a location
which is Leo-memoable, but which is not
Leo-memoized.
A "skip sequence" is a set of consecutive
right recursion parse locations
which are all skips.

Theorem:
A right recursion is either marked or fully
memoable.

Proof:

Assume for a reductio that,
in an unmarked right recursion,
there is a right recursion location,
call it `L`,
and `L` is not memoable.
By assumption for the reduction,
`L` is a right recursive location,
so that there is a right recursive symbol,
call it `RR`,
ending at `L`.
The right recursion must occur in the Earley
parse,
and therefore so must all of its right recursive
symbols.
So there must be a completion for `RR` at `L`.
Therefore `L` is memoable, contrary to assumption
for the reductio.
Hence all locations `L` are memoable,
and the right recursion is fully memoable.
QED.

[ Note: the fact that the right recursion is unmarked
is really not used in the above proof.
This should be cleaned up. ]

At a skip, the right recursive completions
are added as far back as the beginning of
the right recursion,
or as the most recent Leo memoization<commit_msg>Linearity writeup<commit_after># When in Marpa linear?

This contains some theoretical notes
on the grammars for which Marpa is linear.
These notes are very rough and preliminary,
and not intended to be understand by anyone
but Jeffrey.

## Right recursions

A right recursion is a non-trivial sequence of derivations,
in which the the rightmost symbol of the first step
of the sequence is also the rightmost symbol of the
last step.

A right recursion derivation
step is a single step in a right recursion
which replaces the rightmost symbol,
call it `A`,
with `rhs`
where `A ::= rhs` must be a rule in `g`.
`A ::= rhs` is said to have been "used"
in the right recursive derivation step.
If a rule is used in a right recursive
derivation step,
it is called a right recursive rule.

A right recursion is *marked* if and only if
the only Earley set in an Earley parse where
it adds completions is the set built when
scanning its last symbol.

A right recursion is *Leo-memoable*
at a location,
or *memoable*,
if one of its recursion symbols
ends at that location,
and produces a completion in the Earley set
at that location.
A right recursion is *fully memoable* if and only if
it is memoable at the location of all of its recursion
symbols.

A right recursion is *Leo-memoized*, or *memoized*,
at a location,
is if is Leo-memoable,
and the right recursion symbol is unique,
in the sense that it occurs as the postdot
symbol of exactly one Earley item.

A "skip" in a Leo-memoization is a location
which is Leo-memoable, but which is not
Leo-memoized.
A "skip sequence" is a set of consecutive
right recursion parse locations
which are all skips.

Theorem:
A right recursion is either marked or fully
memoable.

Proof:

Assume for a reductio that,
in an unmarked right recursion,
there is a right recursion location,
call it `L`,
and that `L` is not memoable.
If
`L` is a right recursive location,
then there is a right recursive symbol,
call it `RR`,
ending at `L`.
The right recursion must occur in the Earley
parse,
and therefore so must all of its right recursive
symbols.
So there must be a completion for `RR` at `L`.
Therefore `L` is memoable, contrary to assumption
for the reductio.
Hence all locations `L` are memoable,
and the right recursion is fully memoable.
QED.

[ Note: the fact that the right recursion is unmarked
is really not used in the above proof.
This should be cleaned up. ]

At a skip, the right recursive completions
are added as far back as the beginning of
the right recursion,
or as the most recent Leo memoization
{'fraction_non_alphanumeric': 0.0466796875, 'fraction_numerical': 0.0, 'mean_word_length': 4.230847803881511, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3352947', 'n_tokens_mistral': 1510, 'n_tokens_neox': 1419, 'n_words': 885}