Implementing re-entrant parsers in Bison and Flex

In days of yore, Yacc and Lex were two of the most useful tools in a Unix hacker’s kit. The way they interfaced to client code was, however, pretty ugly – global variables and magic macros hanging out all over the place. Their modern descendants, Bison and Flex, have preserved that ugliness in order to be backward-compatible.

That rebarbative old interface generally broke a lot of rules about program structure and information hiding that we now accept as givens (to be fair, most of those had barely been invented at the time it was written in 1970 and were still pretty novel). It becomes a particular problem if you want to run multiple instances of your generated parser (or, heaven forfend, multiple parsers with different grammars) in the same binary without having them interfere with each other.

But it can be done. I’m going to describe how because (a) it’s difficult to extract from the documentation, and (b) right now (that is, using Bison 3.0.2 and Flex 2.5.35) the interface is in fact slightly broken and there’s a workaround you need to know.

First, motivation. I had to figure out how to do this for cvs-fast-export, which contains a Bison/Flex grammar that parses CVS master files – often thousands of them in a single run. In the never-ending quest for faster performance (because there are some very old, very gnarly, and very large CVS repositories out there that we would nevertheless like to be able to convert without grinding at them for days or weeks) I have recently been trying to parallelize the parsing stage. The goal is to (a) to be able to spread the job across multiple processors so the work gets done faster, and (b) not to allow I/O waits for some masters being parsed to block compute-intensive operations on others.

In order to make this happen, cvs-fast-export has to manage a bunch of worker threads with a parser instance inside each one. And in order for that to work, the yyparse() and yylex() driver functions in the generated code have to be reentrant. No globals allowed; they have to keep their parsing and lexing state in purely stack- and thread-local storage, and deliver their results back the way ordinary reentrant C functions would do it (that is, through structures referenced by pointer arguments).

Stock Yacc and Lex couldn’t do this. A very long time ago I wrote a workaround – a tool that would hack the code they generated to encapsulate it. That hack is obsolete because (a) nobody uses those heirloom versions any more, and (b) Bison/Flex have built-in support for this. If you read the docs carefully. And it’s partly broken.

Here’s how you start. In your Bison grammar, you need to include include something that begins with these options:

%define api.pure full
%lex-param {yyscan_t scanner}
%parse-param {yyscan_t scanner}

Here, yyscan_t is (in effect) a special private structure used to hold your scanner state. (That’s a slight fib, which I’ll rectify later; it will do for now.)

And your Flex specification must contain these options:

%option reentrant bison-bridge

These are the basics required to make your parser re-entrant. The signatures of the parser and lexer driver functions change from yyparse() and yylex() (no arguments) to these:

yyparse(yyscan_t *scanner)
yylex(YYSTYPE *yylval_param, yyscan_t yyscanner)

A yyscan_t is a private structure used to hold your scanner state; yylval is where yylex() will put its token value when it’s called by yyparse().

You may be puzzled by the fact that the %lex-param declaration says ‘scanner’ but the scanner state argument ends up being ‘yyscanner’. That’s reasonable, I’m a bit puzzled by it myself. In the generated scanner code, if there is a scanner-state argument (forced by %reentrant) it is always the first one and it is always named yyscanner regardless of what the first %lex-param declaration says – that first declaration seems to be a placeholder. In contrast, the first argument name in the %parse-params declaration actually gets used as is.

You must call yyparse() like this:

    yyscan_t myscanner;

    yylex_init(&myscanner);
    yyparse(myscanner);
    yylex_destroy(myscanner);

The yyinit() function call sets scanner to hold the address of a private malloced block holding scanner state; that’s why you have to destroy it explicitly.

The old-style global variables, like yyin, become macros that reference members of the yyscan_t structure; for a more modern look you can use accessor functions instead. For yyin that is the pair yyget_in() and yyset_in().

I hear your question coming. “But, Eric! How do I pass stuff out of the parser?” Good question. My Bison declarations actually look like this:

%define api.pure full
%lex-param {yyscan_t scanner} {cvs_file *cvsfile}
%parse-param {yyscan_t scanner} {cvs_file *cvsfile}

Notice there’s an additional argument. This should change the function signatures to look like this:

yyparse(yyscan_t scanner, cvs_file *cvs)
yylex(YYSTYPE *yylval_param, yyscan_t yyscanner, cvs_file *cvs)

Now you will call yyparse() like this:

    yyscan_t myscanner;

    yylex_init(&myscanner);
    yyparse(myscanner, mycvs);
    yylex_destroy(myscanner);

Le voila! The cvs argument will now be visible to the handler functions you write in your Bison grammar and your Lex specification. You can use it to pass data to the caller – typically, as in my code, the type of the second argument will be a structure of some sort. The documentation insists you can add more curly-brace-wrapped argument declarations to %lex-param and %parse-param to declare multiple extra arguments; I have not tested this.

Anyway, the ‘yyscanner’ argument will be visible to the helper code in your lex specification. The ‘scanner’ argument will be visible, under its right name, in your Bison grammar’s handler code. In both cases this is useful for calling accessors like yyget_in() and yyget_lineno() on. The cvs argument, as noted before, will be visible in both places.

There is, however, one gotcha (and yes, I have filed a bug report about it). Bison should arrange things so that all the %lex-params information is automatically passed to the generated parser and scanner code via the header file Bison generates (which is typically included in the C preambles to your Bison grammar and Lex specification). But it does not.

You have to work around this, until it’s fixed, by defining a YY_DECL macro that expands to the correct prototype and is #included by both generated source code files. When those files are expanded by the C preprocessor, the payload of YY_DECL will be put in the correct places.

Mine, which corresponds to the second set of declarations above, looks like this:

#define YY_DECL int yylex \
	(YYSTYPE * yylval_param, yyscan_t yyscanner, cvs_file *cvs)

There you have it. Reentrancy, proper information hiding – it’s not yer father’s parser generator. For the fully worked example, see the following files in the cvs-fast-export sources: gram.y, lex.l, cvs.h, and import.c.

Mention should be made of Make a reentrant parser with Flex and Bison, another page on this topic. The author describes a different technique requiring an uglier macro hack. I wasn’t able to make it work, but it started me looking in approximately the right direction.

14 comments

  1. Hi, Eric! I was just looking at your post from 2-11-2006, entitled “Gramscian Damage”–excellent post, btw. In it, you refer to an article/post by Mark Brittingham, and include a link that is now dead–I guess wildmonk.net is no longer operative. Do you have any other source for the referenced Brittingham article?

    1. >Do you have any other source for the referenced Brittingham article?

      Alas, no. I was unaware it had evaporated.

  2. As an aside: someone should design and standardize a much newer API for these tools. Parsers and lexers are key tools, but the APIs used by byacc/bison and flex retain way too much of the early 1970s flavor they started with. It should be straightforward to have a second API associated with these tools and retain all the existing machinery. (I say “straightforward”, not “low effort” — it will be a bunch of work, but there isn’t any rocket science to it.)

    1. >It should be straightforward to have a second API associated with these tools and retain all the existing machinery.

      It wasn’t difficult even 31 years ago. I did it in…1983, I think, though my repo was initialized in ’95. Just for grins here’s the README:

      				yacchack
      
      For updates and related resources, http://www.tuxedo.org/~esr/home.html.
      
      This package contains four files:
      
      0. READ.ME
      	This file.
      
      1. yaccpar
      	This is an upward-compatible replacement for /usr/lib/yaccpar.
      A quick diff will show that the only changes are enclosed in #ifdef YYPARSE/
      #endif pairs; the old interface to YACC-generated parsers is still supported.
      
      2. yyparse.h
      	This file #defines YYPARSE and the yyparse_t parse control structure.
      If you include it in your .y file, therefore, the new interface features will
      be automatically enabled.
      
      3. yacc
      	This shellscript is a front end for /usr/bin/yacc that implements
      both the postprocessing necessary to seal off new-style YACC parsers from
      the outside world and the proposed changes in output file naming (and the
      -b option to generate old-style y.tab.[ch] files).
      
      The new features enabled by these files are as follows:
      
      A. Multiple parsers in one runtime without conflict
      B. Parsing functions may be named by the user.
      C. Lexer functions may have any user-specified name.
      D. Compilation of multiple grammars in one directory won't screw up.
      
      Features A, B and C require inclusion of the yyparse.h header file in your
      YACC source; feature D is implemented (imperfectly, concurrent yacc runs can
      still lose) by the yacc front end.
      If the new header file is included, the value of the preprocessor symbol
      YYPARSE will become the name of the parsing function. This name is set by
      yyparse.h to default to 'yyparse' if no other definition is given.
      
      If the header file is *not* included, yaccpar will compile to the old-style
      code, with the old-style interface and all its globals indecently exposed.
      
      In the new interface, the parser function takes an argument which is the
      address of a parse control block (yyparse_t) as defined in yyparse.h.
      This structure contains
      
      	1. three writeable members; these are to contain the address of
      	   your lexer function, the place the parser expects to find
       	   token values after a lexer call, and the runtime debug flag.
      
      	2. readable members holding all the rest of the parser's state
      	   information.
      
      New-style parsers have no public data other than what's in their control
      blocks. Thus, several may coexist happily in a single runtime.
      
      Most grammar-production and helper code will not need to be modified at all
      to move to the new interface. The yaccpar file defines macros that map all
      the old global names to the corresponding elements of the parse control
      block; these macros are effective over all user code in the parser.
      
      The interface to the lexer changes slightly in that the parse control
      block must be initialized with the lexer function address. Also,
      references to yylval from outside the generated module will raise a
      link error; they'll need to be replaced with references to the proper
      control block slot.
      
      (In C++, the parse control block should become a class with the generated
      parser as a member function associated with each instance. Then the renaming
      kluge via YYPARSE could go away!)
      
      The proposed new naming convention is simply that (unless the new -b option
      is given to force the old behavior) a yacc run on .y produces output
      files .c (instead of y.tab.c), .h (instead of y.tab.h), and
      .d (instead of y.output).
      
      Since the default .y.c make rule moves y.tab.c to .c already, the only
      incompatibility risk this poses is to sites that a) use y.tab.c explicitly in
      their makefiles, or b) both use the -d option *and* have header files named
      .h (a rather unlikely circumstance).
      
  3. @esr: While you’re redefining all of the old Unix APIs to suck less, could you take a swing at the standard I/O routines? Much like disco, ‘errno’ needs to die a horrible death.

  4. Garrett,

    While we’re at it, can we just get rid of C and standardize on C++ or, better yet, Rust or Ada as the system programming language? C’s lack of exceptions, memory safety, and type-safe generic programming is crippling…

    If you must use C, the correct thing to do is return your error code and pass back additional information your function generates via passed-in pointers, like the old Macintosh Toolbox API.

  5. Eric, isn’t D. Richard Hipp’s Lemon designed for exactly the features you want? Of course it is not Yacc compatible, and thus presumably not a real option for extending an existing Bison-using codebase. But if you were starting from scratch, what parser generator would you likely prefer, and why?

    There are many others of course; ANTLR, Packrat parsers, etc.; but my understanding is that they tend to be even more dissimilar from Bison/Yacc.

    1. >Eric, isn’t D. Richard Hipp’s Lemon designed for exactly the features you want?

      Wouldn’t have been an practical option here, as I wasn’t writing the grammar for parsing CVS masters from scratch.

  6. If you have existing Yacc/Lex (Bison/Flex) code, you would probably do not consider to move to different parser, like e.g. Marpa (or to be more exact Libmarpa).

    http://jeffreykegler.github.io/Marpa-web-site/

    It allows for better error recovery than Yacc-like parsers, and less hand-coding. Scanless interface (an extension of (E)BNF with lexing information and possibility of attaching procedural parsing) is really cool…

    “The Bovicide Series” (“Killing Yacc”, “Why the Bovicidal Rage?”, “Bovicide”):
    http://jeffreykegler.github.io/Ocean-of-Awareness-blog/metapages/annotated.html#BOVICIDE

  7. @esr –
    > First, motivation. I had to figure out how to do this for cvs-fast-export, ….

    Are you still looking for help in explicating the cvs-fast-export code?

    1. >Are you still looking for help in explicating the cvs-fast-export code?

      Oh hell yes. The central branch merge algorithm remains mysterious.

      Now I’m wrestling with another problem. As part of the never-ending quest to make this thing run like a screaming bat out of hell (because, increasingly, the remnant CVS repos are sufficiently huge and gnarly that you need screaming-bat speeds to make converting them practical) I parallelized the front end.

      You know what? This is worth a blog post. Soon to issue…

  8. Jakub, thank you for the link to Marpa. I was excited by Ragel before, but saddened that it couldn’t do LALR, etc. How does Marpa compare to Ragel performance-wise?

  9. I’ve read your article and changed my code to convert it to pure parser, but it has some error. I think these errors are related to ‘yyerror’ declaration. unfortunately, I don’t know how to solve it. I’ve asked my question in below address, but no one answered me.

    http://stackoverflow.com/questions/26483735/how-to-write-a-pure-parser-and-reentrant-scanner-by-win-flex-bison

    Could you guide me how to convert my parser to a pure parser?

    In addition, I use ‘win_flex bison’ for generating C codes. It only generate three files (lexer.tab.cpp, parser.tab.cpp, parser.tab.h). It doesn’t generate ‘lexer.tab.h’. So, lexer’s functions(like yy_scan_string) can not called from parser file directly. I have to use another function ( parseExpression in my code ) to call them in my parser file. Could you tell me how can I solve this problem?

    Thanks in advance.

    1. >Could you guide me how to convert my parser to a pure parser?

      Sure. Mail me a tarball of the code and instructions on how to reproduce; I’ll take a look.

Leave a comment

Your email address will not be published. Required fields are marked *