Hacker News Reader

Comment by bakery2k | Hacker News Reader

Isn't code generation during parsing still common today? In particular, bytecode generation in interpreters (and JIT compilers) for scripting languages, e.g. Lua?

View on HN

It's sometimes a good idea to do it that way in practice, but it's still a conflation of two conceptually distinct processes. I think it is a bad approach when teaching compiler implementation, as it means you avoid the extremely core concept of an abstract syntax tree.

Thanks, that makes sense.

But it isn't a core concept if you do not need it. And an AST builder can be "injected" between the parser and codegen at a later point in time, if needed. You do not even need to do it in one go, e.g. if your compiler has something like a "ParseExpression" (assuming recursive descent parsing that spits out code as it parses), you can start by making a partial AST just for the expressions and leave everything else (e.g. declarations, control structures, assignments - assuming those aren't part of an expression, etc) as-is.

This is useful for both practical and teaching purposes: for practical because it keeps things simple in case the additional complexity isn't needed (e.g. scripting languages) and for teaching purposes because someone learns both ways (which are used in real world problems) while at the same time learning why one might be preferable to the other. And if you do the partial AST bit you even introduce the idea of an AST gradually by building off existing knowledge and experience the student has acquired.

Yes, it is. It also doesn't really make much difference per se, as e.g. Wirth-style compilers still maintain careful separation of the code generation and parsing.

And if you want to/need to later, you can trivially introduce an AST in those compilers by replacing the calls to the code-generator with calls to a tree builder, and then write a visitor-style driver for the code generation.

"trivially"?

Yes, it's work of course, but it's quite mechanical work that requires little thought.

Instead of calling the code emitter, you call an AST builder.

Then you build a tree walker that call the code emitter.

At least the Wirth Oberon compiler was retrofitted with an AST by at least one student in Wirth's group as part of experiments with optimization passes.

Reply on news.ycombinator.com