4

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?

hippietrail
  • 15,848
  • 18
  • 99
  • 158

2 Answers2

3

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.

rns
  • 771
  • 4
  • 9
1

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. :-)

Jeffrey Kegler
  • 841
  • 1
  • 6
  • 8
  • I'm using ASF but the example there just gave me the way to iterate through each alternative parse of the forest, rather than along the graph. I'm not sure whether I'm missing the feature of ASF I'm looking for or whether I failed to elucidate my problem ... – hippietrail Sep 18 '14 at 02:31
  • Actually it looks like what I need is probably in there but requires some deep reading and getting to know a bunch of concepts and terminology to grok it. – hippietrail Sep 18 '14 at 02:37
  • 1
    To traverse ambiguities, you have to understand there are different kinds. I was surprised to discover this was not much explored in the literature -- traversing parse trees is very standard stuff, in a lot of the texts, but parse forests are new territory. Much of what's in the ASF and Glade docs is newly worked out. – Jeffrey Kegler Sep 18 '14 at 02:49