Getting Started with Bison

Preface

Syntax analysis means identifying the corresponding syntactic categories from the results of lexical analysis according to the grammar rules of the source language. In essence, it is the process from Parsing -> AST (Abstract Syntax Tree). That is, it converts the token stream produced by the previous lexical analysis phase into an ordered tree structure. What is this good for? It essentially implements parsing of the code text, allowing the program to understand its syntactic meaning, so that it can operate on the meaning of the text rather than merely manipulating the code string itself.

This transformation in syntax analysis can be done recursively, namely via a recursive descent algorithm; it can also be done using a bottom-up shift-reduce algorithm under certain constraints. In real-world scenarios, the latter has far higher non-recursive runtime efficiency than the former, so it is also the implementation approach used by the vast majority of parsers. For the Bison parser generator, the so-called “constraints” here mean that as long as the input formal grammar satisfies an LALR(1) grammar, a parser can be generated automatically.

Abstract Syntax Tree

Here we simply demonstrate what an abstract syntax tree is. In short, it is the result of transforming text into a structured form, making it more convenient to analyze the semantics of the code, or the text, on a tree structure. Since deriving concrete code from grammar rules is essentially a recursive process, a tree structure is well suited to presenting this kind of abstract concept with recursive substructures.

Consider the following illustrative code for the Euclidean algorithm:

while b ≠ 0
if a > b
    a := a − b
else
    b := b − a
return a

After syntax analysis, the resulting abstract syntax tree diagram is as follows:

Arithmetic Expression Evaluation

To implement a program that can evaluate simple arithmetic expressions, on the one hand we could use the classic two-stack arithmetic expression evaluation algorithm from data structures; but a simpler and more elegant implementation is to directly use Bison to generate the corresponding parser.

Lexical Analysis

First perform lexical analysis. The rules are very simple: use regular expressions to match the corresponding floating-point numbers and operators:

%{
#define YYSTYPE double
#include "eval.tab.h"
extern YYSTYPE yylval;
%}
FLOAT   (([0-9]+(\.[0-9]*)?)|(\.[0-9]+))([Ee][+-]?[0-9]+)?
WHITE   [ \t\n]|(\r\n)
%%
{FLOAT}     { sscanf(yytext, "%lf", &yylval); return NUMBER; }
{WHITE}     { /* do nothing */ }
.           { return yytext[0]; }
%%

LALR(1) Grammar

Then construct its LALR(1) grammar:

statement  ::=  expression
expression ::=  expression + expression
                expression – expression
                expression * expression
                expression / expression
                - expression
                ( expression )
                Number

Syntax Analysis

Next, convert the above grammar into rules that Bison can recognize, and add the corresponding actions:

%{
#include <stdio.h>
#include <math.h>
#define YYSTYPE double
%}

%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS

%%
statement: expression { printf("result = %.3f\n", $1); };
expression: expression '+' expression   { $$ = $1 + $3; }
    |   expression '-' expression   { $$ = $1 - $3; }
    |   expression '*' expression   { $$ = $1 * $3; }
    |   expression '/' expression   { if (fabs($3) < 1e-10) yyerror ("divide by zero"); else $$ = $1 / $3; }
    |   '-' expression %prec UMINUS { $$ = - $2; }
    |   '(' expression ')'      { $$ = $2; }
    |   NUMBER              { $$ = $1; }
    ;
%%
int main (void) {
    return yyparse();
}
int yyerror (char *msg) {
    return fprintf (stderr, "YACC: %s\n", msg);
}

Note that to eliminate shift-reduce conflicts, it is necessary to assign context-dependent precedence to the unary minus operator (UMINUS). For details, see Section 5.4 of the Bison manual, "Context-Dependent Precedence".

Result

With just the two files above, you can compile and obtain a runnable program. Finally, with only a dozen or so lines of code, we easily implemented a robust expression evaluation tool. Its runtime output looks like this:

As you can see, even though the expression being evaluated contains various annoying formatting elements such as line breaks and whitespace, the program can still parse it correctly and produce the result. More generally, any other more complex structured text can use the same technique to generate a parser, enabling advanced operations based on the text’s semantics.

The source code and compiled output above can be downloaded here.