A Bison Tutorial: Do We Shift or Reduce?

 in
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 */
{
        printf("%s\n",s);
        return(0);
}

/*--------------------------------------------------------*/

/* 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)) {
                ungetc(c,stdin);
                scanf("%lf",&yylval);
                return(ID);
        }
        
        /* check EOF */
        if (c == EOF)
                return 0;
                
        /* return single character as its own token type */
        return c;
}
/*--------------------------------------------------------*/

/* The controlling function */

int main(void)
{
        yyparse();
        exit(0);
}
/*--------------------------------------------------------*/
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

______________________

Comments

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

at

http://www.seasurf.com/~jdennon

Unpack it with

tar -xvzf hoc7n.tgz

and then read it with any text editor.

jdennon@seasurf.com

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix