[Versa] '-'
Michael Olson
Mike.Olson at fourthought.com
Tue Sep 27 11:24:34 MDT 2005
I think I am about ready to remove the operators we just added, or move
them all to string equivs. We now have issues with "<", or we always
did.
<3>
< 3
Cause a conflict as less then followed by a number is either a uriref
or a less then operator.....
Mike
On Sep 27, 2005, at 9:54 AM, Michael Olson wrote:
>
> Just wanted to send out an update on this. I made pretty good
> progress last night. What I accomplished is to break the expressions
> into different expressions based on type. So you have a
> boolean-expression which is the results of all of the boolean
> operators, constants and a few other things.
>
>
> Then, given the different expression types, I can define which are
> allowed as operands for all of our different operators and which are
> allowed as a top level query (ie DOT is not a top level query).
>
> I have three small things left to do, the first is make sure that
> function arguments are getting allowing the correct arguments (should
> be anything), the second is to fix a shift reduce (see below) and the
> third is to verify that I have precedence set up correctly for some of
> the operators.
>
> A couple of notes, variable-reference and function-call default to
> "list-expressions" as list expressions are the most general in the
> grammar.
>
> I currently have the conversion functions in the grammar. As an
> example, the grammar defines 'boolean(' query-expression ')' as a way
> to convert any expression into a boolean. Without this, it would be
> impossible, in our grammar, to have a boolean expression that starts
> with a function call (as these are lists). We can decide (assumiung
> we like this grammar) if we want to keep that. It would not allow
>
> $x + $y
>
> as a query anywhere, you need to do
>
> number($x) + $y
>
>
> The shift reduce has to do with precedence in a chained traversal,
> given
>
> all() - rdf:type -> . < 2 - 1-> *
>
>
> Which is just a silly traversal but shows the point. It can either be
> reduced into
>
> (all() - rdf:type -> . < 2) - 1 -> *
>
> Which is a traversal chain
>
> or, it can be shifted into
>
> all() - rdf:type -> (. < 2 - 1) -> *
>
> Which is invalid.
>
> Mike
>
>
>
>
>
>
>
>
> On Sep 26, 2005, at 7:50 PM, Michael Olson wrote:
>
>>>>
>>>> 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.
>>>
>>
>> Your example points out the biggest problem I have been running into,
>> variables and functions.
>>
>> Its easy to take all other use cases and separate them into
>> expressions by "what starts a traverse" and "what starts a
>> subtraction".
>>
>> You still run into a reduce/reduce conflict with $x - $y.
>>
>> Now, as you mention we can just order the bison correctly and state
>> in docs that "this always reduces to the start of a traversal".
>>
>> This means
>> 1) you cannot just have "$x - $y" as a query which is sad but not a
>> show stopper
>> 2) the precedence is not in the EBNF, but is implementation
>> specific. If someone took the EBNF and put it through a LR(1) parser
>> they would get different results
>> 3) it is very prone to future errors by simple re-ording of the
>> bison file
>> 4) we would be going against what the bison manual itself says,
>> basically fix all reduce reduce conflicts as they are very bad.
>>
>> 2 & 3 are the biggies for me. 4 give me pause and 1, as I said, is
>> said but not major.
>>
>> I have not given up yet and plan on spending the evening trying to
>> resolve this, but as it currently stands, my vote is for a or b (or e
>> see below). Probably b ( 'sub' is the subtraction operator) since
>> subtraction is a new feature in versa we would not be breaking
>> anything.
>>
>> One other solution I have come up with is typing of variables and
>> functions but I hesitate to bring this up in a mostly python
>> community. It would look something like:
>>
>> The default type for a variable/function is list. This would allow
>> us to then type all possible starting expressions for a traversal.
>> So
>>
>> $x - $y is always the start of a traversal as the type of $x is a
>> list and we can say (in short hand)
>>
>> traversal :== list '-' list '-' boolean
>>
>> Then, given a subtraction you would need to do
>>
>> (number)$x - $y
>>
>> I suppose we could go a step farther and say that the conversion
>> functions are a part of the grammar. Then it would look like
>>
>> number($x) - $y
>>
>> Mike
>>
>>
>>>
>>> -- 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/
>>>
>>> _______________________________________________
>>> Versa mailing list
>>> Versa at lists.fourthought.com
>>> http://lists.fourthought.com/mailman/listinfo/versa
>>>
>> ----------------------------------------------------------------------
>> -------------------
>> Mike Olson Principal
>> Consultant
>> mike.olson at fourthought.com +1 720 253 4662
>> Fourthought, Inc.
>> http://Fourthought.com
>> PO Box 270590, http://4Suite.org
>> Louisville, CO 80027-5009, USA
>> XML strategy, XML tools, knowledge management
>>
>> _______________________________________________
>> Versa mailing list
>> Versa at lists.fourthought.com
>> http://lists.fourthought.com/mailman/listinfo/versa
>>
> -----------------------------------------------------------------------
> ------------------
> Mike Olson Principal
> Consultant
> mike.olson at fourthought.com +1 720 253 4662
> Fourthought, Inc.
> http://Fourthought.com
> PO Box 270590, http://4Suite.org
> Louisville, CO 80027-5009, USA
> XML strategy, XML tools, knowledge management
>
> _______________________________________________
> Versa mailing list
> Versa at lists.fourthought.com
> http://lists.fourthought.com/mailman/listinfo/versa
>
------------------------------------------------------------------------
-----------------
Mike Olson Principal
Consultant
mike.olson at fourthought.com +1 720 253 4662
Fourthought, Inc.
http://Fourthought.com
PO Box 270590, http://4Suite.org
Louisville, CO 80027-5009, USA
XML strategy, XML tools, knowledge management
More information about the Versa
mailing list