The Super Tiny Compiler
github.com
github.com
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.
It's a tiny self-compiling compiler which also includes a bytecode interpreter, and terse but also very understandable.
There is a series of articles on how it was built here: https://crypto.stanford.edu/~blynn/compiler/
For example:
Compiler for a procedural language, compiling to binary in 1500 lines: 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
Self-hosting LISP compiler in 400 lines: http://t3x.org/lfn/liscmp.lisp.html
A dynamic tutorial about a compiler in one JavaScript file (2016) - 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 - March 2020 (27 comments)
Super Tiny Compiler - https://news.ycombinator.com/item?id=11395656 - March 2016 (100 comments)
You wouldn't catch an early syntax error and would go on tokenizing till the end for nothing.
is rather a very good reason to interleave tokenizing and parsing. Otherwise your tokenizer will just get stuck in iowait for no good reason.
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.
String s = hello world";
[-> typename:'String' id's' op'=' id'hello' id'world' ...]
foo("blah"); (...)
[-> strlit';\nfoo(' id'blah' ...]
unknown id 'hello'
Users love consolidated, efficient feedback without having to peel back errors one at a time. It’s a distinguishing feature when you can find a way to do it that suits your input, and specifically so because it can be a hard problem to solve well!
1. Hand-written, recursive descent
2. Error matching expanded grammar beyond minimal gramar
That's interesting! I always assumed it was always more complex than that, I love it. How reliable is this method btw? I'm specifically curious about the risk of catching false positives due to failing to parse some sections, such as missing goto labels, or unused variables.
Most compilers try not to fail when they encounter a syntax error, they try to "recover" and parse the remaining document, usually starting from the next valid statement or declaration. This lets them report more syntax errors and moreover, is very important for good IDE support (if you've ever used an IDE/language combo where you only get completion after you've written the code, you know why). Although if the syntax error messes up tokenization (e.g. missing quote or end comment) it usually screws up the rest of the document anyways.
And some don't even generate an AST. :) Just read in and emit or interpret.
> Some compilers tokenize while parsing, but for a different reason: it's faster and uses less memory
> Most compilers try not to fail when they encounter a syntax error, they try to "recover" and parse the remaining document
But if you're reading a book and can't understand a sentence, you'll probably glance at the rest of the page to see if there are clues in the context.
Maybe it's a printing error and a paragraph has been repeated. A human who sees the entire page will detect that problem immediately and simply skip over the repeated paragraph. A computer that gives up at the first sight of incongruency has no idea that recovery was so easy.
The analogy here might be relevant to error messages. A compiler that "sees the whole page" can potentially offer more useful suggestions to the programmer about how to fix a problem.
The other comments here about catching all errors is valid, but you don't need to store any of the previous output to do so. The tokeniser can provide a token at a time as necessary, and thus also provide errors in the same way.
Better off pulling tokens from semantic analysis through parsing top down, LALR(1), SLR(1), or alternative context-sensitive parsing. Derivation parsing is scannerless.
Thinking otherwise just leads to suffering. The problem with tutorials like Tiny Compiler or Crafting Interpreters is that the authors do not run into problems with the code shown in their teaching materials, but as soon as a student wants to apply it to modestly complex grammars, it stops working. The authors traded conciseness for correctness which IMO is a bad trade-off, especially since a reasonably complete implementation of a parsing algorithm that has no shortcomings is perhaps only four to six times longer than a short and flawed one.
The point of this critique is to raise awareness; each student should not have to figure out that they got the bad end of said trade-off by trial and error, instead the teaching material should make this clear initially.
>> never
> nope you are wrong. I never tokenise everything up front
Explain how you could possibly arrive at the complete opposite meaning of what I wrote when you even use the same word "never" as I did?
Quick, get another downvote in, that'll teach me! Peak HN moment here.
I upvoted your correction.
Fast lexer + cheap validator is a winning combo.
> * function calls.
Isn't this a transpiler, doing mostly string replacement?
Written in JS, runs in the (super big) web browser.
From the top of the source file.
> const input = '(add 2 (subtract 4 2))';
> const output = 'add(2, subtract(4, 2));';