3 ms·

Parser generators are an interesting academic exercise, but in practice it seems most language implementers have concluded that hand coding a recursive descent

Parser generators are an interesting academic exercise, but in practice it seems most language implementers have concluded that hand coding a recursive descent parser is the way to go: GCC being a prime example as the author mentions. I'd be interested to know if Coverity is still using McPeeks elsa/elkhound glr parser generator from years ago. As antlr creator Terence Parr says "Why Program by Hand in Five Days what You Can Spend Five Years of Your Life Automating?" It really is almost trivial to implement recursive descent by hand.

chubot 12y ago
You're drawing the wrong conclusion from that evidence. Parser generators aren't an "academic exercise"; they are a practical and useful tool for designing languages. You want a compact notation to describe the syntax of a new language, from which code can be generated. Once the design has settled, however, then there are engineering advantages to using a hand-written parser. That is why you see GCC moving to a hand-written parser. Lua followed the same evolution -- using Yacc at first, and now a hand-written parser. This is discussed in one of the Lua history papers. To see evidence of this, look at how many crappy proprietary DSLs exist at various companies (I've worked at EA and Google and can name examples from each). Many of them use ad hoc parsers and would have been better off starting with a parser generator.
- aredridel 12y ago
  Indeed -- and we now end up with LL languages, which are a pretty weak grammar class. We spend a lot of time binding our minds to computer languages than computers to understand something more powerful.
- marktangotango 12y ago
  Good points, although I'd point out that parser generator! = E/BNF and code generation is optional since translating E/BNF manually is straight forward.
- vorg 12y ago
  > Parser generators [...] are a practical and useful tool for designing languages. You want a compact notation to describe the syntax of a new language, from which code can be generated. I'm not sure the notation is always that compact, see... http://svn.codehaus.org/groovy/trunk/groovy/groovy-core/src/main/org/codehaus/groovy/antlr/groovy.g http://svn.codehaus.org/groovy/trunk/groovy/groovy-core/src/...
  - chubot 12y ago
    The fact that this file is long doesn't say much about parser generators. There are two components there: recognition (the grammar), and the "actions", i.e. embedded Java code. The embedded Java isn't going to get any shorter if you write it out (it's already "written out"). And the recognition part is definitely shorter with the grammar. ANTLR perhaps has a mode where it will output only the grammar in a compact form. In any case, it's an implementation detail. It's perfectly possible to write a parser generator where recognition is in a separate file from the actions. But yes this is sort of an annoyance of mine and one of the reasons I wrote my own :)
agumonkey 12y ago
Someone needs to merge MetaObjectProtocol and Parser generators ideas together.
- uaygsfdbzf 12y ago
  Done and done. See headlines "Meta-Object Programming" and "Grammars" in <http://perl6.org/compilers/features> http://perl6.org/compilers/features>.
alexchamberlain 12y ago
I think Parser Generators don't have a good name as they often generate code that isn't currently fashionable, but was quite reasonable at a time. Take Lex/Yacc: global variables are now bad practice, not to mention testable interfaces.
Terr_ 12y ago
> As antlr creator Terence Parr says "Why Program by Hand in Five Days what You Can Spend Five Years of Your Life Automating?" Uh, yes, and in the rest of the talk he answers why automation is good. You didn't just stop at the title, did you?

chubot 12y ago

You're drawing the wrong conclusion from that evidence. Parser generators aren't an "academic exercise"; they are a practical and useful tool for designing languages. You want a compact notation to describe the syntax of a new language, from which code can be generated. Once the design has settled, however, then there are engineering advantages to using a hand-written parser. That is why you see GCC moving to a hand-written parser. Lua followed the same evolution -- using Yacc at first, and now a hand-written parser. This is discussed in one of the Lua history papers. To see evidence of this, look at how many crappy proprietary DSLs exist at various companies (I've worked at EA and Google and can name examples from each). Many of them use ad hoc parsers and would have been better off starting with a parser generator.

aredridel 12y ago
Indeed -- and we now end up with LL languages, which are a pretty weak grammar class. We spend a lot of time binding our minds to computer languages than computers to understand something more powerful.
marktangotango 12y ago
Good points, although I'd point out that parser generator! = E/BNF and code generation is optional since translating E/BNF manually is straight forward.
vorg 12y ago
> Parser generators [...] are a practical and useful tool for designing languages. You want a compact notation to describe the syntax of a new language, from which code can be generated. I'm not sure the notation is always that compact, see... http://svn.codehaus.org/groovy/trunk/groovy/groovy-core/src/main/org/codehaus/groovy/antlr/groovy.g http://svn.codehaus.org/groovy/trunk/groovy/groovy-core/src/...
- chubot 12y ago
  The fact that this file is long doesn't say much about parser generators. There are two components there: recognition (the grammar), and the "actions", i.e. embedded Java code. The embedded Java isn't going to get any shorter if you write it out (it's already "written out"). And the recognition part is definitely shorter with the grammar. ANTLR perhaps has a mode where it will output only the grammar in a compact form. In any case, it's an implementation detail. It's perfectly possible to write a parser generator where recognition is in a separate file from the actions. But yes this is sort of an annoyance of mine and one of the reasons I wrote my own :)

agumonkey 12y ago

Someone needs to merge MetaObjectProtocol and Parser generators ideas together.

uaygsfdbzf 12y ago
Done and done. See headlines "Meta-Object Programming" and "Grammars" in <http://perl6.org/compilers/features> http://perl6.org/compilers/features>.

alexchamberlain 12y ago

I think Parser Generators don't have a good name as they often generate code that isn't currently fashionable, but was quite reasonable at a time. Take Lex/Yacc: global variables are now bad practice, not to mention testable interfaces.

Terr_ 12y ago

> As antlr creator Terence Parr says "Why Program by Hand in Five Days what You Can Spend Five Years of Your Life Automating?" Uh, yes, and in the rest of the talk he answers why automation is good. You didn't just stop at the title, did you?