Marpa::R2 enhancement request: Generic AST traversal

[ronsavage]

Would it be possible to add another method to Marpa::R2::ASF, to traverse the tree such that each node is visited once? That's what I need right now, and I suspect it's what many users would expect to have available.

See https://metacpan.org/pod/Tree#traverse-order for 1 way to describe the 3 orderings usually available.

I can see the docs already say "Methods of the glade object are used to find information about the glade, and to move around in it.", but how to move around it is not clear. And the bit above that - "The traverser may be called at every node of the forest" -, using "may", is the bit which worries me. I really do need to visit /every/ node. And hitting each node once is of course assumed.

[jeffreykegler]

Right now I'm immersed in the theory doc rewrite.

Traversing the whole thing in one sense defeats the purpose of the ASF's, which are to avoid that overhead. That is, if full traversal is what you want, the actions and the value() method do that in tree mode. On the other hand, such a thing would be useful as an example, or as a template for folks to start with.

[ronsavage]

I did try (just to see what would happen):
sub traverser
{
my($glade, $cache) = @_;
my($rule_id) = $glade -> rule_id;
my($symbol_id) = $glade -> symbol_id;
my($symbol_name) = $$cache{self} -> grammar -> symbol_name($symbol_id);

if (! defined $rule_id)
{
    return [$glade -> literal];
}

traverser($_, $cache) for $glade -> rh_values;

return [$glade -> literal];

}

But it dies on this line my($rule_id) = $glade -> rule_id;
with Parse failed. Can't call method "rule_id" on unblessed reference...

That suggests something returned by rh_values() is not a glade.

[jeffreykegler]

Hmmmm. @rns, any clue?

[rns]

This line traverser($_, $cache) for $glade -> rh_values; calls the traverser sub from within the traverser, which is a no-no, as the traverser sub must be called by traverse() method only.

I'll post a gist with a template code shortly.

[rns]

Ok, here is the gist -- https://gist.github.com/rns/078334ca156a6fcf30f3 -- it shows how to enumerate alternative parses and then traverses the asf to produce all possible trees.

[ronsavage]

Hi

On 22/10/15 16:16, rns wrote:

This line |traverser($_, $cache) for $glade -> rh_values;| calls the
traverser sub from within the traverser, which is no-no, as the
traverser sub must be called by |traverse()| method only.

OK. In that case please add a note to the docs warning us not to do that!

I'll post a gist with a template code shortly.

I'll try that. $many x $thanx;

Ron Savage - savage.net.au

[rns]

OK. In that case please add a note to the docs warning us not to do that!

Good point. https://metacpan.org/pod/distribution/Marpa-R2/pod/ASF.pod#How-to-write-a-traverser has no such note now.

[ronsavage]

I tried the gist, adapted for my data, but the results are useless.

BTW: https://metacpan.org/pod/Tree::DAG_Node#walk_down-options has a great feature: The return value is used to decide whether or not the tree walk continues. 0 => Stop, 1 => Continue.

[jeffreykegler]

Are they counting the same thing? There can be more than one traversal per
tree -- in fact there almost always will be.

On Wed, Oct 21, 2015 at 11:38 PM, rns notifications@github.com wrote:

Just thought -- enumerating parse trees using value() yields 2, while
traversing the asf yields 5 that looks a bit wierd and I can't come up with
a good explanation. @jeffreykegler https://github.com/jeffreykegler,
perhaps, when you have time?

—
Reply to this email directly or view it on GitHub
#266 (comment)
.

[rns]

@jeffreykegler -- sorry, that was a false positive, I've found a bug in enumerating code and will update the gist.

[rns]

Gist updated.

[ronsavage]

To elaborate:
(1) Tree::DAG_Node's technique in walk_down() of the caller providing a sub is perfect. The sub is called once per node, with enough parameters that the called sub can analyze the node however they wish. Options passed to walk_down() are passed into each call of the sub.
(2) Yes, I understand this somewhat circumvents the purpose of ASF's code.
(3) A major problem I have with the current code is the complexity within the do loop in the traverser. To me, this complexity is an implementation issue which should be hidden from the end-user. By all means maintain this code, but give users a per-node access mechanism, rather than us having to build lists of lists.

[ronsavage]

I patched my code again to use the loop as per the gist, to enumerate the solutions,
simplified :-) to this:

while (my $value = $self -> recce -> value)
{
$self -> log(debug => 'Solution: ' . $self -> decode_result($$value) );
}

decode_result() you've seen before: https://gist.github.com/ronsavage/f1c3f0a44ad7a09ca84e.

It gives 4 solutions:
Solution: 11 jan 1954
Solution: 11 jan 1954
Solution: 11 jan 1954
Solution: 11 jan 1954

This is correct. But having ripped all the events out to play with ASF, I now have no identification of the contexts of these. Sigh. I'm thinking I'll go back to the event mechanism.

But I'll write up something for the FAQ first.

[rns]

Hi Ron, decode_result(), AFAICS effectively strips all context data from the ast and thus hardly can be used to resolve ambiguity.

Items I don't have to work on right now, but plan to in future, for memory sake:

1. note in the doc that a traverser sub should not call itself
2. template code to build ASTs from ASF
3. code to resolve gregorian/julian date ambiguity

[ronsavage]

Hi

On 25/10/15 23:35, rns wrote:

Hi Ron, |decode_result()|, AFAICS effectively strips all context data
from the ast and thus hardly can be used to resolve ambiguity.

Sure. That /is/ a problem.

Items I don't have to work on right now, but plan to in future, for
memory sake:

note in the doc that a traverser sub should not call itself

template code to build ASTs from ASF

code to resolve gregorian/julian date ambiguity

Done. Yesterday I finished coding this, but I have not updated the docs
and tests to match. I'll let you know.

Ron Savage - savage.net.au