BNF Grammer Basics

Context-free grammars are often described using Backus-Naur Form (BNF). For example:

expression : expression '+' expression
           | expression '-' expression
           | NUMBER
           ;

This defines a rule for expression with three alternatives (productions). Each production has a leeft-hand side (LHS) and a right-hand side (RHS). Symbols like NUMBER that cannot be further expanded are terminals; symbols like expression that can be replaced are nonterminals.

Workflow

Using flex alone

A standalone flex scanner reads input and matches patterns without a separate parser.

Using flex with bison

In a combined setup, flex performs lexical analysis and returns tokens to the bison-generated parser. The parser then applies grammer rules to build a parse tree or execute semantic actions.

Structure of a flex file

A typical flex input file (.l) has three sections separated by %%:

1. Declarations (optional C code and options)
2. Rules (patterns and actions)
3. User code (auxiliary C functions)

Flex Details

How input is matched

The generated scanner reads input and looks for the longest match among all patterns. If multiple rules match the same length, the one that appears first in the file is chosen. The matched text is stored in yytext; its length is in yyleng.

Interfacing with bison

When using bison, the file gram.tab.h (produced by bison -d) defines all %token constants. The flex file includes this header and returns the token type along with an optional semantic value via the global yylval:

%{
#include "gram.tab.h"
%}
%%
[0-9]+        yylval = atoi(yytext); return TOK_NUMBER;

Reentrant scanner

A reentrant scanner avoids global state. Enable it with %option reentrant and optionally set an extra data type using %option extra-type="struct stat *". Example:

%{
#include <sys/stat.h>
#include <unistd.h>
%}
%option reentrant
%option extra-type="struct stat *"
%%
__filesize__     printf("%ld", yyextra->st_size);
__lastmod__      printf("%ld", yyextra->st_mtime);
%%
void scan_file(char* filepath) {
    yyscan_t lexer;
    struct stat statBuf;
    FILE *fp;

    fp = fopen(filepath, "r");
    stat(filepath, &statBuf);

    yylex_init_extra(statBuf, &lexer);
    yyset_in(fp, lexer);
    yylex(lexer);
    yylex_destroy(lexer);
    fclose(fp);
}

Access the extra data with yyget_extra and yyset_extra.

Scanner options

• %option bison-bridge – Change the yylex signature to accept YYSTYPE* and YYLTYPE* arguments.
• %option bison-locations – Enable location tracking, adding YYLTYPE* to the scanner interface.

With both options, the yylex declaration becomes:

int yylex(YYSTYPE* lvalp, YYLTYPE* llocp, yyscan_t scanner);

Start conditions

Start conditions allow the scanner to change which rules are active. See the example on GitHub.

Scanning in‑memory strings

Use yy_scan_buffer to scan a string instead of a file.

Overriding default memory management

1. Disable default allocators: ``` %option noyyalloc %option noyyrealloc %option noyyfree

2. Provide custom functions: ``` void* yyalloc(yy_size_t bytes, core_yyscan_t yyscanner) { return palloc(bytes); } void* yyrealloc(void* ptr, yy_size_t bytes, core_yyscan_t yyscanner) { if (ptr) return repalloc(ptr, bytes); else return palloc(bytes); } void yyfree(void* ptr, core_yyscan_t yyscanner) { if (ptr) pfree(ptr); }

Bison Details

Grammar file structure

A bison grammar file (.y) typically contains:

• Prologue (C code and %{...%} blocks)
• Bison declarations (%token, %type, %union, etc.)
• Grammar rules with semantic actions
• Epilogue (auxiliary C code)

Parser components

The generated parser consists of a stack, a state machine, and action tables. It processes tokens from the scanner, shifts them onto the stack, and reduces based on grammar rules.

Lookahead token

When a reduction is possible, the parser looks ahead at the next token without shifting it immediately. This lookahead token is stored in yychar, its semantic value in yylval, and its location in yylloc. This mechanism helps resolve conflicts and choose the correct production.

Overriding memory management in bison

Define macros before including the parser header:

#define YYMALLOC palloc
#define YYFREE   pfree

Bison declarations

Terminal symbols must be declared with %token; nonterminal symbols can be typed with %type. For example:

%token CREATE TABLE
%token <ival> NUMBER
%type <node> create_table_stmt insert_stmt

The data types (ival, node) come from a %union declaration:

%union {
    int ival;
    Node* node;
}

This generates a union YYSTYPE in the parser implementation.

Other common bison options:

/* Request a reentrant parser (new syntax: %define api.pure full) */
%pure-parser

/* Zero shift/reduce conflicts */
%expect 0

/* Enable location tracking */
%locations

/* Pass yyscanner to yyparse */
%parse-param {core_yyscan_t yyscanner}

/* Tell bison that yylex uses the same parameter */
%lex-param {core_yyscan_t yyscanner}

/* Shortcut for common parameters */
%param {core_yyscan_t yyscanner}