[Versa] '-'

[Uche Ogbuji]

On Mon, 2005-09-26 at 14:54 -0600, Michael Olson wrote:
> Just an update,  I've implemented enough of "precedence" that I can  
> produce a .y file with precedence support.
> 
> Its not helping.
> 
> Given the current grammar, here is a bit of output from bison (not  
> bgen) where the reduce reduce conflict is happening.
> 
> """
> state 42
> 
>      primary_expression  ->  resource_expression .   (rule 77)
>      arc_start_expression  ->  resource_expression .   (rule 113)
> 
>      DASH	reduce using rule 77 (primary_expression)
>      DASH	[reduce using rule 113 (arc_start_expression)]
>      PIPE_DASH	reduce using rule 113 (arc_start_expression)
>      $default	reduce using rule 77 (primary_expression)
> 
> """
> 
> Which basically says (for those not familiar with bison)
> 
> Given a resource_expression, if the look ahead is a DASH, then either  
> reduce it to primary_expression, or reduce it to arc_start_expression.
> 
> primary_expression being the road to subtraction, and  
> arc_start_expression leads us to a traversal.
> 
> As the grammar currently stands (with single '-')
> 
> all() - rdf:type -> *
> 
> will not parse because "all() - rdf:type" will reduce to a primary  
> expression and then "primary-expression -> expression" is invalid.

This is where precedence comes in, as you obliquely note below.  (I just
want to make that part more clear).


> However, all 15 other forms of traversal/filter will parse (15  
> including the fwd, bwd, and exitensial)
> 
> ideas?
> 
> The solutions I currently see as possible are
> a)  double dash so all() -- rdf:type -> *
> b)  a new symbol for subtraction.  XPath did it with "div" I assume  
> because of the same problems with the "/" path operator.  We could do  
> "sub"
> c)  A symbol to start a traversal, something like # all() - rdf:type ->  
> *
> d) Reorder the bgen file so that the arc-start-expression always  
> reduces first and live with the error.

d) In effect using precedence.

I actually think we want (d) in combination with parens to disambiguate.
See below.


> IMO
> 
> a) +2
> b) +1
> c) -1
> d) -10
> 
> I'm very opposed to "d" because down the road, someone may try to clean  
> up the grammar and all of the sudden everything breaks for no reason.

We make the precedence rule explicit for this case, either using some
BisonGen feature (I'm not up to date on Bgen features), or by a simple
comment to warn people that the grammar is ordered that way for a
reason.

More importantly, we should require parens in some ambiguous cases.  The
essence of the problem is:

$a - $b - $c -> *

If you restrict the primary-expressions that are allowed as operands in
traversal expressions, you can eliminate this ambiguity.  In other
words, mandate parens and make the above illegal.  The user would have
to write:

($a - $b) - $c -> *

or

$a - ($b - $c) -> *

or

$a - ($b - $c -> *)

This would require primary expression to be split up into two
non-terminals, one of which mandates the parens, and adding another
non-terminal which is a traversal expression with parens around it.  It
would be fiddly, but I think it would be well worth it to avoid options
a through c.


-- 
Uche Ogbuji                               Fourthought, Inc.
http://uche.ogbuji.net                    http://fourthought.com
http://copia.ogbuji.net                   http://4Suite.org
Articles: http://uche.ogbuji.net/tech/publications/