Can you help me understand how to implement NimbleParsec error handling?

I just watched the talk and it was great! @sasajuric or anyone, do you know a good library to consume from the input and get the line/column as well?

Or do you just do something like this:

defmodule Buffer do
  defstruct text: "", line: 0, column: 0

  def new(text) do
    new(text, 0, 0)
  end

  def new(text, line, column) do
    %__MODULE__{text: text, line: line, column: column}
  end

  def take(%__MODULE{text: text, line: line, column: column}) do
    case text do
      <<?\n, rest::binary>> -> {?\n, new(rest, line + 1, 0)}
      <<char::utf8, rest::binary>> -> {char, new(rest, line, column + 1)}
      "" -> :EOF
    end
  end
end

This is fine, and it’s in fact one reason why I recommend rolling your own combinator, rather than using some of the existing ones. With your own combinator you’re in full control, and you can shape the context to your own particular needs.

My talk is envisioned as a “gentle” introduction, so I oversimplified many things. Don’t treat it as a definitive reference, and feel free to diverge from it wherever it makes sense. For example, as I said in my initial post, parsers such as choice, optional, and many, will lead to uninformative reported errors, so you’ll probably need to invent some alternatives based on a lookahead technique (decide what to do next based on what the next term is).

Given I have the luxury of time I have decided to try and roll my own system of parser combinators along the lines you describe in your video but starting from the principle of providing good error reporting. I’ve made good progress on the simple stuff and will try and separate it from the project and upload to Github so others can comment. If nothing else I hope to come back to Nimble with a better perspective.

One thing I have done, for better or worse, is define a “parser context” struct type that contains among other things the input, position, and term data and that parsers are written in terms of a context rather than a binary input. This slightly complicates the beginning in that you have to wrap the initial input in a context but I think makes it easier to do the right thing later. Please someone tell me if I am making a ghastly mistake here.

If precise error handling is required, I personally wouldn’t use Nimble, except maybe for tokenization.

Hand-rolling a parser for complex languages is definitely feasible. For example see this PR in Gleam where switching to a hand-rolled parser improved error reporting and parsing speed. Also, I recall reading that at some point GCC switched to a hand-rolled recursive-descent parser to improve error reporting.

In cases where the grammar is more involved, I’d probably start with a hand-rolled parser combinator. Being in control of the combinator should provide maximum flexibility, while the parser code should remain readable.

If maximum performance is required, parts of the parser could be converted to manual recursive descent. For example of this technique, take a look at this parser which parses regex-like inputs (input example: "^ENWWW(NEEE|SSE(EE|N))$", full problem description is here).

To better understand this, I advise trying these techniques on a small toy grammar. An arithmetic expression parser which supports parentheses and operator precedence is IMO a great example. You could develop it incrementally, e.g.:

1. Support flat expression with just one operator (e.g. 1+2+34).
2. Add support for ignoring whitespaces
3. Introduce the * operator, and handle operator precedence (e.g. parsing 1 * 2 + 3 * 4 should return something like {+, [{*, [1, 2]}, {*, [3, 4]}}).
4. Add support for parentheses
5. Improve quality of reported errors

Start by implementing this with the recursive descent technique. Then see how could it be done with the combinators. This should help you understand the differences between these two approaches.

As a bonus exercise, try implementing two-pass compiling. This can be done by using e.g. Nimble to convert the original input into a list of tokens (e.g. convert 1 * (2 + 3) into [{:integer, 1}, {:operator, "*"}, {:operator, "("}, ...]), and then converting such list into the final ast. IMO, when grammar is more complex, explicit tokenization pass can do wonders for code readability.

Finally, you can also consider using yecc. IIRC, Elixir parser is based on yecc. Also, absinthe does two-phase parsing, using nimble for the first pass, and yecc for the second.

I understand this may all seem overwhelming, and I barely scratched the surface of the complex topic of parsing So as a final parting advice, I think that starting with a hand-rolled combinator is probably a sensible choice which will give you a lot of control and flexibility, while the code should still be readable. As soon as the grammar becomes more complex, consider doing two-phase parsing, with the first pass powered by e.g. nimble.

That makes sense, thanks, Jose. I’m not sure if I’ve done it right but I think I’ve submitted a PR to clarify the docs.

I’m writing a game definition parser (not a natural language parser) as part of an interactive fiction game engine. So I will be parsing primarily human authored text.

In the first case that text will be written by me and I have a low tolerance for being frustrated by error messages (one of my constant bug bears with Clojure). So error handling & reporting are important to me.

Certainly if I imagine anyone else might use it I think it’s essential that an error message be helpful about the position and likely nature of what is wrong.

My understanding is that Jose has done a lot of work on the resulting parsers to make sure they are very performant. While speed is always welcome I’m not writing a parser for HTTP requests where every microsecond counts.

Is the hand-rolled combinator long-term feasible? What would I regret by forgoing NimbleParsec and hand-rolling as you outlined in your video. It seems pretty easy to get started with, but I wonder what I am missing. I guess there is a way to find out…

Thanks.

Matt

That’s the context returned in:

{:ok, [token], rest, context, position, byte_offset} or
{:error, reason, rest, context, line, byte_offset}

?

At this point, I am not sure how to interact with the context but I generally concur with the idea of replacing maps with structs when you know what the structure should look like.

Is this the key to implementing better error handling? That you adorn the context with more information?

I’m not quite sure what you mean. Are you restating point 1 or do you mean that your context should also only contain structs? That doesn’t seem to be the case in the ZigParser. Can you clarify?

I’m really not sure what guidance you are giving here. All of the combinators are textual matching… I think you are talking about something more subtle? I’ve not used post_traverse so far only map and reduce for converting to lists and maps. Do you have an example of what you are saying not to do?

I confess that I am really not following this at all.

That’s good advice. I am switching from defining helpers as inline variables to functions in a helper module which will, I think, help with that.

Looking at where you are doing this I think it relates to my confusion in the points above. I get the idea that you would raise SyntaxErrors (or possibly “SemanticErrors”) but there is something here about the combinator/context/post_traverse interaction that you are assuming as good practice and I have not grasped yet.

Ah well, beginners mind. If you care to expand on any of your points that would be great but you have, in any case, given me a lot to think about. Thank you.

Matt

I’m going to need a little more time to digest your comments Sasa but I wanted to say thanks for the link to your talk which I just watched and which really helped me to understand what was going on with the combinator approach. It’s not a technique I had used before and I kind of skipped over the underlying concepts in my hurry. Thank you.

Sorry, I was speaking from memory and it seems I misspoke.

Please try this interpretation: the offset in {line, offset} is the offset the current line starts. And the other offset is either the offset to the current line or the offset in comparison to the whole binary. If the latter, you can get the line offset by doing binary_offset - line_offset.

This doesn’t seem to be what I’m seeing. According to file I am parsing a file that is ASCII text but the “line offset” is clearly not referring to a column of that line (e.g. getting a value of 60 something in a line with 10 characters in it). I’ll have to come up with a concrete example later but, I don’t think I am seeing columns.