<commit_before># Kollos: sequence rule rewrite

This document describes how the LUIF rewrites
sequence rules.
In the following rule,
`Rep`, `Rep1`, `Rep2`, etc. are mortar symbols,
introduced to function
as left hand sides for intermediate rules.

This rewrite may call for rules with a mortar
LHS and the same
RHS and punctuation to be added
multiple times.
The rules added should be kept in table,
and, when a rule with a RHS and punctuation
identical to one already in the table would be
added,
the rule in the table should be reused instead.

## Eliminate terminators

If any rule has a terminator,
rewrite it as two rules with separation,
one terminated, and one not.
For example, rewrite
```
    A ** 42..1041 %% punct
```
as `Rep`, and add these two rules:
```
    Rep ::= A ** 42..1041 % punct
    Rep ::= (A ** 42..1041 % punct) punct
```

In the second rule of the example,
unnecessary parentheses have been added.
In what follows,
we will often over-parenthesize for clarity.

In the rest of this document, most examples
will be punctuated with separation.
From these, it should be easy to
deduce how the rewrite is done
in the unpunctuated case.

## Eliminate '?' quantifier

Rewrite `A?` or `A**0..1` as two rules
```
   Rep ::= -- empty rule
   Rep ::= A -- singleton rule
```

Ignore any separator.

## Eliminate explicitly-based open ranges

An explicitly based open range is a repetition
of the form `A ** N..* % punct`.

+ Rewrite `A ** 0..* % punct` as `A* % punct`.

+ Rewrite `A ** 1..* % punct` as `A+ % punct`.

* Where N is 2 or more,
  rewrite `A ** N..* % punct` as
  as
```
    Rep ::= Rep1 punct Rep2
    Rep1 ::= (A ** 1 .. N-1 % punct)
    Rep2 ::= A+
```

## Closed ranges with a minimum of zero

All ranges are now closed -- they have an explicit maximum.
Rewrite `A**0..0` or `A**0` as
```
   Rep ::= -- empty rule
```
For `A**0..M % punct`, where M is 1 or more.
introduce these new rules.
```
   Rep ::=  -- empty rule
   Rep ::= A ** 1 .. (M-1) % punct
```

## Closed ranges with a minimum of two or more

Rewrite them so all ranges are either

+ blocks, that is, the minimum and maximum the same; or
+ 1-based.

For `A**N..M % punct`, where N is 2 or more,
introduce these new rules.
```
   Rep ::= Rep1 punct Rep2
   Rep1 ::= A ** N-1 % punct
   Rep2 ::= A ** 1 .. (M-N+1) % punct
```

## Some definitions

In what follows, we'll need some definitions:

+ The *span* of the closed range `A ** N..M` is `(M-N)+1`.

* A block is a closed range with a span of one, for example,
`A**42`.

* A *trivial range* is a range with a span of zero or one.

* `pow2(X)` is the largest power of two
strictly less than `X`.
That is
```
    pow2(5) == 4
    pow2(7) == 4
    pow2(8) == 4
    pow2(9) == 8
```

## One-based non-block ranges

At this point,
all ranges are either one-based or blocks.

We will first consider separators.
For a range of the form<commit_msg>Rewrite RHS repetitions doc<commit_after># Kollos: sequence rule rewrite

This document describes how the LUIF rewrites
sequence rules.
In the following rule,
`Rep`, `Rep1`, `Rep2`, etc. are mortar symbols,
introduced to function
as left hand sides for intermediate rules.

This rewrite may call for rules with a mortar
LHS and the same
RHS and punctuation to be added
multiple times.
The rules added should be kept in table,
and, when a rule with a RHS and punctuation
identical to one already in the table would be
added,
the rule in the table should be reused instead.

## Eliminate terminators

If any rule has a terminator,
rewrite it as two rules with separation,
one terminated, and one not.
For example, rewrite
```
    A ** 42..1041 %% punct
```
as `Rep`, and add these two rules:
```
    Rep ::= A ** 42..1041 % punct
    Rep ::= (A ** 42..1041 % punct) punct
```

In the second rule of the example,
unnecessary parentheses have been added.
In what follows,
we will often over-parenthesize for clarity.

In the rest of this document, most examples
will be punctuated with separation.
From these, it should be easy to
deduce how the rewrite is done
in the unpunctuated case.

## Eliminate '?' quantifier

Rewrite `A?` or `A**0..1` as two rules
```
   Rep ::= -- empty rule
   Rep ::= A -- singleton rule
```

Ignore any separator.

## Eliminate explicitly-based open ranges

An explicitly based open range is a repetition
of the form `A ** N..* % punct`.

+ Rewrite `A ** 0..* % punct` as `A* % punct`.

+ Rewrite `A ** 1..* % punct` as `A+ % punct`.

* Where N is 2 or more,
  rewrite `A ** N..* % punct` as
  as
```
    Rep ::= Rep1 punct Rep2
    Rep1 ::= (A ** 1 .. N-1 % punct)
    Rep2 ::= A+
```

## Closed ranges with a minimum of zero

All ranges are now closed -- they have an explicit maximum.
Rewrite `A**0..0` or `A**0` as
```
   Rep ::= -- empty rule
```
For `A**0..M % punct`, where M is 1 or more.
introduce these new rules.
```
   Rep ::=  -- empty rule
   Rep ::= A ** 1 .. (M-1) % punct
```

## Some definitions

In what follows, we'll need some definitions:

+ The *span* of the closed range `A ** N..M` is `(M-N)+1`.

* A block is a closed range with a span of one, for example,
`A**42`.

* A *trivial range* is a range with a span of zero or one.

* `pow2(X)` is the largest power of two
strictly less than `X`.
That is
```
    pow2(5) == 4
    pow2(7) == 4
    pow2(8) == 4
    pow2(9) == 8
```

## Closed ranges with a minimum of two or more

Rewrite them so all ranges are either

+ blocks, that is, the minimum and maximum the same; or
+ 1-based.

For `A**N..M % punct`, where N is 2 or more,
introduce these new rules.
```
   Rep ::= Rep1 punct Rep2
   Rep1 ::= A ** N-1 % punct
   Rep2 ::= A ** 1 .. (M-N+1) % punct
```

## One-based non-block ranges

At this point,
all ranges are either one-based or blocks.

We will first consider separators.
For a range of the form
{'fraction_non_alphanumeric': 0.12452569851672991, 'fraction_numerical': 0.02173163159710245, 'mean_word_length': 3.0895627644569816, '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': '4581089', 'n_tokens_mistral': 2036, 'n_tokens_neox': 1894, 'n_words': 900}