flex & bison

Chapter 9. Advanced Flex and Bison

Bison was originally a version of yacc, the original Unix parser generator that generated LALR parsers in C. In recent years it’s grown a lot of new features. We discuss some of the most useful ones here.

Pure Scanners and Parsers

A flex scanner and bison parser built in the usual way is not reentrant and can parse only one input stream at a time. That’s because both the scanner and the parser use static data structures to keep track of what they’re doing and to communicate with each other and with the calling program. Both flex and bison can create “pure” reentrant code, which replaces the static data structures with one passed as an argument to each routine in the scanner and parser. This both allows recursive calls to the scanner and parser, which is occasionally useful, and allows scanners and parsers to be used in multithreaded programs where there may be several parses going on at once in different threads.

As a demonstration, we’ll take the calculator from Chapter 3 and modify it to use a pure scanner and parser. Rather than having the parser execute each line of code immediately, it’ll return the AST to the caller. As is usual in reentrant programs, the calling routine allocates a structure with space for the per-instance data and passes it along in each call to the scanner and parser.

Unfortunately, as of the time this book went to press (mid-2009), the code for flex pure scanners and yacc pure scanners is a mess. Bison’s calling sequence ...