3 ms·

Designing a programming language is something I've found very interesting for the past few years now, but this is the one area of programming that really still

Designing a programming language is something I've found very interesting for the past few years now, but this is the one area of programming that really still eludes me and seems unapproachable. I've been through Understanding Computation, but at a certain point I just no longer understood what the hell was going on I was just typing in the examples. I have the Principles of Compiler Design book and I've made a run at that a couple of times, but it seems to theoretical for me to do anything useful with it. I've been thinking about taking a go at creating something with ANTLR alone with the books The Definitive ANTLR 4 Reference and Language Implementation Patterns, but I'm not sure if I'll have much more luck there. If anyone knows of a better path to get from here (can't design my own language) to there (clarity and understanding) I would love to hear your ideas. I'm not trying to create the next Rust, JavaScript, etc... I just believe that being able to implement my own language would give me a deeper understanding. In fact I'm very much interested in the idea of reimplementing an interpreter or compiler for languages I already work with as a way of learning this rather than trying to create something new.

sklogic 11y ago
A word of advise - forget about parsing for now. It's unimportant anyway and obscures the whole thing beyond recognition. Start by designing embedded DSLs on top of sufficiently expressive languages (i.e., any language with compile-time macros), it will give you enough of understanding of how compilers work. From there you can move to standalone compilers and, finally, if you ever need to (most often it's not necessary), to the syntax front-ends.
kctess5 11y ago
I just made a comment here, I might suggest that you do something like what I did. A solid understanding of parsers, lexers, and syntax trees would be an excellent place to start if you're interested in writing your own language. Start with the basics, get a firm grasp of that, then move on. The 'language design' part of things seems to be basically just figuring out how to combine basic ideas (parsing, lexing, ref counting, etc...) in new, fancy ways (or not so fancy, depending on your goals.) If you're interested in compilers/languages then you're probably going to get mighty familiar with manipulating graphs, so I'd try to read up on some graph theory. Language design/implementation gives us the opportunity to mathematically prove correctness of various features, which can be fun, if you're into that kind of thing. I think another great way to learn about language design is to actually just look at other languages and play with them. Once you know know the basic concepts it's usually easy enough to guesstimate how various language features work behind the scenes just by using them. A lot of very smart people put a lot of time into making languages like Rust/Go/etc, so learn from them, and learn their weaknesses. p.s. I'm not sure how much you've already researched, so I apologize if this is above/below where you're at.
dan00 11y ago
It might help to start with something more low level, like writing a compiler and emulator for an assembly language. A quite good candidate for this are artificial, simplified cpus, like the dcpu16.
qznc 11y ago
http://prog21.dadgum.com/30.html http://prog21.dadgum.com/30.html https://programmers.stackexchange.com/questions/165543/how-to-write-a-very-basic-compiler https://programmers.stackexchange.com/questions/165543/how-t... Or do you want to write an interpreter instead? Well, the frontend is the same anyways. Instead of transforming the AST, you evaluate it instead.
- bigtunacan 11y ago
  More likely an interpreter than a compiler in the beginning. Ideally I would like to reimplement something like Ruby, R, or JavaScript since these are the languages I work with on a more day to day basis.
  - vidarh 11y ago
    I would recommend against Ruby and Javascript (R I don't know enough about) for a first attempt. I'm working on a Ruby compiler (http://hokstad.com/compiler http://hokstad.com/compiler). An interpreter is far easier, but still a huge amount of work. I'm sure it'd be fun, but I'd suggest trying a smaller/simpler project first and then revisit Ruby or JS. Ruby is an absolute nightmare to parse. Both Ruby and Javascript have complex execution models that seem deceptively simple at first glance. They're quagmire's. If you do want to do something Ruby-like, define a cut-down version. E.g. write down a grammar that covers the most important subset of Ruby that you use, and similarly define a small set of the core functionality. Parsing 80% of Ruby is easy. Chances are you've never used or seen most of the remaining 20% outside of rants about the complexity of the Ruby grammar. E.g. the plethora of ridiculous supported mechanisms for quoting text that allows you to do criminally unreadable stuff like "% x " (which, excluding the double-quotes parses as the string "x", as "%" introduces a quoted sequence started and terminated by the character after "%", except if the character is one of a set of exceptions of various kinds; this of course only when it occurs in a context when it can't be parsed as the infix modulo operator....) You can write a full compiler for a simpler language in the space it takes to just parse Ruby. You could probably define a suitably small cut-down version of Ruby that'd still be fun/usable relatively easily, especially if you're not concerned about actually being compatible.
lmm 11y ago
> If anyone knows of a better path to get from here (can't design my own language) to there (clarity and understanding) I would love to hear your ideas. http://www.hokstad.com/compiler http://www.hokstad.com/compiler was what made it make sense to me. I found the dragon book approach (where you start with this 4-stage design and you're supposed to implement a parser and lexer and all this because I said so) hopelessly confusing and unmotivated. Hokstad takes you through writing a compiler in a way that makes sense, the same way you'd write any other program.
aodh 11y ago
I strongly recommend following the Kaleidoscope LLVM tutorial: http://llvm.org/docs/tutorial/ http://llvm.org/docs/tutorial/ It should take maybe a day to work through. Even if you don't plan on ultimately using LLVM as a back-end compiler, this touches on a number of other useful concepts that will make your journey much easier. I wanted a more flexible parser for the language I'm working on, so I'm using a variant of an Earley parser that I wrote five years ago. ANTLR uses LL parsing.
tel 11y ago
So as you're probably aware, languages arise from the composition of a few simpler steps: 1. Strings to ASTs (parsing and, for efficiency and ergonomics, lexing) 2. AST to "outputs" (interpretation) 3. AST to "better" AST (optimization) 4. AST to "analysis outputs" (verification, maybe type checking) 5. AST to some other language, maybe assembly (compilation/transpilation, sometimes called codegen, depending on how you look at it) You should pick the ones of these you are most interested in! Most likely, to be honest, this will not be parsing or lexing, but if they are you're in luck because there's a lot of research here. Instead, just get enough parsing so that you can stop worrying about it. Parse a lisp-like language (very easy) or use an embedded DSL (harder, more flexible). From here, focus on step (2) as it's a significant design challenge and will get your feet very wet in what PLs are. You may never have to focus on the others depending on your proclivities and the styles of languages you want to build. Steps (3, 4, 5) are all deep rabbit holes themselves. Steps (3) and (5) mostly are required if you're interested in knowing how to make languages fast—although (5) is also necessary if you want to target a particular platform—e.g. write something to run on the Erlang VM. (4) is REALLY interesting, in my opinion, but optional if you want it to be.
falcolas 11y ago
I bring this up every time, because it's a great approach to writing a compiler, and for showing off Lisp. Even better, if you get really stuck, there are already examples out there to learn from, in multiple languages. Make A Lisp (MAL) https://github.com/kanaka/mal https://github.com/kanaka/mal
- xigency 11y ago
  Lisp is great because it's easy to parse. There's really no need to have either section on lexer or parser when working with s-expr. This would be a great example of where a recursive-descent parser excels, and not only is it easy to build, it's easy to understand. I think writing an interpreter or compiler for Scheme or Lisp would be a much better place to start for learning how to implement programming languages, it's just not what I chose to do here.
rspivak 11y ago
I started a series of articles called "Let’s Build A Simple Interpreter" which might be what you're looking for: - http://ruslanspivak.com/lsbasi-part1/ http://ruslanspivak.com/lsbasi-part1/ - http://ruslanspivak.com/lsbasi-part2/ http://ruslanspivak.com/lsbasi-part2/
- xigency 11y ago
  +1

sklogic 11y ago

A word of advise - forget about parsing for now. It's unimportant anyway and obscures the whole thing beyond recognition. Start by designing embedded DSLs on top of sufficiently expressive languages (i.e., any language with compile-time macros), it will give you enough of understanding of how compilers work. From there you can move to standalone compilers and, finally, if you ever need to (most often it's not necessary), to the syntax front-ends.

kctess5 11y ago

I just made a comment here, I might suggest that you do something like what I did. A solid understanding of parsers, lexers, and syntax trees would be an excellent place to start if you're interested in writing your own language. Start with the basics, get a firm grasp of that, then move on. The 'language design' part of things seems to be basically just figuring out how to combine basic ideas (parsing, lexing, ref counting, etc...) in new, fancy ways (or not so fancy, depending on your goals.) If you're interested in compilers/languages then you're probably going to get mighty familiar with manipulating graphs, so I'd try to read up on some graph theory. Language design/implementation gives us the opportunity to mathematically prove correctness of various features, which can be fun, if you're into that kind of thing. I think another great way to learn about language design is to actually just look at other languages and play with them. Once you know know the basic concepts it's usually easy enough to guesstimate how various language features work behind the scenes just by using them. A lot of very smart people put a lot of time into making languages like Rust/Go/etc, so learn from them, and learn their weaknesses. p.s. I'm not sure how much you've already researched, so I apologize if this is above/below where you're at.

dan00 11y ago

It might help to start with something more low level, like writing a compiler and emulator for an assembly language. A quite good candidate for this are artificial, simplified cpus, like the dcpu16.

qznc 11y ago

http://prog21.dadgum.com/30.html http://prog21.dadgum.com/30.html https://programmers.stackexchange.com/questions/165543/how-to-write-a-very-basic-compiler https://programmers.stackexchange.com/questions/165543/how-t... Or do you want to write an interpreter instead? Well, the frontend is the same anyways. Instead of transforming the AST, you evaluate it instead.

bigtunacan 11y ago
More likely an interpreter than a compiler in the beginning. Ideally I would like to reimplement something like Ruby, R, or JavaScript since these are the languages I work with on a more day to day basis.
- vidarh 11y ago
  I would recommend against Ruby and Javascript (R I don't know enough about) for a first attempt. I'm working on a Ruby compiler (http://hokstad.com/compiler http://hokstad.com/compiler). An interpreter is far easier, but still a huge amount of work. I'm sure it'd be fun, but I'd suggest trying a smaller/simpler project first and then revisit Ruby or JS. Ruby is an absolute nightmare to parse. Both Ruby and Javascript have complex execution models that seem deceptively simple at first glance. They're quagmire's. If you do want to do something Ruby-like, define a cut-down version. E.g. write down a grammar that covers the most important subset of Ruby that you use, and similarly define a small set of the core functionality. Parsing 80% of Ruby is easy. Chances are you've never used or seen most of the remaining 20% outside of rants about the complexity of the Ruby grammar. E.g. the plethora of ridiculous supported mechanisms for quoting text that allows you to do criminally unreadable stuff like "% x " (which, excluding the double-quotes parses as the string "x", as "%" introduces a quoted sequence started and terminated by the character after "%", except if the character is one of a set of exceptions of various kinds; this of course only when it occurs in a context when it can't be parsed as the infix modulo operator....) You can write a full compiler for a simpler language in the space it takes to just parse Ruby. You could probably define a suitably small cut-down version of Ruby that'd still be fun/usable relatively easily, especially if you're not concerned about actually being compatible.

lmm 11y ago

> If anyone knows of a better path to get from here (can't design my own language) to there (clarity and understanding) I would love to hear your ideas. http://www.hokstad.com/compiler http://www.hokstad.com/compiler was what made it make sense to me. I found the dragon book approach (where you start with this 4-stage design and you're supposed to implement a parser and lexer and all this because I said so) hopelessly confusing and unmotivated. Hokstad takes you through writing a compiler in a way that makes sense, the same way you'd write any other program.

aodh 11y ago

I strongly recommend following the Kaleidoscope LLVM tutorial: http://llvm.org/docs/tutorial/ http://llvm.org/docs/tutorial/ It should take maybe a day to work through. Even if you don't plan on ultimately using LLVM as a back-end compiler, this touches on a number of other useful concepts that will make your journey much easier. I wanted a more flexible parser for the language I'm working on, so I'm using a variant of an Earley parser that I wrote five years ago. ANTLR uses LL parsing.

tel 11y ago

So as you're probably aware, languages arise from the composition of a few simpler steps: 1. Strings to ASTs (parsing and, for efficiency and ergonomics, lexing) 2. AST to "outputs" (interpretation) 3. AST to "better" AST (optimization) 4. AST to "analysis outputs" (verification, maybe type checking) 5. AST to some other language, maybe assembly (compilation/transpilation, sometimes called codegen, depending on how you look at it) You should pick the ones of these you are most interested in! Most likely, to be honest, this will not be parsing or lexing, but if they are you're in luck because there's a lot of research here. Instead, just get enough parsing so that you can stop worrying about it. Parse a lisp-like language (very easy) or use an embedded DSL (harder, more flexible). From here, focus on step (2) as it's a significant design challenge and will get your feet very wet in what PLs are. You may never have to focus on the others depending on your proclivities and the styles of languages you want to build. Steps (3, 4, 5) are all deep rabbit holes themselves. Steps (3) and (5) mostly are required if you're interested in knowing how to make languages fast—although (5) is also necessary if you want to target a particular platform—e.g. write something to run on the Erlang VM. (4) is REALLY interesting, in my opinion, but optional if you want it to be.

falcolas 11y ago

I bring this up every time, because it's a great approach to writing a compiler, and for showing off Lisp. Even better, if you get really stuck, there are already examples out there to learn from, in multiple languages. Make A Lisp (MAL) https://github.com/kanaka/mal https://github.com/kanaka/mal

xigency 11y ago
Lisp is great because it's easy to parse. There's really no need to have either section on lexer or parser when working with s-expr. This would be a great example of where a recursive-descent parser excels, and not only is it easy to build, it's easy to understand. I think writing an interpreter or compiler for Scheme or Lisp would be a much better place to start for learning how to implement programming languages, it's just not what I chose to do here.

rspivak 11y ago

I started a series of articles called "Let’s Build A Simple Interpreter" which might be what you're looking for: - http://ruslanspivak.com/lsbasi-part1/ http://ruslanspivak.com/lsbasi-part1/ - http://ruslanspivak.com/lsbasi-part2/ http://ruslanspivak.com/lsbasi-part2/

xigency 11y ago
+1