4. Expressions Are Trees

Expressions turn a flat token sequence into a tree of operations.

Chapter 3 could parse only one deliberately fixed query shape:

SELECT name FROM employees WHERE salary > 50000;

Its Query stored one selected column, one table name, one filter column, and one integer boundary. Those four fields cannot represent salary + 5000, condition_a AND condition_b, or parentheses that change evaluation order. Before the database can reason about such expressions, the frontend must preserve their structure.

This chapter extends the frontend path:

SQL → tokens → expression AST

We will use this query to exercise the richer grammar:

SELECT e.name
FROM employees AS e
WHERE e.salary + 5000 > 70000 AND e.name IS NOT NULL;

Compared with Chapter 3, accepting this query requires table aliases, qualified columns, arithmetic, Boolean operators, and null tests. The frontend must preserve that structure before a later stage can resolve names and check types. Here is the expanded grammar:

query               = "SELECT" expression
                      "FROM" identifier alias?
                      "WHERE" expression ";" ;

alias               = "AS"? identifier ;

expression          = or_expression ;
or_expression       = and_expression ("OR" and_expression)* ;
and_expression      = not_expression ("AND" not_expression)* ;
not_expression      = "NOT" not_expression | predicate ;

predicate           = additive comparison_operator additive
                    | additive "IS" "NOT"? "NULL"
                    | additive ;

additive            = term (("+" | "-") term)* ;
term                = factor (("*" | "/") factor)* ;
factor              = ("+" | "-") factor | primary ;

primary             = column_reference | integer | string
                    | "TRUE" | "FALSE" | "NULL"
                    | "(" expression ")" ;

column_reference    = (identifier ".")? identifier ;
comparison_operator = "=" | "<>" | "<" | "<=" | ">" | ">=" ;

This block describes how tokens form a query. Identifiers and integers retain the lexical rules implemented in Chapter 3. This chapter adds single-quoted strings; Appendix B records the complete lexical grammar.

The grammar describes structure, not database meaning. Sections 4.2 through 4.5 add the runtime values, tokens, expression AST, and precedence parser needed to preserve that structure. Section 4.6 makes the resulting tree visible. The next chapter will resolve its names and check its types.

Before changing the program, begin from the completed Chapter 3 checkpoint:

git switch --create chapter-004 lesson-003

4.1 See why flat fields stop working

Try to place the representative query into Chapter 3’s Query:

pub struct Query {
    pub selected_column: String,
    pub table: String,
    pub filter_column: String,
    pub greater_than: i64,
}

There is nowhere to store the addition inside e.salary + 5000, the two conditions joined by AND, or the IS NOT NULL test. Adding one field for each operation would fail as soon as expressions nest in a different way. An expression tree can represent those combinations without adding a field for every possible shape. We will start by adding the value kinds those expressions can produce.

4.2 Extend Value

This chapter’s grammar requires rows to carry Boolean and null results, so Value needs two new variants. Adding those variants also makes every existing match on Value incomplete until it handles them. We will update row.rs first, then make a temporary compatibility change to Chapter 3’s integer-only filter.

4.2.1 Add Boolean and null values

The new grammar adds Boolean expressions, TRUE, FALSE, and NULL. Their results must fit into rows and pass between expression operators, so the runtime Value representation needs two more variants. Boolean stores true or false, while Null represents SQL’s unknown value rather than an empty string or zero.

src/row.rs: add two variants to Value

pub enum Value {
    Integer(i64),
    Text(String),
    Boolean(bool),
    Null,
}

Value::Null represents SQL NULL while a query is running. It is a distinct value rather than an empty string, zero, or false.

The two new values also need printable forms.

src/row.rs: add arms to impl fmt::Display for Value

Value::Boolean(value) => write!(formatter, "{value}"),
Value::Null => write!(formatter, "NULL"),

4.2.2 Keep the old filter compiling

The Chapter 3 Plan::Filter stores a column and a greater_than integer, so it can evaluate only one fixed predicate: column > greater_than. This chapter needs a general expression predicate that can include arithmetic, comparisons, Boolean operators, and null tests. The next chapter will make that larger change after it has checked the expressions.

Until then, the old filter must continue compiling. It calls row.get(column), which returns Some(value) when the column exists and None when it does not. Previously, Text was the only non-integer Value, so the match handled an integer, text, or a missing column.

Adding Boolean and Null creates two more possible values. Rust now requires the match to handle them, even though this temporary filter cannot use them. Group every non-integer value under Some(_):

src/plan.rs: replace the value match in Plan::Filter

let value = match row.get(column) {
    Some(Value::Integer(value)) => value,
    Some(_) => panic!("column is not an integer: {column}"),
    None => panic!("unknown column: {column}"),
};

The first arm extracts an integer. The second reports that an existing column contains the wrong kind of value, and the third reports that the column does not exist. This temporary edit preserves the old behavior while we build its replacement. We now have the value kinds expressions can produce. Next we teach the lexer to recognize the expanded grammar.

4.3 Extend the lexer

The expanded grammar introduces three kinds of input that Chapter 3’s lexer cannot yet recognize: new fixed words such as AND and TRUE, quoted string literals, and additional punctuation operators such as <= and <>. We will add a token representation for each kind, then teach the scanner how to recognize it.

4.3.1 Add the new tokens

The representative query uses many of the new tokens. Others support additional forms in the grammar, such as name = 'Ada' or (salary + 5000) > 70000. The table groups the new token variants by the role they play.

Every quoted keyword or symbol in the grammar needs a fixed token variant. For example, grammar terminal "AND" becomes Token::And, "+" becomes Token::Plus, and "." becomes Token::Dot. Grammar categories that carry input data use variants with fields: identifier becomes Identifier(String), integer becomes Integer(i64), and string becomes String(String).

src/lexer.rs: replace Token

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Token {
    Select, From, Where, As, And, Or, Not, Is, Null, True, False,
    Identifier(String), Integer(i64), String(String),
    Plus, Minus, Star, Slash, Equal, NotEqual,
    Less, LessOrEqual, Greater, GreaterOrEqual,
    Dot, LeftParen, RightParen, Semicolon,
}

These variants define how the lexer will represent the expanded vocabulary. The scanning rules below still need to recognize the corresponding text.

The single > token is now named Greater alongside Less, GreaterOrEqual, and the other comparison variants. The Chapter 3 parser and two lexer tests still use its old name, GreaterThan. Rename those remaining references so the existing query continues to compile while we extend the parser.

src/lexer.rs and src/parser.rs: replace every remaining Token::GreaterThan

Token::Greater

4.3.2 Lex string literals

The lexical rule for string begins with a single quote, consumes characters until its closing quote, and produces one Token::String. For example:

'Ada'         → String("Ada")
'It''s ready' → String("It's ready")

SQL writes two adjacent quotes inside a string to represent one quote in its value. The lexer therefore needs a string branch that consumes the entire multi-character token. A lone quote must not fall through to the punctuation helper and become an unexpected character.

src/lexer.rs: add after the integer branch in tokenize()

} else if character == '\'' {
    let start = current;
    current += 1;
    let mut value = String::new();

    loop {
        if current >= characters.len() {
            return Err(LexError {
                position: start + 1,
                message: "unterminated string".to_string(),
            });
        }
        if characters[current] == '\'' {
            if characters.get(current + 1) == Some(&'\'') {
                value.push('\'');
                current += 2;
            } else {
                current += 1;
                break;
            }
        } else {
            value.push(characters[current]);
            current += 1;
        }
    }
    tokens.push(Token::String(value));

The complete branch turns both examples into one string token. An unmatched opening quote instead returns unterminated string.

4.3.3 Recognize operators and keywords

The expanded grammar also adds several punctuation tokens, including two-character operators such as <= and <>. Moving punctuation recognition into a helper keeps that growing match separate from the main character scan.

src/lexer.rs: replace the final else branch in tokenize()

} else {
    let (token, consumed) = punctuation(&characters, current)
        .ok_or_else(|| LexError {
            position: current + 1,
            message: format!("unexpected character '{character}'"),
        })?;

    tokens.push(token);
    current += consumed;
}

The helper recognizes two-character operators before their one-character prefixes.

src/lexer.rs: add after tokenize()

fn punctuation(characters: &[char], current: usize) -> Option<(Token, usize)> {
    match (characters[current], characters.get(current + 1)) {
        ('<', Some('=')) => Some((Token::LessOrEqual, 2)),
        ('<', Some('>')) => Some((Token::NotEqual, 2)),
        ('>', Some('=')) => Some((Token::GreaterOrEqual, 2)),
        ('+', _) => Some((Token::Plus, 1)),
        ('-', _) => Some((Token::Minus, 1)),
        ('*', _) => Some((Token::Star, 1)),
        ('/', _) => Some((Token::Slash, 1)),
        ('=', _) => Some((Token::Equal, 1)),
        ('<', _) => Some((Token::Less, 1)),
        ('>', _) => Some((Token::Greater, 1)),
        ('.', _) => Some((Token::Dot, 1)),
        ('(', _) => Some((Token::LeftParen, 1)),
        (')', _) => Some((Token::RightParen, 1)),
        (';', _) => Some((Token::Semicolon, 1)),
        _ => None,
    }
}

The first three arms inspect the following character because < and > may begin a two-character operator. For punctuation with no two-character form, _ ignores whatever follows and only the first character matters.

Classify the new fixed words alongside the original keywords.

src/lexer.rs: replace word_token()

fn word_token(word: String) -> Token {
    match word.to_ascii_uppercase().as_str() {
        "SELECT" => Token::Select,
        "FROM" => Token::From,
        "WHERE" => Token::Where,
        "AS" => Token::As,
        "AND" => Token::And,
        "OR" => Token::Or,
        "NOT" => Token::Not,
        "IS" => Token::Is,
        "NULL" => Token::Null,
        "TRUE" => Token::True,
        "FALSE" => Token::False,
        _ => Token::Identifier(word),
    }
}

The lexer recognizes vocabulary. It still does not know whether e is an alias or whether name + 1 is meaningful. Tokens tell the parser what units it received. We now need an AST capable of storing the structure that the parser recovers from those tokens.

4.4 Define expression operators and the AST

The expanded grammar introduced several ways to build an expression. The factor rule added unary + and -, while not_expression added NOT. The term and additive rules added arithmetic operators, predicate added comparisons and null tests, and the two outer expression levels added AND and OR. The AST needs a value for each operator and a tree shape that preserves how those operations are nested.

Create expression.rs with two operator enums and one expression tree. The operator enums represent the vocabulary added by those grammar rules; the tree records how a particular query composes the operators.

UnaryOp contains the three operators that take one operand. Plus and Minus represent leading signs such as -salary. Not represents Boolean negation such as NOT active.

BinaryOp contains operators that take a left and a right operand. They fall into three groups: arithmetic, comparison, and Boolean. The binder will use the same groups when it checks operand types in the next chapter. Arithmetic works on integers. Comparison operators compare compatible operands and produce a Boolean; the binder will define the accepted types. And and Or combine Boolean operands.

src/expression.rs: create this file

use crate::row::Value;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum UnaryOp {
    Plus,
    Minus,
    Not,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum BinaryOp {
    Add,
    Subtract,
    Multiply,
    Divide,
    Equal,
    NotEqual,
    Less,
    LessOrEqual,
    Greater,
    GreaterOrEqual,
    And,
    Or,
}

Expr is the unresolved expression tree recovered by the parser. The tree is recursive: Unary contains one child expression and Binary contains two. Those children use Box so the recursive enum has a finite, known size.

src/expression.rs: add after BinaryOp

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
    Column {
        qualifier: Option<String>,
        name: String,
    },
    Literal(Value),
    Unary {
        op: UnaryOp,
        expression: Box<Expr>,
    },
    Binary {
        left: Box<Expr>,
        op: BinaryOp,
        right: Box<Expr>,
    },
    IsNull {
        expression: Box<Expr>,
        negated: bool,
    },
}

Column preserves both parts of a possibly qualified name. An unqualified column has no qualifier; a qualified one retains both pieces for the binder:

name    → Column { qualifier: None, name: "name" }
e.name  → Column { qualifier: Some("e"), name: "name" }

The qualifier is still only text. The parser has not proved that e is a valid alias.

Literal stores a value written directly in SQL: 5000, 'Ada', TRUE, FALSE, or NULL. The parser converts each corresponding token into a Value variant.

Unary and Binary carry an operator and their child expressions. For example, a unary-minus node with the salary column as its child will produce the negated salary when evaluated.

IsNull remains separate because IS NULL and IS NOT NULL test for the unknown value rather than comparing two operands. Its negated flag distinguishes the two forms.

We now have the values the parser must produce. Next we will follow the grammar from the outer query through each precedence level and build the corresponding Expr nodes.

4.5 Parse columns, literals, and precedence

Before we begin, replace src/main.rs with this temporary AST inspector. It retains Chapter 3’s rule that the prompt collects lines through the terminating semicolon:

mod expression;
mod lexer;
mod parser;
#[allow(dead_code)] // Row execution reconnects in Chapter 5.
mod row;

use std::io::{self, Write};
use parser::parse;

fn main() -> io::Result<()> {
    run_prompt()
}

fn inspect_sql(sql: &str) {
    match parse(sql) {
        Ok(query) => println!("{query:#?}"),
        Err(error) => eprintln!("error: {error}"),
    }
}

fn run_prompt() -> io::Result<()> {
    loop {
        let mut sql = String::new();

        loop {
            if sql.is_empty() {
                print!("sql> ");
            } else {
                print!("...> ");
            }
            io::stdout().flush()?;

            let mut line = String::new();
            if io::stdin().read_line(&mut line)? == 0 {
                println!();
                if !sql.trim().is_empty() {
                    eprintln!("error: incomplete query at end of input");
                }
                return Ok(());
            }
            if sql.is_empty() && line.trim().is_empty() {
                break;
            }
            if append_sql_line(&mut sql, &line) {
                break;
            }
        }

        if !sql.trim().is_empty() {
            inspect_sql(&sql);
        }
    }
}

fn append_sql_line(sql: &mut String, line: &str) -> bool {
    sql.push_str(line);
    line.trim_end().ends_with(';')
}

The parser mirrors the grammar, beginning with parse_query() and descending through expression methods from the weakest precedence level to the tightest.

As in Chapter 3, methods that implement grammar productions begin with parse_. Small helpers such as peek(), consume(), and expect() only inspect or move through the token list, so they do not use that prefix. We will define those helpers before the production methods that call them.

The next six subsections rebuild the parser as one connected change. The program will not compile until parse_primary() closes the new impl Parser in Section 4.5.6. Section 4.5.7 then removes tests tied to the old representation.

Chapter 3’s Query stored a selected-column name, a filter-column name, and an integer boundary. In the expanded query production, both the SELECT position and the WHERE position now contain an expression, so the new Query stores an Expr for its projection and filter.

Before rebuilding parser.rs, delete the complete old impl Query and impl Parser blocks. Keep ParseError, parse(), and the Parser struct; the following subsections will build a new impl Parser around them.

src/parser.rs: replace the imports and Query

use std::fmt;

use crate::expression::{BinaryOp, Expr, UnaryOp};
use crate::lexer::{Token, tokenize};
use crate::row::Value;

#[derive(Debug, PartialEq, Eq)]
pub struct Query {
    pub projection: Expr,
    pub table: String,
    pub table_alias: Option<String>,
    pub filter: Expr,
}

The existing ParseError, parse(), and Parser still fit. Only the body of parse() must call the new outer method:

src/parser.rs: replace the body of parse()

let tokens = tokenize(sql).map_err(|error| ParseError(error.to_string()))?;
Parser { tokens, current: 0 }.parse_query()

4.5.1 Move through the token list

Before implementing the grammar productions, add the operations they will use to inspect and consume tokens. peek() borrows the next token without advancing. consume() advances only when that token matches. expect() turns a failed match into a parse error, while identifier() extracts the text stored inside an identifier token.

Now begin the parser implementation with the cursor helpers.

src/parser.rs: begin the new impl Parser

impl Parser {
    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.current)
    }

    fn consume(&mut self, token: &Token) -> bool {
        if self.peek() == Some(token) {
            self.current += 1;
            true
        } else {
            false
        }
    }

    fn expect(&mut self, token: Token,
        message: &str) -> Result<(), ParseError> {
        if self.consume(&token) { Ok(()) }
        else { Err(ParseError(message.to_string())) }
    }

    fn identifier(&mut self, message: &str)
        -> Result<String, ParseError> {
        match self.peek().cloned() {
            Some(Token::Identifier(value)) => {
                self.current += 1;
                Ok(value)
            }
            _ => Err(ParseError(message.to_string())),
        }
    }

identifier() calls peek().cloned() to copy the next token before advancing the cursor. It can then return the identifier’s owned String without keeping a borrow of the token list.

4.5.2 Parse the query and its alias

We begin with the outer query and alias productions:

query = "SELECT" expression "FROM" identifier alias?
        "WHERE" expression ";" ;
alias = "AS"? identifier ;

The ? after alias makes the whole alias optional. Inside the alias production, the second ? makes only AS optional. The parser therefore accepts employees, employees AS e, or employees e.

The query production divides a shortened version of the query into four pieces:

SELECT e.name FROM employees AS e WHERE e.salary + 5000 > 70000;
       └────┘      └───────┘    └┘      └──────────────────────┘
     projection      table     alias              filter

parse_query() follows that order. It delegates both expression-shaped pieces to parse_expression(), reads the table identifier itself, and delegates the optional alias to parse_alias().

src/parser.rs: continue impl Parser

    fn parse_query(&mut self) -> Result<Query, ParseError> {
        self.expect(Token::Select, "expected SELECT at start of query")?;
        let projection = self.parse_expression()?;
        self.expect(Token::From, "expected FROM after selected expression")?;
        let table = self.identifier("expected a table name after FROM")?;
        let table_alias = self.parse_alias()?;
        self.expect(Token::Where, "expected WHERE after table name")?;
        let filter = self.parse_expression()?;
        self.expect(Token::Semicolon, "expected ; after query")?;

        if self.current != self.tokens.len() {
            return Err(ParseError("unexpected token after ;".to_string()));
        }

        Ok(Query { projection, table, table_alias, filter })
    }

    fn parse_alias(&mut self) -> Result<Option<String>, ParseError> {
        let alias = if self.consume(&Token::As) {
            Some(self.identifier("expected an alias after AS")?)
        } else if matches!(self.peek(), Some(Token::Identifier(_))) {
            Some(self.identifier("expected a table alias")?)
        } else {
            None
        };
        Ok(alias)
    }

parse_alias() implements the second production. consume() returns true and advances when the next token is AS. Without AS, matches! returns true when the next token fits the Identifier pattern without extracting its text. If it matches, identifier() takes that name as the alias. Otherwise the query has no alias.

4.5.3 Parse Boolean operators

Boolean expressions use four precedence productions:

expression     = or_expression ;
or_expression  = and_expression ("OR" and_expression)* ;
and_expression = not_expression ("AND" not_expression)* ;
not_expression = "NOT" not_expression | predicate ;

Each rule asks the next tighter rule for its operands, which makes the tree preserve precedence. Consider a AND b OR c AND d. parse_or_expression() first asks parse_and_expression() for its left operand. That call consumes a AND b and returns a complete AND node. After the OR, another call consumes c AND d. The resulting tree is (a AND b) OR (c AND d).

Every binary-operator level builds the same Expr::Binary shape. Add a small constructor here so the parsing methods can concentrate on when an operator belongs in the tree. The constructor does not use parser state, so it is an associated function called with Self::binary() rather than a method called with self.binary().

src/parser.rs: continue impl Parser

    fn binary(left: Expr, op: BinaryOp, right: Expr) -> Expr {
        Expr::Binary {
            left: Box::new(left),
            op,
            right: Box::new(right),
        }
    }

    fn parse_expression(&mut self) -> Result<Expr, ParseError> {
        self.parse_or_expression()
    }

    fn parse_or_expression(&mut self) -> Result<Expr, ParseError> {
        let mut expression = self.parse_and_expression()?;
        while self.consume(&Token::Or) {
            expression = Self::binary(expression, BinaryOp::Or,
                self.parse_and_expression()?);
        }
        Ok(expression)
    }

    fn parse_and_expression(&mut self) -> Result<Expr, ParseError> {
        let mut expression = self.parse_not_expression()?;
        while self.consume(&Token::And) {
            expression = Self::binary(expression, BinaryOp::And,
                self.parse_not_expression()?);
        }
        Ok(expression)
    }

The first call to parse_and_expression() implements the required first operand in the or_expression production. Then while self.consume(&Token::Or) implements ("OR" and_expression)*: while the next token is OR, consume() both recognizes it and advances past it. The while loop parses the required right operand and combines it with the expression accumulated on the left. The AND loop maps to its production in exactly the same way.

The vertical bar in the not_expression production separates two alternatives. If the next token is NOT, the method consumes it and calls itself, allowing chains such as NOT NOT condition. Otherwise it chooses the predicate alternative, which ends the recursion. The parse_predicate() call also hands the work to the next precedence level, introduced in the following subsection.

src/parser.rs: continue impl Parser

    fn parse_not_expression(&mut self) -> Result<Expr, ParseError> {
        if self.consume(&Token::Not) {
            return Ok(Expr::Unary {
                op: UnaryOp::Not,
                expression: Box::new(self.parse_not_expression()?),
            });
        }
        self.parse_predicate()
    }

4.5.4 Parse comparisons and null tests

Comparisons and null tests come from the predicate production:

predicate = additive comparison_operator additive
          | additive "IS" "NOT"? "NULL"
          | additive ;

comparison_operator = "=" | "<>" | "<" | "<=" | ">" | ">=" ;

Every alternative begins with an additive expression. After parsing that left expression once, the method inspects the next token to decide which alternative applies. A comparison operator requires a second additive expression. IS requires NULL, with an optional NOT; otherwise the first additive expression is already the complete predicate. Because this method calls the tighter arithmetic level for its operands, comparisons and null tests bind more tightly than NOT.

src/parser.rs: continue impl Parser

    fn parse_predicate(&mut self) -> Result<Expr, ParseError> {
        let left = self.parse_additive()?;

        if let Some(op) = self.parse_comparison_operator() {
            return Ok(Self::binary(left, op, self.parse_additive()?));
        }

        if self.consume(&Token::Is) {
            let negated = self.consume(&Token::Not);
            self.expect(Token::Null, "expected NULL after IS")?;
            return Ok(Expr::IsNull {
                expression: Box::new(left), negated,
            });
        }

        Ok(left)
    }

    fn parse_comparison_operator(&mut self) -> Option<BinaryOp> {
        if self.consume(&Token::Equal) { Some(BinaryOp::Equal) }
        else if self.consume(&Token::NotEqual) { Some(BinaryOp::NotEqual) }
        else if self.consume(&Token::Less) { Some(BinaryOp::Less) }
        else if self.consume(&Token::LessOrEqual) { Some(BinaryOp::LessOrEqual) }
        else if self.consume(&Token::Greater) { Some(BinaryOp::Greater) }
        else if self.consume(&Token::GreaterOrEqual) { Some(BinaryOp::GreaterOrEqual) }
        else { None }
    }

parse_comparison_operator() implements the operator production and returns the matching BinaryOp, if one is present. If there is no comparison or null test, parse_predicate() returns the arithmetic expression itself. Binding will later reject it in WHERE unless it produces a Boolean or null result.

4.5.5 Parse arithmetic

Arithmetic uses three progressively tighter productions:

additive = term (("+" | "-") term)* ;
term     = factor (("*" | "/") factor)* ;
factor   = ("+" | "-") factor | primary ;

The parentheses group alternatives, while the following * permits the entire operator-and-operand group to repeat. parse_additive() therefore asks parse_term() for its first operand and for every operand after + or -. Because parse_term() finishes multiplication or division before returning, those operations become deeper nodes in the tree and bind more tightly.

Precedence decides how different operators group. Associativity decides how repeated operators at the same precedence level group. Each loop replaces the accumulated left expression with a new binary node, so a - b - c becomes (a - b) - c. Subtraction is therefore left-associative.

src/parser.rs: continue impl Parser

    fn parse_additive(&mut self) -> Result<Expr, ParseError> {
        let mut expression = self.parse_term()?;
        loop {
            let op = if self.consume(&Token::Plus) { Some(BinaryOp::Add) }
            else if self.consume(&Token::Minus) { Some(BinaryOp::Subtract) }
            else { None };
            match op {
                Some(op) => expression = Self::binary(
                    expression, op, self.parse_term()?),
                None => break,
            }
        }
        Ok(expression)
    }

    fn parse_term(&mut self) -> Result<Expr, ParseError> {
        let mut expression = self.parse_factor()?;
        loop {
            let op = if self.consume(&Token::Star) { Some(BinaryOp::Multiply) }
            else if self.consume(&Token::Slash) { Some(BinaryOp::Divide) }
            else { None };
            match op {
                Some(op) => expression = Self::binary(
                    expression, op, self.parse_factor()?),
                None => break,
            }
        }
        Ok(expression)
    }

The factor production uses alternatives rather than repetition. A leading sign is followed by another complete factor, so unary signs call themselves and --salary nests correctly. The recursion ends when the parser chooses the primary alternative. Any token other than + or - falls through to parse_primary() immediately.

src/parser.rs: continue impl Parser

    fn parse_factor(&mut self) -> Result<Expr, ParseError> {
        if self.consume(&Token::Plus) {
            return Ok(Expr::Unary {
                op: UnaryOp::Plus,
                expression: Box::new(self.parse_factor()?),
            });
        }
        if self.consume(&Token::Minus) {
            return Ok(Expr::Unary {
                op: UnaryOp::Minus,
                expression: Box::new(self.parse_factor()?),
            });
        }
        self.parse_primary()
    }

4.5.6 Parse primary expressions

The tightest level supplies the leaves of the expression tree:

primary = column_reference | integer | string
        | "TRUE" | "FALSE" | "NULL"
        | "(" expression ")" ;

column_reference = (identifier ".")? identifier ;

The vertical bars list the possible primary forms. A column reference begins with an optional qualifier-and-dot group followed by the required column name. Integer, string, Boolean, and null tokens become literals. Parentheses contain a complete expression, so they deliberately restart parsing at the weakest precedence level while making the enclosed tree act as one primary outside. Showing the entire match together keeps every possible leaf visible in one place.

src/parser.rs: finish impl Parser with parse_primary()

    fn parse_column_reference(&mut self) -> Result<Expr, ParseError> {
        let first = self.identifier("expected a column name")?;
        if self.consume(&Token::Dot) {
            let name = self.identifier(
                "expected a column name after .")?;
            Ok(Expr::Column {
                qualifier: Some(first), name,
            })
        } else {
            Ok(Expr::Column { qualifier: None, name: first })
        }
    }

    fn parse_primary(&mut self) -> Result<Expr, ParseError> {
        match self.peek().cloned() {
            Some(Token::Identifier(_)) => self.parse_column_reference(),
            Some(Token::Integer(value)) => {
                self.current += 1;
                Ok(Expr::Literal(Value::Integer(value)))
            }
            Some(Token::String(value)) => {
                self.current += 1;
                Ok(Expr::Literal(Value::Text(value)))
            }
            Some(Token::Null) => {
                self.current += 1;
                Ok(Expr::Literal(Value::Null))
            }
            Some(Token::True) => {
                self.current += 1;
                Ok(Expr::Literal(Value::Boolean(true)))
            }
            Some(Token::False) => {
                self.current += 1;
                Ok(Expr::Literal(Value::Boolean(false)))
            }
            Some(Token::LeftParen) => {
                self.current += 1;
                let expression = self.parse_expression()?;
                self.expect(Token::RightParen,
                    "expected ) after expression")?;
                Ok(expression)
            }
            _ => Err(ParseError("expected an expression".to_string())),
        }
    }
}

parse_column_reference() implements the second production. It first reads an identifier. A following dot makes that first name the qualifier and requires another identifier for the column; without a dot, the first name is the unqualified column.

peek().cloned() gives this method an owned token before it advances the cursor. The resulting AST can therefore own identifier and string contents instead of borrowing them from the parser’s token list.

4.5.7 Remove obsolete parser tests

The Chapter 3 parser tests still include two checks tied to the old Query. Remove parses_the_supported_query_shape(), which constructs the removed flat fields, and parsed_sql_executes_the_employee_query(), which calls the removed into_plan() method. Keep the tests for a required semicolon and trailing tokens. Those checks still describe valid parser behavior.

The remaining tests use only parse(), so remove their obsolete Query, Row, and Value imports.

src/parser.rs: replace the imports in mod tests

use super::parse;

Further reading

In Robert Nystrom’s Crafting Interpreters, Chapter 5, “Representing Code”, motivates recursive syntax trees, while Chapter 6, “Parsing Expressions”, shows how layered grammar productions encode precedence and associativity. The language differs from SQL, but the tree and parser ideas are the same.

4.6 Run an AST checkpoint

The temporary shell installed before the parser replacement can now display the recovered expression tree. Run the prompt and enter the representative query:

cargo run --quiet

The printed tree places the addition inside the comparison, then joins that comparison and the null test beneath AND. It also retains e on each qualified column reference. This proves that parsing recovered the intended structure. It does not prove that employees, e, or any referenced column exists.

4.7 What we deliberately did not build

This expression frontend remains intentionally bounded:

• A query still has one input table and one selected expression.
• A WHERE clause is still required.
• Arithmetic uses integer literals; decimal values are not yet supported.
• There are no functions, BETWEEN, LIKE, IN, CASE, CAST, dates, or intervals.
• Parsing preserves qualifiers such as e, but does not prove they exist.
• Parsing does not decide whether an operator receives sensible operand types.

These limits keep the chapter focused on one transition: a flat query record becomes a nested expression tree.

4.8 Try it

Run the AST prompt, predict the tree shape for each change, and then inspect the result.

1. Compare salary + 2 * 3 with (salary + 2) * 3.
2. Replace e.salary + 5000 > 70000 with NOT e.salary > 70000.
3. Use the string literal 'It''s ready' as the selected expression.
4. Replace e.name with x.name.
5. Try name + 1 > 0.

4.9 The plan cannot use these trees yet

In Chapter 3, each parsed piece was a single, non-nested value. The projection was one column name, while the filter was one column, the fixed > operator, and one integer:

selected_column: name
filter_column: salary
greater_than: 50000

Those fields mapped directly into the fixed Project and Filter fields in our logical plan. This chapter changed that representation. The projection and filter are now nested trees:

projection: Expr
filter: Expr

The AST-only shell stops after printing those trees because the current plan cannot carry them. More importantly, the trees still contain unchecked names. Attaching them directly to the plan would force the executor to decide whether employees, e, and salary exist and whether an operation such as name + 1 makes sense.

The next chapter introduces the missing boundary. The binder will walk each expression tree, resolve its names through a catalog, check its operand types, and produce a checked expression tree that the logical plan can safely store and the executor can evaluate.