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

141–150 of 173 posts

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

#141

Post by saidnooneever »

emigre wrote: post #118
saidnooneever wrote: post #80

Earlier quoted context omitted.

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.

the dragon book is all i have on the topic. it was a big investment for me.

it taught me to think very differently but i am sure i am still not ready to write a compiler :D

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

#142

Post by omcnoe »

mrkeen wrote: post #49
omcnoe wrote: post #30

Been working on a toy compiler for fun recently. I have ignored all the stuff about parsing theory, parser generators, custom DSL's, formal grammers etc. and instead have just been using the wonderful Megaparsec parser combinator library. I can easily follow the parsing logic, it's unambiguous (only one successful parse is possible, even if it might not be what you intended), it's easy to compose and re-use parser fu…

I'll push back and say that the lexer/parser split is well worth it. And the best thing about the parser combinator approach is that each is just a kind of parser, something like type Lexer = ParsecT e ByteString m [Token] type Parser = ParsecT e [Token] Expr All the usual helper functions like many or sepBy work equally well in the lexing and parsing phases. It really beats getting to the parentheses-interacting-wit…

I am writing a whitespace sensitive parser - trimming whitespace matters because whitespace consumption is used to implement the indentation rules/constraints.

For example, doing things like passing an indentation sensitive whitespace consumer to a parser inside `many` for consuming all of an indented child block. If I split lexing/parsing I think I'd have to do things like insert indentation tokens into the stream, and end up with the same indentation logic (but instead matching on those indentation tokens) in the parser regardless.

I have found that order-of-operations is somewhat trivially solved by `makeExprParser` from `Control.Monad.Combinators.Expr`.

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

#143

Post by unclad5968 »

_false wrote: post #123
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…

Great thread. If you have 1 hour to get started, I recommend opening Engineering a Compiler and studying Static Single-Assignment (SSA) from ch 9.3. The book is famous for its SSA treatment. Chapters 1-8 are not required to understand SSA. This allows you to walk away with a clear win. Refer to 9.2 if you're struggling with dominance + liveness. http://www.r-5.org/files/books/computers/compilers/writing/K...

I bought this book when I was working on a toy language and I think I was too stupid to understand most of it. The first few chapters were great, but it quickly surpassed my capacity to understand. Seeing it mentioned makes me want to revisit.

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

#144

Post by aleph_minus_one »

marcosdumay wrote: post #115
randomNumber7 wrote: post #106

Earlier quoted context omitted.

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.

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

At least in the typical curriculum of German universities, the students already know the whole theory of regular languages from their Theoretical Computer Science lectures quite well, thus in a compiler lecture, the lecturer can indeed rush over this topic because it is just a repetition.

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

#146

Post by sn9 »

krtkush wrote: post #7

I wonder if it makes sense to do the nand2tetris course for an absolute beginner since it too has compiler creation in it.

nand2tetris only requires programming ability at the level of someone who's taken freshman level CS IIRC.

You could take Harvard's CS50 and then tackle it.

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

#147

Post by niyikiza »

itsmemattchung wrote: post #5

It's been about 4 years since I took a compilers course (from OMSCS, graduate program) and still shutter ... it was, hands down, the most difficult (yet rewarding) classes I've taken.

I took that course too and ruined my life...by making me think writing a compiler could be fun. The course itself was worth the money I paid for the program.

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

#148

Post by microtherion »

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.

I would argue the opposite: Being describable in BNF is exactly the hallmark of sensible syntax in a language, and of a language easily amenable to recursive descent parsing. Wirth routinely published (E)BNF for the languages he designed.

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

#149

Post by keyle »

projektfu wrote: post #62
jll29 wrote: post #22

*Donald Knute -> Donald Ervin Knuth is the author of the book "The Art of Computer Programming" (in progress for a couple of decades, currently volume 4c is being written). It is quite advanced, and it will likely not cover compilers anymore (Addison-Wesley had commissioned a compiler book from Knuth when he was a doctoral candidate, now he is retired and has stated his goal for the series has changed). I disagree wi…

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 almost convinced me never to try to write a compiler.
That was the point. That's why it's not a cute beaver on the cover :)

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

#150

Post by bsder »

gf000 wrote: post #91
aldousd666 wrote: post #81

Earlier quoted context omitted.

Parsing is the front end to a compiler. Can't get semantics without first recognizing syntax. I have a hard time thinking about programming languages without seeing them as a parsing exercise first, every time.

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.

> The recommended advice is to start with semantics first. Syntax will change, there is not much point fixing it down too early.

It's actually the reverse, in my opinion. Semantics can change much more easily than syntax. You can see this in that small changes in syntax can cause massive changes in a recursive-descent parser while the semantics can change from pass-by-reference to pass-by-value and make it barely budge.

There is a reason practically every modern language has adopted syntax sigils like (choosing Zig):

    pub fn is_list(arg: arg_t, len: ui_t) bool {
This allows the identification of the various parts and types without referencing or compiling the universe. That's super important and something that must be baked in the syntax at the start or there is nothing you can do about it.
Post reply on HN