gll icon indicating copy to clipboard operation
gll copied to clipboard

Enhance `Handle` with disambiguating lenses.

Open eddyb opened this issue 7 years ago • 0 comments

Right now, Handle<X> only knows the range X matched at, which always presents the same view of X's substructure (i.e. the same ambiguities are always observed when visiting its descendants).

However, @eternaleye suggested adding lenses to Handle, with each lense (or "filter") consisting of a path through the SPPF (which could encode finite substructure compactly, or even be strongly typed), to the source of an ambiguity, paired with the choice made for that ambiguity. (could it be possible to use only a ParseNode, i.e. node type and range, instead of a path, and therefore only need lenses: Map<ParseNode, Choice /*aka usize*/>?)

Disambiguation can thus be deferred, by propagating lenses to parents (which might be able to make a decision based on all the information they have available).

An extreme of this is doing disambiguation not by mutating the SPPF, but by computing the lenses that, combined, disambiguate from the root of the SPPF, deeply. A pure/immutable implementation of GLL might take this approach, and it could have positive implications for

Note: Handle is Copy right now, and reconciling that with lenses needs to be figured out still. (one possibility could be adding another type parameter to Handle) EDIT: @eternaleye is suggesting using a reference to the map instead, which would keep Handle always Copy, and the disambiguator machinery could own the lenses, while only giving out references (more specifically, Option<&Map<ParseNode, Choice>>) in Handles, to the user-defined validation/preference logic.

eddyb avatar Sep 12 '18 18:09 eddyb