7 ms·

I really like that this article suggests against using compiler compilers. My experiences have always been much worse when using them. I think the biggest risk

I really like that this article suggests against using compiler compilers. My experiences have always been much worse when using them. I think the biggest risk when not using them (especially if you're writing a recursive descent by hand) is avoiding the temptation to make things more context sensitive (not necessarily in the rigorous language theory sense) than absolutely necessary.

anaphor 13y ago
Yes, as Rob Pike said, just write everything by hand. Ken Thompson also recommends writing your lexers by hand as well! I also agree about the temptation to make it too complex just because how powerful writing it by hand is, I've found myself succumbing a bit to the temptation by adding in the ability to change the behaviour of the lexer in the source itself.
- wilsonfiifi 13y ago
  +1 for mentioning Rob Pike, the guy's gifted!
  - wilsonfiifi 13y ago
    Yikes! I guess that comment didn't go down well with a few folks! I found his explanation on how the lexer/parser for the templating language used in go http://www.youtube.com/watch?v=HxaD_trXwRE http://www.youtube.com/watch?v=HxaD_trXwRE was created much easier to understand than other media/literature available online on the same subject. Hence my appreciation of his work. :)
    - Dewie 13y ago
      > Yikes! I guess that comment didn't go down well with a few folks! I guess because '+1 I agree' or variations on it aren't appreciated here. That's my impression of this community, anyway. A post usually needs more meat, like the way you elaborated on your OP.
- saurik 13y ago
  This doesn't make any sense to me. The algorithm to construct optimally implemented lexers is not something any human would ever type by hand. Tools like flex were designed with one goal in mind: performance; it even has a mode that analyzes your set of tokens looking for "mistakes" that would cause backtracking, as it has a really keen interest in getting exactly linear performance. It also strives for an insanely low constant multiplier: the manual page even talks about the number of machine instructions used per character of input. Of course, some people might have needs that allow for lower throughput in exchange for "less memory", so it had various modes to "compress" its lookup tables, with varying performance tradeoffs, which you can experiment with without changing your lexer definition. This is one of the super powers you get from "the correct level of abstraction". Like, seriously: what are you trying to achieve by writing your lexer by hand? Your result will be both more difficult to maintain and is pretty much guaranteed to be slower than the output of a tool like flex. At least when people throw away the advantages of parser generators and write recursive descent parsers they gain the ability to have "easy context sensitivity" (which makes implementing many languages much easier), but I don't see why anyone would ever hand write a lexer. "I know how it all works" is also fine, but in that case you write your own lexer generator tool, you don't skip directly to the lexer (unless you are doing your first one as a "homework assignment"). If you don't like the input syntax of your lexer generator, there are many to choose from, or maybe you write one yourself, but that's no reason to switch to something that is not only going to be more verbose and error-prone but will also be slower. (afterthought: I guess an interesting analogy: you don't lay out a hashtable by hand, like in a C initializer list in your source code that has a large number of NULL entries with only a subset filled in, already in hashed order; you instead write a hash function and let the computer reorder your entries for you. Manually hashing the values feels "hard core", but offers no advantages, and means you have to throw away all of your work and start over when the size of your table changes. Doing it by hand is also strictly grunt work: you don't gain anything by having placed it by hand other than the possibility that you made a mistake somewhere and now your element will never be found. And if later you want to try different hash functions or different search algorithms--maybe you are willing to pay some costs to get range queries, and end up using a tree--you can later do so without changing your input files. You should think of your lexer like a really complex data structure tied to an algorithm that always has the abstract interface "get next token".)
- zimbatm 13y ago
  In regards to syntax, I found that using a higher-level syntax like BNF to explore a language space is great. But then write it by hand to get performance. I've only done it a couple of times with relatively simple syntaxes so YMMV.
thinkpad20 13y ago
I have used lex/yacc a number of times, and written several parsers by hand, and I don't see anything really wrong with using compiler compilers. Sure, it's good to have the experience of writing parsers by hand, so that you know how it works. But a compiler compiler is probably more likely to be correct and efficient, especially when still in the process of developing the language and things are changing rapidly. The best of both worlds is a library like Parsec in Haskell, which lets you write in the native language, but feel like you're writing in a DSL. Parsec is a breeze and easily my favorite thing with which to write parsers...
- anaphor 13y ago
  Parser generators are a different issue than lexer generators imo. With a lexer, usually it ends up being a lot easier to do it by hand, because otherwise you end up fighting the system or writing awful regular expressions. Parser generators at least let you use nice formats like BNF. Edit: also your lexical spec is much less likely to change than your grammar is.
  - auvrw 13y ago
    so i really just want to say something like, "yeah, but Parsec is still awesome," but then i saw someone got downvoted for a similar comment with Rob Pike in place of Parsec, so what can i add to the discussion? perhaps just that it's important to keep in mind that computer systems are things we've worked out for ourselves. these notions of "lex" and "parse" are not things given to us by nature... ...although, they do kind of do fall out the circumstances of (1) needing to emit x86 instructions and (2) the preference for writing programs in text editors. the second point gets a lot of discussion what with ideas about editors understanding parse trees and all, but i wonder what happens to the whole lexer-parser dichotomy if we keep 2 and periscope our notions of hardware. does the need for tokenization appear as a result of something fundamental to von neumann architecture, or is it just a result of currently-vogue instruction sets? ah well, back to making things happen with the tools at hand.
    - saurik 13y ago
nemo1618 13y ago
I used Flex/Bison for writing my first interpreter, and I definitely recommended for beginners. I think when you're starting out, it's more important to focus on writing a proper grammar and traversing the AST than to do all the lexing/parsing by hand. Plus, it makes it easier to rapidly prototype your language when you're still in the design phase, and the Flex/Bison files serve as a form of documentation. That said, now that my language's grammar is stable and I have a better understanding of lexing and parsing, I'm thinking about ditching Flex/Bison, mainly to achieve more descriptive error messages.
- knome 13y ago
  I found the lemon parser generator distributed with the source to sqlite3 to be far easier to use than bison. http://www.hwaci.com/sw/lemon/ http://www.hwaci.com/sw/lemon/
  - reidrac 13y ago
    This looks really interesting, thanks. I've playing with PLY* for fun, but I'd like to try something else in C without going back to flex/bison. * http://www.dabeaz.com/ply/ http://www.dabeaz.com/ply/

anaphor 13y ago

Yes, as Rob Pike said, just write everything by hand. Ken Thompson also recommends writing your lexers by hand as well! I also agree about the temptation to make it too complex just because how powerful writing it by hand is, I've found myself succumbing a bit to the temptation by adding in the ability to change the behaviour of the lexer in the source itself.

wilsonfiifi 13y ago
+1 for mentioning Rob Pike, the guy's gifted!
- wilsonfiifi 13y ago
  Yikes! I guess that comment didn't go down well with a few folks! I found his explanation on how the lexer/parser for the templating language used in go http://www.youtube.com/watch?v=HxaD_trXwRE http://www.youtube.com/watch?v=HxaD_trXwRE was created much easier to understand than other media/literature available online on the same subject. Hence my appreciation of his work. :)
  - Dewie 13y ago
    > Yikes! I guess that comment didn't go down well with a few folks! I guess because '+1 I agree' or variations on it aren't appreciated here. That's my impression of this community, anyway. A post usually needs more meat, like the way you elaborated on your OP.
saurik 13y ago
This doesn't make any sense to me. The algorithm to construct optimally implemented lexers is not something any human would ever type by hand. Tools like flex were designed with one goal in mind: performance; it even has a mode that analyzes your set of tokens looking for "mistakes" that would cause backtracking, as it has a really keen interest in getting exactly linear performance. It also strives for an insanely low constant multiplier: the manual page even talks about the number of machine instructions used per character of input. Of course, some people might have needs that allow for lower throughput in exchange for "less memory", so it had various modes to "compress" its lookup tables, with varying performance tradeoffs, which you can experiment with without changing your lexer definition. This is one of the super powers you get from "the correct level of abstraction". Like, seriously: what are you trying to achieve by writing your lexer by hand? Your result will be both more difficult to maintain and is pretty much guaranteed to be slower than the output of a tool like flex. At least when people throw away the advantages of parser generators and write recursive descent parsers they gain the ability to have "easy context sensitivity" (which makes implementing many languages much easier), but I don't see why anyone would ever hand write a lexer. "I know how it all works" is also fine, but in that case you write your own lexer generator tool, you don't skip directly to the lexer (unless you are doing your first one as a "homework assignment"). If you don't like the input syntax of your lexer generator, there are many to choose from, or maybe you write one yourself, but that's no reason to switch to something that is not only going to be more verbose and error-prone but will also be slower. (afterthought: I guess an interesting analogy: you don't lay out a hashtable by hand, like in a C initializer list in your source code that has a large number of NULL entries with only a subset filled in, already in hashed order; you instead write a hash function and let the computer reorder your entries for you. Manually hashing the values feels "hard core", but offers no advantages, and means you have to throw away all of your work and start over when the size of your table changes. Doing it by hand is also strictly grunt work: you don't gain anything by having placed it by hand other than the possibility that you made a mistake somewhere and now your element will never be found. And if later you want to try different hash functions or different search algorithms--maybe you are willing to pay some costs to get range queries, and end up using a tree--you can later do so without changing your input files. You should think of your lexer like a really complex data structure tied to an algorithm that always has the abstract interface "get next token".)
zimbatm 13y ago
In regards to syntax, I found that using a higher-level syntax like BNF to explore a language space is great. But then write it by hand to get performance. I've only done it a couple of times with relatively simple syntaxes so YMMV.

thinkpad20 13y ago

I have used lex/yacc a number of times, and written several parsers by hand, and I don't see anything really wrong with using compiler compilers. Sure, it's good to have the experience of writing parsers by hand, so that you know how it works. But a compiler compiler is probably more likely to be correct and efficient, especially when still in the process of developing the language and things are changing rapidly. The best of both worlds is a library like Parsec in Haskell, which lets you write in the native language, but feel like you're writing in a DSL. Parsec is a breeze and easily my favorite thing with which to write parsers...

anaphor 13y ago
Parser generators are a different issue than lexer generators imo. With a lexer, usually it ends up being a lot easier to do it by hand, because otherwise you end up fighting the system or writing awful regular expressions. Parser generators at least let you use nice formats like BNF. Edit: also your lexical spec is much less likely to change than your grammar is.
- auvrw 13y ago
  so i really just want to say something like, "yeah, but Parsec is still awesome," but then i saw someone got downvoted for a similar comment with Rob Pike in place of Parsec, so what can i add to the discussion? perhaps just that it's important to keep in mind that computer systems are things we've worked out for ourselves. these notions of "lex" and "parse" are not things given to us by nature... ...although, they do kind of do fall out the circumstances of (1) needing to emit x86 instructions and (2) the preference for writing programs in text editors. the second point gets a lot of discussion what with ideas about editors understanding parse trees and all, but i wonder what happens to the whole lexer-parser dichotomy if we keep 2 and periscope our notions of hardware. does the need for tokenization appear as a result of something fundamental to von neumann architecture, or is it just a result of currently-vogue instruction sets? ah well, back to making things happen with the tools at hand.
  - saurik 13y ago

nemo1618 13y ago

I used Flex/Bison for writing my first interpreter, and I definitely recommended for beginners. I think when you're starting out, it's more important to focus on writing a proper grammar and traversing the AST than to do all the lexing/parsing by hand. Plus, it makes it easier to rapidly prototype your language when you're still in the design phase, and the Flex/Bison files serve as a form of documentation. That said, now that my language's grammar is stable and I have a better understanding of lexing and parsing, I'm thinking about ditching Flex/Bison, mainly to achieve more descriptive error messages.

knome 13y ago
I found the lemon parser generator distributed with the source to sqlite3 to be far easier to use than bison. http://www.hwaci.com/sw/lemon/ http://www.hwaci.com/sw/lemon/
- reidrac 13y ago
  This looks really interesting, thanks. I've playing with PLY* for fun, but I'd like to try something else in C without going back to flex/bison. * http://www.dabeaz.com/ply/ http://www.dabeaz.com/ply/