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

Revisiting "Let's Build a Compiler"

eli.thegreenplace.net

Post reply on HN
Print view View original

31–40 of 53 posts

Re: Revisiting "Let's Build a Compiler"

#31

Post by VonTum »

mutkach wrote: post #21
VonTum wrote: post #20

Earlier quoted context omitted.

I've used tree-sitter for generating my parsers in Rust, and just working with the untyped syntax tree it generates, and gives you error-tolerance for free. It's a bit of a setup at first tho, requiring an extra crate for the generated parser, but editing it from there saves so much time.

What do you mean exactly by "error-tolerance"? Is it like, each node is wrapped into a result type, that you have to match against each time you visit it, even though you know for a fact, that it is not empty or something like that? I suppose that one of the pros of using tree-sitter is its portability? For example, I could define my grammar to both parse my code and to do proper syntax highlighting in the browser wi…

Oh nono, with tree-sitter, you get an untyped syntax tree. That means, you have a Cursor object to walk the tree, which creates Node objects as you traverse, that have a "kind" (name of the tree-sitter node), span, and children. (I recommend using the rust tree-sitter bindings itself, not the rust wrapper rust-sitter).

Yes, portability like that is a huge benefit, though I personally utilized it for that yet. I just use it as an error-tolerant frontend to my compiler.

As to how errors are reported, tree-sitter creates an ERROR or MISSING node when a particular subtree has invalid syntax. I've found that it never leaves a node in an invalid state, (so never would it create a binaryop(LeftNode(...), Op, ERROR) if RightNode is not optional. Instead it would create an ERROR for binaryop too. This allows you to safely unwrap known fields. ERROR nodes only really bunch up in repeat() and optional()s where you would implicity handle them.

For an example, I can only point you to my own use: https://github.com/pc2/sus-compiler

tree-sitter-sus has the grammar

sus-proc-macro has nice proc macros for dealing with it (kind!("binop"), field!("name"), etc)

src/flattening/parser.rs has conveniences like iterating over lists

and src/flattening/flatten.rs has the actual conversion from syntax tree to SUS IR

Re: Revisiting "Let's Build a Compiler"

#32

Post by tester756 »

mutkach wrote: post #11
hashtag-til wrote: post #5

For modern compiler and a more direct approach I recommend https://www.cs.cornell.edu/~asampson/blog/llvm.html

LLVM makes it so much easier to build a compiler - it's not even funny. Whenever I use it, I feel like I'm just arranging some rocks on a top of a pyramid.

Yet if only it wasnt that huge, so compilation takes this much time :/

Re: Revisiting "Let's Build a Compiler"

#33

Post by dang »

Revisiting "Let's Build a Compiler" threads:

Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=38773049 - Dec 2023 (15 comments)

Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=36054416 - May 2023 (19 comments)

Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=22346532 - Feb 2020 (41 comments)

Let's Build a Compiler (1995) - https://news.ycombinator.com/item?id=19890918 - May 2019 (18 comments)

Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=6641117 - Oct 2013 (56 comments)

Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=1727004 - Sept 2010 (17 comments)

Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=232024 - June 2008 (5 comments and already complaining about reposts)

Let's build a compiler (dated, but very good) - https://news.ycombinator.com/item?id=63004 - Oct 2007 (2 comments)

It seems there aren't any (interesting) others? I expected more.

But there is this bonus:

An Interview with Jack Crenshaw, Author of the “Let’s Build a Compiler” - https://news.ycombinator.com/item?id=9502977 - May 2015 (0 comments, but good article!)

Re: Revisiting "Let's Build a Compiler"

#34

Post by flufluflufluffy »

mutkach wrote: post #21
VonTum wrote: post #20

Earlier quoted context omitted.

I've used tree-sitter for generating my parsers in Rust, and just working with the untyped syntax tree it generates, and gives you error-tolerance for free. It's a bit of a setup at first tho, requiring an extra crate for the generated parser, but editing it from there saves so much time.

What do you mean exactly by "error-tolerance"? Is it like, each node is wrapped into a result type, that you have to match against each time you visit it, even though you know for a fact, that it is not empty or something like that? I suppose that one of the pros of using tree-sitter is its portability? For example, I could define my grammar to both parse my code and to do proper syntax highlighting in the browser wi…

Error tolerance in this context means the parser produces a walkable AST even if the input code is syntactically invalid, instead of just throwing/reporting the error. It’s useful for IDEs, where the code is often in an invalid state as the developer is typing, but you still want to be able to report diagnostics on whatever parts of the code are syntactically valid.

Re: Revisiting "Let's Build a Compiler"

#36

Post by bokchoi »

dang wrote: post #33

Revisiting "Let's Build a Compiler" threads: Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=38773049 - Dec 2023 (15 comments) Let's Build a Compiler (1988) - https://news.ycombinator.com/item?id=36054416 - May 2023 (19 comments) Let’s Build a Compiler (1995) - https://news.ycombinator.com/item?id=22346532 - Feb 2020 (41 comments) Let's Build a Compiler (1995) - https://news.ycombinator.com/item?…

Thanks! The interview with Jack Crenshaw was great!

Re: Revisiting "Let's Build a Compiler"

#37

Post by norir »

hashtag-til wrote: post #5

For modern compiler and a more direct approach I recommend https://www.cs.cornell.edu/~asampson/blog/llvm.html

Using LLVM is an indirect approach that will limit the quality of your compiler.

When one looks at languages that use LLVM as a backend, there is one consistent property: slow compilation. Because of how widespread LLVM is, we often seem to accept this as a fact of life and that we are forced to make a choice between fast runtime code and a fast compiler. This is a false choice.

Look at two somewhat recent languages that use LLVM as a backend: zig and rust. The former has acknowledged that LLVM is an albatross and are in the process of writing their own backends to escape its limitations. The latter is burdened with ridiculous compilation times that will never get meaningfully better so long as they avoid writing their own backend.

Personally, I find LLVM a quite disempowering technology. It creates the impression that its complexity is necessary for quality and performance and makes people dependent on it instead of developing their own skills. This is not entirely dissimilar to another hot technology with almost the same initials.

Re: Revisiting "Let's Build a Compiler"

#38

Post by microtherion »

fuzztester wrote: post #6
statictype wrote: post #2

This article sums it up perfectly. I was interested in building a compiler long before going to college and this was the most accessible body of work. Building a recursive descent parser from scratch was an eye opener to 17yo me on how a seemingly very complex problem that I had no idea how to approach can be made simple by breaking it down into the right primitives.

>a seemingly very complex problem that I had no idea how to approach can be made simple by breaking it down into the right primitives. https://en.wikipedia.org/wiki/Niklaus_Wirth From the Publications section of that Wikipedia page: >The April 1971 Communications of the ACM article "Program Development by Stepwise Refinement",[22][23] concerning the teaching of programming, is considered to be a classic text in softw…

Wirth also wrote an extremely accessible book on Compiler Construction, using exactly the hand written recursive descent parsing approach discussed by OP.

The initial edition was published in 1976, in German, but the latest version is available online:

https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil...

There are also parser generators like ANTLR (https://en.wikipedia.org/wiki/ANTLR) which take an input not unlike yacc, but generate a LL parser using explicit code, rather than the table driven LALR parsing of yacc.

Re: Revisiting "Let's Build a Compiler"

#39

Post by anthk »

The easiest example: an interpreter for the Subleq VM. One instruction. Literal three or four lines, three more (if any) for I/O.

https://github.com/howerj/subleq/

As a goodie you can run Eforth on top which almost writtes itself. Compiler, interpreter, editor, IDE and a Sokoban, all in a simple VM.

Let's scale. Mu808/n808. Interpreters in C and AWK, a compiler in Python.

https://codeberg.org/luxferre/n808

You have the exact assembly algorithm in the page. What you see it's what you get. Now, for real, I'd suggest getting lvltl (VTL-02) interpreter written in C for a "bigger" language running not just under a VM, but for small machines and simulators such as the 6502 based Kim-1 and Apple1. With that "not enough to be called Basic" a Sokoban might be written with a bit of patience.

Re: Revisiting "Let's Build a Compiler"

#40

Post by fuzztester »

microtherion wrote: post #38
fuzztester wrote: post #6

Earlier quoted context omitted.

>a seemingly very complex problem that I had no idea how to approach can be made simple by breaking it down into the right primitives. https://en.wikipedia.org/wiki/Niklaus_Wirth From the Publications section of that Wikipedia page: >The April 1971 Communications of the ACM article "Program Development by Stepwise Refinement",[22][23] concerning the teaching of programming, is considered to be a classic text in softw…

Wirth also wrote an extremely accessible book on Compiler Construction, using exactly the hand written recursive descent parsing approach discussed by OP. The initial edition was published in 1976, in German, but the latest version is available online: https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil... There are also parser generators like ANTLR ( https://en.wikipedia.org/wiki/ANTLR ) which take an input…

Thank you. Just to confirm, by "accessible", do you mean easy to understand?

Anyway, I think I had come across that book on the net, but did not check it out at the time. I don't remember the exact reason, maybe it was because I didn't want to go into the subject of compilers at the time, and was only interested in interpreters, because I prefer to take things one step at a time.

Now I will check it out.

Post reply on HN