What does "walk the abstract syntax tree" mean?

Question

I'm in a compilers class, in which we have to write a compiler in OCaml, and I keep hearing that a necessary step is "walking the abstract syntax tree." What does that mean, both theoretically, and in terms of actually writing code?

Answer 1

It means you need to take an AST and walk through the nodes to do something, just like traversing a list. So something like this

match ast_token with
| INT_LITERAL(x) -> dsw x
| IF_EXPRESSION(p, e1, e2) -> dsw p e1 e2
...