GNU Bison

GNU Bison generates parsers from context-free grammars. Its Yacc-compatible notation defines tokens, nonterminals, semantic values, and actions; the generated parser obtains tokens from a scanner by convention. Consult the GNU Bison manual for skeleton- and language-specific interfaces.

Grammar Sections, Values, and Actions #

A grammar has declarations, productions, and optional epilogue code, separated by %%. Declarations define tokens, value types, precedence, parser settings, and required code. Productions define nonterminals and actions.

%define api.value.type {int}
%token NUMBER
%left '+' '-'
%%
expression:
    NUMBER                 { $$ = $1; }
  | expression '+' expression { $$ = $1 + $3; }
  ;
%%

An action runs when its production reduces. $$ denotes the result’s semantic value and $1, $2, and so on denote right-hand-side values. Use %type and typed %token declarations with %union, or an appropriate %define api.value.type configuration, when symbols carry different value types. Ensure destructors and ownership rules cover values discarded during error recovery.

Names and Parser Interfaces #

C parsers use yyparse, yylex, and yyerror by default. %define api.prefix {project_} gives generated external names a distinct prefix, so multiple generated parsers can link in one program. Configure the scanner with a matching prefix and header contract.

The default pull parser calls the lexer itself. %define api.push-pull push generates a push interface for callers that supply tokens; both provides pull and push interfaces. %define api.pure full removes parser-global state from the reentrant interface, but a concurrent design also needs a reentrant scanner and explicit context passing. Use %parse-param and %lex-param to pass that context through parser and lexer calls.

Locations, Precedence, and Conflicts #

Enable %locations when diagnostics need source spans. Actions can access @$ and @1 for the left-hand side and right-hand-side locations. The lexer must populate location fields consistently for all input, including ignored whitespace.

%left, %right, %nonassoc, %precedence, and %prec resolve selected shift/reduce conflicts according to declared precedence and associativity. Bison otherwise prefers shift for a shift/reduce conflict and uses the earlier rule for a reduce/reduce conflict; neither default establishes intended language semantics. Investigate every conflict, use -Wcounterexamples where available to obtain examples, and keep %expect only as an asserted, reviewed conflict count.

Error Recovery #

Bison reserves the error token for recovery productions. On syntax error, a production such as statement: error ';' can discard input until a synchronization token and allow later statements to parse. Use yyerrok only when the action deliberately ends recovery; use yyclearin only when the lookahead token is known to be unsuitable.

Recovery must release discarded semantic values, make progress, and avoid reporting cascades as independent root causes. Keep recovery points at stable grammar boundaries—statements, declarations, or closing delimiters—rather than accepting arbitrary tokens within expressions.