5 ms·

Supplementary to that and also a bit more specific I'd be grateful for an answer to the following: Is it considered best practice today to use Flex & Bison for

Supplementary to that and also a bit more specific I'd be grateful for an answer to the following: Is it considered best practice today to use Flex & Bison for the front-end of (for example) a basic C compiler?

chubot 9y ago
I don't think it's ever been the case that C front ends used lex/yacc. Whether it's "best practice" I suppose depends on who you ask! (You'll certainly learn it with parser generators in university because writing a hand-written parser takes too long for an undergrad class, and they will only cover a tiny subset of C if anything.) You can see here that the original C compilers use a hand-written expression parser using the Shunting Yard algorithm, and I'm sure the rest of the front end is hand-written too: http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html C predates lex/yacc so the syntax wasn't really designed with them in mind. Some other potential problems: (1) Distinguishing types and variables in C: https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack (2) The preprocessor. While it doesn't prevent you from using lex/yacc for the C parser, this is an entirely separate lexer and parser that is always written by hand AFAICT. Awk, on the other hand, is almost always parsed with lex/yacc. The language was almost designed around those tools. I think if you're writing say your first compiler you should try to use lex and yacc. I think you can solve the context-sensitivity problem but I haven't done it myself. Operator precedence probably requires some extensions or maybe you can encode the many levels of C precedence in the grammar. One thing I found from implementing a shell parser [1] is that the POSIX spec uses yacc grammars, even if the languages aren't best parsed with bottom-up parsing. For example, all shells except bash use top-down parsing. Analogously, the C grammar may "manually" encode the operator precedence, even though the original C parsers and current ones like GCC/Clang actually use an operator precedence algorithm like the Shunting Yard algorithm, not yacc's shift-reduce algorithm. e.g. this grammar manually encodes it: https://www.lysator.liu.se/c/ANSI-C-grammar-y.html https://www.lysator.liu.se/c/ANSI-C-grammar-y.html Not that yacc can't parse expressions -- it's just something interesting I found. Also, for shell, there are a bunch of parsing rules that are necessarily listed separately from the grammar, and I'm sure the same is true for C. [1] http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...
- delhanty 9y ago
  Thank you very much for all that information - much appreciated! The Portable C Compiler was written using Yacc. [1] >I think if you're writing say your first compiler you should try to use lex and yacc. I've actually started with something higher level still: BNFC [2], which has taken me quite a long way quite quickly. It generates lexer, parser, operator precedence and AST along the lines of the Appel books for a variety of backends: C, Java, OCAML, Haskell etc. But now I'm running into bugs and limitations in BNFC. I may fix some of those if I can, but at some point I will probably dump BNFC and then hand-edit the generated Flex/Bison. Maybe that's what people do eventually - start with a high-level tool and then move lower? [1] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler [2] https://github.com/BNFC/bnfc https://github.com/BNFC/bnfc
  - chubot 9y ago
    OK BNFC is interesting! I think that kind of tool is the holy grail, but they all have limitations. You kind of have to design your language AROUND it, and C obviously doesn't fit in that category. For example, I mentioned that Awk was designed with yacc. It depends how ambitious you want to be. You can tweak C to be more easily parsed, but then you will parse fewer real programs. It's not surprising to me at all that BNFC will have problems with C. So I guess I would say you should use high level tools like BNFC / lex / yacc until you can't. FWIW here is another little problem you will run into with C: https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else I guess the point is that parser generators and even grammars themselves are leaky abstractions! To effectively use parsing tools you have to be familiar with their internals and the underlying algorithm. If there are two levels of code generation like BNFC, then that makes this task harder! I think it makes sense to start high and go low. It also makes sense to start low-level and go high. Once you are sick of writing parsers by hand, you will understand how to write a better parser generator than the ones that currently exist :)
alexfru 9y ago
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.
ufo 9y ago
Lexers are easier to write by hand than parsers are but lexer generators such as flex are still very useful. The thing they are most useful at is that their algorithms always led the longest match possible, which is something that can be easy to get wrong by hand. Regarding LALR parsers, the best thing about them is that they error out if they think your grammar might be ambiguous, which is specially useful if you are designing your own language. It is also easier to evolve a grammar if you build the parser with a high level tool than if you code everything by hand. For example, a top down parser needs to know at every point what are the valid lookahead tokens that might appear and adding a new rule to the grammar might require changing the lookahead tokens in many different spots. The place were yacc doesn't shine is if your grammar isn't context free, in which case you might need to use hacky tricks or advanced parsing techniques. Bottom up parser generators also aren't the best at generating informative error messages (but they do a decent job of doing a bare minimum default error message)
- delhanty 9y ago
  Thank you very much - that's all useful - especially the bit about bottom up parser generators being not the best at generating informative error messages.
  - ufo 9y ago
    There are tools such as merr that help with this but generally its hard to beat hand-crafted error messages developed with love and sweat :)
WalterBright 9y ago
Lexing and parsing are the simplest, by far, parts of a compiler. (That's why it is possible for Flex & Bison to exist.) 99% of the time spent writing a compiler will be elsewhere. If you want a correct to the last drop C preprocessor, prepare to spend 6 months on that, minimum. Or just use Warp: https://github.com/facebookarchive/warp https://github.com/facebookarchive/warp and then you can have fun just working on the compiler bit.
- delhanty 9y ago
  Thank you - that's informative. >99% of the time spent writing a compiler will be elsewhere. Out of interest, has the distribution of labor in that remaining 99% changed at all since you first started out? For example, do things like LLVM change anything?
  - WalterBright 9y ago
    I re-used the Digital Mars C++ optimizer and back end for the dmd D compiler, so that would be like using LLVM for an optimizer and back end. I still wind up spending nearly all my time on the D front end, and not the lexer/parser. The time spent on the lexer/parser is a rounding error. Besides, build the lexer/parser by hand. The mystery of how to do them will evaporate, and you'll find you can apply that knowledge to all sorts of other tasks.

chubot 9y ago

I don't think it's ever been the case that C front ends used lex/yacc. Whether it's "best practice" I suppose depends on who you ask! (You'll certainly learn it with parser generators in university because writing a hand-written parser takes too long for an undergrad class, and they will only cover a tiny subset of C if anything.) You can see here that the original C compilers use a hand-written expression parser using the Shunting Yard algorithm, and I'm sure the rest of the front end is hand-written too: http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html C predates lex/yacc so the syntax wasn't really designed with them in mind. Some other potential problems: (1) Distinguishing types and variables in C: https://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited https://eli.thegreenplace.net/2011/05/02/the-context-sensiti... https://en.wikipedia.org/wiki/The_lexer_hack https://en.wikipedia.org/wiki/The_lexer_hack (2) The preprocessor. While it doesn't prevent you from using lex/yacc for the C parser, this is an entirely separate lexer and parser that is always written by hand AFAICT. Awk, on the other hand, is almost always parsed with lex/yacc. The language was almost designed around those tools. I think if you're writing say your first compiler you should try to use lex and yacc. I think you can solve the context-sensitivity problem but I haven't done it myself. Operator precedence probably requires some extensions or maybe you can encode the many levels of C precedence in the grammar. One thing I found from implementing a shell parser [1] is that the POSIX spec uses yacc grammars, even if the languages aren't best parsed with bottom-up parsing. For example, all shells except bash use top-down parsing. Analogously, the C grammar may "manually" encode the operator precedence, even though the original C parsers and current ones like GCC/Clang actually use an operator precedence algorithm like the Shunting Yard algorithm, not yacc's shift-reduce algorithm. e.g. this grammar manually encodes it: https://www.lysator.liu.se/c/ANSI-C-grammar-y.html https://www.lysator.liu.se/c/ANSI-C-grammar-y.html Not that yacc can't parse expressions -- it's just something interesting I found. Also, for shell, there are a bunch of parsing rules that are necessarily listed separately from the grammar, and I'm sure the same is true for C. [1] http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...

delhanty 9y ago
Thank you very much for all that information - much appreciated! The Portable C Compiler was written using Yacc. [1] >I think if you're writing say your first compiler you should try to use lex and yacc. I've actually started with something higher level still: BNFC [2], which has taken me quite a long way quite quickly. It generates lexer, parser, operator precedence and AST along the lines of the Appel books for a variety of backends: C, Java, OCAML, Haskell etc. But now I'm running into bugs and limitations in BNFC. I may fix some of those if I can, but at some point I will probably dump BNFC and then hand-edit the generated Flex/Bison. Maybe that's what people do eventually - start with a high-level tool and then move lower? [1] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler [2] https://github.com/BNFC/bnfc https://github.com/BNFC/bnfc
- chubot 9y ago
  OK BNFC is interesting! I think that kind of tool is the holy grail, but they all have limitations. You kind of have to design your language AROUND it, and C obviously doesn't fit in that category. For example, I mentioned that Awk was designed with yacc. It depends how ambitious you want to be. You can tweak C to be more easily parsed, but then you will parse fewer real programs. It's not surprising to me at all that BNFC will have problems with C. So I guess I would say you should use high level tools like BNFC / lex / yacc until you can't. FWIW here is another little problem you will run into with C: https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else I guess the point is that parser generators and even grammars themselves are leaky abstractions! To effectively use parsing tools you have to be familiar with their internals and the underlying algorithm. If there are two levels of code generation like BNFC, then that makes this task harder! I think it makes sense to start high and go low. It also makes sense to start low-level and go high. Once you are sick of writing parsers by hand, you will understand how to write a better parser generator than the ones that currently exist :)

alexfru 9y ago

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.

ufo 9y ago

Lexers are easier to write by hand than parsers are but lexer generators such as flex are still very useful. The thing they are most useful at is that their algorithms always led the longest match possible, which is something that can be easy to get wrong by hand. Regarding LALR parsers, the best thing about them is that they error out if they think your grammar might be ambiguous, which is specially useful if you are designing your own language. It is also easier to evolve a grammar if you build the parser with a high level tool than if you code everything by hand. For example, a top down parser needs to know at every point what are the valid lookahead tokens that might appear and adding a new rule to the grammar might require changing the lookahead tokens in many different spots. The place were yacc doesn't shine is if your grammar isn't context free, in which case you might need to use hacky tricks or advanced parsing techniques. Bottom up parser generators also aren't the best at generating informative error messages (but they do a decent job of doing a bare minimum default error message)

delhanty 9y ago
Thank you very much - that's all useful - especially the bit about bottom up parser generators being not the best at generating informative error messages.
- ufo 9y ago
  There are tools such as merr that help with this but generally its hard to beat hand-crafted error messages developed with love and sweat :)

WalterBright 9y ago

Lexing and parsing are the simplest, by far, parts of a compiler. (That's why it is possible for Flex & Bison to exist.) 99% of the time spent writing a compiler will be elsewhere. If you want a correct to the last drop C preprocessor, prepare to spend 6 months on that, minimum. Or just use Warp: https://github.com/facebookarchive/warp https://github.com/facebookarchive/warp and then you can have fun just working on the compiler bit.

delhanty 9y ago
Thank you - that's informative. >99% of the time spent writing a compiler will be elsewhere. Out of interest, has the distribution of labor in that remaining 99% changed at all since you first started out? For example, do things like LLVM change anything?
- WalterBright 9y ago
  I re-used the Digital Mars C++ optimizer and back end for the dmd D compiler, so that would be like using LLVM for an optimizer and back end. I still wind up spending nearly all my time on the D front end, and not the lexer/parser. The time spent on the lexer/parser is a rounding error. Besides, build the lexer/parser by hand. The mystery of how to do them will evaporate, and you'll find you can apply that knowledge to all sorts of other tasks.