Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Super Tiny Compiler

github.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: The Super Tiny Compiler

#11

Post by eatonphil »

armchairhacker wrote: post #10
alcover wrote: post #5

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.

Some compilers tokenize while parsing, but for a different reason: it's faster and uses less memory to generate the AST (and sometimes even do analyses) while you're reading the input than to allocate and store a giant list of tokens and then parse that. 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 state…

> Some compilers tokenize while parsing, but for a different reason: it's faster and uses less memory to generate the AST

And some don't even generate an AST. :) Just read in and emit or interpret.

https://briancallahan.net/blog/20210814.html

Re: The Super Tiny Compiler

#12

Post by whstl »

dtgriscom wrote: post #9
alcover wrote: post #5

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.

Back in the day my Intro To Programming course taught the CLU programming language. I remember one cool feature of the compiler; when it hit a syntax error, it would show the error, skip a few lines until it found a stable place to resume parsing, and then continue compiling in order to catch more syntax errors. Pretty neat!

"skip a few lines until it found a stable place to resume parsing"

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.

Re: The Super Tiny Compiler

#13

Post by alxmng »

alcover wrote: post #5

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.

The purpose of tokenizing everything is to report all errors upfront. Imagine a big source file with two syntax errors. Tokenizing and parsing everything and reporting both errors with one compilation is a better user experience.

Re: The Super Tiny Compiler

#14

Post by alcover »

mostlylurks wrote: post #7
alcover wrote: post #5

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.

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 o…

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.

Re: The Super Tiny Compiler

#15

Post by swatcoder »

alcover wrote: post #14
mostlylurks wrote: post #7

Earlier quoted context omitted.

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 o…

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.

In a mature product, you would apply heuristics to help you provide the most useful feedback to the user while optimizing the time it takes to do so.

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!

Re: The Super Tiny Compiler

#16

Post by alcover »

armchairhacker wrote: post #10
alcover wrote: post #5

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.

Some compilers tokenize while parsing, but for a different reason: it's faster and uses less memory to generate the AST (and sometimes even do analyses) while you're reading the input than to allocate and store a giant list of tokens and then parse that. 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 state…

  > Some compilers tokenize while parsing, but for a different reason: it's faster and uses less memory
Rather legit reasons.. The one I'm writing does this. It seems akin to natural language processing. You'd interrupt a speaker early if you can't make sense of his uttering.

  > Most compilers try not to fail when they encounter a syntax error, they try to "recover" and parse the remaining document
This seems ardous for you'd maybe have to keep parallel explanations of what you read ?

Re: The Super Tiny Compiler

#17

Post by userbinator »

alcover wrote: post #5

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.

If you mean storing the whole tokenised input in memory before processing it again, then I'd say never, and go as far as calling it hugely wasteful and inefficient.

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.

Re: The Super Tiny Compiler

#19

Post by userbinator »

GuB-42 wrote: post #8

I thought is was about this: 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/ ), 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…

Whenever the subject of tiny learning-oriented compilers comes up, I always recommend C4: 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.

Re: The Super Tiny Compiler

#20

Post by dunham »

GuB-42 wrote: post #8

I thought is was about this: 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/ ), 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…

One of my favorites is the self-hosting Haskell compiler from the 2019 IOCCC: 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/

Post reply on HN