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

161–170 of 173 posts

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

#161

Post by aleph_minus_one »

torginus wrote: post #159
hmry wrote: post #76

Earlier quoted context omitted.

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…

The thing about parsing (and algorithms in general) is that it can be hair raisingly complex for arbitrary grammars, but in practice, people have recently discovered, that making simple, unambiguous grammars, and avoiding problems, like context dependent parsing, make the parsing problem trival. Accepting such constraints is quite practical, and lead to little to no loss of power. In fact, most modern languages are d…

> In fact, most modern languages are designed with little to no necessary backtracking and simple parsing, Go and Rust being noteworthy examples.

But to understand how to generate grammars for languages that are easy to parse, you have in my opinion to dive quite deeply into parsing theory to understand which subtle aspects make parsing complicated.

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

#162

Post by sph »

soegaard wrote: post #33

An Incremental Approach to Compiler Construction Abdulaziz Ghuloum http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf Abstract Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an education…

One of the greatest papers in computer science. So dense in its 11 pages, yet very approachable.

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

#163

Post by ape4 »

ethan_smith wrote: post #121
ape4 wrote: post #46

Would a practical approach be parsing the source into clang's AST format. Then let it make the actual executable.

You'd more likely want to emit LLVM IR rather than try to match clang's internal AST. That's essentially what most new language projects do now (Rust, Swift, Zig all use LLVM as their backend). You get optimization passes and codegen for multiple architectures for free, and the IR is well-documented. The tradeoff is you skip learning about the backend, which is arguably the most interesting part.

Right that's what I meant ... the .ll file. Thanks

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

#165

Post by rurban »

pjmlp wrote: post #133
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…

It was a product of its time I guess, much better ones from similar vintage, The Tiger book (with C, Standard ML, and Java variants) https://www.cs.princeton.edu/~appel/modern/ Compiler Design in C (freely available nowadays, beware this is between K&R C and C89) https://holub.com/compiler/ lcc, A Retargetable Compiler for ANSI C https://drh.github.io/lcc/ Or if one wants to go with more clever stuff, Compiling with…

Instead of Lisp in Small Pieces I'd recommend SICP instead. No continuation passing, but much better written.

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

#166

Post by jjtheblunt »

aleph_minus_one wrote: post #144
marcosdumay wrote: post #115

Earlier quoted context omitted.

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 repetitio…

(Same for US universities at least 30ish years ago)

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

#167

Post by 103e »

lateforwork wrote: post #69
angusturner wrote: post #64

Earlier quoted context omitted.

why read that, vs an actually well-written compiler though?

Because an actual compiler would be tens of thousands of lines and most of it is going to be perf optimization. If you want to get the big picture first, read a simple working compiler that has all the key parts, such as a lexer, abstract syntax tree, parser, code generator and so on.

Is it less work than finding a human authored toy compiler of good quality. How long did it take to generate?

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

#168

Post by torginus »

aleph_minus_one wrote: post #161
torginus wrote: post #159

Earlier quoted context omitted.

The thing about parsing (and algorithms in general) is that it can be hair raisingly complex for arbitrary grammars, but in practice, people have recently discovered, that making simple, unambiguous grammars, and avoiding problems, like context dependent parsing, make the parsing problem trival. Accepting such constraints is quite practical, and lead to little to no loss of power. In fact, most modern languages are d…

> In fact, most modern languages are designed with little to no necessary backtracking and simple parsing, Go and Rust being noteworthy examples. But to understand how to generate grammars for languages that are easy to parse, you have in my opinion to dive quite deeply into parsing theory to understand which subtle aspects make parsing complicated.

My personal context to understand where I'm coming from - I'm working on my own language, which is a curly-brace C-style language with quite, where I didn't try to stray too far from established norms, and the syntax is not that fancy (at least not in that regard). I also want my language to look familiar to most programmers, so I'm deliberately sticking close to established norms.

I'm thankfully past the parsing stage and so far I haven't really encountered much issues with ambiguity, but when I did, I was able to fix them.

Also in certain cases I'm quite liberal with allowing omission of parentheses and other such control tokens, which I know leads to some cases where either the code is ambiguous (as in there's no strictly defined way the compiler is supposed to interpret it) or valid code fails to parse,

So far I have not tackled this issue, as it can always be fixed by the programmer manually adding back those parens for example. I know this is not up to professional standards, but I like the cleanliness of the syntax and simplicity of the compiler, and the issue is always fixable for me later. So this is a firm TODO for me.

Additionally I have some features planned that would crowd up the syntax space in a way that I think would probably need some academic chops to fix, but I'm kinda holding off on those, as they are not central to the main gimmickTM and I want release this thing in a reasonable timeframe.

I don't really have much of a formal education in this, other than reading a few tutorials and looking through a few implementations.

Btw, besides just parsing, there are other concerns in modern languages, such as IDE support, files should be parseable independently etc., error recovery, readable errors, autocomplete hints, which I'm not sure are addressed in depth in the dragon book. These features I do want.

My two cents is that for a simple modern language, you can get quite far with zero semantic model, while with stuff like C++ (with macros), my brain would boil at the thought of having to write a decent IDE backend.

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

#169

Post by gbacon »

menato wrote: post #82
armchairhacker wrote: post #11

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

It was saved: https://github.com/asalber/books/blob/master/A%20Nanopass%20...

Also: https://github.com/joseluisq/technically-oriented-pdf-collec...

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

#170

Post by pjmlp »

rurban wrote: post #165
pjmlp wrote: post #133

Earlier quoted context omitted.

It was a product of its time I guess, much better ones from similar vintage, The Tiger book (with C, Standard ML, and Java variants) https://www.cs.princeton.edu/~appel/modern/ Compiler Design in C (freely available nowadays, beware this is between K&R C and C89) https://holub.com/compiler/ lcc, A Retargetable Compiler for ANSI C https://drh.github.io/lcc/ Or if one wants to go with more clever stuff, Compiling with…

Instead of Lisp in Small Pieces I'd recommend SICP instead. No continuation passing, but much better written.

And no information on how to actually do a compiler, end to end, only a self hosted interpreter.

The authors don't have the same audience in mind.

I would recommend both, one is about actual Lisp compilers, the other alternative computation models.

Post reply on HN