Good breakdown of Data Oriented Design for parsers.
14 Likes
Very interresting. I’m currently building a crdt implementation derived from Rope science - Introduction and the xi-editor it is about, written in rust. It uses B-Trees and I use a very similar strategy to the one in the article to store the internal and leaf nodes referenced by stable Indexes.
2 Likes
This post is explaining how the Zig parser works without acknowledging that. This was also written about a while ago: Zig Parser – Mitchell Hashimoto
Without pointing out the prior art it feels a little bit like plagiarism.
3 Likes
How do you deal with ambiguous syntax?
As in when you need to just pick one of the possibilities and see if that parses successfully. After all that would create nodes in the normal arrays.
Would you just save the current index, then try and if it doesn’t work just delete everything after that index?
(Cleaning up the cobwebs in my memory…) This is what GLR parsers do: they basically follow all possible parses, and when one of the currently possible parses is found to be invalid, it is abandoned. The practical case is that for many grammars for programming languages, and for most interesting programs, there usually is only one valid parse at the end. Of course, the trick is doing this in an efficient manner, not only from an algorithmic PoV, but also in how you represent this “forest of parse trees” efficiently.
1 Like