26.3 Listing Earley sets

The parse diagnostics should include a facility for displaying Earley sets by Earley set location. For each Earley item at a location, the facility should display

• the rule;
• the rule’s dot position;
• the origin of the Earley item.

The “progress reports” methods of Libmarpa are available for this purpose. See Progress reports.

It is up to the application how to display rule and dot position, but the most helpful way is usually to display the LHS and RHS, with a bullet or dot at the appropriate position in the RHS. This is what is done when showing dotted rules in this document, as for example in

    [ Y ::= C • X ].

The current location of each Earley item may be displayed with the Earley item but, since it is shared by the entire set of Earley items, it can also be put in a header, or left implicit.

We recall (see Earlemes and Earley set IDs) that the Earley IDs range from 0 to latest, inclusive, where latest is the latest Earley set. See The latest Earley set].

The obvious way to display the Earley items is one at a time. We call this the “raw” method of displaying an Earley set. But we can also try to compact this listing by grouping together Earley items that share a dotted rule (and which therefore differ only in their origins). We call this the “compact” method of displaying an Earley set. Marpa::R2 uses the compact method.

To use the compact method, we must be able to show an arbitrarily large number of origins compactly. The following is an example line from Marpa::R2’s progress reports:

    F11 x12 @0...38-41 L1c1-L2c40 <plain assignment> -> ’x’ ’=’ expression •

In this example line, the following are true:

• The “F11” indicates indicates that the display line is for rule 11, which is a completion. The “F” indicates that the dot is in the “final” position.
• “x12” indicates that the example line represents 12 distinct Earley items.
• “@0...38-41” states that the Earley items represented have origins ranging from 0 to 38, and that the current location for the Earley items represented in the example line is 41.
• “L1c1-L2c40” describes the line and column locations in the input — the Earley items represented in the example line run from line 1, column 1 to line 2, column 40. Line and column tracking is implemented at the Marpa::R2 level.
• “<plain assignment> -> ’x’ ’=’ expression •” indicates the dotted rule.

For more details on Marpa::R2’s implementation of progress reports, see https://metacpan.org/dist/Marpa-R2/view/pod/Progress.pod.

The disadvantage of the compact representation of Earley sets is that it is more complicated to read. The disadvantage of the raw representation is that, for ambiguous grammars, the number of Earley items can be very large, and therefore the listing of the Earley set can be unmanageably long.