As a pedagogic point -- if it's not immediately obvious how SLIF
precedenced statements could be implemented by hand, work a least one
simple one yourself. That will make what my algorithm is doing very
obvious.
Start with really simple, with something like:
Expression ::=
Number
|| Expression '*' Expression
|| Expression '+' Expression
and translate it to pure BNF. Trying to understand the algorithm before
you're solid on the basic concept will probably just confuse things.
On Wed, Aug 31, 2016 at 8:46 PM, Jeffrey Kegler <
[email protected]> wrote:
> At this point I have trouble with tracking all my stuff, but here's I
> think the lastest and/or most accurate: https://github.com/
> jeffreykegler/kollos/blob/master/notes/design/precedenced.md
>
> On Wed, Aug 31, 2016 at 8:24 PM, Anton Dyudin <[email protected]>
> wrote:
>
>> Speaking as someone who isn't fluent in Perl, and doesn't see a "||"
>> anywhere on that page, would you be willing to give some broad strokes of
>> what the code is doing? :3
>>
>>
>> On Wednesday, 31 August 2016, Jeffrey Kegler <
>> [email protected]> wrote:
>>
>>> The code to do it is in Marpa::R2::Internal::Met
>>> aAST_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, <[email protected]> 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, <[email protected]> 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 [email protected].
>>>>>> 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 [email protected].
>>>> 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 [email protected].
>>> 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 [email protected].
>> 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 [email protected].
For more options, visit https://groups.google.com/d/optout.
