Re: Devising a grammar for boolean queries

"Joachim Durchholz" <>
1 Nov 2000 18:37:30 -0500

          From comp.compilers

Related articles
Devising a grammar for boolean queries (Bemmu Sepponen) (2000-10-31)
Re: Devising a grammar for boolean queries (2000-11-01)
Re: Devising a grammar for boolean queries (Joachim Durchholz) (2000-11-01)
Re: Devising a grammar for boolean queries (Randall Hyde) (2000-11-01)
| List of all articles for this month |

From: "Joachim Durchholz" <>
Newsgroups: comp.compilers
Date: 1 Nov 2000 18:37:30 -0500
Organization: Compilers Central
References: 00-10-226
Keywords: parse
Posted-Date: 01 Nov 2000 18:37:30 EST

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


Post a followup to this message

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