I Built a Ruby Parser
mpov.timmorgan.org
mpov.timmorgan.org
I think learning to write interpreters is one of those fundamental skills that everyone should learn at some point in their programming careers. Not because there's a good chance they'd create a popular language out of it (though who knows, I definitely think we could use some new ideas in PLT), but because it removes almost all of the "black magic" feel of programming.
You see arguments for days about "OOP vs FP" and other such faff. And once you've implemented OOP and implemented FP in your own language, it's all just... window dressing. It's all the same thing, just different ways of slicing it. There's nothing inherently evil about one or the other.
You can always do a 2nd project with your interpreter, where you compile down to a bytecode, then JIT the bytecodes to machine language.
But the primitive substrate of the machine (be it real or virtual) turns implementing that execution model into a puzzle all its own. You might implement an array in your interpreted language as just an array in your host language. You might implement an object as just a HashMap between field names and values in your host language. Interpreters don't have to build their own interfaces with the operating system, they reuse those interfaces from the host language in which they are developed, but a compiled language will need some way of its own to execute system calls.
Like, printing some text to a terminal. Say we were implementing an interpreted language in C#. We get to the point of writing our own "print" function for our own language. We'll probably end up creating some kind of translation from our language's print format to some kind of call to System.Console.WriteLine in C#. You might even like the format of Console.WriteLine, so you might even make it a straight, one-to-one translation and call it a day.
But if you're writing a compiled language, you'll need to know how the operating system you're running on expects to receive and execute commands. That's a whole other thing. To grossly oversimplify, it largely means getting a bunch of bytes into the right format and order into memory and then executing a specific CPU instruction. Want to allocate memory? There's another blob-of-memory-plus-execute-an-instruction interface you'll need to adhere to. Want to open a network socket? Same. And modern operating systems provide a lot of functionality.
But also, a lot of that work is kind of grunt work. There are certainly ways you can design a language that make it more difficult to implement as a compiled language than an interpreted one (dynamic typing, for example). Let's gloss over that issue. All else being equal, the language portion of the work being done in interpreters versus compilers is largely the same.
From your compiler's perspective you shouldn't be messing around with all that, you should have an abstraction that lets you say "Pass a by value, b by reference, and c as an out parameter using calling convention X". As long as malloc and opensocket or whatever use the same calling convention, all of the actual byte layout is a one time effort.
Note that taking this broader definition of compilers, it is not necessary for a compiler writer to target the host architecture or learn about the sys calls. Many languages have a non-native host target, e.g. Typescript (javascript), Scala (jvm) and F# (.Net), but we still call the programs that translate source written in these languages to the target executable format compilers.
Going from an interpreter to a transpiler, which I personally consider a compiler, can be an almost trivial step. Let's assume that there is already an interpreter for the language and that it is implemented as a giant switch statement based on the op code of each instruction. Given an arbitrary target language in which all of the required instructions of the interpreter have a concrete representation, one could write a transpiler to this target language by replacing the right hand side of each statement in the switch with code that appends to a source file in the target language (there'd also generally need to be some surrounding boiler plate to do things like import required headers).
In practice, these days it is quite common for languages to transpile to C, LLVM IR, the JVM or Javascript. Even if one does want to emit their own machine code, it would still probably make sense to first target something simpler and not waste time in the low level details of language features that may or may not even prove useful (or the language itself may not prove useful). Again, going from interpreter -> transpiler can be a simple step. It is not unrealistic to write a useful transpiler in a day, particularly if you make the language syntax very simple and/or use a parser generator.
I think that's a very fair definition, and one I agree with completely. But I also admitted that I was grossly oversimplifying, which I thought was necessary given the stated background of the person I was responding to. As you pointed out, the step from interpreter to transpiler is almost trivial. My goal was to attempt to describe the much less trivial portions of the work without getting too bogged down in details.
But you make good points about transpilers that I probably should have mentioned. Lots of very good, very valuable work has been done with languages that have not gone all the way to emitting CPU-specific op codes.
See for instance https://news.ycombinator.com/item?id=5182864
In my professional career, I have written dozens of domain-specific languages for dealing with things like asynchronous protocols, complex configuration, and even safer code generators. It's a great skill to have, and it has greatly contributed to building real products that just wouldn't be possible or wouldn't be built to such exacting quality otherwise.
Separately, I'm curious about how a parser generated out of ANTLR/yacc etc compares to this hand written one? If you've done some benchmarking, it'd be great to see numbers!
I've been reading about parsers recently (https://www.craftinginterpreters.com/contents.html and https://peps.python.org/pep-0617/). It seems like recursive descent parsers are considered a little easier to reason about, and PEG aligns well with recursive descent.
I have not yet dived deeper in yacc, bison, or ANTLR and how you would write a parser from a CFG. Can anyone add their experiences?
Many of them are incomplete, but it gives a good idea of how the grammar looks for ANTLR.
I used the ANTLR grammar for parsing CSS in DiffLens (https://github.com/marketplace/difflens). DiffLens uses the typescript compiler itself to parse TS and JS.
I've also used Roslyn to parse C# (and F#). I wonder if the ruby compiler itself exposes a parser.