I appreciate the suggestion - and I’ve tried all manner of ordering without success. I can’t seen a way to avoid needing some kind of forcing backtracking (failing a parser in my post above).
kip
ex_cldr Core Team
0
josevalim
Creator of Elixir
A very quick suggestion is to unfold the ABNF grammar into complete combinators and then refactor it. IIRC ABNF is able of tracking back multiple levels but nimble isn’t, so you need to restructure the problem. The math example shows how the solutions end-up a bit different.
The other thing I noticed is that you are excessively relying on parsec. You should compose on the helpers as much as possible and fallback to combinators only if compilation times are high.
1
tmbb
I second @josevalim here. If you use regular combinators, the parser will be measurably faster, although it will be slower to compile. By using parsec excessively you WILL decrease runtime performance (although it might be worh it if compile times are too high).
0
kip
ex_cldr Core Team
Appreciate the feedback @josevalim and @tmbb. Moved everything to helpers except the entry point. Shows about 30% performance improvement (in a non scientific timer test). I’ll try some grammar unrolling this weekend to see if I can work around my original issue.
1
tmbb
I have written a small library to make such tests as scientific as possible and as easy as possible. It’s called schism, and it’s available on Github here (no hex package yet): GitHub - tmbb/schism: A library that makes it easy to have alternative implementation of functions for benchmarks · GitHub
There is a post discussing it here in the forum: Schism - a library to make benchmarking easy (and heretical!)
Basically, it uses some macros to define alternative versions of code fragments (function definitions, parts of function definitions, etc). It then provides some utilities to make it easier to benchmark the changes with Benchee.
You use it like this:
defmodule YourModule do
# Some code, don't need to touch here
# The code here is the same for both versions
schism "inline vs parsec" do
dogma "parsec" do
# single combinator, coded in such a way that it uses parsec
end
heresy "inline" do
# same combinator, but avoiding parsec
end
end
# some more code..
# The code here is the same for both versions
end
With benchee you can then compare the dogma and the heresy and determine objectively what is faster. This is obviously something you can do yourself, but the beauty of it is that it provides a very simple API with almost no friction to test the impact of small changes in single functions on the performance of the whole application, without having to maintain two copies of the application.
EDIT: are you afraid the two implementations of the function are not compatible? Don’t worry, the defsnippet macro in the Schism package handles that situation pretty well. For what it’s worth, Schism was originally written to benchmark alternative implementations of nimble_parsec parsers.
4
kip
ex_cldr Core Team
Thats very cool and I can’t believe I missed it when you posted in April. Thanks for the assist! And now back to grammar unrolling … 
0
kip
ex_cldr Core Team
I ran a benchee example of my old parser and the new one using nimble_parsec with only one parsec/1 call. The old one used an ABNF parser (and the even older one used leex and yecc). Really positive results:
Old version: Average of 163.87 μs
Nimble_parsec version: Average of 28.40 μs
I think ~6 times faster was worth the evenings work . Thanks again @josevalim and @tmbb
1
tmbb
kip
ex_cldr Core Team
Not this time - the dependencies are different (abnf2 which I maintain and nimble_parsec). But for sure its going to be a standard part of my performance improvement activities from now on.
0
mjadczak
Note: I initially wrote this as an issue on the repo, but I thought it might be better served by being a forum post, as it turned out quite long, and may invite discussion.
@josevalim, let me first start by saying thanks for making this library. I really like the combination of just creating a data structure describing the parser using functions (thus avoiding excessive macro magic and making things as composable as possible), but then—instead of interpreting that structure at runtime—compiling it into efficient code.
While this isn’t explicitly mentioned anywhere in the project docs, the overall style of the library plus the reference to Parsec suggests that the underlying idea (whether originally intentional or not) is to do PEG-style parsing. Even if it’s not an exact implementation of PEG, it would be reasonable to expect that NimbleParsec should be equal in “parsing power”, if you will, to a PEG parser—that is, admit any languages which a PEG parser does.
If you look, for instance, at Wikipedia’s definition of a PEG, you will see the following combinators mentioned as fundamental operators (you can technically get away with fewer, but it starts to get impractical to implement), and most of these do resemble constructs NimbleParsec has:
- Sequence—either
concat/2or the first argument of a combinator - Ordered choice—
choice/2implements this - Zero-or-more—
repeat/2 - One-or-more—
times/3withmin: 1
However, then you come to these:
- And-predicate (
&) - Not-predicate (
!)
These are the two predicates which denote positive and negative lookahead. Put simply, & asserts that the parser it wraps matches, and ! asserts that the parser it wraps does not match. Crucially, they don’t consume any input. Say that we call them require and deny for the purposes of NimbleParsec. That means that require(string("foo")) |> utf8_string([], min: 3) would parse in any string starting in “foo”, and deny(utf8_char([?0..?9])) |> utf8_string([], min: 1) would parse any string not starting with a digit.
N.B. technically you only need !, since for any parser p, !!p == &p in behaviour, but explicitly implementing & is likely to be more efficient.
Why is proper lookahead support needed?
I know most requests of the form “we should implement a new combinator in NimbleParsec” are met with the response of “this library is supposed to be barebones, and you should make your own combinators”, as well as “what is the particular usecase”? Therefore, I aim to show a couple of grammars which I believe NimbleParsec cannot currently parse properly, but which would be useful to support, and how they could be supported if require and unless are implemented.
N.B. I am not tied to the names require/2 and deny/2—they were the first I though of which seemed to fit in with the existing naming theme.
Keywords and identifiers
Let’s imagine we’re parsing a super simple programming language. For now, we only need to care about keywords (let’s say if and while) and identifiers (let’s say any string at all in the range of [a-zA-Z0-9]).
Great, let’s get started! We go ahead and write some code like this:
defmodule NPL.Helpers do
import NimbleParsec
def keyword(c \\ empty()),
do:
c
|> choice([
string("if") |> replace(:if),
string("while") |> replace(:while)
])
|> tag(:kw)
def identifier(c \\ empty()), do: c |> utf8_string([?a..?z, ?A..?Z, ?0..?9], min: 1) |> tag(:id)
def expr_(),
do:
choice([
keyword(),
identifier()
])
|> optional(string(" ") |> ignore() |> expr())
def expr(c \\ empty()), do: c |> parsec(:expr)
end
defmodule NPL do
import NimbleParsec
import NPL.Helpers
defparsec(
:expr,
expr_()
)
end
Let’s test it:
iex(1)> import NPL
NPL
iex(2)> expr "if"
{:ok, [kw: [:if]], "", %{}, {1, 0}, 2}
iex(3)> expr "foo"
{:ok, [id: ["foo"]], "", %{}, {1, 0}, 3}
iex(4)> expr "foo if"
{:ok, [id: ["foo"], kw: [:if]], "", %{}, {1, 0}, 6}
Seems like it works fine!
iex(5)> expr "iffy"
{:ok, [kw: [:if]], "fy", %{}, {1, 0}, 2}
Uh… no, we wanted that to just be identifier. Now we have a keyboard and a failed parse for the rest of the input. Maybe if we switch the order of the choice around?
def expr_(),
do:
choice([
identifier(),
keyword()
])
|> optional(string(" ") |> ignore() |> expr())
iex(2)> expr "iffy"
{:ok, [id: ["iffy"]], "", %{}, {1, 0}, 4}
iex(3)> expr "if"
{:ok, [id: ["if"]], "", %{}, {1, 0}, 2}
Now identifiers which have a keyword prefix are parsed fine, but we no longer recognise keywords as keywords!
Units
You might say “NimbleParsec was really designed for much simpler parsing—language codes, CSV maybe, simple formats, not full on languages!” Fine, let’s tackle a much simpler problem: parsing measurement units. Let’s define a parser like this:
defmodule NPT.Helpers do
import NimbleParsec
def metric(c \\ empty()),
do:
c
|> choice([
string("mol"),
string("l"),
string("m"),
string("g")
])
|> label("metric base unit")
def datetime(c \\ empty()),
do:
c
|> choice([
string("yr"),
string("mo"),
string("wk"),
string("d"),
string("h")
])
|> label("temporal unit")
def prefix(c \\ empty()),
do:
c
|> choice([
string("m"),
string("k"),
string("c")
])
|> label("metric prefix")
def unit(c \\ empty()),
do:
choice([
datetime() |> tag(:datetime),
metric() |> tag(:metric),
prefix() |> tag(:prefix) |> metric() |> tag(:metric)
])
end
defmodule NPT do
import NimbleParsec
import NPT.Helpers
defparsec(
:parse_unit,
unit()
)
end
iex(1)> parse_unit "m"
{:ok, [metric: ["m"]], "", %{}, {1, 0}, 1}
iex(2)> parse_unit "mol"
{:ok, [datetime: ["mo"]], "l", %{}, {1, 0}, 2}
iex(3)> parse_unit "ml"
{:ok, [metric: ["m"]], "l", %{}, {1, 0}, 1}
It’s the same issue!
It turns out that PEG parsers (which is how NimbleParsec is acting), in contrast to, for instance, regular expressions, are greedy and don’t backtrack. If we have a choice between several underlying parsers, and one of them parses a prefix of the other, we will always have issues. PEG gives us a great deal of control over how exactly parsing takes place, but this also requires us to be very specific where the parser needs to be careful—that is, where it needs to check ahead without consuming any input, so it can make a decision on how to consume further input (PEGs are linear, so once the output is consumed, there’s no going back! In NimbleParsec, once the output is consumed, we have tail-recursed and there is no way to go back!)
Why is lookahead/2 not enough?
This issue has been mentioned on the repo, and as a response, the lookahead/2 function has been implemented. Let’s try fixing our keyword parser using the function, and let’s add a couple more parsecs just for the individual types of objects we have in our grammar, to help with debugging.
Our goal here is to try to say “when we’re trying to parse an identifier, first check if the next token up to a space is a keyword. If so, fail the parse (with the expectation that when in a choice block, this would cause the next choice to be taken).”
...
def identifier(c \\ empty()),
do:
c
|> lookahead(:fail_on_keyword)
|> utf8_string([?a..?z, ?A..?Z, ?0..?9], min: 1)
|> tag(:id)
...
def fail_on_keyword("if " <> _, _, _, _), do: {:error, "if found"}
def fail_on_keyword("while " <> _, _, _, _), do: {:error, "if found"}
def fail_on_keyword(_, ctx, _, _), do: {[], ctx}
...
defparsec(
:keyword,
keyword()
)
defparsec(
:identifier,
identifier()
)
Right off the bat, we see one immediate issue with lookahead/2: it’s not a composable combinator, but rather some sort of halfway measure, where we need to define a separate function for each little thing we want to check. We also need to ensure this extra function is accessible in the module which defines the parsec! We can’t just easily re-use our existing combinators, we’d need to have a separate function call and explicitly call another parsec within it, and return :error or :ok based on whether it succeeds. That’s quite unergonomic, but perhaps could be solved to some degree with a quoted_lookahead. Nevertheless, let’s try our new solution out:
iex(2)> keyword "if"
{:ok, [kw: [:if]], "", %{}, {1, 0}, 2}
iex(3)> identifier "iffy"
{:ok, [id: ["iffy"]], "", %{}, {1, 0}, 4}
iex(4)> identifier "if "
{:error, "if found", "if ", %{}, {1, 0}, 0}
Seems like our individual parsers are working ok. Now, let’s try their combination:
iex(6)> expr "if foo"
{:error, "if found", "if foo", %{}, {1, 0}, 0}
And no, this doesn’t work. Even if you ignore the ergonomic issues around lookahead, its fundamental shortcoming is the fact that it doesn’t compose—when it fails inside a choice or repeat block, the failure leaks to the top level of the parser, instead of causing the parent parser to stop looking at that branch and continue.
Proposed solution
Revisiting the keyword example one more time, I think that you should be able to write something like this:
def id_char(c \\ empty()), do: c |> utf8_char([?a..?z, ?A..?Z, ?0..?9])
def keyword(c \\ empty()),
do:
c
|> choice([
string("if") |> replace(:if),
string("while") |> replace(:while)
])
|> deny(id_char())
|> tag(:kw)
# ignore things like actually joining this into a string
def identifier(c \\ empty()),
do:
c
|> times(id_char(), min: 1)
|> tag(:id)
In fact, adding deny (and having repeat handle it properly) would allow repeat_until to be removed, since it could be written like this:
def repeat_until(c \\ empty(), to_repeat, until),
do:
c
|> repeat(
deny(until())
|> to_repeat()
)
As for implementation, it seems to me reading through the compiler code that failed parsers are already specially handled in some cases, but not all (I’m referring to the catch_all piece of config which is passed around. I believe that for all parsers (bound and unbound), both repeat and choice should respect the failure or success of them. Implementing require and deny will require making a stack frame at the point they are invoked (since we need to be able to get back to the state of the binary, accumulator etc right before we called them), which is unavoidable, but we still retain great efficiency and tail recursion for the majority of the code (we only make extra stack frames in specific places, unlike a full backtracking parser, which needs to keep the full stack around).
Please let me know what you think about this—I’m pretty certain that what I described cannot currently be achieved generally with NimbleParsec, but if I misunderstood how it works somewhere, please let me know. I think implementing this feature would greatly aid the library on its way to be a powerful set of primitives with which fully-featured parsers can be built.
Side note: failures vs errors
While not necessary for more parsing power, it would be useful to distinguish between failures (this parser failed, but it it’s in a choice or repeat then try the next choice / stop the repeat) and errors (something unrecoverable was seen, fail right away and show the user an error) in order to allow better error messages to be reported back to the users. Of course, this would need to come after all errors are actually handled consistently as proposed above, and is probably a separate discussion. This paper gives a good overview of how some other parsers handle this and what advantages it has.
3