NimbleParsec - a simple and fast parser combinator for Elixir

I have added support for state. Here is how to implement a simple XML parser with it:

https://github.com/plataformatec/nimble_parsec/blob/master/examples/simple_xml.exs

We can support two new primitives here. One is context_choice which allows you to choose which branch to process based on what is under a given key in the context.

The other one is to allow context keys to be given to times. So you can say “this integer min/max/length will be given by certain key in context”.

Both should be straight-forward to add and are generalizations of primitives we currently have in place. I don’t plan to work on them now but if someone is working on a parser that needs it, please open up an issue with the use case, code examples and rationale and we can find out the best way to handle it.

@josevalim: How about add optional opts?

I prefer to write: rule(term, ignore: true, optional: true) instead of optional(ignore(rule(term))).

For real world example simply compare my version with its original form from README.md:

defmodule MyParser do
  import NimbleParsec

  date =
    integer(4)
    |> literal("-", ignore: true)
    |> integer(2)
    |> literal("-", ignore: true)
    |> integer(2)

  time =
    integer(2)
    |> literal(":", ignore: true)
    |> integer(2)
    |> literal(":", ignore: true)
    |> integer(2)
    |> literal("Z", optional: true)

  defparsec :datetime, date |> literal("T", ignore: true) |> concat(time), debug: true
end

I know that’s extra work for you, but at least for me code will look much cleaner.

defmodule NimbleParsec do
  @moduledoc "README.md"
             |> File.read!()
             |> String.split("<!-- MDOC !-->")
             |> Enum.fetch!(1)

Where has this been my whole life?

Yep, that’s the traditional way in the original Spirit. Though it’s syntax makes it shorter than the same in Elixir.

And the ability to pass state as arguments to the parsers… ^.^;

A few issues:

First, the length, all of this in Nimble:

  text =
    ascii_char(not: ?<)
    |> repeat(ascii_char(not: ?<))
    |> reduce({List, :to_string, []})

Is this in ExSpirit:

  defrule text( chars(-?<) )

And this in Nimble:

  letter = ascii_char([?a..?z, ?A..?Z])
  tag = letter |> repeat(letter) |> reduce({List, :to_string, []})

Is this in ExSpirit:

  defrule tag_name( chars([?a..?z, ?A..?Z, ?0..?9, ?_, ?-]) )

And this in Nimble:

  opening_tag =
    ignore(string("<"))
    |> concat(tag)
    |> ignore(string(">"))

  closing_tag =
    ignore(string("</"))
    |> concat(tag)
    |> ignore(string(">"))

  defparsec :__xml__,
            opening_tag
            |> traverse(:store_tag_in_context)
            |> repeat_until(
              choice([
                parsec(:__xml__),
                text
              ]),
              [string("</")]
            )
            |> wrap()
            |> concat(closing_tag)
            |> traverse(:check_close_tag_and_emit_tag)

  defp store_tag_in_context([tag], %{tags: tags} = context, _line, _offset) do
    {[tag], %{context | tags: [tag | tags]}}
  end

  defp check_close_tag_and_emit_tag([closing, [opening | contents]], context, _line, _offset) do
    if closing == opening do
      context = update_in(context.tags, &tl/1)

      element =
        case contents do
          [text] -> {String.to_atom(opening), [], text}
          nodes -> {String.to_atom(opening), [], nodes}
        end

      {[element], context}
    else
      {:error, "closing tag #{inspect(closing)} did not match opening tag #{inspect(opening)}"}
    end
  end
end

Is just this in ExSpirit:

  defrule tag(
    lit(?<) |> tag_name() |> put_state(:tagname, :result) |> lit(?>) |> expect(seq([
      get_state_into(:tagname, tag(&1, repeat(node_()))),
      lit("</"), get_state_into(:tagname, lit(&1)), lit(?>)
    ]))
  )

  defrule node_(
    alt([
      tag(),
      text(),
    ])
  )

In addition, though this is an example, it was demonstrating features that, though easy to bypass in this example (you can do it in ExSpirit the same way you did in Nimble), is not bypassable in many other cases. Specifically this line in ExSpirit:

get_state_into(:tagname, lit(&1))

How would this be done in Nimble, your example does not demonstrate this thus your example is not a faithful recreation. This specific expression, though in this case can be done by comparing ‘later’, this shows that you can parameterize parsers based on prior parsed data, and this is what I’ve set to see how you could do it in Nimble as this is an absolutely mandatory capability that a lot of languages need to parse else the parser can become infinitely large in order to handle all possible variants.

Like to make it slightly more complex (though still not infinitely configurable as some languages get), how would you parse the xml example of <foo><bar>one<baz>two</foo> as if it were <foo><bar>one<baz>two</baz></bar></foo>? In ExSpirit that would involve changing this:

      lit("</"), get_state_into(:tagname, lit(&1)), lit(?>)

To be something like (although format it better of course):

      alt([lit("</"), get_state_into(:tagname, lit(&1)), lit(?>), success()])

And then you get nice auto-closing tags when left open, and yet it still fails if there is a mismatched closing tag.

Also, these two cases in your parse call:

      {:ok, _, rest, %{tags: []}, line, offset} ->
        {:error, "document continued after last closing tag", rest, line, offset}

      {:ok, _, rest, %{tags: [tag | _]}, line, offset} ->
        {:error, "tag #{inspect(tag)} was not closed", rest, line, offset}

How would you enforce those as part of the grammar? In ExSpirit for the first you just add an eoi() (and an alternate fail("reason") if you want a customized message) at the end, and for the second, well, that’s already an error in ExSpirit, like why does that parse at all in Nimble as it really absolutely should not (not as big of an issue for something trivial like SimpleXML but a larger issue when you have complex grammars that need to be self-terminating based on state information).

For comparison, here’s how you make SimpleAST in the original Spirit:

        text = lexeme[+(char_ - '<')        [_val += _1]];
        node = (xml | text)                 [_val = _1];

        start_tag =
                '<'
            >>  !lit('/')
            >>  lexeme[+(char_ - '>')       [_val += _1]]
            >>  '>'
        ;

        end_tag =
                "</"
            >>  string(_r1)
            >>  '>'
        ;

        xml =
                start_tag                   [at_c<0>(_val) = _1]
            >>  *node                       [push_back(at_c<1>(_val), _1)]
            >>  end_tag(at_c<0>(_val))
        ;

And yes, that is entire pure and valid C++, no preprocessor or anything of the sort needed, consequently @tmbb you see how the local state it uses has to be passed up and down through the parsers? And yes, it will generate code that is at least on par but usually better than hand-rolling your own parser in any language, even assembly, without substantial work (and even with that work you will only get on par with Spirit in speed, literally if you find any time where spirit is slower than anything else it can optimize for that and fix it, that is part of it’s design, which I did not follow in ExSpirit for a quick whipping up, though the expression version would be better at it).

That is not as useful though, need to pass state into the parser arguments to be able to parse many language grammars, else you end up with infinite parser variations required (or falling back to multiple passes and more code and mis-matched errors with the parsers and all that).

It would not just be times, you’d have to allow passing state as an argument to an any parser to really allow it in full (which the original spirit allows for and ExSpirit allows for in ‘most’ cases, though not all…)

Eh, it might be nicer but generalizing that to everything everyone might possibly make sounds a bit irritating since in his design they are all just functions and not a built expression tree like the C++ spirit is).

Lol! Just module attributes so you can do whatever. ^.^

Also another thing, how do you define a skip parser in Nimble? Or do you have to add the skip parser to every-single-possible-rule-and-skippable-location-which-is-utterly-ginormous-in-count?

Not planned. You can easily wrap it though!

As the name of the library says, my plan is to stay nimble and not focus in providing high level constructs. The fact it allows runtime composition and the focus on primitives mean you should be able to build chars and text yourself, like I did. Put those in a module as regular functions and you will be able to use them as if they were part of nimble.

To clarify, I was not trying to recreate ex_spirit parser here. I haven’t checked its implementation. In any case, what you proposed can be implemented with traverse, which receives the context and can return the accumulator and a possibly updated context.

It can be done by using traverse as well but it should be easy to add a lookahead construct too.

I don’t think this will ever be possible. All combinators are compiled down to function clauses. A combinator cannot be used with state information unless the underlying combinator has been taught to read from state. Which goes back to the point I want to rather focus on the small set of primitives, making them powerful enough to build everything else on top of it.

I mentioned this in the issues tracker but getting a traditional parser combinator and translating it to NimbleParsec is not going to work. I am pretty sure the C++ implementation is faster and more flexible than NimbleParsec but for nimble we need to stay within the rules of the Erlang VM. That’s why I am more interested in particular examples we cannot handle than a particular feature, because when all is said and done, the feature may need to be implemented in completely different way in nimble.

v0.2.0 is out with lookahead, user contexts, custom errors, byte offsets and ascii_string/3 and utf8_string/3. See the CHANGELOG:

https://github.com/plataformatec/nimble_parsec/blob/master/CHANGELOG.md

Cool. I’ll start rewriting my Elixir lexer directly in nimble_parsec. Then, when I see anything worth refactoring into its own module, I’ll start porting Makeup to see if it can be based on nimble_parsec (Makeup is basically a library of useful combinators that can be reused between languages + some plumbing so that the entire chain from lexer to formatter works.

This might take some time, especially because there isn’t a 1-to-1 mapping between ExSpirit combinators and NimbleParsec combinators.

I will be very glad to help if you have any questions or you need help translating some constructs!

Also, maybe a good suggestion is to start with the smaller language you currently handle. So we can directly compare compile and execution times.