What specific advantages and disadvantages of each way to working on a programming language grammar?
Why/When should I roll my own? Why/When should I use a generator?
There are three options really, all three of them preferable in different situations.
Option 1: parser generators, or 'you need to parse some language and you just want to get it working, dammit'
Say, you're asked to build a parser for some ancient data format NOW. Or you need your parser to be fast. Or you need your parser to be easily maintainable.
In these cases, you're probably best off using a parser generator. You don't have to fiddle around with the details, you don't have to get lots of complicated code to work properly, you just write out the grammar the input will adhere to, write some handling code and presto: instant parser.
The advantages are clear:
There's one thing you have to be careful of with parser-generators: the can sometimes reject your grammars. For an overview of the different types of parsers and how they can bite you, you may want to start here. Here you can find an overview of a lot of implementations and the types of grammars they accept.
Option 2: hand-written parsers, or 'you want to build your own parser, and you care about being user-friendly'
Parser generators are nice, but they aren't very user (the end-user, not you) friendly. You typically can't give good error messages, nor can you provide error recovery. Perhaps your language is very weird and parsers reject your grammar or you need more control than the generator gives you.
In these cases, using a hand-written recursive-descent parser is probably the best. While getting it right may be complicated, you have complete control over your parser so you can do all kinds of nice stuff you can't do with parser generators, like error messages and even error recovery (try removing all the semicolons from a C# file: the C# compiler will complain, but will detect most other errors anyway regardless of the presence of semicolons).
Hand-written parsers also usually perform better than generated ones, assuming the quality of the parser is high enough. On the other hand, if you don't manage to write a good parser - usually due to (a combination of) lack of experience, knowledge or design - then performance is usually slower. For lexers the opposite is true though: generally generated lexers use table lookups, making them faster than (most) hand-written ones.
Education-wise, writing your own parser will teach you more than using a generator. You have to write more and more complicated code after all, plus you have to understand exactly how you parse a language. On the other hand, if you want to learn how to create your own language (so, get experience at language design), either option 1 or option 3 is preferable: if you're developing a language, it will probably change a lot, and option 1 and 3 give you an easier time with that.
Option 3: hand written parser generators, or 'you're trying to learn a lot from this project and you wouldn't mind ending up with a nifty piece of code you can re-use a lot'
This is the path I'm currently walking down: you write your own parser generator. While highly nontrivial, doing this will probably teach you the most.
To give you an idea what doing a project like this involves I'll tell you about my own progress.
The lexer generator
I created my own lexer generator first. I usually design software starting with how the code will be used, so I thought about how I wanted to be able to use my code and wrote this piece of code (it's in C#):
The input string-token pairs are converted into a corresponding recursive structure describing the regular expressions they represent using the ideas of an arithmetic stack. This is then converted into a NFA (nondeterministic finite automaton), which is in turn converted into a DFA (deterministic finite automaton). You can then match strings against the DFA.
This way, you get a good idea how exactly lexers work. In addition, if you do it the right way the results from your lexer generator can be roughly as fast as professional implementations. You also don't lose any expressiveness compared to option 2, and not much expressiveness compared to option 1.
I implemented my lexer generator in just over 1600 lines of code. This code makes the above work, but it still generates the lexer on the fly every time you start the program: I'm going to add code to write it to disk at some point.
If you want to know how to write your own lexer, this is a good place to start.
The parser generator
You then write your parser generator. I refer to here again for an overview on the different kinds of parsers - as a rule of thumb, the more they can parse, the slower they are.
Speed not being an issue for me, I chose to implement an Earley parser. Advanced implementations of an Earley parser have been shown to be about twice as slow as other parser types.
In return for that speed hit, you get the ability to parse any kind of grammar, even ambiguous ones. This means you never need to worry about whether your parser has any left-recursion in it, or what a shift-reduce conflict is. You can also define grammars more easily using ambiguous grammars if it doesn't matter which parse tree is the result, such as that it doesn't matter whether you parse 1+2+3 as (1+2)+3 or as 1+(2+3).
This is what a piece of code using my parser generator can look like:
(Note that IntWrapper is simply an Int32, except that C# requires it to be a class, hence I had to introduce a wrapper class)
I hope you see that the code above is very powerful: any grammar you can come up with can be parsed. You can add arbitrary bits of code in the grammar capable of performing lots of tasks. If you manage to get this all working, you can re-use the resulting code to do a lot of tasks very easily: just imagine building a command-line interpreter using this piece of code.
If you have never, ever written a parser I would recommend you do it. It is fun, and you learn how things work, and you learn to appreciate the effort that parser and lexer generators save you from doing the next time you need a parser.
I would also suggest you try reading http://compilers.iecc.com/crenshaw/ as it has a very down-to-earth attitude towards how to do it.
The advantage of writing your own recursive descent parser is that you can generate high-quality error messages on syntax errors. Using parser generators, you can make error productions and add custom error messages at certain points, but parser generators just don't match the power of having complete control over the parsing.
Another advantage of writing your own is that it is easier to parse to a simpler representation that doesn't have a one to one correspondence to your grammar.
If your grammar is fixed, and error messages are important, consider rolling your own, or at least using a parser generator that gives you the error messages you need. If your grammar is constantly changing, you should consider using parser generators instead.
Bjarne Stroustrup talks about how he used YACC for the first implementation of C++ (see The Design and Evolution of C++). In that first case, he wished he wrote his own recursive descent parser instead!
Option 3: Neither (Roll your own parser generator)
Identify why all these tools are not good enough - why don't they let you achieve your goal?
Unless you're certain that the oddities in the grammar you're dealing with are unique, you shouldn't just create a single custom parser+lexer for it. Instead, create a tool that will create what you want, but can also be used to fulfil future needs, then release it as Free Software to prevent other people having the same problem as you.
Rolling your own parser forces you to think directly about the complexity of your language. If the language is hard to parse, it is probably going to be hard to understand.
There was a lot of interest in parser generators in the early days, motivated by highly-complicated (some would say "tortured") language syntax. JOVIAL was a particularly-bad example: it required two symbol lookahead, at a time when everything else required at most one symbol. This made generating the parser for a JOVIAL compiler more difficult than expected (as General Dynamics / Fort Worth Division learned the hard way when they procured JOVIAL compilers for the F-16 program).
Today, recursive descent is universally the preferred method, because it is easier for compiler writers. Recursive descent compilers strongly reward simple, clean language design, in that it is a lot easier to write a recursive-descent parser for a simple, clean language than for a convoluted, messy one.
Finally: Have you considered embedding your language in LISP, and letting a LISP interpreter do the heavy lifting for you? AutoCAD did that, and found it made their life a lot easier. There are quite a few lightweight LISP interpreters out there, some embeddable.
I've written a parser for commercial application once and I used yacc. There was a competing prototype where a developer wrote the whole thing by hand in C++ and it worked about five times slower.
As for the lexer for this parser, I wrote it entirely by hand. It took -- sorry, it was almost 10 years ago, so I don't remember it precisely -- about 1000 lines in C.
The reason why I wrote the lexer by hand was the parser's input grammar. It was a requirement, something my parser implementation had to comply with, as opposed to something I designed. (Of course I would have designed it differently. And better!) The grammar was severely context-dependent and even lexing depended on semantics in some places. For example a semicolon could be part of a token in one place, but a separator in a different place -- based on a semantical interpretation of some element that was parsed out before. So, I "buried" such semantical dependencies in the hand-written lexer and that left me with a fairly straightforward BNF that was easy to implement in yacc.
ADDED in response to Macneil: yacc provides a very powerful abstraction that lets the programmer think in terms of terminals, non-terminals, productions and stuff like that. Also, when implementing
ALSO WANT TO ADD: this is not a recipe for writing parsers in general, just an example of how it worked in one particular situation.
That depends entirely on what you need to parse. Can you roll your own faster than you could hit the learning curve of a lexer? Is the stuff to be parsed static enough that you won't regret the decision later? Do you find existing implementations overly complex? If so, have fun rolling your own, but only if you aren't ducking a learning curve.
Lately, I've come to really like the lemon parser, which is arguably the simplest and easiest that I've ever used. For the sake of making things easy to maintain, I just use that for most needs. SQLite uses it as well as some other notable projects.
But, I'm not at all interested in lexers, beyond them not getting in my way when I need to use one (hence, lemon). You might be, and if so, why not make one? I have a feeling you'll come back to using one that exists, but scratch the itch if you must :)
Have you considered Martin Fowlers language workbench approach? Quoting from the article
Reading that, I would say that the days of writing your own parser are over and it's better to use one of the libraries that are available. Once you've mastered the library then all DSLs that you create in the future benefit from that knowledge. Also, others don't have to learn your approach to parsing.
Edit to cover comment (and revised question)
Advantages of rolling your own
So in short, you should roll your own when you want to really hack deep into the bowels of a seriously difficult problem that you feel strongly motivated to master.
Advantages of using someone else's library
Therefore, if you want a quick end result use someone else's library.
Overall, this comes down to a choice of how much you want to own the problem, and thus the solution. If you want it all then roll your own.
It depends on what your goal is.
Are you trying to learn how parsers/compilers work? Then write your own from scratch. Thats the only way you'd really learn to appreciate all the ins and outs of what they are doing. I've been writing one the past couple months, and its been an interesting and valuable experience, escpecially the 'ah, so thats why language X does this...' moments.
Do you need to put something together quickly for an application on a deadline? Then perhaps use a parser tool.
Do you need something that you'll want to expand upon over the next 10, 20, maybe even 30 years? Write your own, and take your time. It'll be well worth it.
The big advantage to writing your own is that you'll know how to write your own. The big advantage to using a tool like yacc is that you'll know how to use the tool. I'm a fan of treetop for initial exploration.
Why not fork an open-source parser generator and make it your own? If you don't use parser generators, you code will be very hard to maintain, if you made big changes the syntax of your language.
In my parsers, I used regular expressions (I mean, Perl-style) to tokenize, and use some convenience functions to increase code readability. However, a parser-generated code can be faster by making state tables and long
Here are two example of my custom-written parsers:
https://github.com/SHiNKiROU/DesignScript - a BASIC dialect, because I was too lazy to write lookaheads in array notation, I sacrificed error message quality https://github.com/SHiNKiROU/ExprParser - A formula calculator. Notice the weird metaprogramming tricks