16 ms·

Show HN: How to write a tiny compiler

224 points by viebel 10y ago

no_protocol 10y ago
> a string of code and break it down into an array break -> breaks > There a three kinds a -> are > starts with a " and end with a " end -> ends > couple of tokenizer for a tokenizer -> tokenizers > a generic function that tokenize a single tokenize -> tokenizes > by means or regular expressions or -> of
- viebel 10y ago
  Thx a lot. Fixed!
- mrspeaker 10y ago
  Did you just tokenize that blog post?
  - viebel 10y ago
    what do you mean?
vog 10y ago
I like the idea! However, I feel the source and target language are too similar. Won't this discourage people? The result code looks like it could have been done in a simpler way, without all the compiler voodoo, by just moving around some parentheses. Also, the implementation seems to make quite heavy use of external JS libraries. Maybe it is just me, but I'd like to add one NoScript exception for your site, and be done with it, rather than adding exceptions for so many different CDNs.
- viebel 10y ago
  I see. My blog is powered by the klipse plugin (that I have developed): https://github.com/viebel/klipse https://github.com/viebel/klipse The klipse plugin indeed loads a couple of external scripts - mostly from my github pages domain: viebel.github.io
eliben 10y ago
Kudos for writing a compiler-construction walk-through without running out of steam after the parsing part :-) It's a shame this is where most tutorials end, since codegen is often much more interesting
- viebel 10y ago
  So you made the whole journey until the last station without taking any breaks. Right?
  - eliben 10y ago
    Nope, I was just curious so I looked at the blog archive and saw you actually published them all
    - viebel 10y ago
      Ah I see! So what station are you for the moment?
- argv_empty 10y ago
  This still feels unsatisfying, since the target language is really just the source language with slightly modified surface syntax. Connecting languages with nontrivial differences is where writing compilers starts to turn interesting.
- qznc 10y ago
  Here is a plan with more self-sufficient steps: http://belkadan.com/blog/2016/05/So-You-Want-To-Be-A-Compiler-Wizard/ http://belkadan.com/blog/2016/05/So-You-Want-To-Be-A-Compile...
akkartik 10y ago
Semi-tangential rant: I went to grad school for compilers, and yet I've been struggling for several months to get started building something real-world. I can build interpreters and parsers in my sleep at this point, but the crucial next step nobody talks about is having a deep knowledge and understanding of the target language that your compiler will be emitting. For a conventional native ahead-of-time compiler that requires knowledge of x86, the ELF format, OS loading and more. I suppose this is why toolkits like LLVM are so popular :/
- akovaski 10y ago
  Why don't you compile to a language that you know already or that is easy to understand, and then compile that? (Ex. C, Java, C#, C++, go)
  - akkartik 10y ago
    Yes, that's a perfectly valid option if the goal is just to implement a new language. My goal (similar to OP) is to learn how a native compiler works.
    - MaulingMonkey 10y ago
      Some of this starts delving into linking as well. Aside from documentation, you might consider reverse engineering tiny binaries. For example: http://timelessname.com/elfbin/ http://timelessname.com/elfbin/ Cheat a lot. They point out some disassembly for you. ".ELF" is clearly some kind of magic string to confirm it's an elf file. "A4 00 00 00" looks like a 4-byte little endian integer (164) or perhaps an offset (0x000000A4 happens to be exactly where all the strings start), "34 00 20 00" might be a pair of shorts... 0x34 = 52 = "Start of program headers" among other matches - it probably corresponds to one of these fields! Try mutating the file and re-running readelf to see what fields change, or if the program still runs. Just a hex editor and a way to correlate the raw bytes of the disassembly to where the occur in the file can get you surprisingly far. While there will be "dead" data that you can't determine the nature of, documentation can help fill in the holes once you start getting a hold on the "important" bits that actually do stuff (mostly make your program un-runable, I assume.)
niggerdeath 10y ago
This is really cool and not at all a college freshman project literally out of SICP. Your mad skillz are impressive.
popey456963 10y ago
Is my browser messing something up or does the small div at the end seem to be in a really weird font that seems to be way to heavy (on font-weight)? When I read the page I get something resembling: https://puu.sh/tVQAL/ec7bd4a05c.png https://puu.sh/tVQAL/ec7bd4a05c.png Apart from that however, I'm thoroughly enjoying this tutorial! It's remarkably similar to a tokenizer & parser I built when I was experimenting with a language that had no syntax, but was simply an AST that could be easily represented as Haskell/Python in the IDE of your choice. Really love how simplistic your code is though, mine just ended up being a mess of callbacks!
- viebel 10y ago
  Oh. This font is so ugly. What browser are you on?
monokrome 10y ago
Hopefully it isn't intentional to suggest that you need to be a genius "guy" to do this. To be fair, this is about where I closed the article so maybe I missed the point.
- TazeTSchnitzel 10y ago
  It's entirely orthogonal, but the other half of that, the implication you have to be a “genius” to write a compiler, also annoys me. Is it really rocket science? (I suppose it depends on what “real” means, though.)
- OJFord 10y ago
  The actual sentence is: > You probably have to be one of those genius guys ... Used in the plural, 'guys' usually just means 'people'/'folks' - "alright guys, shall we get going?" - Mac Dictionary agrees. Happy people don't go around looking to be insulted.
Msurrow 10y ago
This is great, thank you! I've been looking for something like this: a simple small project that goes through all the involved phases and explains/demonstrates the concepts, that I can mess around with on the weekends. It shouldnt be have real life applications, be serious or academically correct -- it should just be fun. I once found a blog post with an example of defining a grammar for a small language and then building an interpreter (in python i think) for it. It was really great, but I lost the link and can't seem to find it again. The same goes for OS'es - a simple but "end to end" walkthrough would be awesome. Anyway, cheers!
- jonjacky 10y ago
  > I once found a blog post ... but I lost the link ... Maybe this one? Python: Writing a Compiler and Interpreter in 160 lines of code http://www.jroller.com/languages/entry/python_writing_a_compiler_and http://www.jroller.com/languages/entry/python_writing_a_comp...
  - Msurrow 10y ago
    Not the one, it was in multiple parts. BUT thanks - I'll read that one aswell :-)
camus2 10y ago
Mandatory link to lisperator : http://lisperator.net/pltut/ http://lisperator.net/pltut/
AstroJetson 10y ago
Look at Small C from the 70's. You could change the back end to target a different computer.

224 points by viebel 10y ago

> a string of code and break it down into an array break -> breaks > There a three kinds a -> are > starts with a " and end with a " end -> ends > couple of tokenizer for a tokenizer -> tokenizers > a generic function that tokenize a single tokenize -> tokenizes > by means or regular expressions or -> of

viebel 10y ago
Thx a lot. Fixed!
mrspeaker 10y ago
Did you just tokenize that blog post?
- viebel 10y ago
  what do you mean?

vog 10y ago

I like the idea! However, I feel the source and target language are too similar. Won't this discourage people? The result code looks like it could have been done in a simpler way, without all the compiler voodoo, by just moving around some parentheses. Also, the implementation seems to make quite heavy use of external JS libraries. Maybe it is just me, but I'd like to add one NoScript exception for your site, and be done with it, rather than adding exceptions for so many different CDNs.

viebel 10y ago
I see. My blog is powered by the klipse plugin (that I have developed): https://github.com/viebel/klipse https://github.com/viebel/klipse The klipse plugin indeed loads a couple of external scripts - mostly from my github pages domain: viebel.github.io

eliben 10y ago

Kudos for writing a compiler-construction walk-through without running out of steam after the parsing part :-) It's a shame this is where most tutorials end, since codegen is often much more interesting

viebel 10y ago
So you made the whole journey until the last station without taking any breaks. Right?
- eliben 10y ago
  Nope, I was just curious so I looked at the blog archive and saw you actually published them all
  - viebel 10y ago
    Ah I see! So what station are you for the moment?
argv_empty 10y ago
This still feels unsatisfying, since the target language is really just the source language with slightly modified surface syntax. Connecting languages with nontrivial differences is where writing compilers starts to turn interesting.
qznc 10y ago
Here is a plan with more self-sufficient steps: http://belkadan.com/blog/2016/05/So-You-Want-To-Be-A-Compiler-Wizard/ http://belkadan.com/blog/2016/05/So-You-Want-To-Be-A-Compile...

akkartik 10y ago

Semi-tangential rant: I went to grad school for compilers, and yet I've been struggling for several months to get started building something real-world. I can build interpreters and parsers in my sleep at this point, but the crucial next step nobody talks about is having a deep knowledge and understanding of the target language that your compiler will be emitting. For a conventional native ahead-of-time compiler that requires knowledge of x86, the ELF format, OS loading and more. I suppose this is why toolkits like LLVM are so popular :/

akovaski 10y ago
Why don't you compile to a language that you know already or that is easy to understand, and then compile that? (Ex. C, Java, C#, C++, go)
- akkartik 10y ago
  Yes, that's a perfectly valid option if the goal is just to implement a new language. My goal (similar to OP) is to learn how a native compiler works.
  - MaulingMonkey 10y ago
    Some of this starts delving into linking as well. Aside from documentation, you might consider reverse engineering tiny binaries. For example: http://timelessname.com/elfbin/ http://timelessname.com/elfbin/ Cheat a lot. They point out some disassembly for you. ".ELF" is clearly some kind of magic string to confirm it's an elf file. "A4 00 00 00" looks like a 4-byte little endian integer (164) or perhaps an offset (0x000000A4 happens to be exactly where all the strings start), "34 00 20 00" might be a pair of shorts... 0x34 = 52 = "Start of program headers" among other matches - it probably corresponds to one of these fields! Try mutating the file and re-running readelf to see what fields change, or if the program still runs. Just a hex editor and a way to correlate the raw bytes of the disassembly to where the occur in the file can get you surprisingly far. While there will be "dead" data that you can't determine the nature of, documentation can help fill in the holes once you start getting a hold on the "important" bits that actually do stuff (mostly make your program un-runable, I assume.)

niggerdeath 10y ago

This is really cool and not at all a college freshman project literally out of SICP. Your mad skillz are impressive.

popey456963 10y ago

Is my browser messing something up or does the small div at the end seem to be in a really weird font that seems to be way to heavy (on font-weight)? When I read the page I get something resembling: https://puu.sh/tVQAL/ec7bd4a05c.png https://puu.sh/tVQAL/ec7bd4a05c.png Apart from that however, I'm thoroughly enjoying this tutorial! It's remarkably similar to a tokenizer & parser I built when I was experimenting with a language that had no syntax, but was simply an AST that could be easily represented as Haskell/Python in the IDE of your choice. Really love how simplistic your code is though, mine just ended up being a mess of callbacks!

viebel 10y ago
Oh. This font is so ugly. What browser are you on?

monokrome 10y ago

Hopefully it isn't intentional to suggest that you need to be a genius "guy" to do this. To be fair, this is about where I closed the article so maybe I missed the point.

TazeTSchnitzel 10y ago
It's entirely orthogonal, but the other half of that, the implication you have to be a “genius” to write a compiler, also annoys me. Is it really rocket science? (I suppose it depends on what “real” means, though.)
OJFord 10y ago
The actual sentence is: > You probably have to be one of those genius guys ... Used in the plural, 'guys' usually just means 'people'/'folks' - "alright guys, shall we get going?" - Mac Dictionary agrees. Happy people don't go around looking to be insulted.

Msurrow 10y ago

This is great, thank you! I've been looking for something like this: a simple small project that goes through all the involved phases and explains/demonstrates the concepts, that I can mess around with on the weekends. It shouldnt be have real life applications, be serious or academically correct -- it should just be fun. I once found a blog post with an example of defining a grammar for a small language and then building an interpreter (in python i think) for it. It was really great, but I lost the link and can't seem to find it again. The same goes for OS'es - a simple but "end to end" walkthrough would be awesome. Anyway, cheers!

jonjacky 10y ago
> I once found a blog post ... but I lost the link ... Maybe this one? Python: Writing a Compiler and Interpreter in 160 lines of code http://www.jroller.com/languages/entry/python_writing_a_compiler_and http://www.jroller.com/languages/entry/python_writing_a_comp...
- Msurrow 10y ago
  Not the one, it was in multiple parts. BUT thanks - I'll read that one aswell :-)

camus2 10y ago

Mandatory link to lisperator : http://lisperator.net/pltut/ http://lisperator.net/pltut/

AstroJetson 10y ago

Look at Small C from the 70's. You could change the back end to target a different computer.