[Versa] EBNF (start)(patterns, expressions and lists)
Uche Ogbuji
uche.ogbuji at fourthought.com
Thu Sep 15 14:18:32 MDT 2005
On Thu, 2005-09-15 at 12:06 -0600, Michael Olson wrote:
> >> [14] forward-traversal ::= (pattern-expression "-" pattern-expression
> >> "->" filter-expression)
> >> | ( '[' '-' pattern-expression "->"
> >> filter-expression ']' )
> >>
> >> [15] forward-filter ::= (pattern-expression "|-" pattern-expression
> >> "->" filter-expression)
> >> | ( '[' "|-" pattern-expression "->"
> >> filter-expression ']' )
> >>
> >> [16] backward-traversal ::= (filter-expression "<-" pattern-expression
> >> "-" pattern-expression)
> >> | ( '[' filter-expression "<-"
> >> pattern-expression "-" ']' )
> >>
> >> [17] backward-filter ::= (filter-expression "<-" pattern-expression
> >> "-|" pattern-expression )
> >> | ( '[' filter-expression "<-"
> >> pattern-expression "-|" ']' )
> >>
> >> [18] pattern-expression ::= pattern-expression slice-operator
> >> | '(' pattern-expression ')'
> >> | pattern
> >> | variable-reference
> >> | '{' query '}'
> >>
> >>
> >> [20] filter-expression ::= '(' filter-expression ')'
> >> | filter-expression slice-operator
> >> | function-call
> >> | pattern
> >> | operator-expression
> >> | variable-reference
> >
> > I think some of the above confusion could be minimized by adding an
> > expr
> > production, such as:
> >
> > [X] expr ::= '(' expr ')'
> > | function-call
> > | pattern
> > | operator-expression
> > | variable-reference
> > | '.'
> >
> > I may be missing some here, but then
> >
>
> I had that for a while, but it resolved down to not being very useful.
It's more a conceptual grouping than anything else. I think it would
make the grammar more readable, and a parser generator would optimize
it, anyway.
> One big problem is if you represent as
>
> [1] query-expression ::= '(' query-expression ')'
> | expr | other things
>
> and
>
> [2] expr ::= '(' expr ')' | some thing
>
> Then the parser will get confused with "(expr)" as it does not know
> whether to reduce via [2] to an expression or shift to [1] and then
> reduce...
Sure, but you can clean up that shift/reduce conflict by eliminating the
first non terminal:
query-expression ::= expr | other things
> And you still want '(other things)' to reduce via [1] to a
> query-expression.
Again, we both know how to chase down and fix shift/reduce conflicts
(and the rarer reduce/reduce conflicts). I'm trying to get the concept
clear first.
Then again, grouping the grammar is not a big deal to me, but the way
you had it before was very confusing. Perhaps your naming was the worst
problem.
> > [20] filter-expression ::= '(' filter-expression ')'
> > | expr
> > | pattern
> >
> > ?
> >
> > Or perhaps I'm misunderstanding your grammar. In the above I'm trying
> > to separate lists/patterns (which include function calls such as
> > 'all()') from predicates (which include function names such as
> > 'isresource').
> >
>
> Now I'm lost. I don't think in the grammar we can restrict to a
> "function call that returns a list" for what I call a
> "pattern-expression". The grammar must support any function call in
> the first position of a filter/traverse. That is why I decided not to
> separate them. So you could do
I must really be confused by your naming, then. And I never said we
should restrict patterns to functions calls that return a list. Not my
use of the word "includes" above. I'm not sure why you read that as an
exclusive example.
> all() - all() -> all()
sure. That's where I'm trying to get to as well, or
> and get every statement in the model if you want as all() would reduce
> to a pattern-expression and a filter expression.
I'm having a little trouble parsing the above sentence.
> Or as a pattern
>
> * - * -> *
>
> or get nothing back with
>
> * - isLiteral(.) -> *
Still not sure I follow, but I'll try explaining my way:
You can use a predicate or pattern in a traversal function or expression
(collectively known as filters). A predicate is a first-class function
instance. This could be:
* an anonymous function defn
* a function invoked by name (including RDF predicates used as
first-class functions, according to Chime's proposal)
* any expression that returns a function instance
A pattern is either
* an object to compare
* a list of objects to compare
* any expression that returns one the above
* a pattern expression, such as * or ns:*
> Maybe its a matter of clearing up the spec WRT how patterns work. In
> my mind, traverse (and when ever I just say traverse I mean all four)
> start with a list of resources, and a list of predicates. If either of
> these were specified as a pattern, then the pattern is translated into
> a "list of all that match the pattern". Given the two lists we can
> compute a list of statements and apply the filter to each.
You mean traversal expression, not the traverse function, right?
> >> [24] operator-expression ::= operator-expression? operator
> >> filter-expression
> >>
> >> [25] pattern ::= node-pattern | literal-pattern | particle
> >
> > I think we can now separate the particles, and have '*' sit by itself
> > here, and have '.' in under expr?
> >
>
> I think I agree but haven't thought it through. I'm pretty sure that
> DOT is only needed in a filter expression and your right it probably
> does not make sense as a pattern.
It would also be used in anonymous function bodies, right? Based on
tentative agreement in the other thread? That would mean it has to be
more generally allowed in an expression.
--
Uche Ogbuji Fourthought, Inc.
http://uche.ogbuji.net http://fourthought.com
http://copia.ogbuji.net http://4Suite.org
Use CSS to display XML, part 2 - http://www-128.ibm.com/developerworks/edu/x-dw-x-xmlcss2-i.html
XML Output with 4Suite & Amara - http://www.xml.com/pub/a/2005/04/20/py-xml.html
Use XSLT to prepare XML for import into OpenOffice Calc - http://www.ibm.com/developerworks/xml/library/x-oocalc/
Schema standardization for top-down semantic transparency - http://www-128.ibm.com/developerworks/xml/library/x-think31.html
More information about the Versa
mailing list