precedence rules vs. ambiguity

[John Merchant]

Lately I've been working on developing an interpreter using Marpa::R2 v. 8.  For the most part, things are working out very well; however, occasionally I run into situations where with my admittedly incomplete understanding I think something should work but it clearly does not (or vice versa).

For example, consider the following two simple grammars.

:default ::= action => [ values ]
lexeme default = latm => 1

expr ::= number
      || expr '+' expr
      || name '=' expr

name ~ [a-z]+
number ~ [0-9]+
:discard ~ whitespace
whitespace ~ [\s]+

:default ::= action => [ values ]
lexeme default = latm => 1
expr ::= number
      || add_expr
      || name '=' expr
add_expr ::= expr '+' expr
name ~ [a-z]+
number ~ [0-9]+
:discard ~ whitespace
whitespace ~ [\s]+

With an input string like 'a = 5 + 12', parsing with the first grammar produces a single parse tree ([a = [5 + 12]]).  Though the second seems like it should be equivalent, parsing the same input string with the second grammar produces two parse trees ([a = [5 + 12]] and [[a = 5] + 12]).  

Why?  Is the extra rule in the second grammar changing how precedence is applied?  Is this a limitation of R2?  Is there any way to make the second grammar unambiguous without say defining a second version of the expr table?  I apologize that despite reading much of the man documentation, the FAQ, and a decent sampling of this list that I still don't have a really firm handle on how precedence affects ambiguity -- I would definitely appreciate any help or a nudge in the right direction.

Best,

-John M. Merchant

[Jeffrey Kegler]

Thank you for your interest in Marpa, your kind words, your interesting example and your careful write-up of it.

Briefly, precedenced statements work by applying precedence and associativity to instances of the LHS symbol on their RHS.  In the 2nd example, <expr> occurs outside of the precedenced statement and accordingly precedence and associativity are not applied to those instances of <expr>, resulting in ambiguity.

What is going on is that precedenced rules get rewritten into BNF rules which enforce the associativity and precedence declared in the precedenced rule.  BNF rules do not get rewritten.

Basically, the LHS of a precedenced rule should never occur in any rule which is a step of a derivation from the precedenced rule -- while in theory it could have a meaning, in practice it almost always will not do what the grammar writer actually intends.

In R3/Kollos, I will probably have a warning issue on likely problematic uses of the precedenced LHS outside of the precedenced rule. Or I may simply ban them.

Thanks, I hope this was helpful, jeffrey

--
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 marpa-parser...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/marpa-parser/9d3a0520-134b-4492-ac17-536552858656%40googlegroups.com.

[John Merchant]

Thank you for the quick and helpful response!  This definitely explains some of the strangeness I was seeing in my larger project and I think I now have some rule rewriting to get to...

Best,

-John

To view this discussion on the web visit https://groups.google.com/d/msgid/marpa-parser/CA%2B2Wrv9sG3wtFaUS8_k8fiLckUTAuDS3nrwTmddDUG0CU9x%2BbA%40mail.gmail.com.