Parsing and Evaluating Boolean Queries

What does paper OR date AND book mean? Read with AND binding more tightly than OR, as in most programming languages and in logic, it is paper OR (date AND book). Read strictly left to right, it is (paper OR date) AND book. With the postings paper → {1, 2}, date → {2, 3}, and book → {3, 4}, the first reading returns documents 1, 2, and 3, and the second returns only document 3. A Boolean search system has to choose one reading, document it, and implement it consistently. The choice belongs to the parser, the component that turns a query string into a structure the system can evaluate.

This article builds a small parser and evaluator for Boolean queries, traces it on that query, discusses the decisions that arise when queries pass through text analysis, describes the parser behind this site's own search box, and reviews the parser I wrote for the course's second assignment.

Precedence and grammar

The conventional precedence, from tightest to loosest, is NOT, then AND, then OR, with parentheses overriding it. NOT a AND b OR c therefore means ((NOT a) AND b) OR c. The convention can be written as a grammar with one rule per precedence level:

expr    := term ( OR term )*
term    := factor ( AND factor )*
factor  := NOT factor | "(" expr ")" | WORD

Each rule handles one operator and delegates tighter-binding operators to the rule below it. An expr is a sequence of terms joined by OR. A term is a sequence of factors joined by AND. A factor is a negation, a parenthesized expression, or a word. Because OR appears only at the top level, AND always groups first.

Precedence decides how different operators group. Associativity decides how a run of the same operator groups: a AND b AND c could be (a AND b) AND c or a AND (b AND c). For Boolean AND and OR the choice cannot change the answer, since intersection and union are associative, so a parser may pick either. The loops in the grammar build left-leaning trees, which is the conventional choice. An optimizer is free to regroup the terms anyway, as optimizing Boolean queries describes, and this freedom is exactly what lets it intersect the rarest lists first.

A recursive-descent parser

A grammar of this shape translates directly into a recursive-descent parser, with one function per rule:

import re

TOKEN = re.compile(r"\s*(\(|\)|AND\b|OR\b|NOT\b|[^\s()]+)")


def tokenize(query):
    return [m.group(1) for m in TOKEN.finditer(query)]


class Parser:
    def __init__(self, tokens):
        self.tokens, self.pos = tokens, 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def take(self, expected=None):
        tok = self.peek()
        if tok is None or (expected and tok != expected):
            raise SyntaxError(f"expected {expected or 'a term'} at position {self.pos}, found {tok}")
        self.pos += 1
        return tok

    def parse(self):
        tree = self.expr()
        if self.peek() is not None:
            raise SyntaxError(f"unexpected {self.peek()} at position {self.pos}")
        return tree

    def expr(self):
        node = self.term()
        while self.peek() == "OR":
            self.take("OR")
            node = ("OR", node, self.term())
        return node

    def term(self):
        node = self.factor()
        while self.peek() == "AND":
            self.take("AND")
            node = ("AND", node, self.factor())
        return node

    def factor(self):
        if self.peek() == "NOT":
            self.take("NOT")
            return ("NOT", self.factor())
        if self.peek() == "(":
            self.take("(")
            node = self.expr()
            self.take(")")
            return node
        return ("TERM", self.take())

The parser produces a query tree. paper OR date AND book parses to

("OR", ("TERM", "paper"), ("AND", ("TERM", "date"), ("TERM", "book")))

with AND grouped below OR, as the grammar requires. Tracing the calls shows how. The tokens are paper, OR, date, AND, book. Each line below is a call to one of the three rule functions, indented by its depth and showing the next unread token, followed by the value it returns:

expr    (next token: paper)
  term    (next token: paper)
    factor    (next token: paper)
    -> ('TERM', 'paper')
  -> ('TERM', 'paper')                      the next token is OR, so term stops
  [expr consumes OR]
  term    (next token: date)
    factor    (next token: date)
    -> ('TERM', 'date')
    [term consumes AND]
    factor    (next token: book)
    -> ('TERM', 'book')
  -> ('AND', ('TERM', 'date'), ('TERM', 'book'))
-> ('OR', ('TERM', 'paper'), ('AND', ('TERM', 'date'), ('TERM', 'book')))

The decisive moment is the second call to term. Having been called by expr to read one operand of OR, it keeps consuming AND factor pairs before returning, so date AND book is complete before expr builds the OR node. The first call to term returned after one factor because the token after paper was OR, which term does not handle. Precedence is encoded in which function owns which loop.

Operators are recognized only in capitals, the convention of many search systems, so that lowercase and and or are treated as ordinary words rather than operators. (In this grammar, the words of rock and roll would still need operators between them, as discussed under malformed queries below.)

Evaluating the tree

Evaluation walks the tree from the leaves up. Each leaf is analyzed into an index term and replaced by its postings. Each operator combines its children with the corresponding set operation:

def evaluate(node, postings, all_docs, analyze):
    op = node[0]
    if op == "TERM":
        return postings.get(analyze(node[1]), set())
    if op == "NOT":
        return all_docs - evaluate(node[1], postings, all_docs, analyze)
    left = evaluate(node[1], postings, all_docs, analyze)
    right = evaluate(node[2], postings, all_docs, analyze)
    return left & right if op == "AND" else left | right

On the example postings, with five documents in the collection:

This evaluator uses Python sets for clarity, and it assumes that any leaves whose words analysis would discard, such as stop words, have already been removed from the tree, for reasons explained below. A production evaluator works on sorted postings lists with the merge algorithms, reorders the tree's children before evaluating them, as described in optimizing Boolean queries, and turns x AND NOT y into a single difference operation rather than computing a complement.

Separating parsing from evaluation, so that the parser produces a tree and the evaluator consumes it, is what makes those optimizations possible. A parser that computes sets while it parses commits to the order in which the query was written.

Malformed queries

Users type incomplete queries. A parser should reject them with a message that explains why, rather than guess or silently return nothing. The parser above reports three common errors:

The last is a design decision rather than an error in any absolute sense. Many systems, including web search engines, treat adjacent terms as an implicit AND. Supporting that means changing the term rule to continue whenever the next token begins a factor, not only when it is AND.

Writing a parser also avoids a tempting shortcut. Converting a query to a Python expression and calling eval() appears to work, but it executes whatever the user typed as code, which is a serious security hole, and it ties the query language to Python's syntax.

Analysis inside queries

Each query term must be analyzed exactly as document terms were: tokenized, case-folded, checked against the stop list, and stemmed (see text processing and indexing). Two complications arise in Boolean queries.

Analyze each term exactly once. If analysis happens both when the query is tokenized and again when a term is looked up, terms are stemmed twice, and the Porter stemmer is not idempotent, so a second pass can produce a stem that is not in the index.

Decide what a removed stop word means. If analysis discards a query word, the tree loses a leaf, and the operator above it is left with a missing operand. Treating the missing operand as an empty set is wrong for AND, because x AND ∅ is always empty, so Department AND of AND Defense would return nothing. The removed word should instead act as the identity element of its operator: the set of all documents for AND, the empty set for OR. The simplest implementation removes the leaf and its operator from the tree before evaluation, so that the query becomes Department AND Defense.

The parser behind this site's search

The search box on this site accepts the same kind of Boolean query, and its parser makes several of the decisions discussed above differently. A query that contains AND, OR, or NOT in capitals, or a parenthesis, is parsed as Boolean. Any other query is treated as free text and ranked, in the style of a web search engine. The Boolean grammar is

or_expr  := and_expr ( OR and_expr )*
and_expr := not_expr ( [AND] not_expr )*
not_expr := NOT not_expr | primary
primary  := "(" or_expr ")" | atom

It has the same three precedence levels as the grammar above, with two changes. The brackets around AND make it optional, so adjacent terms are joined by an implicit AND, the extension suggested under malformed queries. And the loops collect all the operands of a run into one node, ('and', [x, y, z]), rather than nesting binary nodes, so a flattened conjunction is produced directly. An atom can be more than a word: a quoted phrase, a word with a field prefix such as title:, a prefix pattern such as crawl*, or a word with a leading minus, which the parser reads as NOT. Words are left unanalyzed in the tree and are stemmed when the index evaluates it. Run on example queries, the parser produces these trees:

The second query gives the same tree as the first, because the implicit AND binds as tightly as the explicit one. In the fifth, the minus sign and the space both behave as their Boolean equivalents, and the field restriction travels with its word. In the last, robots.txt is one written word but two tokens, so it becomes a two-word phrase.

The other difference is error handling. This parser never rejects a query. It repairs what it can and reports each repair as a note shown above the results:

The design choice is the opposite of the strict parser's: a search box used by the public should return something useful for an imperfect query, and the note keeps the repair visible. Nesting is capped at 16 levels of parentheses, beyond which further opening parentheses are ignored with a note, so that no query the search box accepts (it keeps the first 200 characters) can exhaust the recursion of the parser.

Bugs found by testing the parser and index together

When this article was first written, testing the parser and index together showed four behaviours that were not correct. All four have since been fixed, and they are kept here because each is a small lesson in where such bugs come from.

• A hyphen after a closing parenthesis was read as NOT. The lexer treated every parenthesis as grouping, so it split (1+1)-ES, the name of an evolution strategy, into (1+1) and -ES, and the second token was an atom with a leading minus. The query became and[phrase "1 1", not ES], which excluded pages that mention ES, the opposite of what was meant. The lexer now splits the query at spaces first and treats a leading ( or trailing ) of a chunk as grouping only if what they enclose is balanced. (1+1)-ES and f(x) are single written words, searched by their parts, while (a OR b) still groups, and -(a OR b) negates the group. An operator written against a parenthesis, as in (a)OR(b), and punctuation after a closing one, as in (a OR b), c, are split off first.
• A stop word became the set of all documents, under any operator. The index evaluated a stop word as every document. That is the identity element for AND, as the section on analysis inside queries recommends, but for OR the identity is the empty set, and the OR pagerank returned every article on the site. The evaluator now returns "no constraint" for a node that holds only stop words, and each operator decides what that means: AND and OR skip it, and NOT of it is also no constraint. the OR pagerank returns the same articles as pagerank, with a note that "the" was ignored.
• Greek letters matched nothing. The tokenizer kept only the letters a to z and the digits after accent folding, so a query word such as μ was looked up, found no postings, and evaluated to the empty set. Greek letters are now replaced by their names on both sides: μ in a query is searched as "mu", and the index adds the names of the Greek letters used in each article's mathematics, written there as TeX commands such as \mu. A search for (μ,λ)-ES or mu lambda now finds the evolution-strategy articles.
• A dangling AND was dropped without a note, although the module's documentation said every repair is reported. The note is now added.

None of these was a parsing error in the narrow sense. Each came from a boundary between components: the lexer and the atom syntax in the first, the analyzer and the evaluator in the second and third, the parser's documentation and its behaviour in the fourth. The fixes are the ones this article recommends, applied at those boundaries: analyze each leaf once, decide in the tree what a removed word means for its operator, and test the parser and index together on queries with hand-computed answers. Each fix now has a regression test in tools/search/test_search.py. The examples above come from tools/experiments/boolean/parsing.py, which runs the site's parser in app/query.py.

Lessons from my assignment

The second assignment in the course was to answer Boolean queries over an extended version of the HW01 index, which added term frequencies and changed the preprocessing. For each query of two to four words, the program generated every combination of AND and OR between the words, evaluated each, and ordered the results by TF-IDF score. Submissions were checked against expected answers for a set of searches on a provided dataset. Precedence had not yet been covered in the course, and the expected answers assumed the operators were applied left to right. An earlier version of my parser that followed the conventional precedence did not match them. It also evaluated set expressions in a way that could have executed injected code, so I set it aside. My submitted solution, HW02 on GitHub, contains a hand-written recursive-descent parser. It handles AND, OR, NOT, and parentheses, computes NOT by subtracting from the set of all documents, never calls eval(), and matched the expected answers.

Testing the parser class in isolation for this article, against a small stand-in index, shows how it behaves beyond the assignment's searches. The stand-in only approximates the assignment's data and preprocessing, so these tests describe the parser, not what the graded runs returned. Three points are worth noting.

Precedence is left to right. AND and OR are handled in the same loop and applied in the order written, as the assignment's expected answers required, so paper OR date AND book is evaluated as (paper OR date) AND book and returns document 3 rather than 1, 2, and 3. The parser's docstring, however, still describes the conventional precedence NOT > AND > OR. Reusing the parser outside the assignment would mean either updating the documentation or adding a precedence level for AND, as in the grammar above.

Dropped words become empty operands. The query tokenizer drops stop words and any token that is not purely alphabetic, a filter carried over from HW01 that the HW02 index itself no longer applied. Department AND of AND Defense becomes depart AND AND defens. When the parser meets the second AND where it expects a term, it returns an empty set, and the intersection with an empty set is empty. The hyphenated word-occurrence fails the letters-only test and disappears in the same way, so word-occurrence AND frequency returns nothing, even though the index probably contains the hyphenated term. With OR elsewhere in the expression the result is not always empty, but it is still wrong: basis AND of OR recommendations returns every document containing recommendations and loses those containing only basis. Three of the assignment's five queries contain such a word: basis of recommendations, Department of Defense, and word-occurrence frequency.

Terms are stemmed twice. The double-stemming error described in building an indexing pipeline carried over from HW01: the parser stems each term when tokenizing the query and again when looking it up. For the assignment's queries, defense becomes defen and purpose becomes purpo, neither of which is in the index. Those two words therefore never match any document, so in Department of Defense and general purpose computer programs, every combination that requires either word returns nothing.

The last two problems are silent. The parser runs, returns plausible results for most combinations, and gives no sign that some answers are missing. The remedies are the ones described above: one rule per precedence level, a separate analysis step applied to each leaf exactly once, and removal of stop-word leaves before evaluation. A small set of tests with hand-computed answers, like the table in the evaluation section, catches all three.

References

• Aho, A. V., Lam, M. S., Sethi, R., and Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools, 2nd edition, chapter 4. Addison-Wesley.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 1.3–1.4. Cambridge University Press.