Hacker News Reader

Comment by mojuba | Hacker News Reader

> My view is that learning and writing a simple compiler will make most of developers on notch better.

Agreed. One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST. I'd say for most languages it's an unnecessary step that makes compilation slower and more resource hungry. However, compiling without AST is a next-level skill, another notch I think.

View on HN

> One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST.

PL (but not compiler) researcher here. What you're saying sounds to me like "One of the interesting insights I got while programming my own game was that despite what every game programming book says, there are games that can be programmed without defining any functions." I mean, yes, you can do that, and it may in fact be more efficient, but it's going to cause trouble down the line if you ever want to do something more complex.

> What you're saying sounds to me like "One of the interesting insights I got while programming my own game was that despite what every game programming book says, there are games that can be programmed without defining any functions."

Ex-game programmer and current PL programmer here. I think a better analogy is that you can make a game without having a scene graph. And, indeed, you can. And it works fine for many simple games, though as some scales it starts to be a hindrance.

Yeah, the grandparent is only true if you don't want to do interesting things with the language, like nearly any but the most basic peephole optimization.

But a fun fact, if you know about single-pass compiling, you can figure out a lot of why the original C syntax is what it is. A declaration is a "reserve some memory" statement. Local variables had to be declared at the beginning of scope so that the compiler could deallocate them at scope close. Without an AST, the compiler had to produce instructions immediately.

With a true AST, you don't need such a restrictive syntax.

There are many other possible examples.

Yes, there's a reason compiler books start with parsing and building an AST.

But I think studying Lua [1] or the Wren codebase [2] is still worthwhile, provided you keep in mind that they're relatively simple languages that are designed to be both fast and embedded.

[1] https://www.lua.org/doc/jucs05.pdf [2] https://github.com/munificent/wren

well there's no need for an AST in a concatenative language - that might be what he's talking about.

No, it's not the same thing. A compiler without the AST phase itself is more compact and arguably more beautiful, but again not every language is compile-able this way (C++ being a notable example).

My experience has been that you can get incredibly far (much farther than you'd think) without any form of AST and just iterate over the raw parse tree and tokens, but the problem you eventually encounter when you do this is that if you want to support all the different cases in a 'real' and messy evolved language like C is that you get a combinatorical exposion when you try to support all the corner cases of the language. A great example of this would be if you try to figure out how to write a function to iterate over the tokens that make up a struct definition in C:

http://blog.robertelder.org/magical-world-of-structs-typedef...

This is the reason for needing the extra 'abstract' syntax tree layer that lets you generalize over all those different cases and avoid having 20-level nested if statements in your compiler.

Compiling without an AST is actually more like an old school skill than a next generation one: very common in the 60s and 70s, very rare today.

Reply on news.ycombinator.com