I Wrote a Compiler | Hacker News Reader

I Wrote a Compiler

blog.singleton.io

112 pointsingve71 comments

>The original authors of yacc were Mike Lesk and Eric Schmidt - yes that Eric Schmidt.

Incorrect, they were authors of lex. yacc was authored by Stephen Johnson.

Surprising to me is all the authors are still around, even though the tools are over 50 years old!. Shows how young computer science field is.

Who coauthored "The C Programming Language" anyway? Oh right, prof. Kernighan.

https://www.cs.princeton.edu/~bwk/

The “k” in awk, of course. I’ve never met Kernighan or Weinberger personally. I did have a great conversation once with Al Aho and Larry Wall, largely about the history and mutual influence of programming languages upon one another.

Eric Schmidt had a career at Sun Microsystems, though he is better known for Google of course.

yeah, he was 20 when he co-authored lex. Had a good career at Sun and was brought into Google as adult supervision and that was 20 years ago! Kind of living example of the (almost) entire history of computing.

This is very similar to the project I have in Chapter 2 of my new book Computer Science from Scratch [0]. It's also Tiny BASIC without INPUT. I called it NanoBASIC. But it's an interpreter not a compiler. This tutorial is a nice starting point. The chapter is much more comprehensive, so if you want to get into the weeds, I can recommend my own chapter (of course). But it's in Python, not Go. The code is on GitHub[1]. But this tutorial is great too.

0: https://nostarch.com/computer-science-from-scratch

1: https://github.com/davecom/ComputerScienceFromScratch

> It’s possible to write the lexer and parser entirely by hand

I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome.

One advantage of doing them by hand is better, more targeted error messages are easier to fold in.

I suspect that this is the more common opinion, especially when the desired outcome is real world use.

Recursive descent is surprisingly ergonomic and clean if one gets the heuristics right. Personally I find it way easier than writing BNF and its derivatives as you quickly get into tricky edge cases, slow performance and opaque errors.

Yeah, grammars seem easy at first, but they're full of arcane knowledge like writing your tokens with the right affinity and greediness, ensuring back tracking is performant, and that you'll get good error messages.

Same with parser combinators. Not until a bunch of trial and error do you build up the intuitions you need to use them in production, I think.

Despite two decades of using those, I've found it much simpler to write my own scanning or RD parser.

D was originally designed to require only one token lookahead, but it turns out to get the aesthetic I wanted, that arbitrary lookup was needed. That turned out to be very handy when adapting it to compile C code.

Much of the parser code, if you compare the code with the BNF grammar, is a 1:1 correspondence. Super easy to do.

> I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome.

It's also the most annoying if you're writing a new language. You want to iterate on its ideas, but can't do so until you have a parser done.

I've been designing a few language concepts over the past year, and it feels 80% of this time has been writing and debugging parsers; by the time I get to the meat of language design - the shape of its AST, the semantics of it - any small syntactic change means going back to update the lexer and parser stage. Doesn't help that I can't settle on a syntax.

BTW I first started with PEG, which are nice in theory, but I feel the separation of lexing and parsing stage to very helpful to reduce boilerplate (handling whitespace in PEG is obnoxious). Later, I hand-wrote my parsers (in C), but it's gotten so repetitive I've dedicated a weekend to just learning lex/yacc (actually flex/bison). Even if parsers are easy to write, it's good to have higher level tools to reduce the tedium of it.

There are other tools for prototyping the grammar for a new language. There are several online tools that can interactively parse input based on a given grammar. The one I developed is: https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu... The page does contain a sample grammar and sample input. For the grammar for the grammar see: https://fransfaase.github.io/MCH2022ParserWorkshop/index.htm...

  > You want to iterate on its ideas, but can't do so until you have a parser done.

Embed your language into host language. It is simple to do even in C++.

Iterate on ideas till your heart content, then add syntax.

Alternatively (or concurrently) use s-expressions and add syntactic sugar later.

Anecdotally, lex and yacc gets your prototype up and running quickly, but the ongoing adjustments needed winds up with it behind. The time lost comes from:

1. having to learn lex and yacc

2. running into limitations with lex and yacc

3. having a foreign program (i.e. lex and yacc) integrated into your build process

4. requiring a particular version of lex and yacc that may be awkward on multiple platforms

5. optimizing the code. (Once you start doing that, you cannot use lex/yacc to generate a new version.)

And so on.

At one point, we decided to write a D program that built the D compiler, instead of using make. Well, that turned out to be a greater time sink than just using make.

In my lifetime parsers have gone from: written by hand with great effort, to: use a parser generator to be sure the grammar is correct and save effort, to: just write by hand because it's not that hard and error reporting, to: just use AI.

Out of curiosity, have you had luck using LLMs for parser generation? I should really try it out with my parser combinator library; would be cool to be able to throw in sample code and some basic instructions and get a usable parser out for prototyping. Think I might try that next time I build a new language, just for fun.

> just use AI

I suspect you might spend more time trying to specify what you want to the AI than just writing it.

I don't think I know any lang devs who don't write their own parser. Beyond just being the easiest part it's also the most fun, and it's the thing that gets you sucked in the first place. If you're using a generator you're missing out.

Another advantage is error recovery code can be made much better. Yacc and lex don't know what common errors are, but you as the language designer knows what the most likely intention of the user was.

Yacc/lex tend to produce generic error messages and do very poorly with error recovery.

Can't pass by without mentioning this amazing post about parsing with error recovery: https://matklad.github.io/2023/05/21/resilient-ll-parsing-tu...

TinyBASIC is fun and beautifully simple. I wrote a 3-part tutorial for making a TinyBASIC-to-C compiler using Python a few years ago.

Let’s make a Teeny Tiny compiler https://austinhenley.com/blog/teenytinycompiler1.html

I know BASIC is kind of a “bad” language, but there’s something so delightful about it. If we’re plugging TinyBASIC projects that others might find interesting, I made an MMO TinyBASIC REPL the other day: http://10klob.com/

BASIC is an amazing language that computing novices (including humanities majors) could learn in an afternoon, that could be efficiently compiled or compactly interpreted, that was small enough to support dozens of interactive users on a mainframe or minicomputer, or to fit into a tiny 8-bit microcomputer – and yet was largely equivalent to FORTRAN in terms of its expressive power.

I think the closest modern equivalents might be Python (for easy onramp and scalability from microcontrollers to supercomputers) and JavaScript (for pure ubiquity in every device with a web browser.)

I wonder if there is a modern-ish (?) environment that can match Visual BASIC in terms of easy GUI app programming. Perhaps Python or Tcl with Tk (Qt seems harder) or maybe Delphi, or perhaps a modern Smalltalk.

Delphi for sure. And while you have to run it on Windows, it can create binaries for Windows, macOS, Linux, and mobile.

https://www.embarcadero.com/products/delphi

FreePascal and Lazarus get you close on other platforms I think. It’s been ages since I’ve looked into it.

Yes, but I'd argue the price of Delphi is totally worth the issues you would then avoid by not using Lazarus.

I thought Lazarus/FreePascal are 100% compatible with Delphi. Is that not the case?

Delphi, and naturally Visual Basic for .NET with Windows Forms, not forgeting about C#, however it is getting a bit too much featurities lately, and most likely not what the BASIC target audience would like.

Well this afternoon bit...

Advanced BASICs are too big for that, and in less advanced ones you get to POKE the hardware to do certain things. Which means you get to learn a bunch of hardware and machine code. That's not all bad though!

People too often complain about original BASIC, and forget most dialects moved away from line numbers and spaghetti GOTOs during the 16 bit days, with widepsread of compilers and structured constructs.

I am really glad that I only got to learn C, after getting through Turbo Basic, Quick Basic, Turbo Pascal[0], doing exactly the same kind of stuff urban myths say it was only possible after C came to be.

[0] - On 16 bit systems, I started coding on an 8bit Timex 2068.

>The original authors of yacc were Mike Lesk and Eric Schmidt - yes that Eric Schmidt.

I don't know if it's worth mentioning, but the author of the post is David Singleton, the former CTO of Stripe. I almost hadn't noticed until I saw the domain.

I worked ~4 layers underneath him when he led Android Wear at Google, and every year or two that happens to me, and it puts a smile on my face. Gotta have love of the game to do this at that level.

IIRC, and man, maybe I'm making it up, but, lore was he always made time on a regular schedule to hack.

Usually 1 layer from the bottom isn't coding so much anymore.

(oddly, I didn't realize he was *CTO* of Stripe until a few months back, when his new thing with Hugo Barra was announced)

I have played around with the Crafting Interpreters book. Maybe the author oversimplifies a bit, but it seems with yacc and lex that nothing is really stopping anyone from making their own language and compiler. It always seemed like black magic.

But the same could be said about books, nothing is stopping you from writing a book except good ideas, story, and structure.

Since 1990, I have developed software with C and later C++. Now that I am working on a C compiler, I am learning new things about the language. So, writing a compiler (or an interpretter) can really help to get a deep understanding of a programming language.

I like these kind of fun projects!

I wrote a very small but complete compiler and VM for a very simple language: boolean expressions. I use it as a "what to expect" type of introduction during the first session of my compiler course.

The whole code is here, it is less than 150 lines of OCaml code (plus a few lines of C for the VM) and uses standard parsing tools: https://gist.github.com/p4bl0-/9f4e950e6c06fbba7e168097d89b0...

This is great! I feel like there's been a resurgence of interest in language design and compilers of late. I have no business having an interest in this kind of thing, but even I have been inspired to try and make the changes to javascript that I think would improve it: https://chicory-lang.github.io/

I thought a compiler, with no adjective or caveat, should turn a HLL into machine language. Isn't what this describes—turning BASIC into Go—more accurately described as a "pseudocompiler" or "Go compiler" or somesuch? I know Emacs is always said to have a "bytecode compiler" that processes Elisp code, not a "compiler" per se. Am I mistaken?

The standard term for this kind of compiler is "transpiler", afaik.

Here's the Wikipedia page for such things, which also taught me several other names for them:

https://en.m.wikipedia.org/wiki/Source-to-source_compiler

The standard term for "transpiler" is "compiler", though.

So, if he had invoked go for you would it be a compiler? Another definition is that it translates a source language into a target language.

What would you call TypeScript’s tsc, which translates TS to JS? Microsoft would say it’s a compiler: https://code.visualstudio.com/docs/typescript/typescript-com...

They do, but that article also mixes “transpile” and “compile” often enough that it is near impossible to deduce what different meanings they might ascribe.

Strictly speaking it's a transpiler, but honestly the delta between the target language (Go) and the source language (BASIC) is very fluffy and wooly, from what I remember from my PL theory days the distinction was always fuzzy enough that people used whatever term felt right to them.

An example off the top of my head — Chicken Scheme (call-cc.org) calls itself a compiler but it's target language is C

"Transpile" is a shortening of the older term "trans-compile". [0]

It's a subset. All transpilers are compilers. Not all compilers are transpilers.

[0] Amiga BASIC called itself a transcompiler, from memory.

yes, that's correct :)

This kind of question winds up being the CS equivalent of “is a hotdog a sandwich”. I agree that transpiler is a more accurate term for it and that a hotdog is not a sandwich. But there are lots of languages that start life as compile-to-C things. Many compiled languages today output LLVM IR which is not machine language. Similarly people would probably call javac a compiler, even though it outputs bytecode.

A compiler is a language translator. To me it makes no difference whether it generates machine code (one type of language, machine executable), asm (equivalent language but which needs additional preprocessing into machine code), or some other language (which also needs additional preprocessing into machine code, but the tool for this is another compiler). Or it might output Java bytecode or MSIL, which doesn't even target a real, physical machine at all.

They translate one language into another. The line between compiler/transpiler just doesn't make sense to me.

Let's put it this way: if a program translates code written in a "smarter" language into code written in a "stupider" language, then it is okay to call it a compiler.

If it translates a restricted subset of BASIC into Go, it doesn't really do anything beyond replacing one syntax with another.

"Smarter" and "stupider" are completely subjective terms.

It translates one language into another, while maintaining logical correctness and its original semantics. Some cases are easier to do than others, but it doesn't change the nature of what is being done: language translation.

It isn't as simple as you think. Ex. in basic, the goto statement allows you to jump from anywhere to anywhere. Go has restrictions, such as it may not jump over variables coming into scope (being declared), nor can it jump into another scope, only outwards. So, for starters, this probably needs to scan the BASIC code for variables and hoist everything to the top as well as rewrite any code where it is trying to jump into a deeper scope (ex. jump from the topmost scope of a function into the body of a for loop).

Yes, it is a compiler. Maintaining semantics.

A compiler is any program that translates from one language to another (source-to-source, source-to-bytecode, or source-to-machine code), so translating BASIC to Go is indeed a proper compiler, just as GCC translating C to LLVM IR before machine code is still a compiler.

The original term for "compiler" was not restricted to compiling down to machine code. From Grace Hopper's paper "The Education of a Computer" (1952)[1]:

   Specifications for computer information, a catalogue, compiling routines, and subroutines will be given after adding another level to the block diagram. As Fig. 5 stands the mathematician must still perform all mathematical operations, relegating to the UNIVAC programming and computational operations. However, the computer information delivered by the mathematician no longer deals with numerical quantities as such. It treats of variables and constants in symbolic form together with operations upon them. The insertion of a fourth level of operation is now possible, Fig. 6. Suppose, for example, the mathematician wishes to evaluate a function and its first n derivatives. He sends the information defining the function itself to the UNIVAC. Under control of a "compiling routine of type B", in this case a differentiator, using task routines, the UNIVAC delivers the information necessary to program the computation of the function and its derivatives. From the formula for the function, the UNIVAC derives the formulas of the successive derivatives. This information processed under a compiling routine of Type A yields a program to direct the computation.

Notice the case for two "compilers": Compiler B (differentiator) compiles symbolic notation to another program, that is fed to Compiler A, which produces an executable that does the actual computation.

IMO, a better term for a compiler would have been a "translator."

[1] https://dl.acm.org/doi/pdf/10.1145/609784.609818

Thank you for digging this up. I agree about "translator". They were called "compilers" because the first ones were little more than linkers.

Indeed. I believe the first use of the word compiler (by Hopper and her team) was to describe "compiling" a bunch of existing machine code subroutines into a whole program, rather than translating one language into another.

BASIC is a good candidate for an easy language to implement. I'd also propose Pascal, Lisp (because S-expressions make parsing easier), and FORTH.

Writing a compiler without first learning how to write a parser is like learning to play an instrument without practicing scales.

> Yes, this is what I do for fun.

Don't we all? ;-)

How does one debug a grammar? This has always eluded me.

Where is the special tooling to help spot errors?

I am probably misunderstanding your requirements but if you are looking for something like regex101 then https://omrelli.ug/nearley-playground/ and https://bnfparser.firebaseapp.com/ although not sure how much 'practical' are they. Googling gives [2], [3], [4].

[2] https://mingodad.github.io/parsertl-playground/playground/ not sure.

[3] https://chrishixon.github.io/chpeg/playground/

[4] https://mdkrajnak.github.io/ebnftest/

Thanks!

If you use something like Antlr (https://www.antlr.org/) it has visualization tools and an online tester (http://lab.antlr.org/). There are also tools for visualizing generic EBNF grammars like this: https://jacquev6.github.io/DrawGrammar/

Notably, this is written by David Singleton, who at the time was the CTO of Stripe.

Love reading these. Keep these blog posts coming!

nice to see that the red dragon book is still a thing. I've heard people have stopped using the wizard book.

Wait! What are == and != doing in a BASIC language? Heresy! :)

Yeah, I really should have included <> :-)

Fun to see this post from the deep archive get some interest - thanks for reading!

I wrote a full fledged interpreter by hand for a vintage BASIC language. I called it Basice (I'm Icemanind, so Basice is a play on BASIC and Iceman). It's a little outdated now though. I wrote it using C# and it doesn't use any external libraries, like yacc or flex. It's all by hand. You can see it at https://github.com/icemanind/Basice

Reply on news.ycombinator.com