7 ms·

The Super Tiny Compiler

126 points by stefankuehnel 4y ago

convolvatron 4y ago
it wasn't clear at all from a 5 second skim of the code and looking at the readme what the source and targets were
- mat_epice 4y ago
  Ten seconds probably would have done it.
- JonChesterfield 4y ago
  * We're going to compile some lisp-like function calls into some C-like * function calls. From the top of the source file.
  - actually_a_dog 4y ago
    Yep, from test.js: > const input = '(add 2 (subtract 4 2))'; > const output = 'add(2, subtract(4, 2));';
  - Karellen 4y ago
    That's on lines 83/84. I'm not entirely sure that qualifies as the "top" of the source file. It's on the 4th page of the source file, given a traditional 80x25 terminal. (Assuming no wrapping, which the ascii art banner definitely could. A lot.)
alcover 4y ago
Question to compiler writers : when is it useful, if ever, to tokenize the whole input beforehand (as done here) ? You wouldn't catch an early syntax error and would go on tokenizing till the end for nothing.
- vitiral 4y ago
  I think most programming languages tokenize first. Tokenizing is absurdly fast, like 100x faster than printing to a terminal.
  - majewsky 4y ago
    > Tokenizing is absurdly fast is rather a very good reason to interleave tokenizing and parsing. Otherwise your tokenizer will just get stuck in iowait for no good reason.
    - vitiral 4y ago
      Sure, if shaving a millisecond off the execution time of your compiler is your idea of a good time.
- mostlylurks 4y ago
  Wrote a C-subset compiler for a compilers course back in university. In general it's useful for a compiler to not just hit the first error it can find in the source code and immediately error out. Instead, if you keep parsing after encountering an error, you can often encounter more errors, so that you can give the user a list of errors they need to fix, not just the first one. In that sense, a compiler's job isn't over the instant it encounters a syntax error, so the extra tokenization would not be useless.
  - alcover 4y ago
    I'm struggling with this idea. You could end up tokenizing the inside of an unopened string literal for (contrived) ex : String s = hello world"; [-> typename:'String' id's' op'=' id'hello' id'world' ...] And it would cascade if then foo("blah"); (...) [-> strlit';\nfoo(' id'blah' ...] A parser-first approach will stop with unknown id 'hello' and avoid the cascade.
    - swatcoder 4y ago
GuB-42 4y ago
I thought is was about this: https://bellard.org/otcc/otcc.c https://bellard.org/otcc/otcc.c (a tiny, obfuscated C compiler, winner of the 2001 IOCCC). It has led to TinyCC (https://bellard.org/tcc/ https://bellard.org/tcc/), not as tiny, but also more complete, not obfuscated and actually useful. It turns out the compiler in the article is the opposite of that. It it a simple toy transpiler and the code is very clear and mostly made of comments. The former is a feat of optimization, the latter is a tutorial.
- userbinator 4y ago
  Whenever the subject of tiny learning-oriented compilers comes up, I always recommend C4: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 It's a tiny self-compiling compiler which also includes a bytecode interpreter, and terse but also very understandable.
- dunham 4y ago
  One of my favorites is the self-hosting Haskell compiler from the 2019 IOCCC: https://www.ioccc.org/2019/lynn/hint.html https://www.ioccc.org/2019/lynn/hint.html There is a series of articles on how it was built here: https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/
quickthrower2 4y ago
Shout out for https://github.com/jneen/parsimmon https://github.com/jneen/parsimmon if you want to build a parser in JS
dang 4y ago
Related: A dynamic tutorial about a compiler in one JavaScript file (2016) - https://news.ycombinator.com/item?id=30129911 https://news.ycombinator.com/item?id=30129911 - Jan 2022 (7 comments) An ultra-simplified example of a modern compiler written in JavaScript - https://news.ycombinator.com/item?id=22522208 https://news.ycombinator.com/item?id=22522208 - March 2020 (27 comments) Super Tiny Compiler - https://news.ycombinator.com/item?id=11395656 https://news.ycombinator.com/item?id=11395656 - March 2016 (100 comments)
hinkley 4y ago
The file is 1053 lines long and the first 380 lines are comments. Including a big ascii banner. That seems deliberate.
nils-m-holm 4y ago
Lots of tiny, self-hosting compilers here: http://t3x.org http://t3x.org For example: Compiler for a procedural language, compiling to binary in 1500 lines: http://t3x.org/t3x/comp.html http://t3x.org/t3x/comp.html Super-portable tiny compiler for DOS, CP/M, Unix, and a VM: http://t3x.org/t3x/index.html#0 http://t3x.org/t3x/index.html#0 Self-hosting LISP compiler in 400 lines: http://t3x.org/lfn/liscmp.lisp.html http://t3x.org/lfn/liscmp.lisp.html
2dmodta04286 4y ago
[flagged]
DeathArrow 4y ago
> * We're going to compile some lisp-like function calls into some C-like > * function calls. Isn't this a transpiler, doing mostly string replacement?
- shadowofneptune 4y ago
  It still has to separate tokens, understand a nested structure, and output a different format. It's a small compiler, but is a compiler, and honestly understanding parsers can help a lot with text processing tasks.
hulitu 4y ago
> The Super Tiny Compiler Written in JS, runs in the (super big) web browser.

126 points by stefankuehnel 4y ago

convolvatron 4y ago

it wasn't clear at all from a 5 second skim of the code and looking at the readme what the source and targets were

mat_epice 4y ago
Ten seconds probably would have done it.
JonChesterfield 4y ago
* We're going to compile some lisp-like function calls into some C-like * function calls. From the top of the source file.
- actually_a_dog 4y ago
  Yep, from test.js: > const input = '(add 2 (subtract 4 2))'; > const output = 'add(2, subtract(4, 2));';
- Karellen 4y ago
  That's on lines 83/84. I'm not entirely sure that qualifies as the "top" of the source file. It's on the 4th page of the source file, given a traditional 80x25 terminal. (Assuming no wrapping, which the ascii art banner definitely could. A lot.)

alcover 4y ago

Question to compiler writers : when is it useful, if ever, to tokenize the whole input beforehand (as done here) ? You wouldn't catch an early syntax error and would go on tokenizing till the end for nothing.

vitiral 4y ago
I think most programming languages tokenize first. Tokenizing is absurdly fast, like 100x faster than printing to a terminal.
- majewsky 4y ago
  > Tokenizing is absurdly fast is rather a very good reason to interleave tokenizing and parsing. Otherwise your tokenizer will just get stuck in iowait for no good reason.
  - vitiral 4y ago
    Sure, if shaving a millisecond off the execution time of your compiler is your idea of a good time.
mostlylurks 4y ago
Wrote a C-subset compiler for a compilers course back in university. In general it's useful for a compiler to not just hit the first error it can find in the source code and immediately error out. Instead, if you keep parsing after encountering an error, you can often encounter more errors, so that you can give the user a list of errors they need to fix, not just the first one. In that sense, a compiler's job isn't over the instant it encounters a syntax error, so the extra tokenization would not be useless.
- alcover 4y ago
  I'm struggling with this idea. You could end up tokenizing the inside of an unopened string literal for (contrived) ex : String s = hello world"; [-> typename:'String' id's' op'=' id'hello' id'world' ...] And it would cascade if then foo("blah"); (...) [-> strlit';\nfoo(' id'blah' ...] A parser-first approach will stop with unknown id 'hello' and avoid the cascade.
  - swatcoder 4y ago

GuB-42 4y ago

I thought is was about this: https://bellard.org/otcc/otcc.c https://bellard.org/otcc/otcc.c (a tiny, obfuscated C compiler, winner of the 2001 IOCCC). It has led to TinyCC (https://bellard.org/tcc/ https://bellard.org/tcc/), not as tiny, but also more complete, not obfuscated and actually useful. It turns out the compiler in the article is the opposite of that. It it a simple toy transpiler and the code is very clear and mostly made of comments. The former is a feat of optimization, the latter is a tutorial.

userbinator 4y ago
Whenever the subject of tiny learning-oriented compilers comes up, I always recommend C4: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 It's a tiny self-compiling compiler which also includes a bytecode interpreter, and terse but also very understandable.
dunham 4y ago
One of my favorites is the self-hosting Haskell compiler from the 2019 IOCCC: https://www.ioccc.org/2019/lynn/hint.html https://www.ioccc.org/2019/lynn/hint.html There is a series of articles on how it was built here: https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/

quickthrower2 4y ago

Shout out for https://github.com/jneen/parsimmon https://github.com/jneen/parsimmon if you want to build a parser in JS

dang 4y ago

Related: A dynamic tutorial about a compiler in one JavaScript file (2016) - https://news.ycombinator.com/item?id=30129911 https://news.ycombinator.com/item?id=30129911 - Jan 2022 (7 comments) An ultra-simplified example of a modern compiler written in JavaScript - https://news.ycombinator.com/item?id=22522208 https://news.ycombinator.com/item?id=22522208 - March 2020 (27 comments) Super Tiny Compiler - https://news.ycombinator.com/item?id=11395656 https://news.ycombinator.com/item?id=11395656 - March 2016 (100 comments)

hinkley 4y ago

The file is 1053 lines long and the first 380 lines are comments. Including a big ascii banner. That seems deliberate.

nils-m-holm 4y ago

Lots of tiny, self-hosting compilers here: http://t3x.org http://t3x.org For example: Compiler for a procedural language, compiling to binary in 1500 lines: http://t3x.org/t3x/comp.html http://t3x.org/t3x/comp.html Super-portable tiny compiler for DOS, CP/M, Unix, and a VM: http://t3x.org/t3x/index.html#0 http://t3x.org/t3x/index.html#0 Self-hosting LISP compiler in 400 lines: http://t3x.org/lfn/liscmp.lisp.html http://t3x.org/lfn/liscmp.lisp.html

2dmodta04286 4y ago

[flagged]

DeathArrow 4y ago

> * We're going to compile some lisp-like function calls into some C-like > * function calls. Isn't this a transpiler, doing mostly string replacement?

shadowofneptune 4y ago
It still has to separate tokens, understand a nested structure, and output a different format. It's a small compiler, but is a compiler, and honestly understanding parsers can help a lot with text processing tasks.

hulitu 4y ago

> The Super Tiny Compiler Written in JS, runs in the (super big) web browser.