| Pattern 14 | Tree Grammar |
Purpose
Tree grammars are a terse and formal way of building an external visitor.
Visitors generated from tree grammars are usually called tree parsers because they are the two-dimensional analog of conventional parsers.
Discussion
In Automatically Generating Visitors from Grammars, we saw that tree grammars look just like conventional parser grammars except that we can match subtree patterns as well. As with parser grammars, we can embed actions to extract information or reorganize the input (a tree, in this case).
In order to convert tree grammars to tree parsers (visitors), we can follow Pattern 1, Mapping Grammars to Recursive-Descent Recognizers. The only extra mapping we need is for tree structures:
| | // match ... |
Get Language Implementation Patterns now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
