10 ms·
TinyCompiler: A compiler in a week-end
- glouwbug 2y agoI appreciate how wonderfully simple and dependency free this is. More often than not people just want to write a compiler of sorts without bison or yacc, or LLVM, and just convert expressions into assembler or vm-like instructions that _just run_. This is a great starting point for that, and I wish I had something like it 10 years ago. (Crenshaw's Let's Build a Compiler is an excellent source too if you want to go one step lower and go standard library free, focusing only on function call stacks: https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/)
- muth02446 2y agoShameless plug for another relatively small compiler written in Python with no dependencies: http://cwerg.org http://cwerg.org
- nurettin 2y agoNot to take away from the author or you, but we had things like this 10 years ago https://github.com/ymyzk/tinyc/tree/master/tinyc https://github.com/ymyzk/tinyc/tree/master/tinyc
- glouwbug 2y agoUnless I am mistaken, this uses LLVM?
- ymyzk 2y agoI'm the author of ymyzk/tinyc and was surprised to see my project mentioned here after more than 10 years. Since the README is written in Japanese, let me answer in English here. The project has two backends: one for NASM (x86) and another for LLVM IR.
- nurettin 2y agoIt can. It can also output x86 nasm, here's the relevant part. https://github.com/ymyzk/tinyc/blob/master/tinyc/generator/nasm.py https://github.com/ymyzk/tinyc/blob/master/tinyc/generator/n...
- fooker 2y agoI’d argue that you should start with doing an interpreter and push it as long as you can. But once you’re ready to generate code, use llvm or something like that because you are going to hit very problematic roadblocks early in your effort that will kill your interest in compilers otherwise. Some examples are: ensuring you can compare expressions for equality, ensuring that changed expressions don’t violate dominance, SSA conversion, avoiding infinite loops when analyzing cfgs. If you don’t start with knowledge of several things like this, you are looking at rewriting your compiler a dozen times. That is a great way to learn about compilers, but perhaps not the first compiler you make.
- Tor3 2y agoThat's great advance in the general, modern case.. however, I want to write small compilers for an archaic minicomputer where no llvm or similar exists or can exist, and for that purpose articles like this are inspirational and very useful.
- glouwbug 2y agoThat's right. Crenshaw's LBAC can make you an interpreter too. LBAC's magic lies in single token read ahead, single character identifiers, and single character digits. It parses its BNF grammar only with recursive function calls (no stacks, no tables for operator precedence, etc). The final language you build is almost useless, but it is done without a standard library (eg. resizable strings, resizable arrays, stacks, queues, associative containers), and serves as an introduction to get one hooked on more advanced compiler theory like SSA. I love OP's work. I consider OP's implementation (and similarities) to be a modern day LBAC. It's just that LBAC is one of those things I'd take to the grave. I have never found such a concise introductory text that produces a working final example in such delightful piecewise prose.
- mingodad 2y agoBut if otherwise anyone want to try with Yacc/Lex I have an online interpreter/editor with more than 250 examples to try/study at https://mingodad.github.io/parsertl-playground/playground/ https://mingodad.github.io/parsertl-playground/playground/ and just included a grammar for tinycompiler there (select "Tinycompiler parser" from "Examples" then click "Parse" to see a parse tree for the content in "Input source").
- bwfan123 2y agolovely from-scratch implementation, without the magic and complexity of lex and yacc. brings back memories from 30+ years ago when I implemented a subset of C in C using lex and yacc in a compiler course. in your blog, i would have liked to see the BNF grammar (without having to peek into the code). now, heres your next assignment :) - do the same for functional programming (lambda calc) or logic programming (prolog). That would round out the education on languages and compilers for computation.
- zvmaz 2y agoI don't think one can understand compilers in a "week-end".
- haqreu 2y agoThe "week-end" part refers to the fact that I wrote it in one week-end with little to no experience in compiler design. You can check the commit history, 12 to 14 Jan, 2024 :)
- not_a_bot_4sho 2y agoI think the "week-end" reference up above was a little tongue in cheek, since the modern spelling is a compound word: https://linguix.com/english/common-mistake/week_end_hyphen https://linguix.com/english/common-mistake/week_end_hyphen Not to take away from this awesome sharing.
- mattgreenrocks 2y agoOne weekend is enough to survey the general concepts. That’s extremely useful on its own, as now you have a better idea of how to orient yourself.
- ramon156 2y agoYou set your own bar. you could understand "how a compiler" in a day, but how much do you want to know?
- sieve 2y agoCompilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.
- sitkack 2y ago5 days if you don't, but have the right tutor.
- sitkack 2y agoOnly a happy customer, but if you want an amazing experience building a compiler I highly recommend David Beazley's Compiler Course (or anything else you can sign up for) https://www.dabeaz.com/ https://www.dabeaz.com/
- cellularmitosis 2y agoWhile I loved this week-long course, I was a bit disappointed that we offloaded all of the code generation to LLVM. I think it would be fantastic to stretch this into a two-week course and actually emit assembly.
- sitkack 2y agoWhen I took the course, each person did their own thing when it came to code generation. I don't recall anyone using LLVM. I think emitting assembly is easier than using LLVM. I would love a a longer course.
- keyle 2y agoFunnily enough, wend looks like what fun programming means to me. C like (prefixed types) syntax, strongly typed but without heartaches of pointers, and simple types. Every features on top of that has either leaky abstractions and/or nightmare scenarios. That said I'm not claiming the world should run on this type of code. Or should it.
- glouwbug 2y agoI think OP is just trying to demystify the complexity of compliers for the sake of an educational resource. It's high quality work, compressed to a very small line count
- andai 2y agoWell, Python and Pascal were designed as a teaching language, and ended up being remarkably good for actual programming.
- f1shy 2y agoAlso Basic, wasn’t it?
- keyle 2y agoI didn't know this regarding Pascal, do you have any source ref on this?
- zabzonk 2y agoFrom wikipedia: "Pascal was influenced by the ALGOL W efforts, with the explicit goals of teaching programming in a structured fashion and for the development of system software.[5] A generation of students used Pascal as an introductory language in undergraduate courses." Its grammar made it relatively easy to write compilers for the language, which could be done as undergraduate exercises. Of course, this did not make it so popular with professional programmers - see http://eprg.org/computerphile/pascal.pdf http://eprg.org/computerphile/pascal.pdf by Brian Kernighan, although extended Pascals such as Delphi were very productive in the Windows environment.
- jcuenod 2y agoThanks! I appreciate your discussion of semantic analysis for wend. I've literally just embarked on creating a (yet another) "compiles to JSX" language[0][1]. I'm using ANTLR for my lexer/parser, but I've just hit a point where I can start doing semantic analysis :) [0]: https://chicory-lang.github.io/ https://chicory-lang.github.io/ [1]: https://github.com/chicory-lang/chicory https://github.com/chicory-lang/chicory
- sylware 2y agoOn the same way than cproc+QBE I guess, 70% of gcc speed in my benchmarks. The more real-life alternatives to those abominations of gcc and clang, the merrier. I wish the linux kernel devs did care to keep the door _reasonably_ open for such compilers (with assembler source files as alternative to inline assembly, some extensions avoidance and niche expensive compiler features). This is another case of why super complex syntax computer languages should be avoided like hell (c++, rust, etc).
- mukunda_johnson 2y agoPretty neat. I would have expected it to take a bit longer, but I suppose the optimizing step is the real magic in a compiler.
- fogleman 2y agoI've been a big fan of the author's tiny renderer. Nice to see a tiny compiler too!
- kragen 2y agoThat sounds interesting! He seems to have four tiny renderers pinned on his GitHub page; is https://github.com/ssloy/tinyrenderer https://github.com/ssloy/tinyrenderer the one you're recommending? What do you like about it?
- vismit2000 2y agoMaybe they recommend that only given this is the one linked on the webpage of this post: https://ssloy.github.io/tinyrenderer/ https://ssloy.github.io/tinyrenderer/
- curtisszmania 2y ago[dead]
- dailykoder 2y agoThe fire.wend code[1] made me smile! I love how oneself tries to push boundaries with a language that barely can do anything, just do prove it to yourself that is works. Code is 10/10. Go for merge! :-) - [1] https://github.com/ssloy/tinycompiler/blob/main/test-programs/gfx/fire.wend#L86 https://github.com/ssloy/tinycompiler/blob/main/test-program...
- pjmlp 2y agoGreat project, this is how language exploration should start, and then carry it from there.
- delta_p_delta_x 2y agoInteresting off-topic—I noticed this paragraph: > Personally, I get a twisted pleasure wearing a T-shirt with this print in the 2020s, even though I hate being a walking billboard. But the number of angry comments from confused people makes up for any moral discomfort of advertising on my belly! It's possible the 'angry comments' are from people who may have mistaken it for an antisemitic, white supremacist symbol[1]. [1]: https://www.adl.org/resources/hate-symbol/not-equal https://www.adl.org/resources/hate-symbol/not-equal
- tsunego 2y ago[dead]
- atan2 2y agoI'm aware people here frown upon paid content but I am currently taking this course and it's excellent: https://pikuma.com/courses/create-a-programming-language-compiler https://pikuma.com/courses/create-a-programming-language-com...
- gustavopezzi 2y agoHey there. Thanks for the mention and for the kind words.