yacc

a parser generator (POSIX)

Syntax:

yacc [-b prefix] [-dltv] file

Options:

-b prefix

Use prefix rather than y for the generated filename prefixes:

• y.tab.h
• y.tab.c
• y.output

-d

Write a header file containing manifests for all tokens.

-l

("el") The file does not contain any #line constructs. If this option is not specified, yacc will attempt to adjust any such constructs as necessary.

-t

Generate a parser with debugging information, which may be enabled by setting yydebug to 1.

-v

Be verbose; generate statistics of the parser.

Description:

The yacc utility transforms a specification of a context-free grammar into a C language function that implements an LR(1) parsing algorithm. Ambiguities in the grammar may be resolved using precedence rules within the specification. The C language function is named yyparse(), and calls yylex() to get input tokens, which are integer values. The value 0 is considered special, as being end-of-input.

You can use the following parser with the lexical analyzer in lex to implement a simple calculator.

%{
/*
 *   calculator:   a simple calculator.
 *   This calculator allows all common arithmetic operations,
 *   including sin, cos, tan, sqrt, exp, pow, log.
 *   The calculator is a simple example of using the yacc
 *   parser generator.
 *  
 */ 
#include <stdio.h>
#include <math.h>

#define YYSTYPE double
    YYSTYPE last_value = 0;

extern int yylex(void);

%}

/*
  * Define the tokens produced by yylex()
 */
%token NUMBER
%token LAST
%left '+' '-'
%left '*' '/'
%left '^'
%left NEGATIVE
%left COS EXP SIN SQRT TAN

/*
 *  Begin specification of the parser.
 */
%%
/*
 * a 'list' may be empty, contain blank lines or expressions.
 */
list:
    |    list '\n'
    |    list expr '\n'           { printf("%.8g\n",last_value=$2);
}
    ; /*
 * Expressions are defined recursively as strings of terms
 * and expressions. Note that the 'sin',... functions do not
 * require bracketed parameters although sin x +1 is
 * interpreted as (sin(x))+1
 */

    expr:     term                 { $$ = $1;         }
    |     expr '+' expr            { $$ = $1 + $3;    }
    |     expr '-' expr            { $$ = $1 - $3;    }
    |     expr '*' expr            { $$ = $1 * $3;    }
    |     expr '/' expr            { $$ = $1 / $3;    }
    |     expr '^' expr            { $$ = pow($1,$3); }
    |     '-' expr  %prec NEGATIVE { $$ = - $2;       }
    |     COS   term               { $$ = cos($2);    }
    |     EXP   term               { $$ = exp($2);    }
    |     SIN   term               { $$ = sin($2);    }
    |     SQRT  term               { $$ = sqrt($2);   }
    |     TAN   term               { $$ = tan($2);    }
    ;
/*
 * The following are of the highest precedence.
 * They needed to be distinguished to allow the
 * functions (sin...) to operate properly without
 * parentheses
 */
term:     NUMBER                   { $$ = $1;         }
    |     LAST                     { $$ = last_value; }
    |     '(' expr ')'             { $$ = $2;         }
    ;
%%

#include <stdlib.h>
#include <string.h>
#include <unistd.h>
int lineno;

char *fname = "-stdin-";
int yyerror(const char *s)
{
    fprintf(stderr,"%s(%d):%s\n",fname,lineno,s);
    return 0;
}
main()
{
	yyparse();
	return 0;
}

See also:

• lex utility (Lexical analyzer generator)
• A.V. Aho and S.C Johnson, "LR Parsing," Computing Surveys, June 1974
• A.V. Aho, R. Sethi and J.D. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley, 1977
• S.C. Johnson, "Yacc — Yet Another Compiler-Compiler," Bell Laboratories Computing Science Technical Report # 32, July 1978
• Brian W. Kernighan and Rob Pike, The UNIX Programming Environment, Prentice-Hall, 1984
• J. P. Bennett, Introduction to Compiling Techniques — A First Course using ANSI C, LEX and YACC, McGraw-Hill, 1990
• John R. Levine, Tony Mason and Doug Brown, lex and yacc, O'Reilly and Associates, 1990

Author:

Vern Paxton, The University of California at Berkeley