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 <jeffreykegler@jeffreykegler. > com> 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.
