bison Command in Linux

Introduction to Bison: A Comprehensive Guide

This lab provides a practical exploration of the bison command-line tool, a critical parser generator for compiler and interpreter development. As a robust, free software implementation of YACC, bison enables the generation of parsers from context-free grammar specifications. We begin with the installation of the bison package on an Ubuntu 22.04 system, followed by the creation of a simple grammar file. Using this file, we'll generate a parser with the bison command. Finally, we will implement error handling strategies to deal with syntax issues inside the generated parser.

This tutorial encompasses the following key areas:

  • Understanding the bison Command
  • Generating Parsers Using bison
  • Implementing Syntax Error Handling in bison

Understanding the bison Command

This section delves into the bison command, a parser generator essential for creating compilers and interpreters. Bison stands out as a free software alternative to YACC (Yet Another Compiler-Compiler), a widely used tool for producing parsers from specifications based on context-free grammars.

Let's start by installing the bison package on our Ubuntu 22.04 environment:

sudo apt-get update
sudo apt-get install -y bison

Example output:

Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
The following additional packages will be installed:
  m4
Suggested packages:
  bison-doc
The following NEW packages will be installed:
  bison m4
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 1,141 kB of archives.
After this operation, 4,470 kB of additional disk space will be used.
Do you want to continue? [Y/n] Y
...

With bison successfully installed, we'll proceed to create a rudimentary grammar file for parser generation. In the ~/project directory, create a file named example.y and populate it with the following content:

%{
#include <stdio.h>
%}

%token NUM
%%

input:
    | input line
;

line:
    NUM '\n' { printf("Received number: %d\n", $1); }
;

%%

int main() {
    yyparse();
    return 0;
}

This grammar file defines a streamlined calculator-like syntax that can discern and handle numerical inputs. The %token NUM declaration specifies a token type specifically for numbers, while the line rule dictates that a valid line should contain a number immediately followed by a newline character.

Generating Parsers Using bison

This section focuses on parser generation using the bison command, leveraging the grammar file established in the preceding section.

First, let's generate the parser source code from the example.y file:

bison -d example.y

This command yields two output files: example.tab.c and example.tab.h. The example.tab.c file encapsulates the parser's implementation details, while example.tab.h contains the token definitions necessary for the parser.

Next, we must compile the parser's source code and link it with a lexer (scanner) to produce the final executable. We will utilize the flex tool for lexer generation:

sudo apt update
sudo apt-get install -y flex
flex -o example.lex.c example.l
gcc -o example example.tab.c example.lex.c

The flex command generates the example.lex.c file containing the lexer implementation. The gcc command compiles and links the parser and lexer sources to create the example executable.

Now, let's test our parser by running the example program:

./example
123
Received number: 123
456
Received number: 456

As demonstrated, the parser accurately identifies and processes the provided numerical inputs.

Implementing Syntax Error Handling in bison

In this section, we'll explore methods for managing syntax errors within parsers generated using bison.

Let's modify the example.y file to incorporate error handling features:

%{
#include <stdio.h>
%}

%token NUM
%error-verbose

%%

input:
    | input line
    | input error '\n' { yyerrok; }
;

line:
    NUM '\n' { printf("Received number: %d\n", $1); }
    | error '\n' { yyerror("Invalid input"); }
;

%%

void yyerror(const char *s) {
    fprintf(stderr, "%s\n", s);
}

int main() {
    yyparse();
    return 0;
}

The significant modifications are:

  1. Addition of %error-verbose to enhance the detail of error messages.
  2. Introduction of an error rule within the input and line productions to manage syntax errors gracefully.
  3. Implementation of the yyerror function to display custom error messages.

Now, let's regenerate the parser and test it again:

bison -d example.y
flex -o example.lex.c example.l
gcc -o example example.tab.c example.lex.c

Execute the example program and input some invalid data:

./example
abc
example.y:12: syntax error, unexpected error, expecting NUM
Invalid input
123
Received number: 123

As can be seen, the parser effectively detects and reports syntax errors when encountering "abc" instead of a numerical input.

Summary

In this lab, we investigated the bison command-line tool, a key resource in compiler and interpreter development. We began by installing the bison package on Ubuntu 22.04 and then crafted a simple grammar file to define a basic calculator syntax. Following that, we generated parser source code using the bison command, leading to the creation of parser implementation and header files. Finally, we learned how to implement syntax error handling within the generated parser, an important consideration for robust applications. This tutorial gives systemadmin and other techincal experts the basics for using Bison.

400+ Linux Commands