Parsing selection syntax

General Usage
10

I think the approach you are taking will be difficult to generalize to a more complicated query grammar. Here’s an approach that avoids metaprogramming.

The idea is to build up an Abstract Syntax Tree (AST). But I don’t mean a Julia AST, I mean an AST for your query language. The AST for your query language can be represented by nested tuples.

Atom code

struct Atom
	index::Int
	iswater::Bool
	isiron::Bool
end

iswater(a::Atom) = a.iswater
isiron(a::Atom) = a.isiron

a = Atom(50, true, false)
b = Atom(200, false, false)
c = Atom(200, false, true)

Example query to parse

s = "index < 100 or not water and not iron"

Parsing function

The following function parse_query parses a query string into a nested tuple that represents the AST of your query. Each tuple represents an S-expression where the first argument of the tuple is a function and the remaining arguments of the tuple are the arguments of that function.

A couple things to note:

  • parse_query is a recursive function, because the query could have arbitrarily nested ands, ors, and nots.
  • The if-else block is ordered from lowest operator precedence to highest operator precedence, with "or" being the lowest precedence and function application (like iswater) the highest precedence.
function parse_query(s)
    if occursin("or", s)
        (|, parse_query.(split(s, "or"))...)
    elseif occursin("and", s)
        (&, parse_query.(split(s, "and"))...)
    elseif occursin("not", s)
        rest = match(r".*not(.*)", s)[1]
        (!, parse_query(rest))
    elseif occursin("index <", s)
        k = parse(Int, match(r"index < ([0-9]*)", s)[1])
        a -> a.index < k
    elseif occursin("water", s)
        iswater
    elseif occursin("iron", s)
        isiron
    else
        error("Parsing error!")
    end
end

Let’s run this on the query string and see what we get:

julia> q = parse_query(s)
(|, var"#5#6"{Int64}(100), (&, (!, iswater), (!, isiron)))

So we see that we get our AST as a nested tuple! Now we need a way to apply the AST to an atom.

Apply parsed query to atom

function apply_query(q, a)
	if !(q isa Tuple)
		q(a)
	else
		f, args = Iterators.peel(q)
		f(apply_query.(args, Ref(a))...)
	end
end

This function recursively calls the first argument of each tuple with the remaining arguments of the tuple. When apply_query gets down to a point in the AST where q is not a tuple, it assumes that q is a function (e.g., either iswater, isiron, or a -> a.index < k) and it calls that function on the atom a.

Now let’s apply our parsed query to an atom:

julia> apply_query(q, a)
true

julia> apply_query(q, b)
true

julia> apply_query(q, c)
false

It works, and all without using any metaprogramming!

EDIT:
I had my operator precedence wrong in the initial post, so I’ve fixed that.

11 Likes