Language Implementation Patterns

Automatically Generating Visitors from Grammars

Rather than writing parsers by hand, we write grammars and have a parser generator like ANTLR generate parsers automatically for us. Similarly, ANTLR can automatically generate tree visitors from tree grammars. That’s great because we get to express ourselves in a DSL designed to describe trees. We tell ANTLR what the trees look like, and it figures out how to walk them. The only wrinkle is describing a two-dimensional tree structure with a grammar.

To parse a two-dimensional structure, we have to serialize the tree to a one-dimensional list of nodes. Then we can use a conventional parser. To serialize, we start with the “flat” text-based tree format from ​Representing Trees in Text​ and then replace ...