Parser Generator Workflow

Introduction

Using Flex and Bison together is the standard industrial approach to building parsers for compilers, interpreters, and domain-specific languages. Individually, each tool handles one half of the problem — Flex converts characters to tokens, Bison converts tokens to parse trees. Together, they form a powerful pipeline that automates the tedious work of hand-writing scanners and parsers. Understanding this workflow — how the tools interact, how to build and debug the generated code, and how to handle common pitfalls — is essential knowledge for any compiler developer.

The End-to-End Workflow

The complete process from specification to running program involves several stages:

The order matters critically. Bison must run first because it generates y.tab.h, which contains the #define statements for token types (like #define NUMBER 258, #define PLUS 259). The Flex specification includes this header so that the lexer returns the same token codes the parser expects.

How Flex and Bison Communicate

The interface between lexer and parser is elegant in its simplicity:

Every time the parser needs the next token, it calls yylex(). The lexer reads characters, matches a pattern, executes the associated action (which typically sets yylval and returns the token type). The parser receives the token type and uses yylval for semantic computations.

For tokens that carry values (like numbers), the lexer must set yylval before returning:

For more complex value types, Bison's %union declaration defines what yylval can hold:

A Complete Working Example

Here is a minimal but complete calculator implementation showing both files:

calculator.y (Bison grammar):

calculator.l (Flex lexer):

Build System Integration

Makefile (Most Common)

Note the dependency: lex.yy.c depends on y.tab.h, which ensures Bison runs before Flex.

CMake (Modern Projects)

Debugging Parser Generators

Enabling Bison Debug Trace

Add these to your .y file to see every shift and reduce action:

The trace output shows you exactly what the parser is doing:

Enabling Flex Debug Output

Using Bison's Verbose Report

The .output file shows all parser states, the item sets in each state, and any conflicts with detailed explanations of why they occur.

Common Problems and Solutions

Problem 1: "Undefined reference to yylex"

• Cause: The Flex-generated lexer object file was not linked
• Solution: Ensure lex.yy.o is included in the gcc link command

Problem 2: Token values are always zero

• Cause: Forgot to set yylval in lexer actions before returning
• Solution: Add yylval = atoi(yytext); before return NUMBER;

Problem 3: Shift-reduce conflicts

• Cause: Grammar ambiguity (usually precedence-related)
• Solution: Add %left, %right, or %nonassoc declarations for operators
• Diagnostic: Run bison -v and examine the .output file for conflict details

Problem 4: Parser accepts nothing / immediate syntax error

• Cause: Token types mismatch between .l and .y files
• Solution: Verify that .l file includes "y.tab.h" and returns the correct token macros

Problem 5: Infinite loop on error

• Cause: Error recovery consumes no tokens
• Solution: Add error productions that consume at least one token: stmt: error ';' { yyerrok; }

Best Practices

1. Run Bison first, always — The header file it generates is needed by Flex
2. Use %define parse.error verbose — Get meaningful error messages instead of just "syntax error"
3. Start simple, add incrementally — Get a minimal grammar working, then add operators one at a time
4. Test the lexer independently — Print tokens before connecting to the parser to verify tokenization
5. Use %locations — Bison can track line/column numbers automatically for better error messages
6. Keep semantic actions small — Call helper functions rather than embedding complex logic in grammar rules
7. Use %destructor — For dynamic memory (strings, AST nodes), define cleanup rules to prevent leaks

Key Takeaways

The Flex-Bison workflow is a disciplined process: write specifications, generate code, compile, link, test. The most common source of bugs is the interface between the two tools — ensuring token definitions match, semantic values are set correctly, and the build order is right. Once you have the workflow mastered, you can focus on the interesting part: designing your language's grammar and implementing its semantics. This same pattern — specification-driven code generation — applies to modern tools like ANTLR, tree-sitter, and language workbenches.