4 ms·

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production comp

by sieve 2y ago

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

sitkack 2y ago
5 days if you don't, but have the right tutor.
- sieve 2y ago
  If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour. The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.
  - RossBencina 2y ago
    I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters).
    - sieve 2y ago
      The Dragon Book is terrible as an introduction. There are better books I would probably recommend, but not to a beginner. The best "complete" intro out there today is Nystrom's Crafting Interpreters.[1] [1] https://www.craftinginterpreters.com/contents.html https://www.craftinginterpreters.com/contents.html
      - RossBencina 2y ago
        > There are better books I would probably recommend I'm curious what you'd recommend. For what it's worth my goal was to compile to machine code. Anything less would have seemed insufficient. Later I got Appel's "Modern Compiler Implementation in Java" and Allen and Kennedy "Optimizing Compilers for Modern Architectures". Cooper and Torczon "Engineering a Compiler" was recommended here recently. I haven't seen it.
        sieve 2y ago
        I got started from the books that were available here in the early 2000s. The one I like the most is "Programming Language Pragmatics" by Michael Scott, mainly for its simplicity. Then there is "Advanced Compiler Design and Implementation" by Steven Muchnick. I have Allen-Kennedy's book too, but I think it went over my head when I went through it. So I kept it aside. "Engineering a Compiler" is quite approachable. But, once you know the basics, you get the best bang-for-the-buck by looking at source code of various compilers and virtual machines.
        sitkack 2y ago
        There is a whole body of non-academic work aimed at practioners for implementing compilers. Nils Holm's work https://t3x.org/ https://t3x.org/ Teaching and Learning Compilers Incrementally - Jeremy Siek - RacketCon 2023 https://www.youtube.com/watch?v=43VA_QaTRT8 https://www.youtube.com/watch?v=43VA_QaTRT8 Nanopass https://nanopass.org/ https://nanopass.org/ original paper that was the basis for nanopass http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf https://www.reddit.com/r/ProgrammingLanguages/comments/gnzrap/the_nanopass_framework_as_a_nanopass_compiler_els/ https://www.reddit.com/r/ProgrammingLanguages/comments/gnzra... The Crafting Interpreters and the Thorsten Ball books https://craftinginterpreters.com/contents.html https://craftinginterpreters.com/contents.html https://interpreterbook.com/ https://interpreterbook.com/ https://compilerbook.com/ https://compilerbook.com/ https://www.phind.com/search/cm7efcpv000002e6hqdbfojex https://www.phind.com/search/cm7efcpv000002e6hqdbfojex
        ratmice 2y ago
    - delta_p_delta_x 2y ago
      > It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters) This is exactly how my university's compiler course did it[1]. It was really nice to start with assembly and go upwards. We had all the lexing/parsing stuff being discussed around the middle of the semester rather than being saddled with theory-heavy regex, automata theory, etc right at the beginning. [1]: https://ilyasergey.net/CS4212/ https://ilyasergey.net/CS4212/
jcuenod 2y ago
Honestly, antlr made this pretty straightforward to me. I didn't want to work in java, but they have a ton of targets. You can definitely write it all yourself, and that's a great learning exercise. But I wanted to get a parser for a language idea I had in mind and it took a couple of days with antlr (https://github.com/chicory-lang/chicory https://github.com/chicory-lang/chicory)
- sieve 2y ago
  Problem with these tools is, you have to spend time wrangling them instead of learning to write a lexer/parser yourself. A recursive-descent parser is a beautiful thing and can be implemented very quickly.
whartung 2y ago
The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.
- andai 2y ago
  Is that really the hard part? I figured that part out before I knew much programming: made a simple Excel type formula parser. (A horrible, horrible solution based around replacing strings and manually counting parentheses... but it worked!) I never got much farther than that though, I've looked into making a compiler many times and got overwhelmed every time.
  - lelanthran 2y ago
    It's hard if: 1. You dont recognise the recursive nature of the problem, Or 2. You don't recognise the stack-based nature in the problem (shunting yard algo, etc). IOW, you did it the hard way :-).
  - PhilipRoman 2y ago
    Good to know I wasn't alone in writing terrible expression parsers. Since I knew absolutely nothing about parsing, my parser/interpreter consisted of splitting on whitespace, followed by linear scanning to find the most high precedence operation, repeated until a single token remains (basically how a human would do it).
- sieve 2y ago
  > The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression” This is why teaching material should be tailored towards teaching rather than implementing demented stuff from the real world just because it is "there." You can easily implement a parser that ignores precedence and tell the reader that we are using brackets to force precedence instead. In a real-word parser, you might use something like this[1] or some other home-grown algorithm if you didn't know about it. Doesn't matter as long as the parser works. [1] Top-Down operator precedence (Pratt) parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...
RossBencina 2y ago
> lexer + parser + treewalk interpreter If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter. I would expect: lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C where X includes - definition of an intermediate representation (IR) - lowering AST to IR - static analysis - improvers/optimisation passes (at least some simple stuff) - code gen including register allocation This can still be a simple "complicated" program, but there's more to a compiler than an AST interpreter. EDIT: I notice that the author of the original article has also started work on an optimizing compiler: https://ssloy.github.io/tinyoptimizer/ https://ssloy.github.io/tinyoptimizer/
- sieve 2y ago
  > If all you do is construct an AST and interpret it it's not really a compiler is it. What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-) > where X includes I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compile down to C/JS. Many compilers use LLVM as their backend. By your definition, none of them use (or are) compilers.
  - RossBencina 2y ago
    > Would you consider that to be a compiler? :-) :) No. Under my definition there needs to be some non-trivial transformation into or out of an intermediate and/or target representation (either syntax-directed directly out of the parser, or from a materialized AST). Personally I would argue that even if you trivially "compiled" to sequential bytecode, if the bytecode is then interpreted it is hard to argue that you have created a compiler (the pre-JIT cpython interpreter is still an interpreter, even though it includes a bytecode representation). But I can see that this point can be argued, and historically a school exercise of writing a Pascal-to-pcode converter would be called a compiler, so sure, you can take that perspective if you like. Just don't get confused about whether you are learning to build a compiler (definition 1) or a compiler (definition 2).

by sieve 2y ago

sitkack 2y ago

5 days if you don't, but have the right tutor.

sieve 2y ago
If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour. The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.
- RossBencina 2y ago
  I never took a compilers course. The first reading recommendation I got was The Dragon Book. Perhaps not the worst starting place at the time (mid 90s) but my memory of it was that the book was front-loaded with automata and parser theory. At the time I didn't really make it past the front end. It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters).
  - sieve 2y ago
    The Dragon Book is terrible as an introduction. There are better books I would probably recommend, but not to a beginner. The best "complete" intro out there today is Nystrom's Crafting Interpreters.[1] [1] https://www.craftinginterpreters.com/contents.html https://www.craftinginterpreters.com/contents.html
    - RossBencina 2y ago
      > There are better books I would probably recommend I'm curious what you'd recommend. For what it's worth my goal was to compile to machine code. Anything less would have seemed insufficient. Later I got Appel's "Modern Compiler Implementation in Java" and Allen and Kennedy "Optimizing Compilers for Modern Architectures". Cooper and Torczon "Engineering a Compiler" was recommended here recently. I haven't seen it.
      - sieve 2y ago
        I got started from the books that were available here in the early 2000s. The one I like the most is "Programming Language Pragmatics" by Michael Scott, mainly for its simplicity. Then there is "Advanced Compiler Design and Implementation" by Steven Muchnick. I have Allen-Kennedy's book too, but I think it went over my head when I went through it. So I kept it aside. "Engineering a Compiler" is quite approachable. But, once you know the basics, you get the best bang-for-the-buck by looking at source code of various compilers and virtual machines.
      - sitkack 2y ago
        There is a whole body of non-academic work aimed at practioners for implementing compilers. Nils Holm's work https://t3x.org/ https://t3x.org/ Teaching and Learning Compilers Incrementally - Jeremy Siek - RacketCon 2023 https://www.youtube.com/watch?v=43VA_QaTRT8 https://www.youtube.com/watch?v=43VA_QaTRT8 Nanopass https://nanopass.org/ https://nanopass.org/ original paper that was the basis for nanopass http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf https://www.reddit.com/r/ProgrammingLanguages/comments/gnzrap/the_nanopass_framework_as_a_nanopass_compiler_els/ https://www.reddit.com/r/ProgrammingLanguages/comments/gnzra... The Crafting Interpreters and the Thorsten Ball books https://craftinginterpreters.com/contents.html https://craftinginterpreters.com/contents.html https://interpreterbook.com/ https://interpreterbook.com/ https://compilerbook.com/ https://compilerbook.com/ https://www.phind.com/search/cm7efcpv000002e6hqdbfojex https://www.phind.com/search/cm7efcpv000002e6hqdbfojex
        ratmice 2y ago
  - delta_p_delta_x 2y ago
    > It would be interesting to see a compiler tutorial that started at codegen and worked backwards (or started at the ends: lexing and codegen, and worked towards the middle in alternating chapters) This is exactly how my university's compiler course did it[1]. It was really nice to start with assembly and go upwards. We had all the lexing/parsing stuff being discussed around the middle of the semester rather than being saddled with theory-heavy regex, automata theory, etc right at the beginning. [1]: https://ilyasergey.net/CS4212/ https://ilyasergey.net/CS4212/

jcuenod 2y ago

Honestly, antlr made this pretty straightforward to me. I didn't want to work in java, but they have a ton of targets. You can definitely write it all yourself, and that's a great learning exercise. But I wanted to get a parser for a language idea I had in mind and it took a couple of days with antlr (https://github.com/chicory-lang/chicory https://github.com/chicory-lang/chicory)

sieve 2y ago
Problem with these tools is, you have to spend time wrangling them instead of learning to write a lexer/parser yourself. A recursive-descent parser is a beautiful thing and can be implemented very quickly.

whartung 2y ago

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.

andai 2y ago
Is that really the hard part? I figured that part out before I knew much programming: made a simple Excel type formula parser. (A horrible, horrible solution based around replacing strings and manually counting parentheses... but it worked!) I never got much farther than that though, I've looked into making a compiler many times and got overwhelmed every time.
- lelanthran 2y ago
  It's hard if: 1. You dont recognise the recursive nature of the problem, Or 2. You don't recognise the stack-based nature in the problem (shunting yard algo, etc). IOW, you did it the hard way :-).
- PhilipRoman 2y ago
  Good to know I wasn't alone in writing terrible expression parsers. Since I knew absolutely nothing about parsing, my parser/interpreter consisted of splitting on whitespace, followed by linear scanning to find the most high precedence operation, repeated until a single token remains (basically how a human would do it).
sieve 2y ago
> The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression” This is why teaching material should be tailored towards teaching rather than implementing demented stuff from the real world just because it is "there." You can easily implement a parser that ignores precedence and tell the reader that we are using brackets to force precedence instead. In a real-word parser, you might use something like this[1] or some other home-grown algorithm if you didn't know about it. Doesn't matter as long as the parser works. [1] Top-Down operator precedence (Pratt) parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...

RossBencina 2y ago

> lexer + parser + treewalk interpreter If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter. I would expect: lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C where X includes - definition of an intermediate representation (IR) - lowering AST to IR - static analysis - improvers/optimisation passes (at least some simple stuff) - code gen including register allocation This can still be a simple "complicated" program, but there's more to a compiler than an AST interpreter. EDIT: I notice that the author of the original article has also started work on an optimizing compiler: https://ssloy.github.io/tinyoptimizer/ https://ssloy.github.io/tinyoptimizer/

sieve 2y ago
> If all you do is construct an AST and interpret it it's not really a compiler is it. What if I dumped the AST to disk, called it "bytecode" and updated the "interpreter" to run this "bytecode"? Would you consider that to be a compiler? :-) > where X includes I don't consider any of these things to be essential. There are entire languages out there which run on interpreters of some kind. There are others which compile down to C/JS. Many compilers use LLVM as their backend. By your definition, none of them use (or are) compilers.
- RossBencina 2y ago
  > Would you consider that to be a compiler? :-) :) No. Under my definition there needs to be some non-trivial transformation into or out of an intermediate and/or target representation (either syntax-directed directly out of the parser, or from a materialized AST). Personally I would argue that even if you trivially "compiled" to sequential bytecode, if the bytecode is then interpreted it is hard to argue that you have created a compiler (the pre-JIT cpython interpreter is still an interpreter, even though it includes a bytecode representation). But I can see that this point can be argued, and historically a school exercise of writing a Pascal-to-pcode converter would be called a compiler, so sure, you can take that perspective if you like. Just don't get confused about whether you are learning to build a compiler (definition 1) or a compiler (definition 2).