Language Implementation Patterns

Building Recursive-Descent Parsers

A parser checks whether a sentence conforms to the syntax of a language. (A language is just a set of valid sentences.) To verify language membership, a parser has to identify a sentence’s parse tree. The cool thing is that the parser doesn’t actually have to construct a tree data structure in memory. It’s enough to just recognize the various substructures and the associated tokens. Most of the time, we only need to execute some code on the tokens in a substructure. In practice, we want parsers to “do this when they see that.”

To avoid building parse trees, we trace them out implicitly via a function call sequence (a call tree). All we have to do is make a function for each named substructure (interior node) ...