A Bison Tutorial: Do We Shift or Reduce?

Reading, using and making Bison grammar files.
An Actual Bison Grammar File

The following text is an actual Bison grammar file for a two-function calculator patterned after the previous example.

Each rule in the grammar file can have associated with it an action, which is C code enclosed in braces. When the parser reduces using a grammar rule, it executes the action associated with that rule.

This real grammar file requires two additional nonterminal symbols that did not appear in our earlier example. The nonterminal named line is defined as an expression followed by a newline, and its associated action is used to print out the value of the expression. The purpose of line is to get the answer printed.

For the case where the user just presses Enter, the production for <line> has been defined such that it can also be nothing followed by a newline. The calculator will work after we define this one new nonterminal. It will work until the user enters a newline alone, then it will get a parse error. So what we do is define yet another nonterminal to catch the result of entering only a newline.

The nonterminal symbol <input> defines our start symbol; it is either a line or it can be "nothing," to catch nothing followed by newline. In either case, we accept the parse as complete and error-free.

/* twofunc2.y - a two function calculator */
#define YYSTYPE double  /* yyparse() stack type */

/* BISON Declarations */
%token ID

/* Grammar follows */
input:          /* empty string */
        | input line

line:     '\n'
        | expr '\n'             { printf("\t%.10g\n",$1); }

expr:     expr '+' term         { $$ = $1 + $3; }
        | term
term:     term '*' factor       { $$ = $1 * $3; }
        | factor
factor:   '(' expr ')'          { $$ = $2; }
        | ID

/* Additional C code */

/* Error processor for yyparse */
#include <stdio.h>

int yyerror(char *s)    /* called by yyparse on error */


/* Lexical analyzer returns a double floating point
   number on the stack and the token ID, or the ASCII
   character read if not a number. Skips all white space
   and returns 0 for EOF. */

#include &ltctype.h>

int yylex(void)
        int c;
        /* slip white space */
        while ( (c=getchar()) == ' ' || c == '\t')
        /* process numbers */
        if (c == '.' || isdigit(c)) {
        /* check EOF */
        if (c == EOF)
                return 0;
        /* return single character as its own token type */
        return c;

/* The controlling function */

int main(void)
Layout of a Bison Grammar File

All Bison grammar files have the form of the example above. The two-character strings %% , %{ and %} are punctuation marks that appear in every Bison grammar file to separate the sections. The general form of all Bison grammar files can be summarized as follows:

        C declarations
        Bison declarations
        Grammar rules
        Additional C code

From the Bison Manual:

The C declarations may define types and variables used in the actions. You can also use preprocessor commands to define macros used there, and use



Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Re: A Bison Tutorial: Do We Shift or Reduce?

jackdennon's picture

My browser manages to seriously mangle

the display of this article. What was a

visible newline
disappears and the

parse table for the example two-function

calculator gets badly disfigured.

If yours does the same, you can

download the plain text version of the

article in the compressed file hoc7n.tgz



Unpack it with

tar -xvzf hoc7n.tgz

and then read it with any text editor.


Geek Guide
The DevOps Toolbox

Tools and Technologies for Scale and Reliability
by Linux Journal Editor Bill Childers

Get your free copy today

Sponsored by IBM

8 Signs You're Beyond Cron

Scheduling Crontabs With an Enterprise Scheduler
On Demand
Moderated by Linux Journal Contributor Mike Diehl

Sign up now

Sponsored by Skybot