Ask HN: How to learn to write a compiler and interpreter?

#1

Post by lala_lala » Thu, Jan 24, 2019, 2:37 PM UTC

Greetings,

I am in my late 30s without a formal CS education. I write software for a living and have this itch to learn to write a compiler / interpreter.

DO I have to take any courses (e.g. Discrete Maths, Automata Theory) in order to do it?

Do I have to take any courses? If so, do you have recommendations for those as online courses?

I really want to do this in 2019 but the thought that I have to study Maths, then Automata, maybe OS, then Compilers sounds like a long path.

Is there who has learned to write compiler / interpreter without CS background? How did you do it?

Re: Ask HN: How to learn to write a compiler and interpreter?

#2

Post by ablerman » Thu, Jan 24, 2019, 2:54 PM UTC

Robert Nystrom has been putting an online book together. I’ve found it really clear so far.

http://craftinginterpreters.com/

Re: Ask HN: How to learn to write a compiler and interpreter?

#3

Post by lala_lala » Thu, Jan 24, 2019, 3:00 PM UTC

ablerman wrote: post #2

Robert Nystrom has been putting an online book together. I’ve found it really clear so far. http://craftinginterpreters.com/

Does it require any background in CS?

Re: Ask HN: How to learn to write a compiler and interpreter?

#4

Post by snazz » Thu, Jan 24, 2019, 3:05 PM UTC

lala_lala wrote: post #3

ablerman wrote: post #2

Robert Nystrom has been putting an online book together. I’ve found it really clear so far. http://craftinginterpreters.com/

Does it require any background in CS?

You can probably pick the CS and math up as you go. I haven’t gone through that resource but it looks interesting and useful.

Re: Ask HN: How to learn to write a compiler and interpreter?

#5

Post by tudelo » Thu, Jan 24, 2019, 3:32 PM UTC

You may be interested in this https://beautifulracket.com/stacker/intro.html. At the end you have a small interpreter that can handle math. There are further tutorials on https://beautifulracket.com to expand it. This is probably the most approachable option.

Re: Ask HN: How to learn to write a compiler and interpreter?

#6

Post by auganov » Thu, Jan 24, 2019, 4:44 PM UTC

Well, the way you ask your question in abstract sort of biases it towards a CS-heavy approach, doesn't it?

What's your goal?

I've written non-trivial macros that could be understood to be a tiny compiler, but wasn't ever interested in compiler design and I can't claim to know much about it.

Re: Ask HN: How to learn to write a compiler and interpreter?

#7

Post by lala_lala » Thu, Jan 24, 2019, 6:23 PM UTC

auganov wrote: post #6

Well, the way you ask your question in abstract sort of biases it towards a CS-heavy approach, doesn't it? What's your goal? I've written non-trivial macros that could be understood to be a tiny compiler, but wasn't ever interested in compiler design and I can't claim to know much about it.

It is just that I have a job and a family to support. So I want to create something in whatever time I have. The prospect of engaging myself in myriad of courses sounds dull.

Maybe it's a folly but I am just intrigued by how they work and want to be able to develop them without committing to taking lot of courses.

Re: Ask HN: How to learn to write a compiler and interpreter?

#8

Post by WaltPurvis » Thu, Jan 24, 2019, 6:36 PM UTC

I cannot recommend Thorsten Ball's books highly enough. They're really fantastic, step-by-step tutorials, and you certainly don't need a CS degree to understand what he's doing.

Writing An Interpreter In Go https://amzn.to/2FYwwiQ

Writing A Compiler In Go https://amzn.to/2sLilph

Re: Ask HN: How to learn to write a compiler and interpreter?

#9

Post by stephen82 » Thu, Jan 24, 2019, 6:38 PM UTC

I would highly recommend you start with this book first https://interpreterbook.com and then feel free to read Nystrom's online book as ablerman suggested.

The you can read more formal CS book for the sake of covering the necessary theory.

Another suggestion would be to check the source code of various SQL databases, such as SQLite3 and PostgreSQL.

Also, I would suggest to read lots of lots of source code from github.

Here is a short list of suggestions:

  * https://github.com/lemon-lang/lemon
  * https://github.com/d5/tengo
  * https://github.com/wren-lang/wren (by Robert Nystrom)
  * https://github.com/tj/luna (by TJ Holowaychuk, creator of Express.js)

Re: Ask HN: How to learn to write a compiler and interpreter?

#10

Post by kazinator » Thu, Jan 24, 2019, 6:38 PM UTC

Some books on compilers go into the automata theory for the following reason: they teach about the workings of tools that generate lexical analyzers and parsers. A compiler writer is usually just a consumer of those tools. The skills that come into play is being good in program design: structuring code and data.

How much CS comes into play depends on how advanced you make the compiler and what design choices you make. E.g. if you make a stack-based VM, or one with unlimited registers, instead of targeting a real machine with a fixed number of registers, you don't have to study the algorithms for register allocation.

Some languages avoid the complexities of parsing, such as those in the Forth family, and to a large extent Lisp family. To make a language, you don't even need to be a consumer of scanner and parser generating tools, let alone understand how they work.