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?

rns rns · Accepted Answer · 2014-09-18T03:45:37

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.

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

2 Answers