Grammars and Parsing

Tokens in a row are not yet a query. author:"le guin" AND year>1970 OR subject:utopia can mean two different searches, depending on which operator binds tighter, and the two return different records. One returns Le Guin's books after 1970 plus every book about utopia by anyone. The other returns only Le Guin's books, those after 1970 or about utopia.

A grammar settles it: a handful of rules that say what a valid query is and how its parts nest. The parser reads tokens against those rules and builds a syntax tree, the structure every later stage works on. This topic writes Lantern's grammar, builds its parser and follows the grammar's choices to where they are paid for: in results, in error messages and in stack depth.

A Grammar Is a Short List of Rules

Lantern's grammar is four rules, with one helper for values. A query is one or more AND-groups joined by OR. An AND-group is one or more NOT-terms joined by AND, or by nothing at all, which is the implicit AND. A NOT-term is NOT followed by another NOT-term, or a primary. A primary is a query in parentheses, a word followed by a colon or a comparison and then a value, or a bare word, phrase or number.

query     = and_group { "OR" and_group }
and_group = not_term { ["AND"] not_term }        (no operator = implicit AND)
not_term  = "NOT" not_term | primary
primary   = "(" query ")" | WORD ":" value | WORD compare value | value
value     = WORD | PHRASE | NUMBER

The notation above is the rule list in the previous paragraph, written compactly: braces mean "repeated any number of times", square brackets mean "optional", and a vertical bar separates alternatives. Each rule refers only to rules below it, or to itself in the case of NOT, except the primary, which refers back to the whole query inside parentheses. That one loop is what lets queries nest to any depth.

Precedence Lives in the Layers

NOT binds tightest, then AND, then OR: the same order as SQL and as Python's not, and and or. The grammar encodes it by layering. A query is built from AND-groups, and an AND-group from NOT-terms, so a tighter operator always ends up deeper in the tree, closer to the values it combines. a AND b OR c means "a and b", or c. Parentheses are how a user asks for the other grouping.

The upper tree is what Lantern's parser returns for the mixed query from the opening: OR at the root, with the AND of author and year beneath it. Its results include Thomas More's Utopia, because every book about utopia matches the right side on its own. The lower tree is the grouping the grammar rules out, which a user gets only by writing the parentheses around the OR.

Recursive Descent

The simplest way to turn the grammar into a parser is recursive descent: one function per rule, each calling the functions for the rules inside it, and looking one token ahead to decide which alternative applies. The function for a query calls the one for an AND-group; that one calls the one for a NOT-term; that one calls the one for a primary; and a primary that finds an opening parenthesis calls the query function again.

def and_group(self):
    node = self.not_term()
    while self.peek().kind == "AND" or self.peek().kind in TERM_START:
        if self.peek().kind == "AND":
            self.take()
        node = And(node, self.not_term())
    return node

The function reads one NOT-term. Then, while the next token is AND or the start of another term, it consumes the AND if there is one, reads another NOT-term and joins the two under an AND node. The "start of another term" check is the implicit AND: two terms side by side with no operator. The parser's own call stack, the structure Chapter 3 describes, mirrors the nesting of the query, with one frame for each rule being read.

The Syntax Tree

For the canonical query, the parser returns an AND node with two children: a field match of author against the phrase "le guin", and a comparison of year, greater than, 1970. The colon, the quotes and any parentheses have done their job and are dropped. That is what "abstract" means in abstract syntax tree: the tree keeps the structure and the values and forgets the punctuation that expressed them.

The lines in the figure run from each token to the node it became. The author word and the phrase become one field-match node, the AND token becomes the root, and the year word, the greater-than sign and the number become one comparison node. The colon has no line: nothing in the tree records it. Every later stage, checking, evaluating and optimizing, is a traversal of this tree, the kind Chapter 6 describes, and no stage after the parser looks at the raw string again.

Left Recursion and Ambiguity

The natural way to write the OR rule is "a query is a query, then OR, then an AND-group". A recursive-descent parser cannot use it: the query function would call itself before consuming a single token, and call itself again, until the stack runs out. Recursive-descent grammars therefore write repetition as a loop, the braces in Lantern's grammar, instead of as a rule that refers to itself on the left.

A grammar without layers, such as "a query is a query, an operator and a query", allows two trees for one input. A hand-written parser does not report that ambiguity; it silently takes whichever alternative its code tries first. CPython's own parser has been a PEG parser since Python 3.9, replacing the older LL(1) parser, which was removed in 3.10. A PEG parser tries alternatives in a fixed order and can backtrack, and CPython's remembers which of 20 marked rules matched at which positions, a technique called packrat memoization. It is memory spent to keep backtracking from going exponential, the time-space trade of Chapter 1.

What Parsing Costs

For a grammar like Lantern's, recursive descent touches each token once or twice, so a query parses in microseconds. The real price is stack depth. Each level of parentheses costs four Python frames: query, AND-group, NOT-term and primary. Without a limit, Lantern's parser on Python 3.15 first failed at 249 nested parentheses, against CPython's default recursion limit of 1,000, and the worker died with a RecursionError. One search string was a denial of service.

The fix is a nesting limit far above anything a person types. Lantern's parser stops at 100 levels and reports "parentheses nested deeper than 100" at the offending parenthesis. The precedence choice has a price too, paid by the user who wrote a AND b OR c meaning "a, and b or c", and got more records than they asked for with no error. That is why Lantern prints the grouping it chose above the results, in this case "(a AND b) OR c".