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

21–30 of 44 posts

Re: The Super Tiny Compiler

#21

Post by brennvin »

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.

Tokenizing everything in one go is usually the right approach. The typical case is the error-free case, so you won't actually tokenize more characters than necessary, but you will simplify the implementation and avoid jumping back and forth between parsing and tokenizing (thus improving locality).

Re: The Super Tiny Compiler

#22

Post by actually_a_dog »

JonChesterfield wrote: post #4
convolvatron wrote: post #2

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

* We're going to compile some lisp-like function calls into some C-like * function calls. From the top of the source file.

Yep, from test.js:

> const input = '(add 2 (subtract 4 2))';

> const output = 'add(2, subtract(4, 2));';

Re: The Super Tiny Compiler

#23

Post by 1letterunixname »

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.

Sounds like a 2 to 3 pass compiler or LL(k).

Better off pulling tokens from semantic analysis through parsing top down, LALR(1), SLR(1), or alternative context-sensitive parsing. Derivation parsing is scannerless.

Re: The Super Tiny Compiler

#24

Post by 1letterunixname »

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.

Strings typically have a token state context. Antlr allows pushing and popping a context state. Not a CFG and won't work with simple tools or book approaches.

Re: The Super Tiny Compiler

#25

Post by 1letterunixname »

swatcoder wrote: post #15
alcover wrote: post #14

Earlier quoted context omitted.

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!

Precise diagnostics usually follow one of 2 approaches:

1. Hand-written, recursive descent

2. Error matching expanded grammar beyond minimal gramar

Re: The Super Tiny Compiler

#26

Post by dang »

Related:

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)

Re: The Super Tiny Compiler

#27

Post by gnulinux »

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.

You got many answers, but I'll give another brutally honest answer: I do this because it's simply much much easier to implement. I would much rather have my AST generator's input be a token stream. It just simplifies everything.

Re: The Super Tiny Compiler

#29

Post by bmn__ »

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.

For the year 1970 and after: never. This should always be part of the parser for reasons of being confidently correct.

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.

Re: The Super Tiny Compiler

#30

Post by fooker »

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.

This is useful when your language is simple enough that you don’t need a real parser.

Fast lexer + cheap validator is a winning combo.

Post reply on HN