How do I (do I need to) see alternatives (choice points) in parse trees?

[rns]

What happened was—I ran into too many parses situation [1], tried to sort/reject parses by setting ranks in the grammar, failed and ended up fixing the grammar (by going from sequences to recursion) so that the number of parses reduced greatly and the first parse produced by Marpa was just right—but I thought I need to share my probably naive experience so here goes.

When setting ranks for my rules I felt the need for the method like show_choice_points [2] to be able to see which rules form alternatives and set their ranks accordingly. YAGNI might well apply, but still.

I understand that the rule ranks do not add up when a parse tree is being evaluated—the rank of a parse tree node (alternative) at a choice point equals the rank of its rule, rather than the sum of the children nodes' ranks—am I right? I understand that descending order of parse tree evaluation speaks against such an addition but just in case.

Another general (and rather naive, methinks—my background in grammars and parsing is sparse so excuse is in order) question: if parse trees can contain alternatives then what is the difference among multiple parse trees? I mean how alternatives (choice points) are distributed among multiple parse trees?

Thanks in advance.

[1] I parsed sequences of nouns (N) modified by adjectives (A) modified by adverbs (adv), e.g. "adv, adv and adv A, adv, and adv A N, A, A N, and A N".

[2]

When ranking, the logic descends the parse trees top-down and left-to-right. Places where there is more than one alternative are called choice points. 

— https://github.com/jeffreykegler/Marpa--R2/blob/master/r2/pod/Semantics/Order.pod

[Jeffrey Kegler]

The documentation quoted in your [2] is somewhere between unclear and wrong.  In ranking, Marpa descends the parse BOCAGE looking for choice points, constructing a parse tree as it does so.  Parse TREES do not contain alternatives -- the set of parse trees is in one-to-one correspondence with the set of all possible sets of choices.  In other words, in a parse tree, all the choices have been made.

I understand that the rule ranks do not add up when a parse tree is being evaluated—the rank of a parse tree node (alternative) at a choice point equals the rank of its rule, rather than the sum of the children nodes' ranks—am I right?

Yes, ranks are not recursively evaluated.  Doing so quickly gets into an exponential explosion.  I learned this the hard way.

As for a show_choice_points(), it's not a YAGNI.  It could be quite useful.  Implementation is the obstacle.

Obstacle 1: Another useful Marpa extension would be the ability to mark already-recognized rules (and already-scanned tokens?) as rejected.  I would want the ability to show choice points to be consistent with the ability to reject rules/tokens.  But that means some alternatives at choice points would lead to rejected parses.  (Currently, Marpa can rely on each alternative representing a real parse.)

Obstacle 2:  If a show_choice_points is to be useful, the choice points would have to be translated from their internal representation into external rules.  This is complicated.

These are not insuperable obstacles, but some very careful thinking would have to go into a mechanism for listing choice points.  Note that for specific cases something along the lines of show_choice_points() could be faked using the progress report mechanisms.

Hope this helps,

jeffrey

[rns]

Thanks for explaining, it helps a lot.