5 ms·

It amazes me how far out of their way many people will go to avoid using parsing tools. He avoided using a lexer generator because "I'd figured using a lexer g

It amazes me how far out of their way many people will go to avoid using parsing tools. He avoided using a lexer generator because "I'd figured using a lexer generator was more trouble than it was worth". To him it was more convenient to write a lexer manually (using macros) in C++, then later completely rewrite it in a different language (D) as a one-off trie matcher code generator. I am amazed that this could be thought of as less work. How can writing two lexers from scratch manually be less trouble than writing a bunch of regexes in a Flex or Ragel file? Especially since the result was likely slower than using Flex or Ragel would have been? To me the interesting question is: how much of this allergy to external tools is: 1. the trouble of learning/maintaining something new/different (inherent tool overhead) 2. design of the tool isn't as user-friendly as it could be (incidental tool overhead) 3. irrational belief that the tool will be more work/trouble than it actually is (non-optimal decision making) If part of the answer is (2), then improved tools will lead to greater adoption. And hopefully more convenient tools will lead to them being better known and more widely adopted, which should lessen (1) also. Everyone uses regexes; using a lexer generator should (in my opinion) be as easy as using a one-off regex. I think the key is to make the lexer generator an embeddable library like regex libraries are.

p0nce 13y ago
See my comment here https://news.ycombinator.com/item?id=7293796 https://news.ycombinator.com/item?id=7293796, to make anyone able to add a company-specific check quickly is a valuable asset (to ensure decisions like "We don't want to use idiom X anymore"). Moreover, fake parsers like cppcheck will lint your code even if the code does not even build, so they are really easy to setup.
eco 13y ago
> Everyone uses regexes; using a lexer generator should (in my opinion) be as easy as using a one-off regex. I think the key is to make the lexer generator an embeddable library like regex libraries are. There actually is a really powerful parser generator for D by Philippe Sigaud: https://github.com/PhilippeSigaud/Pegged https://github.com/PhilippeSigaud/Pegged It's much more pleasant to use than something like Boost Spirit. Somewhat relatedly, D's standard library has a compile time regex engine that compiles regular expressions down at compile-time resulting in some of the fastest regular expressions in the world.
- haberman 13y ago
  That's cool, though "some of the fastest regular expressions in the world" might be a bit of hyperbole: it would be comparable to any compile-time generator like Flex, Ragel, or a JIT generator like PCRE-sljit. And since D is a memory-safe language, I would expect the guards on buffer access to cause measurable overhead compared with C or C++ generated code.
  - eco 13y ago
    By that I meant it is in the same league as the fastest regular expression engines in the world. I should have worded that better. It comes out around the same performance as V8's and Boost Xpressive.
  - pjmlp 13y ago
    > And since D is a memory-safe language, I would expect the guards on buffer access to cause measurable overhead compared with C or C++ generated code. The typical C FUD being spread against memory safe languages since the early 80's. Most optimizing compilers are able to remove bounds checking if dataflow analysis can prove the code stays within bounds. For the cases where the compiler is not that smart, and the programmer has proven with help of profilers that bounds checking are indeed a problem, most compilers offer the possibility to disable bounds checking either at module or code region level. So one gets the memory safety by default, but if really really really required, it is still possible to rescue those extra ms. The thing is, in these languages one needs to ask permission to shot our foots off, instead of being able to do it in every code line.
andralex 13y ago
There's a fine line to walk between "Not Invented Here" and suffering through an inadequate tool. We at Facebook have a long history of trying stock tools and see them failing at our scale. Walter Bright puts out a good argument against lexer generators here: http://www.drdobbs.com/architecture-and-design/so-you-want-to-write-your-own-language/240165488 http://www.drdobbs.com/architecture-and-design/so-you-want-t.... Besides, tokenization is hardly the interesting/bulky part of the task. The verifications are.
- quotemstr 13y ago
  > Walter Bright puts out a good argument against lexer generators here: http://www.drdobbs.com/architecture-and-design/so-you-want-t... http://www.drdobbs.com/architecture-and-design/so-you-want-t.... I'm going to have to disagree with you and Walter. While I agree that for a fixed language, a well-written hand-built recursive descent parser will beat the pants off the output of a parser generator, languages aren't necessarily fixed and writing a good hand-build parser is harder than it seems. I still recommend that people start with parser generators. (Edit: yes, we're talking about lexers above, but the article mentions both lexers and parsers. I think the case for using a hand-built lexer is much weaker than the case for using a hand-built parser, not that I'm a fan of either.) If you use a parser generator, you can be sure that your language has a clear, (hopefully) LALR(1) syntax that anyone can understand and port to another parsing environment. If you hand-parse, then the temptation exists not only to introduce subtle irregularities and context dependencies into the language, but also to mix semantic interpretation and parse tree generation, and both of these anti-patterns make it difficult to build generic tools that work with your new language. With a hand parser, you also run the risk of making silly coding errors that end up being baked into your language specification. (Ahem, PHP.)
  - haberman 13y ago
    > While I agree that for a fixed language, a well-written hand-built recursive descent parser will beat the pants off the output of a parser generator I'm not sure this is true, do you have numbers that demonstrate this? I know that Clang knows some tricks that lexer generators don't currently know like using SSE to skip long blocks of comments. But even that, to me, represents an opportunity for better parsing tools, not an inherent performance advantage of hand-written parsers/lexers.
quotemstr 13y ago
By the way: I'm glad you mentioned Ragel. It's a fantastic dependency-free state machine generator that everyone should check out. http://www.complang.org/ragel/ http://www.complang.org/ragel/
- zackmorris 13y ago
  I just discovered Ragel also, and was wondering if you or anyone else might know of a tool that could convert a coroutine or generator to a state machine? I asked about it on stack overflow but so far no responses: http://stackoverflow.com/questions/21713904/convert-coroutine-to-finite-state-machine-fsm-and-vice-versa http://stackoverflow.com/questions/21713904/convert-coroutin...
tbirdz 13y ago
Well one problem could be that C++ does not have a context free grammar, and in fact its grammar is notoriously difficult to parse, so perhaps it's just as easy to write it by hand as it is to bend an existing parser generator to fit C++'s grammar? In fact, I am not aware of any modern C++ static analyzer or compiler that uses an automatic parser generator.
- riffraff 13y ago
  but this isn't a parser, it only tokenizes and then applies matching of rules against a stream of tokens. I.e. it doesn't need to know what C(X) means as long as it knows that it matches <ident,paropen,ident,parclose>. IIUC.
WalterBright 13y ago
Using third party lexer generators means your project is now dependent on that tool. This means: 1. the tool must exist on every platform your project will ever be ported to 2. the same version of that tool must exist on every such platform 3. if the hosted compiler changes, the tool must be updated in sync with that compiler - out of sync means your project won't build 4. if there are blocker bugs in the tool, you're not in a good position to fix it. You're stuck with developing workarounds. 5. Everyone building your project has to get the tool successfully installed. The current build of D's runtime library has a dependency on libcurl. Supposedly, since libcurl is ubiquitous, that shouldn't be any problem. But it has been an ongoing sore relentlessly sucking up multiple peoples' time, of the issues I outlined above.
- haberman 13y ago
  Your arguments seem to equally apply to using third-party libraries at all. Are you suggesting that it's better to (for example) re-implement HTTP rather than use libcurl?
  - WalterBright 13y ago
    I'm saying you've got to have pretty strong arguments to make a project dependent on a third party tool, if you expect to distribute it, expect it to be long lived, and expect to port it to many platforms.
    - haberman 13y ago
      Yes I agree with the point that the portability of your dependencies limits your own portability. This is definitely something that is dependent on the tool or library though. For example, if you decided to use Lua as a tool, it is extremely unlikely that the portability of Lua will be a limiting factor. It is very likely to be more portable than your code (given that it compiles unmodified on Turbo C 1.0 from 1990: http://www.youtube.com/watch?v=-jvLY5pUwic http://www.youtube.com/watch?v=-jvLY5pUwic) So I definitely agree with "choose your dependencies wisely."
CamperBob2 13y ago
Writing parsers is fun, and having done it several times, I know roughly how long it will take. Using a highly specialized tool has risks of its own: that I'll sink a lot of time into learning it, only to discover it isn't a good fit for what I want to do, and that I'll have to go through the whole learning curve again a few years from now because I don't write parsers very often and will have forgotten how the tool worked by then. Then there's the fun of debugging Other People's Code. Not to mention the way that open-source tools tend to drag in a godawful mess of dependencies, most of which they don't really even need. In my experience, I can write a basic recursive-descent parser from scratch in C++ before I can get a warning-free compile out of many open-source packages. So yes, there are reasons to roll your own parser. They may not be good reasons in your view, but don't shoot the messenger. (All of this being said, there's no way I'd try to bake a fully-compliant C++ language parser from scratch.)
herokusaki 13y ago
Ouch! This seems to apply to me. I've written lexers manually in the past but never bothered to learn a lexer generator properly. I guess I should. Would Flex, Ragel or something else be the best starting point? I have unpleasant memories of really cryptic error messages from the compiler when trying to get someone's toy project in Flex to work.
- eru 13y ago
  I recommend you start learning a Parser Combinator Library (like Parsec). These are nicer (especially to start out with). The downside is that not all programming languages are powerful enough to host these libraries---so you might have to fall back on a parser generator later, if you language of choice is not supported.
ithkuil 13y ago
> Everyone uses regexes; using a lexer generator should (in my opinion) be as easy as using a one-off regex. I think the key is to make the lexer generator an embeddable library like regex libraries are. Interesting read: http://commandcenter.blogspot.ie/2011/08/regular-expressions-in-lexing-and.html http://commandcenter.blogspot.ie/2011/08/regular-expressions...
alok-g 13y ago
Are there any studies available comparing development effort for the two approaches, using an existing tool vs. writing one's own? It is not obvious to me in how many percent cases the former is better. I have many a times used an existing tool and after getting the thing to work, have come out with a feeling that it may have been easier to do it myself. I used Flex in a compilers course on Coursera, and getting the lexer to match the specifications took about full two days, which sounded too much for the specifications at hand in the assignment. I have written a CFG parser from scratch in less time (not to say that these two tasks are comparable from development effort point of view).

p0nce 13y ago

See my comment here https://news.ycombinator.com/item?id=7293796 https://news.ycombinator.com/item?id=7293796, to make anyone able to add a company-specific check quickly is a valuable asset (to ensure decisions like "We don't want to use idiom X anymore"). Moreover, fake parsers like cppcheck will lint your code even if the code does not even build, so they are really easy to setup.

eco 13y ago

> Everyone uses regexes; using a lexer generator should (in my opinion) be as easy as using a one-off regex. I think the key is to make the lexer generator an embeddable library like regex libraries are. There actually is a really powerful parser generator for D by Philippe Sigaud: https://github.com/PhilippeSigaud/Pegged https://github.com/PhilippeSigaud/Pegged It's much more pleasant to use than something like Boost Spirit. Somewhat relatedly, D's standard library has a compile time regex engine that compiles regular expressions down at compile-time resulting in some of the fastest regular expressions in the world.

haberman 13y ago
That's cool, though "some of the fastest regular expressions in the world" might be a bit of hyperbole: it would be comparable to any compile-time generator like Flex, Ragel, or a JIT generator like PCRE-sljit. And since D is a memory-safe language, I would expect the guards on buffer access to cause measurable overhead compared with C or C++ generated code.
- eco 13y ago
  By that I meant it is in the same league as the fastest regular expression engines in the world. I should have worded that better. It comes out around the same performance as V8's and Boost Xpressive.
- pjmlp 13y ago
  > And since D is a memory-safe language, I would expect the guards on buffer access to cause measurable overhead compared with C or C++ generated code. The typical C FUD being spread against memory safe languages since the early 80's. Most optimizing compilers are able to remove bounds checking if dataflow analysis can prove the code stays within bounds. For the cases where the compiler is not that smart, and the programmer has proven with help of profilers that bounds checking are indeed a problem, most compilers offer the possibility to disable bounds checking either at module or code region level. So one gets the memory safety by default, but if really really really required, it is still possible to rescue those extra ms. The thing is, in these languages one needs to ask permission to shot our foots off, instead of being able to do it in every code line.

andralex 13y ago

There's a fine line to walk between "Not Invented Here" and suffering through an inadequate tool. We at Facebook have a long history of trying stock tools and see them failing at our scale. Walter Bright puts out a good argument against lexer generators here: http://www.drdobbs.com/architecture-and-design/so-you-want-to-write-your-own-language/240165488 http://www.drdobbs.com/architecture-and-design/so-you-want-t.... Besides, tokenization is hardly the interesting/bulky part of the task. The verifications are.

quotemstr 13y ago
> Walter Bright puts out a good argument against lexer generators here: http://www.drdobbs.com/architecture-and-design/so-you-want-t... http://www.drdobbs.com/architecture-and-design/so-you-want-t.... I'm going to have to disagree with you and Walter. While I agree that for a fixed language, a well-written hand-built recursive descent parser will beat the pants off the output of a parser generator, languages aren't necessarily fixed and writing a good hand-build parser is harder than it seems. I still recommend that people start with parser generators. (Edit: yes, we're talking about lexers above, but the article mentions both lexers and parsers. I think the case for using a hand-built lexer is much weaker than the case for using a hand-built parser, not that I'm a fan of either.) If you use a parser generator, you can be sure that your language has a clear, (hopefully) LALR(1) syntax that anyone can understand and port to another parsing environment. If you hand-parse, then the temptation exists not only to introduce subtle irregularities and context dependencies into the language, but also to mix semantic interpretation and parse tree generation, and both of these anti-patterns make it difficult to build generic tools that work with your new language. With a hand parser, you also run the risk of making silly coding errors that end up being baked into your language specification. (Ahem, PHP.)
- haberman 13y ago
  > While I agree that for a fixed language, a well-written hand-built recursive descent parser will beat the pants off the output of a parser generator I'm not sure this is true, do you have numbers that demonstrate this? I know that Clang knows some tricks that lexer generators don't currently know like using SSE to skip long blocks of comments. But even that, to me, represents an opportunity for better parsing tools, not an inherent performance advantage of hand-written parsers/lexers.

quotemstr 13y ago

By the way: I'm glad you mentioned Ragel. It's a fantastic dependency-free state machine generator that everyone should check out. http://www.complang.org/ragel/ http://www.complang.org/ragel/

zackmorris 13y ago
I just discovered Ragel also, and was wondering if you or anyone else might know of a tool that could convert a coroutine or generator to a state machine? I asked about it on stack overflow but so far no responses: http://stackoverflow.com/questions/21713904/convert-coroutine-to-finite-state-machine-fsm-and-vice-versa http://stackoverflow.com/questions/21713904/convert-coroutin...

tbirdz 13y ago

Well one problem could be that C++ does not have a context free grammar, and in fact its grammar is notoriously difficult to parse, so perhaps it's just as easy to write it by hand as it is to bend an existing parser generator to fit C++'s grammar? In fact, I am not aware of any modern C++ static analyzer or compiler that uses an automatic parser generator.

riffraff 13y ago
but this isn't a parser, it only tokenizes and then applies matching of rules against a stream of tokens. I.e. it doesn't need to know what C(X) means as long as it knows that it matches <ident,paropen,ident,parclose>. IIUC.

WalterBright 13y ago

Using third party lexer generators means your project is now dependent on that tool. This means: 1. the tool must exist on every platform your project will ever be ported to 2. the same version of that tool must exist on every such platform 3. if the hosted compiler changes, the tool must be updated in sync with that compiler - out of sync means your project won't build 4. if there are blocker bugs in the tool, you're not in a good position to fix it. You're stuck with developing workarounds. 5. Everyone building your project has to get the tool successfully installed. The current build of D's runtime library has a dependency on libcurl. Supposedly, since libcurl is ubiquitous, that shouldn't be any problem. But it has been an ongoing sore relentlessly sucking up multiple peoples' time, of the issues I outlined above.

haberman 13y ago
Your arguments seem to equally apply to using third-party libraries at all. Are you suggesting that it's better to (for example) re-implement HTTP rather than use libcurl?
- WalterBright 13y ago
  I'm saying you've got to have pretty strong arguments to make a project dependent on a third party tool, if you expect to distribute it, expect it to be long lived, and expect to port it to many platforms.
  - haberman 13y ago
    Yes I agree with the point that the portability of your dependencies limits your own portability. This is definitely something that is dependent on the tool or library though. For example, if you decided to use Lua as a tool, it is extremely unlikely that the portability of Lua will be a limiting factor. It is very likely to be more portable than your code (given that it compiles unmodified on Turbo C 1.0 from 1990: http://www.youtube.com/watch?v=-jvLY5pUwic http://www.youtube.com/watch?v=-jvLY5pUwic) So I definitely agree with "choose your dependencies wisely."

CamperBob2 13y ago

Writing parsers is fun, and having done it several times, I know roughly how long it will take. Using a highly specialized tool has risks of its own: that I'll sink a lot of time into learning it, only to discover it isn't a good fit for what I want to do, and that I'll have to go through the whole learning curve again a few years from now because I don't write parsers very often and will have forgotten how the tool worked by then. Then there's the fun of debugging Other People's Code. Not to mention the way that open-source tools tend to drag in a godawful mess of dependencies, most of which they don't really even need. In my experience, I can write a basic recursive-descent parser from scratch in C++ before I can get a warning-free compile out of many open-source packages. So yes, there are reasons to roll your own parser. They may not be good reasons in your view, but don't shoot the messenger. (All of this being said, there's no way I'd try to bake a fully-compliant C++ language parser from scratch.)

herokusaki 13y ago

Ouch! This seems to apply to me. I've written lexers manually in the past but never bothered to learn a lexer generator properly. I guess I should. Would Flex, Ragel or something else be the best starting point? I have unpleasant memories of really cryptic error messages from the compiler when trying to get someone's toy project in Flex to work.

eru 13y ago
I recommend you start learning a Parser Combinator Library (like Parsec). These are nicer (especially to start out with). The downside is that not all programming languages are powerful enough to host these libraries---so you might have to fall back on a parser generator later, if you language of choice is not supported.

ithkuil 13y ago

> Everyone uses regexes; using a lexer generator should (in my opinion) be as easy as using a one-off regex. I think the key is to make the lexer generator an embeddable library like regex libraries are. Interesting read: http://commandcenter.blogspot.ie/2011/08/regular-expressions-in-lexing-and.html http://commandcenter.blogspot.ie/2011/08/regular-expressions...

alok-g 13y ago

Are there any studies available comparing development effort for the two approaches, using an existing tool vs. writing one's own? It is not obvious to me in how many percent cases the former is better. I have many a times used an existing tool and after getting the thing to work, have come out with a feeling that it may have been easier to do it myself. I used Flex in a compilers course on Coursera, and getting the lexer to match the specifications took about full two days, which sounded too much for the specifications at hand in the assignment. I have written a CFG parser from scratch in less time (not to say that these two tasks are comparable from development effort point of view).