8 ms·
Let's write a compiler, part 1: Introduction, selecting a language, and planning
- waynesonfire 5y agopart 1 isn't parser / lexer???? nice job. "On the next episode: A lexer" oh, it is.
- turminal 5y agoWell, it's the first thing in the pipeline, so why not?
- mpd 5y agoI'm not your parent commentor, but imo, it's because there's is an enormous amount of existing info out there about these two steps. For these kinds of projects, they are necessary whether you're translating to another language (i.e. generating code) or not. And everyone starts with lexing and parsing. And just repeats the same old shit.
- dmitriid 5y agoThere's too much emphasis on parsing in all the teaching materials on compiling. And there's rarely any good stuff on the actual hard problems
- habibur 5y ago> And there's rarely any good stuff on the actual hard problems So what are those hard problems?
- sim_card_map 5y agocodegen, optimizations, ast transformations
- dmitriid 5y agoThe actual compilation. Actual programming language design. Types, type inference, function implementations, error handling and recovery, incremental compilation, interfacing with the external world, code generation, fixing problems in code generation tools, CPU architecture concerns... The toy languages that most learning materials make can be parsed with regexps and is definitely not something to spend a lot of time on at the beginning. Because actual parsing problems are never addressed in these materials, and can come later (example of concerns: https://matklad.github.io//2018/06/06/modern-parser-generator.html https://matklad.github.io//2018/06/06/modern-parser-generato...).
- rualca 5y ago> The actual compilation. Actual programming language design. Isn't that intimately tied to parsing? I mean, how do you expect to implement a parser if you have no idea if a specific programming construct can actually be parsed, or what are the implications in compilation time of doing things one way or another?
- dmitriid 5y ago> Isn't that intimately tied to parsing? Not entirely > how do you expect to implement a parser if you have no idea if a specific programming construct can actually be parsed Every construct can be parsed. However, there are significantly more aspects to language design than "parsing programming constructs". For example, C++ header/implementation split with no real module system affects compilation orders of magnitudes more than the parsing rules for C++.
- kragen 5y agoI think there are several good reasons not to start with the lexer and parser: 1. If you write a code generator whose input is something like Forth ("operators are separated by spaces") you have written a compiler. If you write a lexer and parser, you have not written a compiler. So, if we want to develop the compiler incrementally, we should start with a back end, then add a front end. 2. Parsing and lexing are much more theoretically tractable than code generation, which is only now beginning to succumb to systematic formalization after nearly 50 years of efforts. Consequently there are enormous edifices of theory and tooling built up around parsing and lexing, which are fascinating and delightful. The problems is that people tend to teach all this stuff, which is not actually necessary to write a useful parser. Rather than studying Chomsky's hierarchy of languages and automata theory, you're probably better off just learning how context-free languages work, a little about refactoring them to eliminate left recursion, and about chronological backtracking search and applying it to the parsing problem, and then just write a recursive-descent parser. If you want to study the LALR algorithm and the refinements that have made Earley's algorithm practical, that's great, but you shouldn't really have to puzzle over shift-reduce conflicts in order to get up and running. 3. It's very tempting for novices to see syntax as the important aspect of programming, because it's what you can see most easily; but of course it is purely superficial. By teaching lexers and parsers as the first step, and thus implicitly the most important step, in writing a compiler, you're hurting novice programmers by reinforcing that misconception instead of helping them by ripping it away.
- tester756 5y ago>3. It's very tempting for novices to see syntax as the important aspect of programming, because it's what you can see most easily; but of course it is purely superficial. By teaching lexers and parsers as the first step, and thus implicitly the most important step, in writing a compiler, you're hurting novice programmers by reinforcing that misconception instead of helping them by ripping it away. I'm newbie in those topics and I don't see it this way for me lexer is way of building abstraction above syntax. Syntax is important from perspective of language design team, meanwhile compiler is operating on abstraction
- 5y ago
- risk 5y agoThe author of this is part of the binary grand prix and made my favorite submission to the contest. Very cool content thanks for posting it.
- lisper 5y ago> Outputting to C is a well-recognized compilation strategy. That's true, but it's not a good choice for teaching how to write a compiler because the C compiler does too much of the heavy lifting for you while at the same time imposing unnecessary constraints. Compiling to C allows you to entirely side-step the question of how to compile arithmetic and function calls, which is like 90% of the battle. Also, if you want your source language to, for example, be able to do non-local transfers of control or have automatic memory management then you will have to do extra work that you would not have to do if you were compiling to assembler or an abstract RTL. Finally, compiling to C gives the student the impression that there is something holy and immutable about C, that C is The Way and the Truth and the Light and no man comes to the lambda nature but through C. It's not true, and, to paraphrase Dykstra, the psychological damage caused by indoctrinating people into this worldview is hard to undo.
- lebuffon 5y agoEverybody knows that CPU stands for: 'C' Processing Unit ;-)
- lebuffon 5y agoKrenshaw's classic version is available in C. https://github.com/lotabout/Let-s-build-a-compiler https://github.com/lotabout/Let-s-build-a-compiler
- thelittlenag 5y agoI agree. Compiling to C as your target just feels like a let down. I guess if you have to compromise on the hard parts why not target something like WASM or JVM bytecode? At least then you learn two interesting things.
- rualca 5y agoI thought that the technical term for parsing a high-level programming language to output another high-level programming language was transcompiling. https://en.wikipedia.org/wiki/Source-to-source_compiler https://en.wikipedia.org/wiki/Source-to-source_compiler
- reeealloc 5y agoWrote a compiler with .NET last year. Used F# for the Lexing/Parsing to an AST and C# for LLVM IR code gen. Interop was so easy, but the docs for the C# LLVM bindings were not so great, so it's a little incomplete. I only got it to effectively interpret, never actually executed a whole outputted object file.
- tester756 5y agoWhen I've been messing with this stuff, then I decided to manually write LLVM IR instead of using C#'s LLVM Bindings
- lostmsu 5y agoWith .NET you could also emit IL.
- fishmaster 5y agoHow was F# for the task?
- mpd 5y agoin my case, I learned by writing a brainfuck compiler last year. Now I'm working on a compiler / vm for a 30 year old esoteric mud language.
- rishav_sharan 5y agoSo, I just started writing a compiler for my toy language an I must say, the hardest part is not the lexing, parsing, compiling etc but just settling on a language syntax/semantics. I just can't let my poor toy language be - and keep on revamping it everyday. Anyone who is just starting on this or has as poor self discipline as I do, I would recommend choosing any existing language to create a compiler for. Don't male your own language unless you have frozen down its details. Changing the lexer and ST everyday just because you decide that you are switching to begin-end instead of curlies, is a special kind of hell in itself.
- vanderZwan 5y agoAlternatively, do a lot of pen-and-paper design first, including writing a few toy programs for every feature you want to add. Mentally working your way through how a program would be interpreted and run helps a lot with working out the kinks, and in my case a least pen and paper helped me focus a lot and spot details and mistakes that would have been lost if I had been typing in some mock plaintext file. EDIT: I'm fine with people thinking I said something stupid, so I don't mind the downvote, but I'd like to know why exactly so I can learn from the other viewpoint. What is the problem with suggesting to work out out problems on paper, including the semantic design of a programming language in particular? It's a good stress-test for "how well can I debug this in my head", for starters.
- hutzlibu 5y ago"that you are switching to begin-end instead of curlies" Why not both? It is your language ..
- erezsh 5y agoIf you're using a good parser, switching between begin-end and curlies should be a one minute job. Now, updating the tests and the library code.. that's a different story.
- rishav_sharan 5y agoI am hand rolling >.>
- p4bl0 5y agoI've been teaching a compiler class for 5 years. My experience has been that writing and teaching to write compiler is more efficient using horizontal step rather than vertical steps. What I call vertical steps are lexing, parsing, typing, compiling, emitting output code. What I call horizontal steps are language features going through all the vertical steps. For example it is far better to start with a compiler for the "int language" (valid programs consist in a single integer and that's it), and then progressively add horizontal layers (features) to the language, being able to tests these new features each time. For example adding additions, then other binary operation, then multiple instructions, then variables and affectation, etc. Next fall I will try the backward approach in my course (still using horizontal steps for building the project, but teaching the vertical steps backward). I'm quite convinced it will work better since I read this article: https://blog.sigplan.org/2021/02/23/teaching-compilers-backward/ https://blog.sigplan.org/2021/02/23/teaching-compilers-backw...
- Zababa 5y agoThanks for the advice, I've tried before to build a compiler with the vertical approach and it got really frustrating at some point. I will try again with the horizontal approach.
- p4bl0 5y agoCool :). The thing is to have an always start-to-end working compiler for an increasingly (even if the steps are very small) complex language. Another point would be to use simple tools at least to begin with. Racket [1] provides good lexer/parser tools [2] and you can use pattern matching [3] to browse and transform your AST. You can also target MIPS assembly [4] using the SPIM platform [5] for example, it is easy to learn and has very good debugging tools (basically the whole platform behaves like a gdb session). For the compiler implementation language OCaml is also a very good choice (even better because static typing will actually help you a lot with the horizontal approach) but it is less easier to setup as you need to install a lot more tools: ocaml itself, ocamllex (lexer), menhir (parser), ocamlbuild (automated build system), etc. [1] https://racket-lang.org/ https://racket-lang.org/ [2] https://docs.racket-lang.org/parser-tools/ https://docs.racket-lang.org/parser-tools/ [3] https://docs.racket-lang.org/guide/match.html https://docs.racket-lang.org/guide/match.html [4] http://www.cburch.com/cs/330/reading/mips-ref.pdf http://www.cburch.com/cs/330/reading/mips-ref.pdf [5] http://spimsimulator.sourceforge.net/ http://spimsimulator.sourceforge.net/