Lesson 30 · Parsing boolean queries

Parsing boolean queries

Today you read a boolean query like "cats AND dogs" into a token stream where operators are recognized and the words between them are analyzed into terms. This is the parse step before boolean evaluation.

The goal

Parse a boolean query string into a list of analyzed terms and AND/OR/NOT operators.

Start here - the target

TO DO

Scenario: Splitting a boolean query into terms and operators

Giventhe boolean query "Cats AND dogs"

Whenit is parsed

Thenthe tokens are ["cat", "AND", "dog"]

And"cat OR NOT bird" parses to ["cat", "OR", "NOT", "bird"]

Background

So far queries have been bags of words. A boolean query adds structure with the operators AND, OR, and NOT. Before you can evaluate one, you have to parse it: walk the whitespace-separated words, recognize the three operators (in any case), and analyze everything else into a term - so Cats becomes cat, matching the index.

Keep the operators uppercase and the terms analyzed, and you get a clean token stream like ["cat", "AND", "dog"]. This flat list is enough for the left-to-right evaluation you will write tomorrow; a production parser would build a tree with precedence, but the token stream keeps the idea in view without the machinery.

Make it work

OPS = {"AND", "OR", "NOT"}
def parse_bool(query):
    out = []
    for word in query.split():
        if word.upper() in OPS:
            out.append(word.upper())
        else:
            out.extend(analyze(word))   # a term becomes its analyzed form
    return out