In the first post of this series we looked at a few different ways of parsing a simple JSON-like language. In the second post we implemented a few lexers, and looked at the performance when the parsers from the first post are combined with the lexers in the second post.
One of the surprising results in these posts is that our recursive descent parser, which parses the input directly to an AST, and in some sense is the simplest possible implementation when we need an AST, actually performs the worst.
(The implementations that collect tokens in a vector before parsing perform worse than recursive descent parsing, but those implementations have other issues as well, and can’t be used in many cases. Maybe I should’ve omitted them entirely.)
To recap, the “iter” variants are Iterators that return one parse (or lexing) event at a time. The “push” variants take a “listener” argument with callbacks for events. See the first post for details.
When the AST generator asks for the next parse event, the parse event generator asks for the next token (maybe multiple times) and returns an event. AST generator consumes all of the events and builds the AST.