How to iterate "along" a Marpa parse forest rather than "through" its parse trees?

Question

Say I have a nice ambiguous Marpa grammar and a nice ambiguous input string.

I can parse the string with Marpa and end up with a parse forest. I can even iterate through each parse tree in the forest.

But how can I iterate "along" the parse forest?

To describe what I mean:

A parse forest is a kind of graph which can have nodes where alternatives split off, and nodes where alternatives join back together into a "main stream".

Say these are the alternative parse trees of one parse forest:

• A B1 C
• A B2 C
• A B3 B4 C

There is a main stream A ... C but an ambiguous B section.

Of course in real world parses there can be many levels of branching upon branching and there may be streams that do not rejoin a single main stream. But in general there will be a lot of parts common to two or many interpretations.

What approaches can be used to iterate along the chain of unambiguous and ambiguous nodes?

In fact can I output the entire graph?

Answer 1

This gist shows 2 examples (basic and advanced) of iterating over an ASF nodes to produce a list of serialized ASTs.

Both are based on the code from Marpa::R2 test suite (cpan/t/sl_panda(1).t).

Hope it helps.

P.S. This gist will probably serve you better — it prints all ASF nodes in the order of visiting — you can use

$spans->{ $literal }->{ $start }

hash to see if a node is ambiguous or not and build the graph from there based on span intervals ($start, $start + $length) to build child/parent links.

Answer 2

The interface to do this just went from alpha to stable in Marpa::R2, so the question is well timed. Look at https://metacpan.org/pod/distribution/Marpa-R2/pod/ASF.pod and https://metacpan.org/pod/distribution/Marpa-R2/pod/Glade.pod.

Can you output the entire graph? Yes, but that's the easy thing to provide. The hard part was coming up with a nice way to drilling down to parts of interest, without going exponential.

Btw, another Marpa expert, may chime in here, one who's at this point got more experience working with my interface than I have. Perhaps you'd like to wait a bit for his answer, which you might like better than mine. :-)