Make a reentrant parser with Flex and Bison

Making a reentrant (thread-safe) parser with Flex and Bison involves several stages.

To eliminate global variables from Flex, use the following line:

%option reentrant

This changes yylex () to yylex (void *). The argument to yylex contains initialized memory for the lexer which is initialized using yylex_init:

void * something;
yylex_init (& something);
yylex (something);

and then release the memory after finishing the lexing:

yylex_destroy (something);

In the flex documentation, this is given as yyscan_t, but it's void *.

If the lexer is combined with a Bison parser, add

%option bison-bridge

This makes Bison send yylex another argument to use instead of using the global variable yylval:

int yylex ( YYSTYPE * lvalp, yyscan_t scanner );

You can then use yylval in the Flex lexer, and it will refer to whatever is passed in as the first argument to yylex above.

The type of yylval, YYSTYPE, is also needed, so run Bison with the -d option to create the file yy.tab.h which defines it for you, and include this file into the lex file using the top section:

%{
#include "yy.tab.h"
%}

See C Scanners with Bison Parsers - Flex manual for more details.

In the Bison input file, add

%pure-parser

to make a reentrant parser,

%lex-param {void * scanner}

to tell it to send the lexer an extra argument, and

%parse-param {void * scanner}

to add another argument to yyparse, which is the thing to pass in to Flex.

The above is already enough to create a reentrant parser. If you also need to pass in something to Bison, you can add a member

struct pass_to_bison {
    ....
    void * scanner;
} x;

with

%parse-param {struct pass_to_bison * x}

then use a preprocessor macro like

#define scanner x->scanner

in the Bison preamble to make Bison send the scanner. In this case, use

struct pass_to_bison x;
yylex_init (& x->scanner);
yyparse (& x);
yylex_destroy (& x->scanner);

To use private data in the Flex lexer, set its value with yylex_set_extra:

struct user_type {
    int number;
};
struct user_type * user_data;
yylex_set_extra (user_data, scanner);

after calling yyinit_lexer. Here scanner is the data passed to yyinit_lexer. In the preamble of the Flex file, add

%{
#define YY_EXTRA_TYPE struct user_type *
%}

The data in user_data is then available in the lexer as yyextra:

%%
.*             { yyextra->number++; }
%%

See Extra Data - Flex manual.

Web links

Writing a Reentrant Parser with Flex and Bison By Edsko de Vries

This is an example of a reentrant parser using C++. It also gives the parser and lexer different prefixes.
JSON::Argo, a JSON parser for Perl

This is an example of a reentrant parser for JSON using Bison and Flex. See the files src/json_parse_lex.l for the Flex, and src/json_parse_grammar.y for the Bison, as well as json_parse.c for the caller.
Reentrant C Scanners - Flex manual
Building a reentrant parser in C with Flex/Bison

This is quite a nice example without complications.

Ask and answer questions on C in the new C forum