4 ms·

Writing a toy compiler for one sane input language and one target platform is indeed surprisingly easy, and very educational. I had to do this back in the 90's

Writing a toy compiler for one sane input language and one target platform is indeed surprisingly easy, and very educational. I had to do this back in the 90's for C when the O/S SW group I worked for needed to start work on a UNIX port to a new proprietary architecture (simulator) and the company's compiler group wasn't getting anything started any time soon. It took maybe 3-4 KLOC to get a boring old recursive descent parser and simple code generator working well enough to compile a minimal kernel configuration and pass a compiler self-replication test. The most interesting bit was actually the preprocessor.

mr_toad 3y ago
Writing a compiler was part of the undergraduate compsci curriculum back where I did it. I still have vague memories of ancient tools like Flex and Bison (and I’m puzzled that the author seems to be hand-rolling code rather than use existing tooling).
- badsectoracula 3y ago
  AFAIK nowadays it is more common to write a recursive descent parser to build whatever structure you want to work with (if not use the parsing directly) than rely on Flex/Bison. Personally i've written so many parsers over the years that the code for writing one "flows" naturally and i feel like Flex/Bison would introduce complexity and dependencies for no gain.
  - jakobson14 3y ago
    Those Dodekalogue people are laughing.
  - kragen 3y ago
    it introduces knowing where the ambiguities are in your grammar and eliminates large classes of parsing bugs it's also dramatically easier for other people to understand
    - lifthrasiir 3y ago
      Unfortunately `%expect` is so easy to reach even in yacc.
  - CalChris 3y ago
    There is also the ANTLR parser generator which generates a top-down parser. It's nice to write in a grammar. Still, almost all production lexers and parsers are hand written. https://www.antlr.org https://www.antlr.org
    - mdaniel 3y ago
      > Still, almost all production lexers and parsers are hand written. As a counterpoint, I consider the JetBrains parsing system to be world class and they hand-write very few (instead building on this system: https://github.com/JetBrains/Grammar-Kit#readme https://github.com/JetBrains/Grammar-Kit#readme ) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/java/java-frontback-psi-impl/src/com/intellij/lang/java/lexer/_JavaLexer.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (the parser I'll concede, as they do seem to be hand-rolling that part) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/python/python-parser/src/com/jetbrains/python/lexer/Python.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (same for its parser) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/src/com/intellij/sh/lexer/Sh.flex https://github.com/JetBrains/intellij-community/blob/idea/23... and https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/grammar/sh.bnf https://github.com/JetBrains/intellij-community/blob/idea/23... - https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/MakefileLexer.flex https://github.com/JetBrains/intellij-plugins/blob/idea/233.... and https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/Makefile.bnf https://github.com/JetBrains/intellij-plugins/blob/idea/233....
  - vidarh 3y ago
    I keep writing parser generators because I hate writing parsers manually, but keep returning to writing parsers manually because making a parser generator survive the first few meetings with reality without the pretty grammar turning into a hairy beast (when e.g. adding error recovery or trying to wrangle it into producing the trees you'd prefer rather than what fits the structure of the grammar) remains elusive. Ironically I think the sheer number of parser generators reflects our collective failure to make a good one more so than their amazing utility (sure, some projects so actually use some). I'm knee deep in her another parser generator these days, and I'm mildly hopeful (then that's always the case at the outset) of taking an augmented BNF variant and producing something DFA like that retains links from each state to higher level rules to retain enough information to backtrack to a reasonable place to both report errors from and/or resume parsing after an error. I doubt the overall approach is novel in any way, and I suspect I'll be back to hand rolling parsers soon enough, but who knows, I might end up with some worthwhile reusable components from it...
    - kragen 3y ago
      there are boatloads of projects that use flex and bison, or antlr, for their parsers. handy here right now i have gcc 0.9, gforth, yosys's ilang and verilog frontends, linux kconfig, perf, and pcc, all using yacc or bison. also wget uses lex for css (maybe flex) but not yacc. but i only have the source code of a few dozen free software projects handy here to grep many of them do eventually switch to shotgun parsers, but in a sense that's sort of like rewriting a c subroutine in assembly; it gives you, usually, modestly more benefit, for enormously more effort — but it's a benefit you can't get any other way i recently worked on a project that parsed pdf files with a peg parser generator, a parser generator we had to extend in significant ways during the project in order to get what we needed
- ww520 3y ago
  Undergrad was when I learned about the subject. It was done with tools like Lex and Yacc, along with the Dragon book. These tools are fine but only work in C. Yacc/Bison generate LALR bottom up parsers, which can be difficult to debug and use. Also it's difficult to implement error recovery. If you want to do it in another language or want to have more control, hand rolling the lexer and parser is not too bad.
- red-iron-pine 3y ago
  yeah had to do it as part of a Carnegie Mellon undergrad course. One of the higher level optional ones. Generally worthwhile experience.

mr_toad 3y ago

Writing a compiler was part of the undergraduate compsci curriculum back where I did it. I still have vague memories of ancient tools like Flex and Bison (and I’m puzzled that the author seems to be hand-rolling code rather than use existing tooling).

badsectoracula 3y ago
AFAIK nowadays it is more common to write a recursive descent parser to build whatever structure you want to work with (if not use the parsing directly) than rely on Flex/Bison. Personally i've written so many parsers over the years that the code for writing one "flows" naturally and i feel like Flex/Bison would introduce complexity and dependencies for no gain.
- jakobson14 3y ago
  Those Dodekalogue people are laughing.
- kragen 3y ago
  it introduces knowing where the ambiguities are in your grammar and eliminates large classes of parsing bugs it's also dramatically easier for other people to understand
  - lifthrasiir 3y ago
    Unfortunately `%expect` is so easy to reach even in yacc.
- CalChris 3y ago
  There is also the ANTLR parser generator which generates a top-down parser. It's nice to write in a grammar. Still, almost all production lexers and parsers are hand written. https://www.antlr.org https://www.antlr.org
  - mdaniel 3y ago
    > Still, almost all production lexers and parsers are hand written. As a counterpoint, I consider the JetBrains parsing system to be world class and they hand-write very few (instead building on this system: https://github.com/JetBrains/Grammar-Kit#readme https://github.com/JetBrains/Grammar-Kit#readme ) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/java/java-frontback-psi-impl/src/com/intellij/lang/java/lexer/_JavaLexer.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (the parser I'll concede, as they do seem to be hand-rolling that part) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/python/python-parser/src/com/jetbrains/python/lexer/Python.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (same for its parser) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/src/com/intellij/sh/lexer/Sh.flex https://github.com/JetBrains/intellij-community/blob/idea/23... and https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/grammar/sh.bnf https://github.com/JetBrains/intellij-community/blob/idea/23... - https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/MakefileLexer.flex https://github.com/JetBrains/intellij-plugins/blob/idea/233.... and https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/Makefile.bnf https://github.com/JetBrains/intellij-plugins/blob/idea/233....
- vidarh 3y ago
  I keep writing parser generators because I hate writing parsers manually, but keep returning to writing parsers manually because making a parser generator survive the first few meetings with reality without the pretty grammar turning into a hairy beast (when e.g. adding error recovery or trying to wrangle it into producing the trees you'd prefer rather than what fits the structure of the grammar) remains elusive. Ironically I think the sheer number of parser generators reflects our collective failure to make a good one more so than their amazing utility (sure, some projects so actually use some). I'm knee deep in her another parser generator these days, and I'm mildly hopeful (then that's always the case at the outset) of taking an augmented BNF variant and producing something DFA like that retains links from each state to higher level rules to retain enough information to backtrack to a reasonable place to both report errors from and/or resume parsing after an error. I doubt the overall approach is novel in any way, and I suspect I'll be back to hand rolling parsers soon enough, but who knows, I might end up with some worthwhile reusable components from it...
  - kragen 3y ago
    there are boatloads of projects that use flex and bison, or antlr, for their parsers. handy here right now i have gcc 0.9, gforth, yosys's ilang and verilog frontends, linux kconfig, perf, and pcc, all using yacc or bison. also wget uses lex for css (maybe flex) but not yacc. but i only have the source code of a few dozen free software projects handy here to grep many of them do eventually switch to shotgun parsers, but in a sense that's sort of like rewriting a c subroutine in assembly; it gives you, usually, modestly more benefit, for enormously more effort — but it's a benefit you can't get any other way i recently worked on a project that parsed pdf files with a peg parser generator, a parser generator we had to extend in significant ways during the project in order to get what we needed
ww520 3y ago
Undergrad was when I learned about the subject. It was done with tools like Lex and Yacc, along with the Dragon book. These tools are fine but only work in C. Yacc/Bison generate LALR bottom up parsers, which can be difficult to debug and use. Also it's difficult to implement error recovery. If you want to do it in another language or want to have more control, hand rolling the lexer and parser is not too bad.
red-iron-pine 3y ago
yeah had to do it as part of a Carnegie Mellon undergrad course. One of the higher level optional ones. Generally worthwhile experience.