Re: Devising a grammar for boolean queries

Bemmu Sepponen <lomise@uta.fi> 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
"or", so


    a or b and c


parses as


    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 ->
    expression_i-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
line with


    | 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.


Regards,
Joachim

Return to the comp.compilers page.
Search the comp.compilers archives again.