The code to do it is in Marpa::R2::Internal::MetaAST_Nodes::priority_rule::
evaluate()
<https://metacpan.org/source/JKEGL/Marpa-R2-3.000000/lib/Marpa/R2/MetaAST.pm#L568>
.
On Wed, Aug 31, 2016 at 8:15 PM, <iobas...@gmail.com> wrote:
> Interesting. Can you suggest any references on how to implement this
> grammar rewriting?
>
> Thanks!
>
> - Ryan
>
> On Wednesday, August 31, 2016 at 8:55:21 PM UTC-6, Jeffrey Kegler wrote:
>>
>> I've remembered a major reason for preferring the rewrite approach. If
>> you parse then rank, you're using ambiguous parsing -- Marpa is cool with
>> that, but it is not necessarily as fast as an unambiguous parse. If the
>> expression is of size X the parse could be as bad as O(X^3) and that can
>> make a difference if you have a lot of long expressions.
>>
>> If the grammar enforces precedence, ambiguous parsing can be avoided.
>>
>> On Wed, Aug 31, 2016 at 4:43 PM, <ioba...@gmail.com> wrote:
>>
>>> I'm working on Ruby bindings for libmarpa. They're coming along quite
>>> well. Right now I'm trying to implement prioritized alternatives ('||' in
>>> SLIF). I think I'm close, but the following example has me scratching my
>>> head. Please be patient as I try to give just enough background. (It's
>>> really not that much if you skip the code and dumps.)
>>>
>>> First of all, to implement priorities in the Ruby wrapper, I'm using the
>>> rule ranking. I'm not modifying the symbol rankings at all. Here is the
>>> Perl version. (I know there are plenty of examples on how to do the
>>> calculator grammar "right." It's the most straightforward example I could
>>> come up with.)
>>>
>>> my $grammar_str = "
>>> :default ::= action => [name,values]
>>> :start ::= expr
>>> expr ::= number ||
>>> expr '*' expr ||
>>> expr '+' expr
>>> number ~ [\\d]+
>>> ";
>>> my $input = '3+4*5+6*7*8';
>>>
>>> my $grammar = Marpa::R2::Scanless::G->new({ source => \$grammar_str
>>> });
>>> my $recce = Marpa::R2::Scanless::R->new({ grammar => $grammar});
>>>
>>> # check for complete parsing
>>> my $len_read = $recce->read( \$input );
>>> die "Incomplete read" if $len_read != length $input;
>>>
>>> # check for ambiguous parse result
>>> if ( my $ambiguous_status = $recce->ambiguous() ) {
>>> chomp $ambiguous_status;
>>> die "Parse is ambiguous\n", $ambiguous_status;
>>> }
>>>
>>> I get a single parse result with the '+' before the 6 at the top of the
>>> expression tree.
>>>
>>> In my Ruby bindings, I'm assigning the ranks so that the "number" rule
>>> has the highest rank, the multiply rule has the middle rank, and the
>>> addition rule has the lowest rank. Here is the output of the 'show_rules'
>>> method for my grammar. (The default rank is 0. If the rank is equal to
>>> zero, it is not printed.)
>>>
>>> R0: S2 ::= S3
>>> number ::= number.rule
>>> R1: S1 ::= S2 rank 2
>>> expr.rule ::= NUMBER
>>> R2: S4 ::= S0 S5 S0
>>> EXPR /\*/ EXPR ::= EXPR /\*/ EXPR
>>> R3: S1 ::= S4 rank 1
>>> expr.rule ::= EXPR /\*/ EXPR
>>> R4: S6 ::= S0 S7 S0
>>> EXPR /\+/ EXPR ::= EXPR /\+/ EXPR
>>> R5: S1 ::= S6
>>> expr.rule ::= EXPR /\+/ EXPR
>>> R6: S0 ::= S1
>>> expr ::= expr.rule
>>>
>>> The DSL gets in the way a little on the LHS of the productions (no, this
>>> is not a CSG). Remember, it's a work in progress. :-) The point is that
>>> I'm generating the rules with the ranks I expect because the output above
>>> reads the rule rank back from libmarpa.
>>>
>>> The parsing result I get has five results, with the '*' operators at the
>>> top of the tree. In prefix notation, the results are as follows.
>>>
>>> "(* (* (* (+ 3 4) (+ 5 6)) 7) 8)"
>>> "(* (* (+ 3 4) (* (+ 5 6) 7)) 8)"
>>> "(* (* (+ 3 4) (+ 5 6)) (* 7 8))"
>>> "(* (+ 3 4) (* (* (+ 5 6) 7) 8))"
>>> "(* (+ 3 4) (* (+ 5 6) (* 7 8)))"
>>>
>>> This looks like an equivalent of the 'dangling-else' ambiguity.
>>>
>>> I have two questions.
>>>
>>> 1. Why is my priority backwards? Marpa::R2 gave me the '+' rule at the
>>> outer-most level, while my Ruby wrapper gave the '*' rule at the outer-most
>>> level every time. In other words, help me understand what 'rank' means in
>>> the Marpa context, and how it is applied.
>>>
>>> 2. Why does Marpa::R2 give an unambiguous result? Even with the '+'
>>> rule on the outside, there are two choices for associativity.
>>>
>>> Thanks!
>>>
>>> - Ryan
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "marpa parser" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to marpa-parser...@googlegroups.com.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "marpa parser" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to marpa-parser+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"marpa parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to marpa-parser+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
