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.
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...
I definitely don't think there's anything wrong with using them, but my experience has been more pleasurable without in general. I'm also not entirely sure you can ever really understand the benefits of using a CC, or the reasons they impose the limitations they do, if you've never even attempted to go without one. And I think that when you're first learning about parsing you'll probably be learning more at a faster pace doing it yourself than trying to learn your way around the rather frustrating tooling built around CCs.
I guess if I'm trying to be more clear I'm glad to see this perspective expressed, since it's a relatively rare one to see expressed authoritatively. There are a few topics in parsing that I don't think get enough discussion.
Like, my pet peeve is people thinking a naive implementation of the packrat parser is guaranteed to perform better than a plain recursive descent parser. In reality you might just be trading explosive memory growth for algorithmic steps. In a lot of cases that's actually slower.
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.
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.
The argument for lexers has nothing to do with machine instructions: it has to do with algorithmic performance. Grammars tend to have time complexity that is greater than linear with a moderate constant (and a parser combinator library, which is really just a lightweight programming abstraction making it easier to develop by-hand recursive descent parsers, normally doesn't try to help with this problem), whereas a good lexer tends to have linear time complexity with a nearly zero constant. If you can separate your compilation phase into "first run a lexer, then run a grammar", you can parse much longer files (not just constantly longer, but asymptotically longer) in the same amount of time. There is no fundamental reason to separate these phases, however, and it has minimal effect on the resulting compiler: numerous compilers, even numerous compiler generators, have these phases combined into a single grammar step, with the tokens now being effectively characters. (There are also engines that try to slide between the two levels, using an algorithm more similar to a lexer at the base of your grammar, but still letting you define these psuedo-tokens in the unified grammar as rules.)
I've personally found that even when working with parser generators or handwritten parsers that don't need the separation it still helps to consider them separate. Having a stable and solid set of fundamental tokens makes the resulting language easier to understand. Whenever I see a language (usually made with a PEG generator) that blurs these lines everything feels very shifty. Yes I know these are very touchy-feely attributes I'm describing, and you can obviously avoid them without that separation as well, but these things are important as well.
It's an interesting accident, to me at least, that this separation turned out to be both optimal and useful.
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.
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".)
Lexing is such a small part of compilation overhead that not being optimal isn't going to kill you. In my case, writing the elder by hand is necessary because I have to memoize token identities (and all the parsing/typing info attached).
Yes, I write my own hash tables also for the same reason (so they support incremental computations).
> Lexing is such a small part of compilation overhead that not being optimal isn't going to kill you.
You still then need to just the extra boilerplate per element. If you use a tool, you are literally looking at just "keyword <space> code when that keyword is pressed" without any surrounding "how to check if it is that keyword". This is easier to write and easier to maintain, in addition to the advantages I discussed earlier.
> In my case, writing the elder by hand is necessary because I have to memoize token identities (and all the parsing/typing info attached).
If I understand what you mean, then this is trivially done with most existing tools as part of your token rule (retired an interned string, which you can use an existing data structure for). If not, then you would first write a tool. Again: it may feel really "hard core" to write a lexer, but it is repetitive code that a good design factors out into a lexer generator.
> Yes, I write my own hash tables also for the same reason (so they support incremental computations).
Careful: I imagine you mean to say you write your own hash table library/compiler, which is different from laying out the hashtable by hand. I have also written my own hashtable for many reasons, but I would never sit down with an array literal and manually put the entries in there by hand: even if I don't make any mistakes, it is a pointless waste of my time that is trivially automatable using a computer.
Keywords are quite easy: just plug your identifiers into the hash table after their boundaries are detected. Again, it is much more expensive than generating a FSM, but the expense is really in the noise when everything else is considered.
As for incremental lexing, you need to tell if your tokens pre-existed as the same kind (not necessarily the same string!) before the edit or not. It would be trivial to add this to a generator, but how would it then feedback the signals needed to take advantage of the memoization (e.g. by providing a persistent token ID that can unlock pre-existing information about the token). There are simply no standards for that.
In most of the professionally written compilers (e.g. scalac) I've worked on, lexer and parser generators aren't even used, and it really isn't that big of a deal to write these in code; you also get the benefit that the same language is being used. This becomes especially true when IDE services are considered, whereas most generators are pretty much limited to batch applications.
> I have also written my own hashtable for many reasons, but I would never sit down with an array literal and manually put the entries in there by hand: even if I don't make any mistakes, it is a pointless waste of my time that is trivially automatable using a computer.
I see your point, but it really depends on the key space you are optimizing for. You might just put the elements in by hand if a generic algorithm isn't really called for.
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.
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 was created much easier to understand than other media/literature available online on the same subject. Hence my appreciation of his work. :)
> 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.
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.
