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.
