Visit The Parse Tree

Context:

You've got a big chunk of data to parse. Following the advice of ParseUsingGrammars and AlwaysBuildAParseTree, you've used a parser generator (for example, AntlrTranslatorGenerator), built a BNF and gone to town.

Problem:

What now ? Now that you've got all the information in memory, in a nice form, how do you actually do something with it ?

Forces:

Implementation complexity. Oh my god. Haven't you written enough code already ? Do you really need to implement a lot more code. This investment in infrastructure may be a long term gain, may have helped you UnderstandContext? and it will EncourageExperimentation but ... you need to see something running and doing something soon.

Extendability.

In order for an investment in infrastructure to pay off, it needs to be flexible (and efficient). that's why you went to the trouble of defining a BNF and building a parse tree, right ?

Solution:

Use visitors to perform tasks. Implement the full DoubleDispatch version from the start (you're going to need it and, at the start, it's no problem to build it in) and do all your processing via visitors. You'll be amazed at how elegant the resulting code is (and how easy it is to extend).

Related Patterns:

ParsingPatterns, EncourageExperimentation, VisitorPattern


Compiler experts often don't follow this advice, because they don't build parse trees. Building parse trees is a bit of overhead, and the fastest compilers don't. But unless you are pretty sure you won't need them, you are better off building parse trees because compilers based on parse trees are a lot easier to understand (in my opinion). So, I agree that this pattern is the one you should use by default. -RalphJohnson
Please clarify how you see DoubleDispatch working with the visitor. I can imagine at least two implementations.

Personally I feel a better question would be how do you implement the Visitor pattern without full DoubleDispatch working?

Odd. The VisitorPattern does not require DoubleDispatch. I've never used DoubleDispatch to parse or process data. I've never used DoubleDispatch to parse or interpret code.

Of what value is DoubleDispatch in this context? -- JeffGrigg


EditText of this page (last edited December 5, 2010) or FindPage with title or text search