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] <javascript:>> 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] <javascript:>. >> 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.
