4 ms·

"I wanted to explore what it feels like to write a parser, a lexer, and an interpreter without using a framework or some other ready-made solution" This is an

"I wanted to explore what it feels like to write a parser, a lexer, and an interpreter without using a framework or some other ready-made solution" This is an excellent exercise for any programmer who wants to really understand what's going on behind the scenes. I've always believed it's useful to understand at least one layer below what you normally work with. Some people will criticise you for "why create another programming language when we already have X?" but ignore them. As long as you explain that it's an experiment (as you have) you should be fine. And it's possible that by starting something completely from the ground up you'll discover a different take on things that might be better than what exists already. Just be prepared to do a complete rewrite or three once you've got your initial prototype working ;) "and I didn't really consult any literature either" I really recommend that you do. The single best resource on this topic is the "Dragon Book" (officially "Compilers: Principles, Techniques, and Tools" by Aho, Lam, Sethi, and Ullman) - the latest edition is from 2006, though the older one should be fine for what you want too. I wrote my first compiler before learning the "proper" way of doing things and it was a complete mess. It was only after studying compiler construction at university that I learnt about things like formal grammars, syntax trees, etc. The dragon book will take you all the way through to expert level, and is written in such a way that you can implement different parts of your compiler as you go through the book. One caveat though is it's huge (close to 1,000 pages). I spent a couple of months full time working through it (coding as I went along) during a long break from work a couple of years ago, and only got about half-way through in that time. But you only really need the first few chapters to get the basics; the later parts go on to a lot of advanced code optimisation techniques that you only really need if you're trying to write a high-performance production compiler or get into compiler research. SICP, as someone else mentioned, is also very good, though it's really more about the overarching theoretical concepts and doesn't go into the same amount of depth as the dragon book. I think reading both is a good idea. Just be warned, this stuff is highly addictive, and you can spend years studying it and still end up with lots of gaps in your knowledge ;)

Udo 14y ago
Thanks for the encouragement! Doing this was pretty exciting. > and I didn't really consult any literature either In hindsight I shouldn't have written that, because it practically forces people to ignore the project itself and begin suggesting emergency reading material to the illiterate goof who wrote this thing (a.k.a. me). I want to clarify: it's not that I have no clue how anything works, I just didn't study up especially for this project. There is a continuum ranging from absolutely no prior knowledge, to some intellectual contamination, up to just aping established methods because you couldn't imagine doing things any other way. I was probably somewhere around the middle when I started this and it's not a bad place to be. In fact, I'd go so far as to recommend this as a good perspective for anyone who wants to try something similar. Learning "how it's done" beforehand not only defeats the point of the exercise, it also results in a lot of projects that are strikingly monocultural. Now that I have a better understanding of the problem space, I imagine I will read more on these topics. I'm excited to find out how others have approached some of the problems I struggled with. So thanks for suggesting the Dragon Book, which I haven't read yet (as opposed to SICP on which I already commented)!
rohitarondekar 14y ago
Great advice. I'd also recommend the Compilers course on Coursera. Although it is already underway, you can take the self paced version. https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers
stiff 14y ago
The single best resource on this topic is the "Dragon Book" Your advice is great in general, but I wish people would back up statements like this with some context, for example, what specifically have you compared it with? Inspired by Steve Yegge blogposts I once decided to write a toy compiler for educational purposes and I started with reading the Dragon Book, in fact I eventually read it almost cover to cover and implemented many algorithms from it, it is definitely full of valuable information. But it also is a very roundabout way of learning how to write an actual compiler, it is more a theoretical reference work than anything else. There are several hundreds of pages devoted to parsing, but some of the more modern techniques are not covered, runtime is treated much more briefly and many practical issues are not discussed at all. There are some nice modern textbooks that are more to the point: http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471976970/ http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471... http://www.amazon.com/Engineering-Compiler-Second-Keith-Cooper/dp/012088478X/ http://www.amazon.com/Engineering-Compiler-Second-Keith-Coop... ANTLR is a great tool and many practical issues I solved with the help of this book about it: http://www.amazon.com/gp/product/1934356999/ http://www.amazon.com/gp/product/1934356999/ Finally, source code of original AWK is a great example codebase to learn about real-world parsing, building and traversing parse trees etc.: https://github.com/danfuzz/one-true-awk https://github.com/danfuzz/one-true-awk It is an interpreter and not a compiler but once you know how to do the things just mentioned converting it to a naive compiler isn't that hard if you are not interested in fancy optimization like the OP said.
- peterkelly 14y ago
  s/The single best resource/Out of the resources I've read, the one I've personally found most useful/ ;) I should also probably add that I only ever read the dragon book years after I first started learning about compilers through more gentle means such as the 3rd-year compiler construction course I studied, and a bunch of other reading and experimentation. It's probably better to start off with something simpler. I haven't read either of the two books you referenced; they may indeed be more appropriate for a beginner. While I haven't used ANTLR, I've used bison & flex, as well as Stratego (which operates on a much higher level and is actually very nice). I guess it depends on what aspect of compilers you're most interested in and how much depth you want to go into. The dragon book will teach you all about how to write your own lexer + parser generator (which I found quite fascinating), but you don't need to know about NFAs/DFA construction etc. if you just want to create your own language implementation, given the existence of many good lexer/parser generators to which you can just pass in a formal grammar. Another book I also found very useful was "The Implementation of Functional Programming Languages" by Simon Peyton Jones (http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm http://research.microsoft.com/en-us/um/people/simonpj/papers...), though it's mostly of use only if you're specifically interested in functional programming (which is what I've mainly focused on my research; this book is much more specialised than some of the others).

Udo 14y ago

Thanks for the encouragement! Doing this was pretty exciting. > and I didn't really consult any literature either In hindsight I shouldn't have written that, because it practically forces people to ignore the project itself and begin suggesting emergency reading material to the illiterate goof who wrote this thing (a.k.a. me). I want to clarify: it's not that I have no clue how anything works, I just didn't study up especially for this project. There is a continuum ranging from absolutely no prior knowledge, to some intellectual contamination, up to just aping established methods because you couldn't imagine doing things any other way. I was probably somewhere around the middle when I started this and it's not a bad place to be. In fact, I'd go so far as to recommend this as a good perspective for anyone who wants to try something similar. Learning "how it's done" beforehand not only defeats the point of the exercise, it also results in a lot of projects that are strikingly monocultural. Now that I have a better understanding of the problem space, I imagine I will read more on these topics. I'm excited to find out how others have approached some of the problems I struggled with. So thanks for suggesting the Dragon Book, which I haven't read yet (as opposed to SICP on which I already commented)!

rohitarondekar 14y ago

Great advice. I'd also recommend the Compilers course on Coursera. Although it is already underway, you can take the self paced version. https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers

stiff 14y ago

The single best resource on this topic is the "Dragon Book" Your advice is great in general, but I wish people would back up statements like this with some context, for example, what specifically have you compared it with? Inspired by Steve Yegge blogposts I once decided to write a toy compiler for educational purposes and I started with reading the Dragon Book, in fact I eventually read it almost cover to cover and implemented many algorithms from it, it is definitely full of valuable information. But it also is a very roundabout way of learning how to write an actual compiler, it is more a theoretical reference work than anything else. There are several hundreds of pages devoted to parsing, but some of the more modern techniques are not covered, runtime is treated much more briefly and many practical issues are not discussed at all. There are some nice modern textbooks that are more to the point: http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471976970/ http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471... http://www.amazon.com/Engineering-Compiler-Second-Keith-Cooper/dp/012088478X/ http://www.amazon.com/Engineering-Compiler-Second-Keith-Coop... ANTLR is a great tool and many practical issues I solved with the help of this book about it: http://www.amazon.com/gp/product/1934356999/ http://www.amazon.com/gp/product/1934356999/ Finally, source code of original AWK is a great example codebase to learn about real-world parsing, building and traversing parse trees etc.: https://github.com/danfuzz/one-true-awk https://github.com/danfuzz/one-true-awk It is an interpreter and not a compiler but once you know how to do the things just mentioned converting it to a naive compiler isn't that hard if you are not interested in fancy optimization like the OP said.

peterkelly 14y ago
s/The single best resource/Out of the resources I've read, the one I've personally found most useful/ ;) I should also probably add that I only ever read the dragon book years after I first started learning about compilers through more gentle means such as the 3rd-year compiler construction course I studied, and a bunch of other reading and experimentation. It's probably better to start off with something simpler. I haven't read either of the two books you referenced; they may indeed be more appropriate for a beginner. While I haven't used ANTLR, I've used bison & flex, as well as Stratego (which operates on a much higher level and is actually very nice). I guess it depends on what aspect of compilers you're most interested in and how much depth you want to go into. The dragon book will teach you all about how to write your own lexer + parser generator (which I found quite fascinating), but you don't need to know about NFAs/DFA construction etc. if you just want to create your own language implementation, given the existence of many good lexer/parser generators to which you can just pass in a formal grammar. Another book I also found very useful was "The Implementation of Functional Programming Languages" by Simon Peyton Jones (http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm http://research.microsoft.com/en-us/um/people/simonpj/papers...), though it's mostly of use only if you're specifically interested in functional programming (which is what I've mainly focused on my research; this book is much more specialised than some of the others).