⚠

The web version only has simple instructions since chapter 04, while the full book has detailed explanations and background info.

0504: Expression Parser

SQL Operators

This step adds many SQL operators, with precedence from low to high:

a OR b
a AND b
NOT a
a = b, a <> b, a < b, a > b, a <= b, a >= b
a + b, a - b
a * b, a / b
-a

Test case:

// f or e and not d = a + b * -c
&ExprBinOp{op: OP_OR,
    left: "f", right: &ExprBinOp{op: OP_AND,
        left: "e", right: &ExprUnOp{op: OP_NOT,
            kid: &ExprBinOp{op: OP_EQ,
                left: "d", right: &ExprBinOp{op: OP_ADD,
                    left: "a", right: &ExprBinOp{op: OP_MUL,
                        left: "b", right: &ExprUnOp{op: OP_NEG,
                            kid: "c"}}}}}}}

Extract Common Functions

Like parseAdd() in the previous step, each priority level maps to a parseXXX() function, which calls the next parseYYY(). Earlier, parseMul() was copied from parseAdd(). Now with many functions, we can extract the shared logic:

func (p *Parser) parseOr() (interface{}, error) {
    return p.parseBinop([]string{"OR"}, []ExprOp{OP_OR}, p.parseAnd)
}
func (p *Parser) parseAnd() (interface{}, error) {
    return p.parseBinop([]string{"AND"}, []ExprOp{OP_AND}, p.parseNot)
}
func (p *Parser) parseNot() (expr interface{}, err error)
func (p *Parser) parseCmp() (interface{}, error) {
    return p.parseBinop(
        []string{"=", "!=", "<>", "<=", ">=", "<", ">"},
        []ExprOp{OP_EQ, OP_NE, OP_NE, OP_LE, OP_GE, OP_LT, OP_GT},
        p.parseAdd)
}
func (p *Parser) parseAdd() (interface{}, error) {
    return p.parseBinop([]string{"+", "-"}, []ExprOp{OP_ADD, OP_SUB}, p.parseMul)
}
func (p *Parser) parseMul() (interface{}, error) {
    return p.parseBinop([]string{"*", "/"}, []ExprOp{OP_MUL, OP_DIV}, p.parseNeg)
}
func (p *Parser) parseNeg() (expr interface{}, err error)

Extract the differences between parseAdd() and parseMul() as parameters:

func (p *Parser) parseBinop(
    tokens []string, ops []ExprOp, inner func() (interface{}, error),
) (interface{}, error)

Prefix Operators

NOT a and -a have only 1 child, so add a new struct:

type ExprUnOp struct {
    op  ExprOp
    kid interface{}
}

Note that the child can include operators at the same level, such as NOT NOT a.

func (p *Parser) parseNot() (expr interface{}, err error)

evalExpr() should be extended to handle this as well.

ⓘ

CodeCrafters.io has similar courses in many programming languages, including build your own Redis, SQLite, Docker, etc. It’s worth checking out.