The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
Fog Creek Copilot

The Old Forum

Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

Lex/Yacc book recommendation?

Hi all,

I'd like to get a deeper understanding of Lex and Yacc, how they really work, as opposed to my own terrible user model.

I'd prefer a short book, but if the best has to be a tome, then I'll be fine with that too. (If you could point out the central chapters I'll be very thankful)

So do you have a good one on your shelf you'd like to recommend to me?

Thanks in advance
Peter Monsson Send private email
Friday, February 17, 2006
Allen Holub's 'Compiler design in C' fully describes & implements lex & yacc clones from scratch, and uses them to build a compiler.

Kind of thick, but I don't think the author is to blame - the subject matter is not simple.
J Send private email
Friday, February 17, 2006
John Levine's book from O'Reilly Associates:
George Jansen Send private email
Friday, February 17, 2006
I agree that Allen Holub's book is good.  Unfortunately, the errata is also book-length. :(
Friday, February 17, 2006
Why Lex/Yacc?

They're quite long in the tooth.  And plain lex/yacc aren't OO (some variants are, as an extension).

But then again, I've yet to find a parser generator that I really like...
David Jones Send private email
Friday, February 17, 2006

If you want to know how Lex/Flex and Yacc/Bison actually do their stuff internally, as opposed to reading the user manuals, I'd recommend looking through:-

Lex / Flex: chapter 3 of "Compilers: Principles , Techniques and Tools" (Aho, Sethi, Ullman) - the Dragon Book.

Yacc/Bison: a bit more difficult, this one. To understand LR parsing techniques in general, I wouldn't recommend the Dragon book for a first reading. You could look at Chapters 4 to 6  of "Crafting a Compiler (Fischer, LeBlanc)" first and go back to the Dragon book. An alternative would be to plough through chapter 2 of "Modern Compiler Design (Grune, Bal, Jacobs, Langendoen).

Both of these last two books also cover lexical analysis quite well - it's quite interesting to read Modern Compiler Design's approach to lexical analysis after reading the Dragon book, and come to think of it, it  makes the understanding of LR parsing a bit easier too.

Either way, once you've understood LR(1) and specifically LALR(1) parsing, have a look through the Bison manual, if you haven't already done so: the blurb on error productions should make more sense.

If you want to understand Yacc's mid-action rules, go back to chapter 5 of the Dragon book and read about the simulation of inherited attributes in bottom-up parsing.

Have fun!
Friday, February 17, 2006
I'd also recommend Levine's book for Lex/Yacc (or Flex/Bison). That's what I used to get started, and it worked well. I'm using flex/bison now and like them fine.

But still, if I were starting fresh, I'd think about using something other than Lex/Yacc. I'd suggest looking at some of the more recent options and see which one looks good to you.

It depends on the language you want to use.
EKB Send private email
Friday, February 17, 2006
Well, it wasn't what I hoped for, but thanks for your help anyway. I'll take a run to the store to see what they've got there.

Best Regards
Peter Monsson Send private email
Wednesday, February 22, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz