6 ms·

A Simple Compiler in JavaScript

126 points by mgechev 9y ago

endisukaj 9y ago
... but why?
- smallnamespace 9y ago
  Why not?
trygvis 9y ago
Aaw, this would have been great if it didn't use `eval`, but just executed `+`, `-` etc directly.
- packetslave 9y ago
  It doesn't use the built-in eval(). There's a local function in the code named "eval" that executes the operation -- not the best choice of names, really.
  - trygvis 9y ago
    Oops, guess I read it a bit too fast.
adtac 9y ago
*interpreter/transpiler, not a compiler
- tomsmeding 9y ago
  The interpreter is certainly an interpreter, but a transpiler is arguably also a compiler, be it maybe with an easier target than most conventional compilers. Assembly language and machine code are also languages you can program in; in that sense you'd also have to call gcc a transpiler ;)
  - adtac 9y ago
    Indeed, every compiler is a transpiler: it transpiles into asm. But not every transpiler is a compiler in the truest sense of the term. IMO only transpiling to machine language qualifies as compiling. But we're just arguing about semantics here :) My comment was more directed towards the interpreter part of things.
    - sebazzz 9y ago
      > IMO only transpiling to machine language qualifies as compiling. It is not black and white, compiling to IL or bytecode qualifies as compiling. Perhaps compiling means compilation to a binary executable format?
      - pjmlp 9y ago
        Bytecode is machine language, specially on mainframes and computer architectures up to early 80's. It is all a matter how the CPU executes it, direct mapping of machine code into gates, or micro-coded translation layer.
    - wtetzner 9y ago
      > Indeed, every compiler is a transpiler: it transpiles into asm. But not every transpiler is a compiler in the truest sense of the term. I think you have it backwards. Every transpiler is a compiler, but the reverse is not necessarily true.
    - Vendan 9y ago
      GCC compiles C to assembly, and then uses GAS to turn that into actual machine code... So is GCC a transpiler, and GAS the compiler?
- always_good 9y ago
  Can you update the first sentence of this wikipedia article to point out that a transpiler is not a compiler? https://en.wikipedia.org/wiki/Source-to-source_compiler https://en.wikipedia.org/wiki/Source-to-source_compiler It would help squelch the confusion for future forum bike shedding. Someone seems to try and point this out every time it comes up like they're winning some sort of pedantry points, but I don't see how they could be. Please illuminate me so I understand the next time someone says this and possibly join la resistencia.
tomsmeding 9y ago
Of course, the implemented language is simple enough, to accomodate this simple implementation. Still, looks nice, the code is very clear, and the comments are pretty good. The syntax is of course very limited with a one-line lexer, so more sophistocation here would somewhat expand the lexer, even though if it remains centered around regexes (which it probably will), it can remain pretty small. When expanding the language, the tree building code can probably stay pretty small as well, if the syntax of your new constructs are chosen wisely. (I foresee control structures as prefix operators, which will be interesting to say the least.) The evaluator and transpiler would complicate themselves significantly when adding control structures to the language: I think the most code-expanding task would be handling of not-directly evaluated code blocks. In the case of conditionals, you can probably get away with the ?: operator, also seeing as JS has the comma operator. But in the case of loops, you need a conpletely different structure in the output; it would depend on the implementation whether that stays small or not. Of course, adding control structures is only useful if there's some way of defining names, be it variables (producing an imperative language) or recursion-capable functions (producing a functional language). It might be an interesting exercise to see how far you can push this language while still keeping the compiler under, say, 100 lines. :P Protip if you do that: ditch the evaluator. A compiler doesn't need an interpreter to compile. ;)
willtim 9y ago
I think compiler implementation is a particular sweetspot for functional languages. Here's a similar tiny example in Haskell: http://www.timphilipwilliams.com/posts/2014-05-22-the-essence-of-compilation.html http://www.timphilipwilliams.com/posts/2014-05-22-the-essenc...
- pjmlp 9y ago
  When I did my degree, the older students were forbidden to use any language from the Lisp, ML or Prolog families for the compiler design assignment as that would be too easy. As Java was just released by the time my class got to do the same assignment, we ended up using Java with JavaCC and JJTree. While not as easy as Lisp, ML or Prolog, it was still much easier than the Jurassic yacc/lex that still prevails in some circles.
  - smadge 9y ago
    Something about that rule seems extremely backwards to me. Might as well implement a Prolog or Scheme in a lower level language then do your compiler assignments in that. Reminds me of this quote "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." Source: https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule
  - 1298312321 9y ago
    What is this nonsense? ML uses yacc and lex. Again, could you point us to a repository that contains your work?
  - willtim 9y ago
    I think I'd have been confused as to why using a parser generator was also not similarly regarded as being too easy :) Interestingly, most mature industrial languages (e.g. Java, GCC, clang) use hand-coded recursive descent parsers. And of course such parsers can be implemented very easily from first principles using parser combinators in FP. I've used both JavaCC and Antlr in the past for small DSLs, both are very good tools, when working with Java.
tempodox 9y ago
Nicely done. It demonstrates the principles comprehensibly with no extraneous noise.
mrspeaker 9y ago
I thought it would be good to include the output of the example executions at the bottom of the page... then I remembered i could just paste that in a console - very cool! A while back I started making a game in javascript called "BASIC Instincts" that was going to be about finding clues in the world and typing in BASIC programs from magazines to solve puzzles. The parser/interpreter was the most fun part (https://www.youtube.com/watch?v=GwBiJR_rj_w https://www.youtube.com/watch?v=GwBiJR_rj_w)
prezjordan 9y ago
Wow, excellent work! These are always super interesting to read. A similar project: https://github.com/thejameskyle/the-super-tiny-compiler https://github.com/thejameskyle/the-super-tiny-compiler
tlrobinson 9y ago
I did the same thing for a conference talk once, but also “golfed” each of the 4 components down to Tweet size (back in my day, Tweets were 140 characters): https://gist.github.com/tlrobinson/1257254 https://gist.github.com/tlrobinson/1257254 Every programmer should implement a simple Lisp from scratch at least once, just to understand compilers and interpreters aren’t magic.
burlesona 9y ago
This is really cool, thanks for posting this. I've always been vaguely curious how compilers work, but have never set aside time to research it. This was a great introduction, I have a better beginner's notion of how they work now :)
jayflux 9y ago
if anyone found this interesting, i recommend reading http://lisperator.net/pltut/ http://lisperator.net/pltut/ It called "How to implement a programming language" its in JS and its made by the guy who's behind uglifyJS

126 points by mgechev 9y ago

endisukaj 9y ago

... but why?

smallnamespace 9y ago
Why not?

trygvis 9y ago

Aaw, this would have been great if it didn't use `eval`, but just executed `+`, `-` etc directly.

packetslave 9y ago
It doesn't use the built-in eval(). There's a local function in the code named "eval" that executes the operation -- not the best choice of names, really.
- trygvis 9y ago
  Oops, guess I read it a bit too fast.

adtac 9y ago

*interpreter/transpiler, not a compiler

tomsmeding 9y ago
The interpreter is certainly an interpreter, but a transpiler is arguably also a compiler, be it maybe with an easier target than most conventional compilers. Assembly language and machine code are also languages you can program in; in that sense you'd also have to call gcc a transpiler ;)
- adtac 9y ago
  Indeed, every compiler is a transpiler: it transpiles into asm. But not every transpiler is a compiler in the truest sense of the term. IMO only transpiling to machine language qualifies as compiling. But we're just arguing about semantics here :) My comment was more directed towards the interpreter part of things.
  - sebazzz 9y ago
    > IMO only transpiling to machine language qualifies as compiling. It is not black and white, compiling to IL or bytecode qualifies as compiling. Perhaps compiling means compilation to a binary executable format?
    - pjmlp 9y ago
      Bytecode is machine language, specially on mainframes and computer architectures up to early 80's. It is all a matter how the CPU executes it, direct mapping of machine code into gates, or micro-coded translation layer.
  - wtetzner 9y ago
    > Indeed, every compiler is a transpiler: it transpiles into asm. But not every transpiler is a compiler in the truest sense of the term. I think you have it backwards. Every transpiler is a compiler, but the reverse is not necessarily true.
  - Vendan 9y ago
    GCC compiles C to assembly, and then uses GAS to turn that into actual machine code... So is GCC a transpiler, and GAS the compiler?
always_good 9y ago
Can you update the first sentence of this wikipedia article to point out that a transpiler is not a compiler? https://en.wikipedia.org/wiki/Source-to-source_compiler https://en.wikipedia.org/wiki/Source-to-source_compiler It would help squelch the confusion for future forum bike shedding. Someone seems to try and point this out every time it comes up like they're winning some sort of pedantry points, but I don't see how they could be. Please illuminate me so I understand the next time someone says this and possibly join la resistencia.

tomsmeding 9y ago

Of course, the implemented language is simple enough, to accomodate this simple implementation. Still, looks nice, the code is very clear, and the comments are pretty good. The syntax is of course very limited with a one-line lexer, so more sophistocation here would somewhat expand the lexer, even though if it remains centered around regexes (which it probably will), it can remain pretty small. When expanding the language, the tree building code can probably stay pretty small as well, if the syntax of your new constructs are chosen wisely. (I foresee control structures as prefix operators, which will be interesting to say the least.) The evaluator and transpiler would complicate themselves significantly when adding control structures to the language: I think the most code-expanding task would be handling of not-directly evaluated code blocks. In the case of conditionals, you can probably get away with the ?: operator, also seeing as JS has the comma operator. But in the case of loops, you need a conpletely different structure in the output; it would depend on the implementation whether that stays small or not. Of course, adding control structures is only useful if there's some way of defining names, be it variables (producing an imperative language) or recursion-capable functions (producing a functional language). It might be an interesting exercise to see how far you can push this language while still keeping the compiler under, say, 100 lines. :P Protip if you do that: ditch the evaluator. A compiler doesn't need an interpreter to compile. ;)

willtim 9y ago

I think compiler implementation is a particular sweetspot for functional languages. Here's a similar tiny example in Haskell: http://www.timphilipwilliams.com/posts/2014-05-22-the-essence-of-compilation.html http://www.timphilipwilliams.com/posts/2014-05-22-the-essenc...

pjmlp 9y ago
When I did my degree, the older students were forbidden to use any language from the Lisp, ML or Prolog families for the compiler design assignment as that would be too easy. As Java was just released by the time my class got to do the same assignment, we ended up using Java with JavaCC and JJTree. While not as easy as Lisp, ML or Prolog, it was still much easier than the Jurassic yacc/lex that still prevails in some circles.
- smadge 9y ago
  Something about that rule seems extremely backwards to me. Might as well implement a Prolog or Scheme in a lower level language then do your compiler assignments in that. Reminds me of this quote "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." Source: https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule
- 1298312321 9y ago
  What is this nonsense? ML uses yacc and lex. Again, could you point us to a repository that contains your work?
- willtim 9y ago
  I think I'd have been confused as to why using a parser generator was also not similarly regarded as being too easy :) Interestingly, most mature industrial languages (e.g. Java, GCC, clang) use hand-coded recursive descent parsers. And of course such parsers can be implemented very easily from first principles using parser combinators in FP. I've used both JavaCC and Antlr in the past for small DSLs, both are very good tools, when working with Java.

tempodox 9y ago

Nicely done. It demonstrates the principles comprehensibly with no extraneous noise.

mrspeaker 9y ago

I thought it would be good to include the output of the example executions at the bottom of the page... then I remembered i could just paste that in a console - very cool! A while back I started making a game in javascript called "BASIC Instincts" that was going to be about finding clues in the world and typing in BASIC programs from magazines to solve puzzles. The parser/interpreter was the most fun part (https://www.youtube.com/watch?v=GwBiJR_rj_w https://www.youtube.com/watch?v=GwBiJR_rj_w)

prezjordan 9y ago

Wow, excellent work! These are always super interesting to read. A similar project: https://github.com/thejameskyle/the-super-tiny-compiler https://github.com/thejameskyle/the-super-tiny-compiler

tlrobinson 9y ago

I did the same thing for a conference talk once, but also “golfed” each of the 4 components down to Tweet size (back in my day, Tweets were 140 characters): https://gist.github.com/tlrobinson/1257254 https://gist.github.com/tlrobinson/1257254 Every programmer should implement a simple Lisp from scratch at least once, just to understand compilers and interpreters aren’t magic.

burlesona 9y ago

This is really cool, thanks for posting this. I've always been vaguely curious how compilers work, but have never set aside time to research it. This was a great introduction, I have a better beginner's notion of how they work now :)

jayflux 9y ago

if anyone found this interesting, i recommend reading http://lisperator.net/pltut/ http://lisperator.net/pltut/ It called "How to implement a programming language" its in JS and its made by the guy who's behind uglifyJS