December 2009
Intermediate to advanced
380 pages
9h 2m
English
| Pattern 14 | Tree Grammar |
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.
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 ... |