NimbleParsec - a simple and fast parser combinator for Elixir

Whooo thank you! That looks like the expression based generator output I had started to write! Whooo! I do not want to have to manage more libraries than I have to so I’m glad to have a better one out, thank you! ^.^

A few questions before I delve too far in:

Upon output and errors does it give at the very least the byte location, UTF-8 column, UTF-8 line, and the rest of the stream itself?

How’s its error handling, detailed errors? Line/Column info and all? Is it 1-based or 0-based?

For one of my own projects I really do need to parse very weird integral bases (which is why ex_spirit supports bases from 2 all the way up to base 36), does it support these (and are they chooseable based on prior parsed data instead of having to hardcode all variants, I was fixing that bit in my expression based parser but not got around to it yet)?

Is there any way of passing parsing state through the parser (the ‘state’ functions in ex_spirit) as those are pretty well required for most of the things I write and what can they effect?

I.E. All functionality currently in ex_spirit is functionality that I’ve needed so far so I’d need equivalent methods to be able to replace it, is all such functionality possible in nimble?

P.S. I love how you name things NimbleSomething. ^.^

EDIT: I see it removes the context map. The map itself was definitely a bit of the slow down in mine and I really wanted to remove it, but it made it just so convenient to use. How can state be stored and matched against?

Like the examples at:

How would all of those be done in nimble?

We don’t give the byte location. We do give UTF-8 line and column.

Yes. We also build an error message from labels and the combinators themselves.

I am not quite sure what you mean but if you annotate each token properly, you have all of the information that you need that then can be reduced into a final result with reduce/3.

Thank you!

The map is not the issue as long as you guarantee the first argument is the binary and you avoid referencing it outside of a tail recursion or a pattern match.

I have no idea!

Btw, I have one question. It annoys me that the tokens emitted by the parser do not contain the line+column information. But none of the parser combinator libraries seem to do it by default. How do you tackle this in ex_spirit?

Good enough for me. Actually, for my purposes there are no parse errors (Makeup lexers should consume every binary passed as an argument)

This is definitely not the same thing. You can’t parse context-sensitive languages without storing the context somewhere. You’d have to change the grammar into something that’s context-free either in a preprocessing stage or at a later stage. For example, how would you, using nimble write a parser that would detect when a line is less indented than the previous line? For example, this bit of python code:

def f(x):
    if x > 0:
        return x
    else:
        return -x

Blocks are dictated by indentation, so you need to store the indentation stack somewhere and compare it with the current indentation level. With ExSpirit, it’s trivial to write indent() and dedent() parsers that recognize this (so that you can match a block as indent() |> block() |> dedent() or something like that). AFAIK, you can’t do this if you don’t store the context somewhere. This is not a showstopper for many applications, but when you need these kinds of context-dependent parser, you really need them.

(Actually the Python parser is context-free; During a preprocessing stage, the lexer introduces some special INDENT and DEDENT tokens which can be matched by the parser as if they were matching parenthesis)

So yeah, if you apply arbitrary transformations to your string before or after parsing you don’t need the context, but in some cases it might be simpler to just keep a context.

What API do you propose for that? Doing this kind of thing by default is kinda hard… Which tokens would you want to tag? what is a token?

You don’t. ExSpirit doesn’t handle this by default. It’s trivial to define a parser combinator that does it, though. You just take the old context (before running the inner parser) and the new context (after running the inner parser), and this will give you old_position and new_position with which you can annotate the token if you wish. In ExSpirit you can do it like this: ExSpirit.Parser – ex_spirit v0.4.0

I think this does require first-class access to the context map (in your case a tuple, although a record might be even better).

How hard is this to add? I can think of some uses for that (and I can elaborate on that, but first I’d like to study nimble’s internals)

Could you elaborate on this? If the code compiled at runtime? This doesn’t make much sense, especially because later you claim that Nimble leaves no trace on your modules after compilation.

I give a byte location as well in mine because a couple of times I needed grab a range of the binary from a before/after and that makes it O(1) instead of O(N) that just a line/column would allow for because UTF-8.

Like take the XML mini-parser in the example, it confirms the open tag matches the closing tag by holding the state (name) of the open tag. The example will fail to parse if that doesn’t match but I could, for example, default to self-creating a close tag if there is a mismatch if I so wanted. Binding holding is significantly useful for a LOT of stuff and I use it rather excessively… >.>

Compare that to just parsing out the tags straight means you have to make ‘yet another parse step’ over your output from the parser, and at that point you are basically using it as a tokenizer instead of a full modern style PEG parser.

Yeah that is how the BEAM is built, unfortunately Elixir is built to support piping into the first argument instead of the last argument, which contrasts to what I wanted in the system… ^.^;

Lol, those are very basic simple tests that, honestly, don’t use near the functionality that I needed, but at the very least they need to be supported… ^.^;

Pretty trivially. In ex_spirit I don’t do it by default because I can’t know what form the user wants it in and I HATE FURGIN HATE when a parser library only outputs in a specific format instead of the AST that I want. That is the purpose of the Spirit style, that you can parse out into the exact output format that you want all at the same time without getting those irritating multiple parsing steps from format to format especially when the ‘way’ you want to parse may change based on information that you have parsed from before ‘after’ you have massaged it into the needed format, like the XML example is the absolute barest form of an example of that.

Consequently, that is why I have the map_around and map_context_around and other various mapping forms. In the original C++ Version of Spirit this was handled via nice overloading (things like (uint_ >> ':' >> uint_) [tagger_] in ExSpirit’ese would be something like map_context(seq([uint(), lit(?:), uint_], &tagger/1)), and just like in the C++ version how you can put the [...] on any rule part, you can put the map-parts on any part in Elixir too. I come with a basic tag/3 call Ex-Spirit to wrap it in a 2-tuple (for easy migration from more leex’y style things), but I could easily make one called, oh, ast or whatever that puts them in an Elixir style 3-tuple with whatever position information is wanted, but I do not assume what form is wanted so the user should make their own function for it, which is pretty trivial to do, like the ast form the user could just define something like this that will put in the line/column and auto-set the tag name based on the defrule name:

      def ast(%{error: nil, result: result, rulestack: [name | _]} = context) do
        %{ context |
          result: {name ||, [line: context.line, column: context.column], result}
        }
      end
      def ast(context) do
        context
      end

Then just use it like:

defrule blah(
  ), fun: ast()

And of course you could pass the name into the ast() call if you wanted, or make it optional or whatever. But at this point you just add that , fun: ast() to the defrules.

Yeah for parsing elixir that would entirely be fine.

Yep, this is the state. Like knowing whether you are parsing an expression that resolve to an integer compared to a string may change how you parse next, this is the requirement of state.

Which of course you can’t do if you don’t control the language that you are parsing… ^.^;

This is also the same thing as the XML parser example I linked in my prior post.

And this was a big reason C++ Spirit was created, and why I use it so much.

Yeah the official python parser has multiple stages. To do it all in one stage you have to hold the context somewhere.

Ah yep here, cannot assume a form of how you want it to output. Like C++'s and My Spirit libraries can output everything from a literal token stream just like any other tokanizer all the way up to an AST to even performing, say, interpretation of a language as it runs it (say a lisp’y language). One of the examples of the C++ Spirit is writing a calculator, first they write it as an AST, then they wrote it again where it actually calculates the output ‘as’ it parses, so the final result is not an AST but rather the actual answer, no AST is needed, nothing needs to be held but a simple number at each recursion and it is blazing fast in C++.

Yeah the pipe_context_around/3 is what you’d use instead if you want both the before and after contexts so you can record a ‘range’ (which is where storing the byte locations is VERY useful because then you can simply binary split it or match out the specific range to store, or just store the byte locations which is O(1) instead of O(N) of handling the lines/columns). Or using the state system you can store the byte location (or binary location and the byte to get a range) at the start of the rule and use that in the fun/1 on the defrule to grab the location information. There are many ways to handle it, all depends on whatever fits best in to your style and what you are parsing.

Yeah if you want to grab a range from the binary to hold as, say, location data, the byte is SIGNIFICANTLY faster (O(1) again) compared to just using the line/column (O(N)).

@tmbb His parser is working a LOT like my expression parser was going to work, it’d be able to generate all it needs directly, that is what his one defparsec call does, transforms the expressions into the reified code, he just saved me the work of doing it since I’ve been too busy to implement it thus far… ^.^;

I think it’s because it doesn’t leave a trace in that it doesn’t leave any calls ‘into’ his library once it’s made (well, mine doesn’t either except for the Context __struct__ name), but rather it generates efficient functions directly (where the current/old version of ExSpirit was relying on optimizations at the BEAM level instead, where the new expression style version was generating everything directly as NimbleParsec is doing).

Also blah! I forgot to git push the updated ex_spirit to github, so hex is more updated than it, and my work ssh pipe is not responding (and I’m not going to be back at work until next wednesday/thursday due to real-life reasons).

I could drop by this weekend and use my key to get in if it’s really wanted for me to upload it to github (hmm, or I could rip out the parts from the hex package as that contains all the changes too…).

Also an example of holding the byte location is that it makes parsers like lexeme trivial to implement.

I’m not actually sure how to implement that parser in NimbleParsec from what I’m looking at actually… How would you implement lexeme (it’s a parser I use a LOT).

Everything currently in ExSpirit is something I use, so at the very least all of it would need to be reproduceable.

Also notice that all of ExSpirit a user can replicate and write themselves if they so wish as well, it is highly extensible (which is one of the issues I was running into when I started on the expression parser, I could still make it extendable, just not near as easily for the user…).

Yes, that’s eaxctly why having byte positions is useful. I might need this for makeup lexers that feature a language embedded inside the other, like EEx: I must slice the input string, feed it into different subparsers, solit the token streams and stitch them again in the rigt order. Byte offsets make splitting these strings easier.

Buy writing a combinator that takes up the previous and the next context and extracts the relevant number of bytes (admittedly very hard if nimble doesn’t support byte offsets). I’m not sure you can access the previous and next context tuples (analogous to exSpirit’s map)