We're using “prefix” to mean the predecessor of an Earley item in several places. Let's clean that up?

Since we're doing bit-packing, let's make sure we have well-documented preconditions and that we test the edge cases.

If uniqueness wasn't guaranteed by other features of the algorithm, it's hard to imagine that the Leo optimization would actually work for all grammars and inputs. Something seems a little bit fishy about this test, but I need to better understand the optimization before I can say.

I've given the recognizer code a couple of readings, and two comments:

I take it the PartialParses object is more or less what's called an "Earley table" in the literature. Analogous with what I suggested for PartialParse, I'd suggest the name be changed to make it easier for a reader to see the connection to the Earley literature.

"Earleme" seems to be used as a synonym for "Earley set". In my usage it refers to locations, and differs from "Earley set ID" or "Earley set ordinal" only when variable length tokens are in use, and there are locations without Earley sets. If you are not currently implementing that feature, I would not use the term "earleme" at all, to avoid confusion with the concept in my writings.

I can see how the confusion might arise, because you'll see me use phrases like "look for a prediction at an earleme" all the time in the Marpa literature, where the meaning is very close to "look for a prediction in an Earley set". And perhaps I used the term loosely at points. But, analogous to "Earley item" and "Earley table", best to track the terms in the literature, when all else is equal.

I just found a JavaScript implementation, https://github.com/aredridel/lotsawa, which may be of some interest.

/cc @jeffreykegler

We could store them along with Earley items (PartialParses) in a single array in various ways:

1. Add storage for a symbol (perhaps the postdot symbol) to Earley items to make them the same size as Leo items. Burn a bit to indicate Leo or Earley.
2. Store the transition symbol of a Leo item separately from its PartialParse

It would be useful to be able to validate that a grammar is LR-regular and thus can be parsed in linear time. It would be useful to diagnose the causes of non-LR-regularity.

First of all Chart.Item should be renamed Chart.ItemID, since multiple entries with the same ID
actually constitute an item.

Then, perhaps Entry should be renamed Cause or Causation or Derivation.

Then Item should be a first-class type wrapping a Chart.Entries.SubSequence, and having a sequence of Derivations or at least MainstemIndices.

Then there should be a first-class representation for the sequence of Items in an Earleme having a given
transition symbol.

All of this is currently ad-hoc in the type system.

It really wants first-class access to chart items.

It's an optimization, but MARPA's implementation does this, and simply reconstructs them during tree traversal.

Hello,

I am interested in using Lotsawa for parsing a custom metalanguage.

May I ask what license this project has? I know the val-compiler is Apache-2.0, but I didn't know if a similar license applies for Lotsawa. I am following the advice in this post.

Auxilliary hashtables probably only become efficient when there are many partial parses active in each Earleme, but may be necessary to guarantee a strict O(N) upper bound on parsing.

Also possible: sort the elements of an Earleme so we can use binary search. Likely also only a win when there are many partial parses in each Earleme. Slightly complicated by the fact that the current earleme can't be sorted (though #6 would make that a non-issue).

Small linear searches are extremely hard to beat—this suggests that the break-even point for int-sized data is around 60 elements, and this suggests 22 elements for int triples.

Probably Aycock&Horspool optimization into a pushdown automaton would reduce the number of partial parses in each Earleme, so in the end this may never become a real win for any practical grammar.

Need to measure, obviously