On Thu, May 23, 2002 at 08:32:57PM -0400, Ray denenberg wrote:
> So the bnf would instead be:
>
> CqlString ::= Term | Term Boolean CqlString | "("Term Boolean CqlString")"
> Term ::= [IndexQualifier Relationship] SearchTerm
> IndexQualifier ::= [IndexSet.] IndexId
>
> IndexSet ::= SimpleString
> Relationship ::= "=" | "<" | ">" (etc)
> IndexId ::= SimpleString
> SearchTerm::= FunnyString
> Boolean::= 'AND', 'OR' (etc)
>
> Does that help? Putting parenthesis around "term operator term" should
> resolve the ambiguity question (though perhaps not the way you would
> prefer). Whether we still need parenthesis (or something) around term is
> still a question.
>
> --Ray
No, it does not address the ambiguity of AND/OR/NOT precedence.
Also the way the grammar is written you can only do one level of
nesting of parenthesis.
The normal thing to do is have a series of rules, one rule defined
per precedence level (in maths + and - have the same precendence
so have a single rule which allows either symbol). The higher the
rule, the looser the binding. Then at the bottom level, you tend to
allow parenthesis and then mention the highest rule again in the
parenthesis.
term ::= factor *( add-op factor ) -- loose binding
add-op ::= "+" | "-"
factor ::= primary *( mul-op primary ) -- tighter binding
mul-op ::= "*" | "/" | "%"
primary ::= constant | "(" term ")" -- loops back to top.
So
a+b*c
expands using
term -> factor(a) "+" factor(b*c)
factor(a) -> primary(a)
primary(a) -> constant(a)
factor(b*c) -> primary(b) "*" primary(c)
primary(b) -> constant(b)
primary(c) -> constant(c)
whereas
(a+b)*c
expands using
term -> factor((a+b)*c)
factor((a+b)*c) -> primary((a+b)) "*" primary(c)
primary((a+b)) -> "(" term(a+b) ")"
term(a+b) -> factor(a) "+" factor(b)
factor(a) -> primary(a)
primary(a) -> constant(a)
factor(b) -> primary(b)
primary(b) -> constant(b)
primary(c) -> constant(c)
So the grammar only defines one possible legal expansion, getting
the precendence of operators right.
Most systems don't give AND and OR the same precendence. The grammar
you gave does not specify whether AND or OR binds more tightly.
So it could either mean you want left to right semantics (like + and -),
but thats bad because AND and OR are not associative like + and -,
otherwise you have to specify the precendence as prose. Using the
grammar is better because its more precise.
Grammars are not for humans to read - they are for programmers.
Normal humans can read examples and prose.
Sorry, I might have got carried away here!
Alan
|