dcast
dcast

Reputation: 111

Applying visitor on syntax tree

I am building a c interpreter. My AST uses the composite-pattern. To check semantics and perform actions, I wanna use the visitor-pattern. Now there's one problem. This is an grammar rule of the c-preprocessor: if-section = if-group [ elif-groups ] [ else-group ] endif-line. The visitor of if-section needs information about the child nodes, to know which groups have to be skipped. In the visitor-pattern, every "visit"-method returns void. So I can't get any information about these nodes (only with adding information to the nodes, but that's ugly ...). Are there any opportunities?

Upvotes: 1

Views: 719

Answers (1)

Ira Baxter
Ira Baxter

Reputation: 95420

You've nailed the problem: you have to have additional information above and beyond the raw data that comprises the AST.

You can associate all of that extra information with just individual tree nodes: if you do that, you'll end up building what is called an attributed tree. In theory (and if you work at), you make this idea work completely. Your visitor may have to inspect/update the information associated with not only the AST node it is visiting, but that of key children and parents.

In practice, it is useful to build auxiliary data structures (e.g., symbol tables) which can consulted by the visitor (and updated) as it walks the tree. You end up with kind of degenerate attributed tree: you associate symbol table chunks with AST nodes that form scopes.

You've artificially constrained your visitor from returning any value; if you didn't do that, a child visitor could pass useful values to a parent visitor, enabling the parent to do less ad hoc reaching down the tree.

In your problem statement, you have not constrained your visitor from passing values down to children, so you can pass down useful values. An extremely useful value to pass is the symbol table associated with the surrounding scope, so that children visitors don't have to climb back up the tree to find the scoping node, and the associated symbol table.

Upvotes: 2

Related Questions