Exercise 34: Analyzers

You now have a parser that should be producing a tree of grammar production objects. I'll call this your "parse tree," and it means you can analyze the whole program by starting at the top of the parse tree and then "walking" it until you've visited every node. You've done something like this when you were learning about the BSTree and TSTree data structures. You started at the top and visited each node, and the order you visited them in (depth-first, breadth-first, in-order, etc.) determined how the nodes were processed. Your parse tree has the same capability, and your next step in writing the little Python interpreter is to walk the tree and analyze it.

The Analyzer's job is to find semantic mistakes in your grammar and to fix or add information the next stage needs. The semantic mistakes are errors that, while grammatically correct, don't make sense as a Python program. This can be anything from a variable that hasn't been defined yet to non-sequitur code that simply makes no sense. Some language grammars are so loose the Analyzer has to do more work to fix the parse tree. Other languages are so easy to parse and process that they don't even need an Analyzer step.

To write an analyzer you'll need a way to visit each node in your parse tree, analyze it for errors, and fix any missing information. There are three general ways you can do this:

• You create an analyzer that knows how to update each grammar production. It will walk the parse tree in a similar way as your Parser did, with a function for each type of production, but its job is to alter, update, and check the productions.

• You change your grammar productions so they know how to analyze their own state. Then your analyzer is simply an engine that walks the parse tree calling each production's analyze() method. With this style you'll need some state that is passed around to each grammar production class, which should be a third class.

• You create a separate set of classes that implement the final analyzed tree you can hand to an interpreter. In many ways you'd mirror the parser's grammar productions with a set of new classes that take a global state, a grammar production, and configure their __init__ so that they're the analyzed result.

I recommend either #2 or #3 for your Exercise Challenge today.