Expression[Mul] ::= Number | Expression[Mul] '*' Expression[Mul] Expression[Add] ::= Expression[Mul] | Expression[Add] '+' Expression[Add] Expression ::= Expression[Add]
I think I was looking for the prioritized_symbol section, thank you On Wednesday, 31 August 2016, Jeffrey Kegler < [email protected]> wrote: > 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] > <javascript:_e(%7B%7D,'cvml','[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/j >> effreykegler/kollos/blob/master/notes/design/precedenced.md >> >> On Wed, Aug 31, 2016 at 8:24 PM, Anton Dyudin <[email protected] >> <javascript:_e(%7B%7D,'cvml','[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] >>> <javascript:_e(%7B%7D,'cvml','[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] >>> <javascript:_e(%7B%7D,'cvml','marpa-parser%[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] > <javascript:_e(%7B%7D,'cvml','marpa-parser%[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.
