Re: HELP: Using an abstract syntax tree for semantic checking

"Neal" == Neal Harder <nealh@dinigroup.com> remarks:


        Neal> I realize that this could be accomplished simply by
        Neal> traversing the parse tree and calling functions based on a
        Neal> gigantic switch statement (In which the token value of the
        Neal> node in the parse tree is used to decide which function(s)
        Neal> should be called) - but with hundreds of rules, this is
        Neal> rather ugly and inefficient. My current approach is to
        Neal> write a function for each rule in the grammar.


Check out the Interpreter and Visitor patterns in Design Patterns by
Gamma et al. The basic idea is to have a class for each rule, and an
object of the corresponding class for each node of the parse tree. You
either write the "gigantic switch" as a virtual method on each class
(Interpreter pattern), or write a generic visit() method that applies
a function to the parts of an object, and pass the switch as a visitor
(Visitor pattern). You might also check out the Singleton and Flywheel
patterns, which can be handy for keeping the parse tree from sucking
too much memory.


I've found this to be a nice way to keep things clean; it's easy to
drop in a new syntax class to implement a new piece of syntax. On the
other hand, if your syntax is relatively fixed, it's easy to drop in
new compiler passes by creating a new visitor.


Jake
--

Return to the comp.compilers page.
Search the comp.compilers archives again.