5 ms·
I Built a Ruby Parser
- rambambram 4y agoNice read and good job. You can be proud on yourself!
- hiepph 4y agoBig shout out to "Writing an Interpreter In Go". I followed along for about a month. The code is clearly written and tested. It's practical enough with theory explanation along the way. Now I feel confident to write a Lua interpreter in Go (considered Lua is simple enough).
- moron4hire 4y agoThere is a popular saying (especially amongst The Olds) that "you don't understand programming until you understand pointers." I found it to be the opposite: I didn't understand pointers until after I had been programming for years and then implemented my first, interpreted scripting language. 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.
- ammanley 4y agoRandom question from someone who is is self-taught and doesn't know better: is there a significant difference in this saying about learning interpreters vs learning to write your own _compiler_? Or are the two functionally equivalent for learning purposes?
- stcredzero 4y agoI'd say that either one is good. Writing your own compiler, depending on how you do it, will get you into assembly and machine language, which will benefit your understanding of the lowest levels of computers, and of the low-level mechanisms behind concurrency and operating systems. You can always do a 2nd project with your interpreter, where you compile down to a bytecode, then JIT the bytecodes to machine language.
- ammanley 4y agoI do like that idea, thank you.
- moron4hire 4y agoI'd say there's probably about 1/2 to 2/3rds overlap between the two. You'd still need to do all the same lexing and parsing. You still need to create a model of execution for your 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.
- tylerscott 4y agoI second your opinion that learning to write an interpreter is a great idea at some point in a career. It definitely helped me gain a new level of understanding and, well, confidence in my knowledge of how pretty much any language “works”. It makes everything more interesting, too!
- jxf 4y agoI'll always root for new fundamental tools, even toy examples. That's how broader change happens.
- brink 4y agoFunny enough, I started one a few weeks ago too. I wanted to do some basic automatic type checking. Though I will probably never finish it. https://github.com/codabrink/tolkien https://github.com/codabrink/tolkien
- vidarh 4y agoThere are many at this point...
- toniks 4y agoThanks. Can you recommend some free resources to learn from?
- runevault 4y agoCrafting Interpreters is probably the gold standard. They do phase 1 in Java and phase 2 in C but most of the code is pretty translatable. http://craftinginterpreters.com/ http://craftinginterpreters.com/
- tylerscott 4y agoSeconding this recommendation. Bob (author) did such an amazing job of that book. I proudly display it in my office. The illustrations alone are worth the cost.
- deleted 4y ago[deleted]
- jrochkind1 4y agoRuby is well-known to be especially challenging to parse, btw. See for instance https://news.ycombinator.com/item?id=5182864 https://news.ycombinator.com/item?id=5182864
- nanolith 4y agoThe first parser that one writes for a real language is a big accomplishment. I remember the one I wrote for C89 back in high school, which was more annoying than many because it requires writing a preprocessor as well. All of the theory and toy language parsers just don't compare to being able to parse a real language. It's a baptism of fire, and it feels great afterward. 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.
- difflens 4y agoI'm most familiar with specifying grammar for the ANTLR tool. Just out of curiosity, is the antlr grammar a parsing expression grammar? Does anyone know? 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!
- intrepidhero 4y agoAt least according to wikipedia, ANTLR accepts a CFG (context free grammar), while PEG (parsing expression grammar) is not context free, specifically, the choice operator in a PEG selects the first match. I've been reading about parsers recently (https://www.craftinginterpreters.com/contents.html https://www.craftinginterpreters.com/contents.html and https://peps.python.org/pep-0617/ 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?
- difflens 4y agoFWIW, here's a repo of ANTLR grammars: https://github.com/antlr/grammars-v4 https://github.com/antlr/grammars-v4 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 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.
- thinkpad13 4y agomay I know what type is that thinkpad timm?