This isn’t “gate-keeping nonsense”. I’m just saying that you or anyone else is not qualified to write parsers. In fact, on several occasions, I have praised the design of NimbleParsec and its composability, which is in many ways superior to ExSpirit, which is a good example of a fully general parser. NimbleParsec is also better than anything I would ever write, and also very fast, because of the way it compiles into binary pattern matches. This owes a lot to your insights on performance on the BEAM.
Tha said, I’d like to highlight a quote from post in thist opic:
This seems to have been lost in translation somwhere. I was under the impression that NimbleParsec was supposed to support (at least) the same as a PEG parser. I was under the impression that it already supported such grammars, or at least it had been designed with that goal in mind.
I mever got the impression that it was supposed to be a limited parser. Otherwise I’d never have suggested the context-sensitive features. Adding context-sensitivity on top of a parser that isn’t wven equivalent to a PEG parser was not one of my brightest ideas.
The main problem here is that parsers with different capabilities need different architectures.
For example, you can’t reliably parse HTML with regular expressions. Which means that if you qant to parse HTML your parser can’t be based on a regular expressions engine.
That’s why I think it’s important to decide which capabilities you want in your parser before commiting to an architecture.
From what I understand, the main goal is to compile into fast binary pattern matches. That is a perfectly valid design goal, and in no way i want to criticise that goal as invalid.
But, i is possible that this design will make it imposible to recognize certain patterns. And again, this is perfectly valid.
I just wanted to illustrate the tradeoff we’re dealing with… Was it clear?
One last update: I have optimized bound lookaheads, so looking ahead patterns where the size is known upfront now generates only one clause, which is super efficient. This makes things like repeat_until more efficient than it was before using a more composable construct! v0.5 should be out in the next minutes.
Indeed, thanks!
All I can say is that I never said any of this.
In any case, according to @mjadczak, we should be equivalent to a PEG parser now, so hurray. If somebody is confident about this topic and want to send a PR that amends the README accordingly, please do it!
No, you didn’t, but because you presented it as a (not as featureful) alternative to ExSpirit, I thought it was at least as powerful as a PEG parser. But that was not your fault.
It should also be relatively straight-forward to migrate to v0.5.0, you likely only need to rewrite replace_until(foo, bar) as replace(lookahead_not(bar) |> foo) but I can’t look into it right now, sorry.
Traditional PEG parsers are little composable functions that operate on a ‘state’ structure, that state structure holds things like the unparsed input, positioning information, returned result, metadata, etc… ExSpirit is almost a direct translation of the ‘traditional’ PEG library, which though crazy efficient on efficient languages like C++/Rust/OCaml is less efficient on Elixir (hence why I really need to finish my Parserx version). But each ‘function’ just takes the state and returns state, the first thing every function should do is test if the state is in a good state (no error condition) and if not then immediately return it directly (passing the existing error back) else it does whatever it needs to do and transforms the state and returns it.
Functions that take other functions, like repeat or lookahead_not can do things like call the input and test it’s returns state until it fails, then take all the successful results and put them in a list and return them, or for lookahead_not it runs the function and it just returns a flipped error state from the originally passed in state (ignoring everything else of the state returned from the function).
Close enough yeah, it’s more like the transforming ‘piped data’ flow I described above internally in most implementations.
It’s possible to make a pattern matching version of it though with a lot more code generation, I started working on such a thing in the Parserx version but never continued it since NimbleParsec came out that mostly completed the same thing (though with significantly fewer features), so I figured I could use NimbleParsec where it is good and mine where it was necessary (I’ve even used them together, NimbleParsec is very usable from within ExSpirit ^.^).
Yeesh, you’ll need multiple passes for that. You cannot represent a proper XML parser in PEG without state handling, thus meaning you have to use multiple passes. Like I made a mini-xml parser (no attributes) in ExSpirit as an example at ex_spirit/examples/simple_xml.exs at master · OvermindDL1/ex_spirit · GitHub and you can see the required state work for accurate parsing in it:
You can see that when it parses the tag_name then it puts it into the state on that current rulestack of the name :tagname, then it pulls the :tagname state into two different places, first is into a tag, which just wraps the children so an XML node of <blah>children</blah> becomes {"blah", children}, and also into the closing tag, so an opening <blah>has to match a closing </blah> or compilation fails. As per the example run of it:
$ mix run examples/simple_xml.exs
Input a single line of xml-like syntax:
<test1>Some text<test2>Hi</test2> and more</test1>
Result: {"test1", ["Some text", {"test2", ["Hi"]}, " and more"]}
$ mix run examples/simple_xml.exs
Input a single line of xml-like syntax:
<a-tag>How about an improperly terminated tag</b-tag>
<unknown>:1:48: Expectation Failure: literal `a-tag` did not match the input
RuleStack: [tag, node_]
Input: b-tag>
$ mix run examples/simple_xml.exs
Input a single line of xml-like syntax:
<
<unknown>:1:1: Parse error: Repeating over a parser failed due to not reaching the minimum amount of 1 with only a repeat count of 0
RuleStack: [text, node_]
Input: <
And it can easily be decorated to transform error messages into something more domain-specific like closing tag does not match opening tag or something as well by decorating the PEG commands with another. All single pass. This is why I say that state handling is so extremely important in PEG parsers and why all of them have some form of state handling. I can trivially make a calculator in ExSpirit that let’s you define variables, calculate, etc… all in a single pass. I’ve already made a single pass Lisp (with macro’s and read-macro!) and Forth parsers in ExSpirit and all.
ExSpirit’s goal was supposed to be a Traditional PEG Parser, I tried to make it fast (and it was faster than all others in Elixir until NimbleParsec came along) but accuracy was my first goal (and there are still a couple of niggles I’m not happy with that Parserx was supposed to fix as well).
Make sure to bump the major version! ^.^
Ooo, very cool! I really should flesh out the Parserx branch sometime… ^.^;
Eh, almost, it’s missing a couple of features still, like expect is absolutely necessary to have proper errors at the correct locations in many cases and state handling is extremely important in many types of parsers or you can’t get context-sensitive parsers to work without multiple passes (which often makes errors significantly more inaccurate as well as overall slower). Maybe a couple other things but those are the biggies.
If you have some time, can you please expand on what I am missing? If you could provide a reference, even better!
We state-handling via traverse and repeat_while. I.e. it is possible to pass a context around, with your own state, as nimble parsec operates. What am I missing here too?
@OvermindDL1 is mixing a couple things that make his post confusing. A PEG parser is something that abides by the definition above. PEG parsers don’t need to keep state and they don’t need to recognize context-sensitive languages.
I believe they also don’t require the expect combinator to be considered PEG parsers. It’s just something that’s nice to have. Currently, NimbleParsec handles all errors as something that says that you should try the next parser. But sometimes, you might have an error in which you want to stop parsing altogether instead of keep trying. That saves you time (because you interrupt the parsing process) and gives better error messages. Basically, expect is a convenience combinator which raises an exception which halts parsing completely (and could even be implemented as such).
So, there are two things here:
State handling, à la Spirit, to recognize things like indentation, matching XML tags, etc
The expect handler
None of which are strictly required in a PEG parser. The first makes your parser more powerful than a PEG parser and the second one is just a convenience.
Thank you @tmbb for explaining! I think the expect handler should be straight-forward to implement. For the state stuff, I will wait for use cases as usual.
