Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Want to write a compiler? Just read these two papers (2008)

prog21.dadgum.com

Post reply on HN
Print view View original

111–120 of 173 posts

Re: Want to write a compiler? Just read these two papers (2008)

#111

Post by ablob »

hmry wrote: post #76
tovej wrote: post #66

Earlier quoted context omitted.

I started with the dragon book, and I found it to be a good introductory text. A lot of people say the dragon book is difficult, so I suppose there must be something there. But I don't see what it is, I thought it was quite accessible. I'm curious, what parts/aspects of the dragon book make it difficult to start with?

It's been a few years since I worked with the dragon book, but I think the most common complaint was that it starts with like 350 pages on parser theory: generating bottom-up and top-down parsers from context free grammars, optimizing lexers for systems that don't have enough RAM to store an entire source file, etc... before ever getting to what most people who want to write a compiler care about (implementing type i…

I guess "back in the day" you had to be able to write an efficient parser, as no parser generators existed. If you couldn't implement whatever you wanted due to memory shortage at the parser level, then obviously it's gonna be a huge topic. Even now I believe it is good to know about this - if only to avoid pitfalls in your own grammar.

I repeatedly skip parts that are not important to me when reading books like this. I grabbed a book about embedded design and skipped about half of it, which was bus protocols, as I knew I wouldn't need it. There is no need to read the dragon book from front to back.

  > But there's a reason most modern resources skip over all of that and just make the reader write a recursive descent parser.
Unless the reason is explicitly stated there is no way to verify it's any good. There's a reason people use AI to write do their homework - it just doesn't mean it's a good one. I can think of plenty arguments for why you wouldn't look into the pros and cons of different parsing strategies in an introduction to compilers, "everyone is(or isn't) doing it" does not belong to them. In the end, it has to be written down somewhere, and if no other book is doing it for whatever reason, then the dragon book it shall be. You can always recommend skipping that part if someone asks about what book to use.

Re: Want to write a compiler? Just read these two papers (2008)

#112

Post by ablob »

thefaux wrote: post #108
gf000 wrote: post #91

Earlier quoted context omitted.

The recommended advice is to start with semantics first. Syntax will change, there is not much point fixing it down too early. Most of the work is actually the backend, and people sort of illusion themselves into "creating a language" just because they have an AST.

Syntax and semantics are never orthogonal and you always need syntax so it must be considered from the start. Any reasonable syntax will quickly become much more pleasant to generate an ast or ir than, say, manually building these objects in the host language of the compiler which is what the semantics first crowd seem to propose. It also is only the case that most of the work is the backend for some compilers, thoug…

I think his point is that "form follows function". If you know what kind of semantics you're going to have, you can use that to construct a syntax that lends itself to using it properly.

Re: Want to write a compiler? Just read these two papers (2008)

#113

Post by [deleted] »

orthoxerox wrote: post #56
armchairhacker wrote: post #11

Nowadays I’ve heard recommended Crafting Interpreters. ( https://craftinginterpreters.com ) The Nanopass paper link doesn’t work.

Crafting Interpreters is great, I wish it had a companion book that covered: - types and typing - optimization passes - object files, executables, libraries and linking Then two of them would be sufficient for writing a compiler.

[deleted]

Re: Want to write a compiler? Just read these two papers (2008)

#114

Post by LLMCodeAuditor »

lateforwork wrote: post #110
LLMCodeAuditor wrote: post #95

Earlier quoted context omitted.

I did not and will not run this on my computer but it looks like while loops are totally broken; note how poor the test coverage is. This is just my quick skimming of the code. Maybe it works perfectly and I am dumber than a computer. Regardless, it is incredibly reckless to ask Claude to generate assembly if you don't understand assembly, and it's irresponsible to recommend this as advice for newbies. They will not…

Are you concerned that the compiler might generate code that takes over your computer? If so the provided Dockerfile runs the generated code in a container. Regarding test coverage, this is a toy compiler. Don't use it to compile production code! Regarding while loops and such, again, this is a simple compiler intended only to compile sort and search functions written in C.

No, the problem is much more basic than "taking over your computer," it looks like the compiler generates incorrect assembly. Upon visual inspection I found a huge class of infinite loops, but I am sure there are subtle bugs that can corrupt running user/OS processes... including Docker, potentially. Containerization does not protect you from sloppy native code.

> Don't use it to compile production code!

This is an understatement. A more useful warning would be "don't use it to compile any code with a while loop." Seriously, this compiler looks terrible. Worse than useless.

If you really want AI to make a toy compiler just to help you learn, use Python or Javascript as a compilation target, so that the LLM's dumb bugs are mostly contained, and much easier to understand. Learn assembly programming separately.

Re: Want to write a compiler? Just read these two papers (2008)

#115

Post by marcosdumay »

randomNumber7 wrote: post #106
projektfu wrote: post #62

Earlier quoted context omitted.

The dragon book almost convinced me never to try to write a compiler. I don't know why people recommend it. I guess you're a lot smarter than I am. There are some excellent books out there. In its own way, the dragon book is excellent, but it is a terrible starting place. Here are a bunch of references from the same vintage as OP. I recommend starting with a book that actually walks through the process of building a…

Imho the problem is the fixation on parser generators and BNF. It's just a lot easier to write a recursive descent parser than to figure out the correct BNF for anything other than a toy language with horrible syntax.

The problem with recursive descent parsers is that they don't restrict you into using simple grammars.

But then, pushing regular languages theory into the curriculum, just to rush over it so you can use them for parsing is way worse.

Re: Want to write a compiler? Just read these two papers (2008)

#116

Post by dlopes7 »

bradley13 wrote: post #25

Maybe I'm missing the point of this article? Writing a simple compiler is not difficult. It's not something for beginners, but towards the end of a serious CS degree program it is absolutely do-able. Parsing, transforming into some lower-level representation, even optimizations - it's all fun really not that difficult. I still have my copy of the "Dragon Book", which is where I originally learned about this stuff. In…

Maybe you are a genius among mere mortals, but for the majority of people even after a CS degree writing a compiler is a bit difficult

Re: Want to write a compiler? Just read these two papers (2008)

#117

Post by lateforwork »

LLMCodeAuditor wrote: post #114
lateforwork wrote: post #110

Earlier quoted context omitted.

Are you concerned that the compiler might generate code that takes over your computer? If so the provided Dockerfile runs the generated code in a container. Regarding test coverage, this is a toy compiler. Don't use it to compile production code! Regarding while loops and such, again, this is a simple compiler intended only to compile sort and search functions written in C.

No, the problem is much more basic than "taking over your computer," it looks like the compiler generates incorrect assembly. Upon visual inspection I found a huge class of infinite loops, but I am sure there are subtle bugs that can corrupt running user/OS processes... including Docker, potentially. Containerization does not protect you from sloppy native code. > Don't use it to compile production code! This is an u…

You have not provided any evidence that can be refuted, only vague assertions.

The compiler is indeed useless for any purpose other than learning how compilers work. It has all the key pieces such as a lexer, abstract syntax tree, parser, code generator, and it is easy to understand.

If the general approach taken by the compiler is wrong then I would agree it is useless even for learning. But you are not making that claim, only claiming to have found some bugs.

Re: Want to write a compiler? Just read these two papers (2008)

#118

Post by emigre »

saidnooneever wrote: post #80
projektfu wrote: post #62

Earlier quoted context omitted.

The dragon book almost convinced me never to try to write a compiler. I don't know why people recommend it. I guess you're a lot smarter than I am. There are some excellent books out there. In its own way, the dragon book is excellent, but it is a terrible starting place. Here are a bunch of references from the same vintage as OP. I recommend starting with a book that actually walks through the process of building a…

the dragon book is how to write a production grade thing i guess. it has all the interesting concepts very elaborated on which is great but it dives quickly into things that can clutter a project if its just for fun..

It’s academic and comprehensive, that’s the issue. It’s not about writing a production grade compiler, though, in my humble opinion. There are more things to learn for that, unfortunately… is just a pretty big topic with lots of stuff to learn.

Re: Want to write a compiler? Just read these two papers (2008)

#119

Post by markus_zhang »

hmry wrote: post #76
tovej wrote: post #66

Earlier quoted context omitted.

I started with the dragon book, and I found it to be a good introductory text. A lot of people say the dragon book is difficult, so I suppose there must be something there. But I don't see what it is, I thought it was quite accessible. I'm curious, what parts/aspects of the dragon book make it difficult to start with?

It's been a few years since I worked with the dragon book, but I think the most common complaint was that it starts with like 350 pages on parser theory: generating bottom-up and top-down parsers from context free grammars, optimizing lexers for systems that don't have enough RAM to store an entire source file, etc... before ever getting to what most people who want to write a compiler care about (implementing type i…

I actually think the parsing part is more important for laymen. Like, there may be a total of 10K programmers who are interested in learning compiler theories, but maybe 100 of them are ever going to write the backend -- the rest of them are stuck with either toy languages, or use parsing to help with their job. Parsing is definitely more useful for most of us who are not smart enough :D

Re: Want to write a compiler? Just read these two papers (2008)

#120

Post by khat »

The biggest issue with technical books is they spend the first 1-2 chapters vaguely describing some area and then follow up with but that's for a later more advanced discussion or we'll cover that in that last 1-2 chapters. Don't vaguely tell me about something you're not gonna go into detail about, because now all I'm thinking about reading the subsequent chapters is all the questions I have about that topic.
Post reply on HN