|Devising a grammar for boolean queries email@example.com (Bemmu Sepponen) (2000-10-31)|
|Re: Devising a grammar for boolean queries nailed_barnacleSPAMFREE@hotmail.com (2000-11-01)|
|Re: Devising a grammar for boolean queries firstname.lastname@example.org (Joachim Durchholz) (2000-11-01)|
|Re: Devising a grammar for boolean queries email@example.com (Randall Hyde) (2000-11-01)|
|From:||"Joachim Durchholz" <firstname.lastname@example.org>|
|Date:||1 Nov 2000 18:37:30 -0500|
|Posted-Date:||01 Nov 2000 18:37:30 EST|
Bemmu Sepponen <email@example.com> wrote:
> I assume the precedence of "and" and "or" is the same (true?).
Precedence is a matter of convention in general, so this isn't "wrong",
but the common convention is still to make "and" higher precedence than
a or b and c
a or (b and c)
> This is the first parser I've ever attempted to write. I figure the
> next reasonable thing to do is form a grammar for the valid queries.
> I wonder what it should be like, I'll make an attempt:
> query -> phrase | phrase operator query
> operator -> and | or
> phrase -> word | word phrase
> Am I even close? How about the parentheses?
Here's a grammar with parentheses and precedence (general case for n
precedence levels, duplicate the expression_i rule once for each
precedence level and replace the i with the precedence level):
expression -> expression_1
| expression_i-1 operator_i expression_i-1
simple_expression -> word | "(" expression_1 ")"
This gives nonassociative operators. If you wish the operators on
precedence level i to be left-associative, you have to replace the last
| expression_i operator_i expression_i-1
for right-associative operators, you need
| expression_i-1 operator_i expression_i
(If you make the last line to be
| expression_i operator_i expression_i
then your grammar will be ambiguous, so Don't Do That.)
BTW this is an exceedingly simple operator-precedence language. There
are specialized algorithms for parsing such languages, so you don't need
to write a BNF grammar, a list of operator symbols and precedences is
enough - provided that you have or write such an algorithm.
As our esteemed moderator says, any compiler textbook will give you an
introduction. Operator-precedence parsing was one of the first parsing
techniques studied, and it's very simple to implement, so the vast
majority of compiler texts start with operator-precedence parsing.
Return to the
Search the comp.compilers archives again.