feat: Wrapper macros for grammar definition + folds

[impact-basin]

Firstly - great package, thank you for all your hard work!

I have been wrapping the PikaParser.jl workflow in a few macros, and wanted to float them for your consideration.

The two macros are in the gist here -- @pika_grammar produces a callable function which parses the input, and @pika_evaluate provides syntactic sugar for fold-function definitions.

I think an example is best - a simple calculator with whitespace (mind I don't write many PEG grammars, so you will probably find a better way of doing this!)

The grammar is defined with this macro like so:

calc_grammar = @pika_grammar :top begin
    :ws     => many(satisfy(isspace)),
    :digit  => satisfy(isdigit),
    :number => some(:digit),
    :plus   => seq(:expr, :ws, token('+'), :ws, :expr, :ws),
    :minus  => seq(:expr, :ws, token('-'), :ws, :expr, :ws),
    :times  => seq(:expr, :ws, token('*'), :ws, :expr, :ws),
    :divby  => seq(:expr, :ws, token('/'), :ws, :expr, :ws),
    :paren  => seq(:ws, token('('), :ws, :expr, :ws, token(')'), :ws),
    :expr   => first(:paren, :times, :divby, :plus, :minus, :number),
    :top    => seq(:expr)
end

(Note that the @pika_grammar macro traverses the syntax tree, and replaces PikaParser.jl library symbols with their qualified names, e.g. seq => PikaParser.seq).

Now we write the evaluator with some additional output:

calc_eval = @pika_evaluate :top m v begin
    :number => parse(Int, m.view)
    :plus   => begin
        println("Parsing plus: $(m.view) => $(v[1]) + $(v[5])")
        v[1] + v[5]
    end
    :minus  => begin
        println("Parsing minus: $(m.view) => $(v[1]) - $(v[5])")
        v[1] - v[5]
    end
    :times => begin
        println("Parsing times: $(m.view) => $(v[1]) * $(v[5])")
        v[1] * v[5]
    end
    :divby => begin
        println("Parsing divby: $(m.view) => $(v[1]) / $(v[5])")
        v[1] / v[5]
    end
    :expr  => v[1]
    :paren => v[4]
    :top   => begin
        println("Parsing top: $(m.view) => $(v[1])")
        v[1]
    end
end

Finally, we parse according to the grammar and evaluate:

julia> calc_grammar("12 + ( 34* 56)") |> calc_eval
Parsing times: 34* 56 => 34 * 56
Parsing plus: 12 + ( 34* 56) => 12 + 1904
Parsing top: 12 + ( 34* 56) => 1916
1916

Please let me know if I can be of any help - whether there are additional aspects to consider, or whether I should open a pull request.

And once again, thanks for the great parsing library!

[exaexa]

Hi, yeah this looks great, thanks & please open a PR!

Re the requirements, the code should be 100% covered by the test run from documentation (see docs/src), so feel free to write a super simple tutorial for these that shows how to use the macros.

By The Way, since you're at macros already: most people use exactly 1 evaluator per grammar, so if you would have time, try to invent a way to actually glue the rules&evals together so that we can get a somewhat bison-like mixed spec -- that could be great. I wanted to do that at some point but never got to it.

Thanks again!

[impact-basin]

Sounds great! I'll fork the tree now and check this out on a branch called "sugar."

I've ended up being a little long-winded here, so I've added a few sections :-)

Schedule

I'm currently trying to parse ODL - going to use this as a chance to shake out any oddities and bikeshed a bit more. Once I'm done, I'll put together tests and docs; hopefully should have a PR ready by Friday, if not the weekend!

I've actually found one or two rough edges in the macros already: there seems to be some oddities related to assignment in the evaluate clauses; I think I might have gotten an esc() wrong somewhere. One change since the gist was posted is that I've swapped the nothing terminal clause for a return of subvalues, indexing into the array if it's a singleton:

    postwalk(exprs) do e
        @capture(e, rule_ => value_) || return e
        push!(rules, quote 
            $(m).rule == $rule ? $value :
                (length($v) > 1 ? $(v) : length(v) == 1 ? $(v)[1] : nothing)
        end)
        return e
    end

So I'm definitely going to polish things up!

Regex

If you'd like, I can also have a look at identifying expressions in the @pika_grammar invocation that map symbols to regex literals -- then the syntax from #21 could go from

rules = Dict(
    ...,
    :id => PikaParser.scan() do x
        matched = match(r"^[a-z][a-zA-Z0-9_]*", x)
        isnothing(matched) && return 0
        length(matched.match)
    end,
    ...,
)

to

rules = @pika_grammar :top begin
    ...,
    :id => r"^[a-z][a-zA-Z0-9_]*",
   ...
end

This shouldn't be too tricky, and we can verify in the macro that the carat prefixes all regex expressions. The bikeshedding question is whether it's an error to omit the carat, or whether the carat is implicit. Actually, checking out the expression tree for a regex literal, this should be very straightforward:

julia> using Term: expressiontree

julia> expressiontree(:(r"^[0-9]+"))
r"^[0-9]+"                
  ├─ 1 ⇒ @r_str           
  ├─ 2 ⇒ #= REPL[16]:1 =# 
  └─ 3 ⇒ ^[0-9]+          

One macro to rule them all

I had a think about gluing things together; the functions generated by @pika_grammar and @pika_evaluate compose, so we could traverse the AST in @pika_parse to pull the inputs to @pika_grammar and @pika_evaluate, then return their composition as a lambda function. The syntax could look something like this:

calc = @pika_parser :top m v begin
    :ws     => many(satisfy(isspace))
    :digit  => satisfy(isdigit)
    :number => some(:digit) => parse(Int, m.view)

    :plus => seq(:expr, :ws, token('+'), :ws, :expr, :ws) => begin
        println("Parsing plus: $(m.view) => $(v[1]) + $(v[5])")
        v[1] + v[5]
    end

    :minus  => seq(:expr, :ws, token('-'), :ws, :expr, :ws) => begin
        println("Parsing minus: $(m.view) => $(v[1]) - $(v[5])")
        v[1] - v[5]
    end

    :times => seq(:expr, :ws, token('*'), :ws, :expr, :ws) => begin
        println("Parsing times: $(m.view) => $(v[1]) * $(v[5])")
        v[1] * v[5]
    end

    :divby => seq(:expr, :ws, token('/'), :ws, :expr, :ws) => begin
        println("Parsing divby: $(m.view) => $(v[1]) / $(v[5])")
        v[1] / v[5]
    end

    :paren  => seq(:ws, token('('), :ws, :expr, :ws, token(')'), :ws) => v[4]
    :expr   => first(:paren, :times, :divby, :plus, :minus, :number)  => v[1]
    :top    => seq(:expr) => begin
        println("Parsing top: $(m.view) => $(v[1])")
        v[1]
    end
end

What do you think? Eager to hear your feedback :-).

[exaexa]

OK, since this is getting a lot of topics at once please do separate out any parts that are working and do individual PRs so that stuff is easy to review. I guess we can have one PR on the grammar, one on the evals, one to combine them, and a completely independent one on regex.

Re naming: no need to prefix with pika_ -- assume people import pikaparser with qualifier as P, and they will want to write P.@grammar instead of P.@pika_grammar :)

[impact-basin]

Sounds good! I've just renamed the macros.

I'm a bit sloppy with my version control - so for now I've just updated the gist here.

The linked code includes the regex handling in @grammar; we can also cope with postfixed flags to the regex (e.g. r"[a-z]+"i). Some example code:

test1 = @grammar :top begin
    :ws    => first(satisfy(isspace), epsilon),
    :ident => r"[a-z_]+[a-z0-9_]*"i,
    :decl  => seq(:ident, :ws),
    :top   => some(:decl)
end

test2 = @evaluate :top m v begin
    :ident => Symbol(m.view)
    :decl  => v[1]
end

Giving it a run:

julia> test1("foo Bar bA9Z QUx") |> test2
4-element Vector{Any}:
 :foo
 :Bar
 :bA9Z
 :QUx

When I go to commit this into the tree, I'll go for the branches grammar, evaluate, and parser and raise separate PRs for each!

[impact-basin]

PRs are up! I'm going to punt on gluing together @grammar and @evaluate as I need to get a few things done over the next few days. I'm going to test-drive this a bit more with some of my own code, and will come back to write the docs + add more tests + polish off everything properly -- well, probably this weekend, but I'll respond to messages.

[impact-basin]

Heya - sorry for the radio silence, just a few updates for you.

I'm writing a quick-and-dirty parser for KDL with these macros; that, plus the ODL parser from earlier has given me some ideas about annoying edges for both macros.

My workflows are generally quite "use-driven" -- bringing up the KDL parser has given me a few ideas about where pain points lie, and features that are useful. I've made a few changes:

• Rename @grammar to @syntax and @evaluate to @semantics
  • The name @evaluate didn't sound right (it's not an interpreter) -- the thought is that syntax + semantics = grammar.
• Add the clause maybe(x) as an alias for first(x, epsilon)
• Regexes can be placed arbitrarily within the parse.

My to-do list:

• @syntax -- postwalk the tree as in @semantics to generate cases; requiring commas in one but not the other is an annoying inconsistency.
• Swap the macro bodge for import PikaParser as $(gensym())`

I've got my commits on the master branch of my fork. When I'm happy with the spit-and-polish of everything, I'll look to building a few branches rebased off your master, so we can have a few PRs and adequate code review for each.

In the meantime, I'll close those early PRs.

[exaexa]

Hi!
that's great, thanks! I didn't have much time to have a look at this yet, so it's still in the queue. Sorry.

random notes:

• maybe sounds OK but perhaps better call it failable or so -- it is not a true "optional" maybe but a PEG-style greedy one, which the first name gets right. That thing is a common pitfall with PEGs. Also, with first(x,epsilon) you're then forced to do if when evaluating the matched alternative number, while you should have this handled in the children nodes (x returns something, and instead of epsilon you use a named parser that returns the appropriate "empty value" for the situation).
• @syntax and @semantics sound great
• great to see that regexes work :)

-mk

[impact-basin]

No worries! All is good :-)

I'm quite happy with the regexes! Here's a snippet from the KDL parser -- will drop it on you soon.

syn = P.@syntax :kdl begin
    # ...

    :hex => seq(
        :sign,
        tokens("0x"),
        r"[0-9a-fA-F]+[0-9a-fA-F_]*",
    ),

    :octal => seq(
        :sign,
        tokens("0o"),
        r"[0-7]+[0-7_]*",
    ),

    :binary => seq(
        :sign,
        tokens("0b"),
        r"[0-1]+[0-1_]*",
    ),

    # ...
end

[impact-basin]

Hey! A few updates -- I've been hacking around a bit and have some good stuff.

The big thing is that @syntax now attempts to call make_grammar() at compile time. This means that Julia can optimise and even precompile outputs from @syntax and @semantics -- nice for any packages downstream. This requires any helpers used to be in the toplevel context of the calling module; if they aren't, we catch the error, emit an (optional) warning, and kick the grammar build to runtime, where variables can be resolved in-scope. Both of these are covered by test cases to ensure no changes overall to macro usage. I've also verified that this works when precompiling downstream packages.

I've also defined an alternate variant of @syntax allowing specification of arbitrary token types; we also process the toplevel rule to allow a single symbol or a list of them.

Likewise, @semantics :top, with no other arguments, will emit an AST tagged with the grammar rules, with elements given by the matched substrings. This is useful when bringing up grammars (to test that they are being parsed correctly), and gives a good starting point for semantics bring-up. As an example, given the "pull-symbols-from-a-string" test-case:

julia> identifiers = P.@syntax :top begin
              :ws    => first(satisfy(isspace), epsilon)
              :ident => r"[a-z_]+[a-z0-9_]*"i
              :decl  => seq(:ident, :ws)
              :top   => some(:decl)
       end
julia> testsemantics = P.@semantics :top 
julia> testsemantics(identifiers(identifiers("foo Bar bA9Z QUx")))
        (:top => Any[
            :decl => Any[:ident => "foo",  :ws => Any[Symbol("ws-1") => " "]],
            :decl => Any[:ident => "Bar",  :ws => Any[Symbol("ws-1") => " "]],
            :decl => Any[:ident => "bA9Z", :ws => Any[Symbol("ws-1") => " "]],
            :decl => Any[:ident => "QUx",  :ws => ""]])

I've also removed maybe(), but added an alternate spelling of epsilon -- ϵ, from \epsilon at the REPL -- to make first(x, ϵ) nice and terse.

The "search-for-PikaParser" hack is now completely gone. Turns out that we can just use @__MODULE__ in macro context to get a binding to PikaParser, and interpolate that into our quoted expressions.

I've also removed the need for commas in @syntax rules, for parsimony with @semantics invocations. Finally, I've added docstrings to @syntax and @semantics, and have refactored the code somewhat to clean things up.

I am getting to the point where I am fairly happy with these macros, and will focus on tests + documentation from here on. I'm giving a talk this week, so I might be a little slow. I'm also going to put a few last touches on a KDL parsing library which makes use of PikaParser, which will be a nice test-case.

Please do have a play if you have the time! Would like to get your thoughts and early feedback; I'm getting the feeling that PRs are approaching.

[impact-basin]

Sorry - one last thought; I still need to handle @precedences and precedence_cascade() correctly. This is still very much on the to-do list!