5 ms·

If you haven't used flex & bison and you're writing your first compiler, you need to learn them and still take care of the things they don't do for you out of t

If you haven't used flex & bison and you're writing your first compiler, you need to learn them and still take care of the things they don't do for you out of the box (they don't know C and the context of the input). IOW, it looks like the hardest work may still be up to you, but now you're dependent on external tools and self-hosting has become a bit questionable/problematic (you'd want those tools to be compiled by your compiler as well, right?). Parsing tokens, OTOH, isn't a big deal. You don't need heavy artillery for them. IOW, if you haven't had lots of experience with those tools or compiler creation already, you may not gain much from using them for the first time. If you have, you may reuse your experience and possibly even code.

delhanty 9y ago
Thank you very much for your reply. That's helpful and fits in well with my experience so far. I asked the question in the context where self-hosting was required, but I probably don't need it. On the other-hand, more dependencies does complicate things. So I was interested to know whether Flex & Bison (or equivalent tools in other languages e.g. Alex & Happy for Haskell) were worth the extra complexity. I started from one of the Appel books that I had on my book shelf for years: Modern Compiler Implementation in ML. Reading Appel, he writes "The task of constructing LR(1) or LALR(1) grammars is simple enough to be automated. And is so tedious to do by hand that LR parsing for realistic grammars is rarely done except using parser-generator tools." p68. (Agreeing with what you advise, even Appel admits that the lexing of tokens isn't a big deal.) But after that the only C compiler (for example) that I could find that used Bison (or Yacc) was the Portable C Compiler, so I was starting to suspect that Appel might be taking a rather academic view. [1] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler
- groovy2shoes 9y ago
  That's likely because most C compilers (in my experience) use top-down parsers (LL) rather than bottom-up ones (LR). In contrast to LR parsers, LL parsers are quite easy to write and maintain by hand (recursive descent, parser combinators, etc.), and the nature of such hand-written parsers makes it comparatively easy to step outside theoretical bounds and implement context-sensitive portions of the grammar. Such parsers have some other benefits, too, like being easier to debug and making it easier to provide useful error messages (but see Menhir for OCaml, for example, which offers some improvements in these areas over traditional LR parser generators). What Appel has said is true—it's rare to encounter hand-written LR(1) or LALR(1) parsers in practice. However, many practical languages are easy enough to parse with hand-written top-down parsers that it's quite common to encounter hand-written LL(1)-ish parsers in practice.
  - delhanty 9y ago
    Thank you - that's very useful information! I had been wondering how one was meant to provide meaningful error messages for code that failed to parse or failed to lex using the LR approach and looks like maybe the answer is "with difficulty", which is definitely a downer.
    - tjalfi 9y ago
      Phillipe Charles Phd thesis[0] describes a method for generating good error messages with an LALR parser generator. lpg[1] implements these techniques. [0] http://jikes.sourceforge.net/documents/thesis.pdf http://jikes.sourceforge.net/documents/thesis.pdf [1] https://sourceforge.net/projects/lpg/ https://sourceforge.net/projects/lpg/
- WalterBright 9y ago
  > were worth the extra complexity No.
  - delhanty 9y ago
    Succinct! If anyone should know it would be you, so thank you for your verdict.

delhanty 9y ago

Thank you very much for your reply. That's helpful and fits in well with my experience so far. I asked the question in the context where self-hosting was required, but I probably don't need it. On the other-hand, more dependencies does complicate things. So I was interested to know whether Flex & Bison (or equivalent tools in other languages e.g. Alex & Happy for Haskell) were worth the extra complexity. I started from one of the Appel books that I had on my book shelf for years: Modern Compiler Implementation in ML. Reading Appel, he writes "The task of constructing LR(1) or LALR(1) grammars is simple enough to be automated. And is so tedious to do by hand that LR parsing for realistic grammars is rarely done except using parser-generator tools." p68. (Agreeing with what you advise, even Appel admits that the lexing of tokens isn't a big deal.) But after that the only C compiler (for example) that I could find that used Bison (or Yacc) was the Portable C Compiler, so I was starting to suspect that Appel might be taking a rather academic view. [1] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler

groovy2shoes 9y ago
That's likely because most C compilers (in my experience) use top-down parsers (LL) rather than bottom-up ones (LR). In contrast to LR parsers, LL parsers are quite easy to write and maintain by hand (recursive descent, parser combinators, etc.), and the nature of such hand-written parsers makes it comparatively easy to step outside theoretical bounds and implement context-sensitive portions of the grammar. Such parsers have some other benefits, too, like being easier to debug and making it easier to provide useful error messages (but see Menhir for OCaml, for example, which offers some improvements in these areas over traditional LR parser generators). What Appel has said is true—it's rare to encounter hand-written LR(1) or LALR(1) parsers in practice. However, many practical languages are easy enough to parse with hand-written top-down parsers that it's quite common to encounter hand-written LL(1)-ish parsers in practice.
- delhanty 9y ago
  Thank you - that's very useful information! I had been wondering how one was meant to provide meaningful error messages for code that failed to parse or failed to lex using the LR approach and looks like maybe the answer is "with difficulty", which is definitely a downer.
  - tjalfi 9y ago
    Phillipe Charles Phd thesis[0] describes a method for generating good error messages with an LALR parser generator. lpg[1] implements these techniques. [0] http://jikes.sourceforge.net/documents/thesis.pdf http://jikes.sourceforge.net/documents/thesis.pdf [1] https://sourceforge.net/projects/lpg/ https://sourceforge.net/projects/lpg/
WalterBright 9y ago
> were worth the extra complexity No.
- delhanty 9y ago
  Succinct! If anyone should know it would be you, so thank you for your verdict.