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 ...

Get Language Implementation Patterns now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.