I’ll admit that I haven’t thought this through completely, but would it not be possible to implement something like the n:x,x,x,x,x case by first reading n, putting the parsed integer into the parser state (the context), and then simply having a construct which looked something like this: put_0_into_context_as_x() |> repeat(assert_x_less_than_n() |> integer() |> increment_x_in_context()), therefore using dynamic state to fail or succeed a parser dynamically, but not actually generating any new parsing trees at runtime? In general, for more dynamic things, you could also generate a choice some of whose clauses would fail immediately depending on the current context. It seems at least like a lot of common cases could be implemented like this but perhaps I’m missing some limitation.
mjadczak
tmbb
You don’t have to generate new parse trees at runtime. You just have to return a combinator at runtime. I really hope you can do that without generating and compiling an entire parsing tree! My idea (maybe I didn’t explain myself properly) didn’t generate a tree at runtime. It would generate a tree at compile time and compile that into a higher order function which returns a combinator. Or something like that.
I’d like to avoid solutions of the form “a lot of common cases”, because if you’re working only on the common cases you might be locking yourself into a place you can’t escape later. I’m a little short on time, but my basic idea is the following:
-
Write a version of
post_traverse, which returns a “full” result tuple, not only a{acc, context}pair. That is, turnpost_traverseinto something closer to a normal combinator -
That means it could consume input based on the function passed as an argument (which it can’t do now!)
-
Because the function you pass into
post_traversecan be literally anything, you can then implement this functionality as “user-level” code outside ofnimble_parsec.
The way you implement that is not very relevant. The most important is thatyou’d have an avenue to explore compilation of context-sensitive parsers without any changes to nimble_parsec’s core. At least that’s the basic idea, I don’t have the time to code it right now. EDIT: I’m actually a little sleep deprived, so just because this seems like a good idea it doesn’t mean it’s actually a good idea.
josevalim
Yeah… that’s a no-no because it pretty much defeats the point of NimbleParsec. 
I am pretty sure I said this before but I don’t mind it. But let’s be honest here, your hand-written example is not really shorter than NimbleParsec’s. The NimbleParsec one was written with readability in mind. If we inline NimbleParsec’s code (using a similar style to yours) and run the formatter on both, NimbleParsec is definitely shorter. And if we update NimbleParsec to also use the new eos stuff and what not, then it comes down to this:
defmodule SimpleXML do
import NimbleParsec
def parse(xml, opts \\ []) do
opts = Keyword.put(opts, :context, %{tags: []})
xml(xml, opts)
end
tag = ascii_string([?a..?z, ?A..?Z], min: 1)
text = ascii_string([not: ?<], min: 1)
opening_tag = ignore(string("<")) |> concat(tag) |> ignore(string(">"))
closing_tag = ignore(string("</")) |> concat(tag) |> ignore(string(">"))
defcombinatorp :node,
opening_tag
|> post_traverse(:store_tag_in_context)
|> repeat(lookahead_not(string("</")) |> choice([parsec(:node), text]))
|> wrap()
|> concat(closing_tag)
|> post_traverse(:check_close_tag_and_emit_tag)
defparsec :xml, parsec(:node) |> eos()
defp store_tag_in_context(_rest, [tag], %{tags: tags} = context, _line, _offset),
do: {[tag], %{context | tags: [tag | tags]}}
defp check_close_tag_and_emit_tag(_rest, [tag, [tag | contents]], context, _line, _offset) do
context = update_in(context.tags, &tl/1)
text_or_nodes = if match?([_], contents), do: hd(contents), else: contents
{[{String.to_atom(tag), [], text_or_nodes}], context}
end
defp check_close_tag_and_emit_tag(_rest, [opening, [closing | _]], _context, _line, _offset),
do: {:error, "closing tag #{inspect(closing)} did not match opening tag #{inspect(opening)}"}
end
Although I wouldn’t personally write in the style above.
But of course, the ExSpirit one is remarkably concise, which is expected as the libs have different goals.
tmbb
Maybe, BUT this is just for the context-sensitive combinators. I believe that this can be made to work without any changes to the “normal” combinator. It makes sense to me that stateful parsing will be less efficient than the highlght optimized things that NimbleParsec does now. That’s the cost of having a more powerful parser.
As long as this doesn’t make the rest of NimbleParsec less efficient, I think it would make sense to include it. But my bet is that you wouldn’t need to. I think I can add a new combinator to NimbleParsec which will allow users to implement context-sensitive parsers without any changes to NimbleParsec.
Also, don’t think of “interpreting the parser” as something very slow and inefficient. You don’t need to interpret the parsing tree at runtime (I hope…). As @OvermindDL1 said, it might just cost the same as a function call, which is perfectly acceptable.
josevalim
Maybe I am completely missing the approach you have in mind but NimbleParsec emits function clauses. To evaluate them, you would need to either transform those clauses into cases and control the state machine yourself OR write a hand-written evaluator for each combinator.
If we are interested in going in this direction, then I would rather try the approach I mentioned earlier, where we teach each existing combinator how to read things from context, because that would definitely be less work. So you could do: times(..., min: :context_key) and we get the min from the context, which would mix well with the dynamic combinator proposed earlier.
EDIT: You can also always define your custom functions too, that don’t know about nimble_parsec at all, and hook them in with the parsec(:function_name) combinator.
tmbb
I’m aware of that. That’s why you’d have to expand the AST inside a macro so that the macro could compile the AST into something else, instead of function clauses remember that anything given to a macro can be expanded and compiled into something else. Although there might be sole problems with variable contexts, ao maybe this is not a good idea at all…
You’re probably right. Although I suggest a more “typesafe” approach in which you write something like this:
times(..., min: from_context(:key))
And even something like:
times(..., min: from_context(:key, fn k -> ... end))
The from_context/2 function would just return a tuple which the parsec compiler would know how to handle and compile.
Which transforms the results prior to useing them. This is very similar to what I do in vampyre! In both cases one has to try to optimize the static parts as open as possible and defer the evaluation of the dynamic ones so that they happen at runtime.
OvermindDL1
Yeah that’s what I was trying to think, couldn’t think of a way without needing to write a second stage function to post-process the parsed data, but that could easily parse ‘too much’ and waste time…
I actually find the pattern matching style extremely readable. It’s not always the easiest to follow because of how much it jumps around, but it is quite readable, the heads are encoding essentially all of the parsing.
Ah that is much more readable, but the check_close_tag_and_emit_tag function still seems very odd, like it itself is throwing the error instead of the parsing failing to parse. I’m curious if it returning that error tuple if the parser then would try other alternate paths if they were defined?
It would be even more concise in C++ by a significant margin (ExSpirit’s is easily 3 to 4 times the size on average), but then again the backend of Spirit in C++ is exceptionally large (it’s essentially a compiler written in the C++ template meta-language, so that’s a place Elixir can be MUCH more readable on!). ^.^
I had considered doing compile-time string parsing in ExSpirit at first but I thought I’d try to stick to the AST at least for version 1.
For parser libraries though I’ve always seen the purpose of all of them that I’ve seen is to have a very concise front-end for defining grammar’s since grammar’s tend to be exceptionally hairy overall, so minimizing everything related to the grammar has always been well worth it. I don’t reach for ExSpirit after all to do parsing of a simple integer list, but rather for parsing complex language definitions, often for shorter things then simple pattern matching is more effect and more readable then needing to bring in another dependency just to do some parsing in 3 lines instead of 15, but when the different is 300 lines compared to 20000 then it is a significant difference.
For a stateful parser this closing_tag would need to be able to take in an argument at parsing time and replace the concat(tag) part with a lit(&1) where &1 is the passed in argument. With that simple change in the user-side definition then the great majority of defined functions there then vanish, from store_tag_in_context to all of check_close_tag_and_emit_tag except for it’s tuple building part (and whatever text_or_nodes = if match?([_], contents), do: hd(contents), else: contents is doing, where-ever the list version of contents comes from it seems like the parser should handle returning it in a normalize format with the rest of the children). That’s a significant amount of user code that no longer needs to exist.
It makes sense to me that stateful parsing will be less efficient than the highlght optimized things that NimbleParsec does now. That’s the cost of having a more powerful parser.
No reason for it to not be except for just taking the time to build the ‘compiler’ to convert from the DSEL to a set of functions to handle it directly (instead of the macro-munging that ExSpirit does currently, I.E. what Parsex was going to do).
What C++'s Spirit ends up doing is taking the DSEL used in the type system (in Elixir that’s just grabbing the AST at compile-time), using templates to walk the DSEL’s AST to generate a couple of sets of data of lifetime information for the ‘arguments’ used, holding the types, normalizing the return types, etc… etc… (in Elixir that’s just walking the AST at compile-time to generate data for making the functions), then it runs optimization passes basically a pattern matcher over the processed AST and values to find patterns to reduce to more efficient patterns), then lastly the templates build a single inlineable function per rule that passes the data via direct argument passing (in Elixir that’s basically what NimbleParsec is doing but with the added information of arguments and more stuff to generate specific code for each type of thing), and this goes right down to even something as simple as parsing characters where the char_ parser gets any part of it replaced with specific values (say matching “a-z”) and any variables are injected in-place, the C++ compiler then does it’s normal optimization of folding constants (since the template ‘processor’ injects constants in every place it can), which let’s it end up having a call like parse(input.begin(), input.end(), char_ >> int_) take literally a few dozen assembly instructions all inline (if the input type is held in order in memory, otherwise it generates streaming calls and so forth, which is more, but still efficient).
This same pattern is entirely doable in Elixir (and was planned in ExSpirit, I just wanted something workable at first for my own work), it just needs to be done.
As a side note, those ‘optimization passes’ mentioned above is why C++'s Spirit is and will always remain the fastest parser, because anything any other parser does better they can see how it generates the output assembly and make a new optimization pass to optimize for that pattern to at least meet if not exceed the original. This is all while it is possible for users to create their own (even root terminal) constructs (as a bit of a template horror but thankfully only ever needs to be done once). It’s entirely doable in Elixir much more simply.
josevalim
Which is why I didn’t enter the merit of readability (it is personal) and focused on code size. And I just noticed we actually don’t use the tags stored in the context, so now the whole thing can be written as:
defmodule SimpleXML do
import NimbleParsec
defparsec :parse, parsec(:node) |> eos()
tag = ascii_string([?a..?z, ?A..?Z], min: 1)
text = ascii_string([not: ?<], min: 1)
opening_tag = ignore(string("<")) |> concat(tag) |> ignore(string(">"))
closing_tag = ignore(string("</")) |> concat(tag) |> ignore(string(">"))
defcombinatorp :node,
opening_tag
|> repeat(lookahead_not(string("</")) |> choice([parsec(:node), text]))
|> wrap()
|> concat(closing_tag)
|> post_traverse(:match_and_emit_tag)
defp match_and_emit_tag(_rest, [tag, [tag, text]], context, _line, _offset),
do: {[{String.to_atom(tag), [], text}], context}
defp match_and_emit_tag(_rest, [tag, [tag | nodes]], context, _line, _offset),
do: {[{String.to_atom(tag), [], nodes}], context}
defp match_and_emit_tag(_rest, [opening, [closing | _]], _context, _line, _offset),
do: {:error, "closing tag #{inspect(closing)} did not match opening tag #{inspect(opening)}"}
end
OvermindDL1
Ah much nicer!
I’m curious, I’m guessing line is the line number, what is offset, is it the column number or is the position in the overall file? Both values are useful for various purposes.
josevalim
Offset is the byte offset the line starts. You can compute the column from the line offset and the overall offset.