1.5.1 Using GLR on Unambiguous Grammars

In the simplest cases, you can use the GLR algorithm to parse grammars that are unambiguous but fail to be LR(1). Such grammars typically require more than one symbol of lookahead.

Consider a problem that arises in the declaration of enumerated and subrange types in the programming language Pascal. Here are some examples:

type subrange = lo .. hi;
type enum = (a, b, c);

The original language standard allows only numeric literals and constant identifiers for the subrange bounds (‘lo’ and ‘hi’), but Extended Pascal (ISO/IEC 10206) and many other Pascal implementations allow arbitrary expressions there. This gives rise to the following situation, containing a superfluous pair of parentheses:

type subrange = (a) .. b;

Compare this to the following declaration of an enumerated type with only one value:

type enum = (a);

(These declarations are contrived, but they are syntactically valid, and more-complicated cases can come up in practical programs.)

These two declarations look identical until the ‘..’ token. With normal LR(1) one-token lookahead it is not possible to decide between the two forms when the identifier ‘a’ is parsed. It is, however, desirable for a parser to decide this, since in the latter case ‘a’ must become a new identifier to represent the enumeration value, while in the former case ‘a’ must be evaluated with its current meaning, which may be a constant or even a function call.

You could parse ‘(a)’ as an “unspecified identifier in parentheses”, to be resolved later, but this typically requires substantial contortions in both semantic actions and large parts of the grammar, where the parentheses are nested in the recursive rules for expressions.

You might think of using the lexer to distinguish between the two forms by returning different tokens for currently defined and undefined identifiers. But if these declarations occur in a local scope, and ‘a’ is defined in an outer scope, then both forms are possible—either locally redefining ‘a’, or using the value of ‘a’ from the outer scope. So this approach cannot work.

A simple solution to this problem is to declare the parser to use the GLR algorithm. When the GLR parser reaches the critical state, it merely splits into two branches and pursues both syntax rules simultaneously. Sooner or later, one of them runs into a parsing error. If there is a ‘..’ token before the next ‘;’, the rule for enumerated types fails since it cannot accept ‘..’ anywhere; otherwise, the subrange type rule fails since it requires a ‘..’ token. So one of the branches fails silently, and the other one continues normally, performing all the intermediate actions that were postponed during the split.

If the input is syntactically incorrect, both branches fail and the parser reports a syntax error as usual.

The effect of all this is that the parser seems to “guess” the correct branch to take, or in other words, it seems to use more lookahead than the underlying LR(1) algorithm actually allows for. In this example, LR(2) would suffice, but also some cases that are not LR(k) for any k can be handled this way.

In general, a GLR parser can take quadratic or cubic worst-case time, and the current Bison parser even takes exponential time and space for some grammars. In practice, this rarely happens, and for many grammars it is possible to prove that it cannot happen. The present example contains only one conflict between two rules, and the type-declaration context containing the conflict cannot be nested. So the number of branches that can exist at any time is limited by the constant 2, and the parsing time is still linear.

Here is a Bison grammar corresponding to the example above. It parses a vastly simplified form of Pascal type declarations.

%token TYPE DOTDOT ID

%left '+' '-'
%left '*' '/'

%%
type_decl: TYPE ID '=' type ';' ;

type:
  '(' id_list ')'
| expr DOTDOT expr
;

id_list:
  ID
| id_list ',' ID
;

expr:
  '(' expr ')'
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| ID
;

When used as a normal LR(1) grammar, Bison correctly complains about one reduce/reduce conflict. In the conflicting situation the parser chooses one of the alternatives, arbitrarily the one declared first. Therefore the following correct input is not recognized:

type t = (a) .. b;

The parser can be turned into a GLR parser, while also telling Bison to be silent about the one known reduce/reduce conflict, by adding these two declarations to the Bison grammar file (before the first ‘%%’):

%glr-parser
%expect-rr 1

No change in the grammar itself is required. Now the parser recognizes all valid declarations, according to the limited syntax above, transparently. In fact, the user does not even notice when the parser splits.

So here we have a case where we can use the benefits of GLR, almost without disadvantages. Even in simple cases like this, however, there are at least two potential problems to beware. First, always analyze the conflicts reported by Bison to make sure that GLR splitting is only done where it is intended. A GLR parser splitting inadvertently may cause problems less obvious than an LR parser statically choosing the wrong alternative in a conflict. Second, consider interactions with the lexer (see Semantic Info in Token Kinds) with great care. Since a split parser consumes tokens without performing any actions during the split, the lexer cannot obtain information via parser actions. Some cases of lexer interactions can be eliminated by using GLR to shift the complications from the lexer to the parser. You must check the remaining cases for correctness.

In our example, it would be safe for the lexer to return tokens based on their current meanings in some symbol table, because no new symbols are defined in the middle of a type declaration. Though it is possible for a parser to define the enumeration constants as they are parsed, before the type declaration is completed, it actually makes no difference since they cannot be used within the same enumerated type declaration.

1.5.2 Using GLR to Resolve Ambiguities

Let’s consider an example, vastly simplified from a C++ grammar.¹

%{
  #include <stdio.h>
  int yylex (void);
  void yyerror (char const *);
%}

%define api.value.type {char const *}

%token TYPENAME ID

%right '='
%left '+'

%glr-parser

%%

prog:
  %empty
| prog stmt   { printf ("\n"); }
;

stmt:
  expr ';'  %dprec 1
| decl      %dprec 2
;

expr:
  ID               { printf ("%s ", $$); }
| TYPENAME '(' expr ')'
                   { printf ("%s <cast> ", $1); }
| expr '+' expr    { printf ("+ "); }
| expr '=' expr    { printf ("= "); }
;

decl:
  TYPENAME declarator ';'
                   { printf ("%s <declare> ", $1); }
| TYPENAME declarator '=' expr ';'
                   { printf ("%s <init-declare> ", $1); }
;

declarator:
  ID               { printf ("\"%s\" ", $1); }
| '(' declarator ')'
;

This models a problematic part of the C++ grammar—the ambiguity between certain declarations and statements. For example,

T (x) = y+z;

parses as either an expr or a stmt (assuming that ‘T’ is recognized as a TYPENAME and ‘x’ as an ID). Bison detects this as a reduce/reduce conflict between the rules expr : ID and declarator : ID, which it cannot resolve at the time it encounters x in the example above. Since this is a GLR parser, it therefore splits the problem into two parses, one for each choice of resolving the reduce/reduce conflict. Unlike the example from the previous section (see Using GLR on Unambiguous Grammars), however, neither of these parses “dies,” because the grammar as it stands is ambiguous. One of the parsers eventually reduces stmt : expr ';' and the other reduces stmt : decl, after which both parsers are in an identical state: they’ve seen ‘prog stmt’ and have the same unprocessed input remaining. We say that these parses have merged.

At this point, the GLR parser requires a specification in the grammar of how to choose between the competing parses. In the example above, the two %dprec declarations specify that Bison is to give precedence to the parse that interprets the example as a decl, which implies that x is a declarator. The parser therefore prints

"x" y z + T <init-declare>

The %dprec declarations only come into play when more than one parse survives. Consider a different input string for this parser:

T (x) + y;

This is another example of using GLR to parse an unambiguous construct, as shown in the previous section (see Using GLR on Unambiguous Grammars). Here, there is no ambiguity (this cannot be parsed as a declaration). However, at the time the Bison parser encounters x, it does not have enough information to resolve the reduce/reduce conflict (again, between x as an expr or a declarator). In this case, no precedence declaration is used. Again, the parser splits into two, one assuming that x is an expr, and the other assuming x is a declarator. The second of these parsers then vanishes when it sees +, and the parser prints

x T <cast> y +

Suppose that instead of resolving the ambiguity, you wanted to see all the possibilities. For this purpose, you must merge the semantic actions of the two possible parsers, rather than choosing one over the other. To do so, you could change the declaration of stmt as follows:

stmt:
  expr ';'  %merge <stmt_merge>
| decl      %merge <stmt_merge>
;

and define the stmt_merge function as:

static YYSTYPE
stmt_merge (YYSTYPE x0, YYSTYPE x1)
{
  printf ("<OR> ");
  return "";
}

with an accompanying forward declaration in the C declarations at the beginning of the file:

%{
  static YYSTYPE stmt_merge (YYSTYPE x0, YYSTYPE x1);
%}

With these declarations, the resulting parser parses the first example as both an expr and a decl, and prints

"x" y z + T <init-declare> x T <cast> y z + = <OR>

Bison requires that all of the productions that participate in any particular merge have identical ‘%merge’ clauses. Otherwise, the ambiguity would be unresolvable, and the parser will report an error during any parse that results in the offending merge.

The signature of the merger depends on the type of the symbol. In the previous example, the merged-to symbol (stmt) does not have a specific type, and the merger is

YYSTYPE stmt_merge (YYSTYPE x0, YYSTYPE x1);

However, if stmt had a declared type, e.g.,

%type <Node *> stmt;

or

%union {
  Node *node;
  ...
};

%type <node> stmt;

then the prototype of the merger must be:

Node *stmt_merge (YYSTYPE x0, YYSTYPE x1);

(This signature might be a mistake originally, and maybe it should have been ‘Node *stmt_merge (Node *x0, Node *x1)’. If you have an opinion about it, please let us know.)

1.5.3 GLR Semantic Actions

The nature of GLR parsing and the structure of the generated parsers give rise to certain restrictions on semantic values and actions.

• Deferred semantic actions
• YYERROR
• Restrictions on semantic values and locations

1.5.4 Controlling a Parse with Arbitrary Predicates

In addition to the %dprec and %merge directives, GLR parsers allow you to reject parses on the basis of arbitrary computations executed in user code, without having Bison treat this rejection as an error if there are alternative parses. For example,

widget:
  %?{  new_syntax } "widget" id new_args  { $$ = f($3, $4); }
| %?{ !new_syntax } "widget" id old_args  { $$ = f($3, $4); }
;

is one way to allow the same parser to handle two different syntaxes for widgets. The clause preceded by %? is treated like an ordinary midrule action, except that its text is handled as an expression and is always evaluated immediately (even when in nondeterministic mode). If the expression yields 0 (false), the clause is treated as a syntax error, which, in a nondeterministic parser, causes the stack in which it is reduced to die. In a deterministic parser, it acts like YYERROR.

As the example shows, predicates otherwise look like semantic actions, and therefore you must take them into account when determining the numbers to use for denoting the semantic values of right-hand side symbols. Predicate actions, however, have no defined value, and may not be given labels.

There is a subtle difference between semantic predicates and ordinary actions in nondeterministic mode, since the latter are deferred. For example, we could try to rewrite the previous example as

widget:
  { if (!new_syntax) YYERROR; }
    "widget" id new_args  { $$ = f($3, $4); }
|  { if (new_syntax) YYERROR; }
    "widget" id old_args  { $$ = f($3, $4); }
;

(reversing the sense of the predicate tests to cause an error when they are false). However, this does not have the same effect if new_args and old_args have overlapping syntax. Since the midrule actions testing new_syntax are deferred, a GLR parser first encounters the unresolved ambiguous reduction for cases where new_args and old_args recognize the same string before performing the tests of new_syntax. It therefore reports an error.

Finally, be careful in writing predicates: deferred actions have not been evaluated, so that using them in a predicate will have undefined effects.

2.1.1 Declarations for rpcalc

Here are the C and Bison declarations for the Reverse Polish Notation calculator. As in C, comments are placed between ‘/*…*/’ or after ‘//’.

/* Reverse Polish Notation calculator. */

%{
  #include <stdio.h>
  #include <math.h>
  int yylex (void);
  void yyerror (char const *);
%}

%define api.value.type {double}
%token NUM

%% /* Grammar rules and actions follow. */

The declarations section (see The prologue) contains two preprocessor directives and two forward declarations.

The #include directive is used to declare the exponentiation function pow.

The forward declarations for yylex and yyerror are needed because the C language requires that functions be declared before they are used. These functions will be defined in the epilogue, but the parser calls them so they must be declared in the prologue.

The second section, Bison declarations, provides information to Bison about the tokens and their types (see The Bison Declarations Section).

The %define directive defines the variable api.value.type, thus specifying the C data type for semantic values of both tokens and groupings (see Data Types of Semantic Values). The Bison parser will use whatever type api.value.type is defined as; if you don’t define it, int is the default. Because we specify ‘{double}’, each token and each expression has an associated value, which is a floating point number. C code can use YYSTYPE to refer to the value api.value.type.

Each terminal symbol that is not a single-character literal must be declared. (Single-character literals normally don’t need to be declared.) In this example, all the arithmetic operators are designated by single-character literals, so the only terminal symbol that needs to be declared is NUM, the token kind for numeric constants.

2.1.2 Grammar Rules for rpcalc

Here are the grammar rules for the Reverse Polish Notation calculator.

input:
  %empty
| input line
;

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

exp:
  NUM
| exp exp '+'   { $$ = $1 + $2;      }
| exp exp '-'   { $$ = $1 - $2;      }
| exp exp '*'   { $$ = $1 * $2;      }
| exp exp '/'   { $$ = $1 / $2;      }
| exp exp '^'   { $$ = pow ($1, $2); }  /* Exponentiation */
| exp 'n'       { $$ = -$1;          }  /* Unary minus   */
;

%%

The groupings of the rpcalc “language” defined here are the expression (given the name exp), the line of input (line), and the complete input transcript (input). Each of these nonterminal symbols has several alternate rules, joined by the vertical bar ‘|’ which is read as “or”. The following sections explain what these rules mean.

The semantics of the language is determined by the actions taken when a grouping is recognized. The actions are the C code that appears inside braces. See Actions.

You must specify these actions in C, but Bison provides the means for passing semantic values between the rules. In each action, the pseudo-variable $$ stands for the semantic value for the grouping that the rule is going to construct. Assigning a value to $$ is the main job of most actions. The semantic values of the components of the rule are referred to as $1, $2, and so on.

• Explanation of input
• Explanation of line
• Explanation of exp

input:
  %empty
| input line
;

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

exp:
  NUM
| exp exp '+'     { $$ = $1 + $2;    }
| exp exp '-'     { $$ = $1 - $2;    }
…
;

exp: NUM;
exp: exp exp '+'  { $$ = $1 + $2; };
exp: exp exp '-'  { $$ = $1 - $2; };
…

exp: NUM | exp exp '+' {$$ = $1 + $2; } | … ;

exp:
  NUM
| exp exp '+'    { $$ = $1 + $2; }
| …
;

2.1.3 The rpcalc Lexical Analyzer

The lexical analyzer’s job is low-level parsing: converting characters or sequences of characters into tokens. The Bison parser gets its tokens by calling the lexical analyzer. See The Lexical Analyzer Function yylex.

Only a simple lexical analyzer is needed for the RPN calculator. This lexical analyzer skips blanks and tabs, then reads in numbers as double and returns them as NUM tokens. Any other character that isn’t part of a number is a separate token. Note that the token-code for such a single-character token is the character itself.

The return value of the lexical analyzer function is a numeric code which represents a token kind. The same text used in Bison rules to stand for this token kind is also a C expression for the numeric code of the kind. This works in two ways. If the token kind is a character literal, then its numeric code is that of the character; you can use the same character literal in the lexical analyzer to express the number. If the token kind is an identifier, that identifier is defined by Bison as a C enum whose definition is the appropriate code. In this example, therefore, NUM becomes an enum for yylex to use.

The semantic value of the token (if it has one) is stored into the global variable yylval, which is where the Bison parser will look for it. (The C data type of yylval is YYSTYPE, whose value was defined at the beginning of the grammar via ‘%define api.value.type {double}’; see Declarations for rpcalc.)

A token kind code of zero is returned if the end-of-input is encountered. (Bison recognizes any nonpositive value as indicating end-of-input.)

Here is the code for the lexical analyzer:

/* The lexical analyzer returns a double floating point
   number on the stack and the token NUM, or the numeric code
   of the character read if not a number.  It skips all blanks
   and tabs, and returns 0 for end-of-input. */

#include <ctype.h>
#include <stdlib.h>

int
yylex (void)
{
  int c = getchar ();
  /* Skip white space. */
  while (c == ' ' || c == '\t')
    c = getchar ();

  /* Process numbers. */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      if (scanf ("%lf", &yylval) != 1)
        abort ();
      return NUM;
    }

  /* Return end-of-input. */
  else if (c == EOF)
    return YYEOF;
  /* Return a single char. */
  else
    return c;
}

2.1.4 The Controlling Function

In keeping with the spirit of this example, the controlling function is kept to the bare minimum. The only requirement is that it call yyparse to start the process of parsing.

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

2.1.5 The Error Reporting Routine

When yyparse detects a syntax error, it calls the error reporting function yyerror to print an error message (usually but not always "syntax error"). It is up to the programmer to supply yyerror (see Parser C-Language Interface), so here is the definition we will use:

#include <stdio.h>

/* Called by yyparse on error. */
void
yyerror (char const *s)
{
  fprintf (stderr, "%s\n", s);
}

After yyerror returns, the Bison parser may recover from the error and continue parsing if the grammar contains a suitable error rule (see Error Recovery). Otherwise, yyparse returns nonzero. We have not written any error rules in this example, so any invalid input will cause the calculator program to exit. This is not clean behavior for a real calculator, but it is adequate for the first example.

2.1.6 Running Bison to Make the Parser

Before running Bison to produce a parser, we need to decide how to arrange all the source code in one or more source files. For such a simple example, the easiest thing is to put everything in one file, the grammar file. The definitions of yylex, yyerror and main go at the end, in the epilogue of the grammar file (see The Overall Layout of a Bison Grammar).

For a large project, you would probably have several source files, and use make to arrange to recompile them.

With all the source in the grammar file, you use the following command to convert it into a parser implementation file:

$ bison file.y

In this example, the grammar file is called rpcalc.y (for “Reverse Polish CALCulator”). Bison produces a parser implementation file named file.tab.c, removing the ‘.y’ from the grammar file name. The parser implementation file contains the source code for yyparse. The additional functions in the grammar file (yylex, yyerror and main) are copied verbatim to the parser implementation file.

2.1.7 Compiling the Parser Implementation File

Here is how to compile and run the parser implementation file:

# List files in current directory.
$ ls
rpcalc.tab.c  rpcalc.y

# Compile the Bison parser.
# -lm tells compiler to search math library for pow.
$ cc -lm -o rpcalc rpcalc.tab.c

# List files again.
$ ls
rpcalc  rpcalc.tab.c  rpcalc.y

The file rpcalc now contains the executable code. Here is an example session using rpcalc.

$ rpcalc
4 9 +
⇒ 13
3 7 + 3 4 5 *+-
⇒ -13
3 7 + 3 4 5 * + - n              Note the unary minus, ‘n’
⇒ 13
5 6 / 4 n +
⇒ -3.166666667
3 4 ^                            Exponentiation
⇒ 81
^D                               End-of-file indicator
$

2.4.1 Declarations for ltcalc

The C and Bison declarations for the location tracking calculator are the same as the declarations for the infix notation calculator.

/* Location tracking calculator. */

%{
  #include <math.h>
  int yylex (void);
  void yyerror (char const *);
%}

/* Bison declarations. */
%define api.value.type {int}
%token NUM

%left '-' '+'
%left '*' '/'
%precedence NEG
%right '^'

%% /* The grammar follows. */

Note there are no declarations specific to locations. Defining a data type for storing locations is not needed: we will use the type provided by default (see Data Type of Locations), which is a four member structure with the following integer fields: first_line, first_column, last_line and last_column. By conventions, and in accordance with the GNU Coding Standards and common practice, the line and column count both start at 1.

2.4.2 Grammar Rules for ltcalc

Whether handling locations or not has no effect on the syntax of your language. Therefore, grammar rules for this example will be very close to those of the previous example: we will only modify them to benefit from the new information.

Here, we will use locations to report divisions by zero, and locate the wrong expressions or subexpressions.

input:
  %empty
| input line
;

line:
  '\n'
| exp '\n' { printf ("%d\n", $1); }
;

exp:
  NUM
| exp '+' exp   { $$ = $1 + $3; }
| exp '-' exp   { $$ = $1 - $3; }
| exp '*' exp   { $$ = $1 * $3; }

| exp '/' exp
    {
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

| '-' exp %prec NEG     { $$ = -$2; }
| exp '^' exp           { $$ = pow ($1, $3); }
| '(' exp ')'           { $$ = $2; }

This code shows how to reach locations inside of semantic actions, by using the pseudo-variables @n for rule components, and the pseudo-variable @$ for groupings.

We don’t need to assign a value to @$: the output parser does it automatically. By default, before executing the C code of each action, @$ is set to range from the beginning of @1 to the end of @n, for a rule with n components. This behavior can be redefined (see Default Action for Locations), and for very specific rules, @$ can be computed by hand.

2.4.3 The ltcalc Lexical Analyzer.

Until now, we relied on Bison’s defaults to enable location tracking. The next step is to rewrite the lexical analyzer, and make it able to feed the parser with the token locations, as it already does for semantic values.

To this end, we must take into account every single character of the input text, to avoid the computed locations of being fuzzy or wrong:

int
yylex (void)
{
  int c;

  /* Skip white space. */
  while ((c = getchar ()) == ' ' || c == '\t')
    ++yylloc.last_column;

  /* Step. */
  yylloc.first_line = yylloc.last_line;
  yylloc.first_column = yylloc.last_column;

  /* Process numbers. */
  if (isdigit (c))
    {
      yylval = c - '0';
      ++yylloc.last_column;
      while (isdigit (c = getchar ()))
        {
          ++yylloc.last_column;
          yylval = yylval * 10 + c - '0';
        }
      ungetc (c, stdin);
      return NUM;
    }

  /* Return end-of-input. */
  if (c == EOF)
    return YYEOF;

  /* Return a single char, and update location. */
  if (c == '\n')
    {
      ++yylloc.last_line;
      yylloc.last_column = 0;
    }
  else
    ++yylloc.last_column;
  return c;
}

Basically, the lexical analyzer performs the same processing as before: it skips blanks and tabs, and reads numbers or single-character tokens. In addition, it updates yylloc, the global variable (of type YYLTYPE) containing the token’s location.

Now, each time this function returns a token, the parser has its kind as well as its semantic value, and its location in the text. The last needed change is to initialize yylloc, for example in the controlling function:

int
main (void)
{
  yylloc.first_line = yylloc.last_line = 1;
  yylloc.first_column = yylloc.last_column = 0;
  return yyparse ();
}

Remember that computing locations is not a matter of syntax. Every character must be associated to a location update, whether it is in valid input, in comments, in literal strings, and so on.

2.5.1 Declarations for mfcalc

Here are the C and Bison declarations for the multi-function calculator.

%{
  #include <stdio.h>  /* For printf, etc. */
  #include <math.h>   /* For pow, used in the grammar. */
  #include "calc.h"   /* Contains definition of 'symrec'. */
  int yylex (void);
  void yyerror (char const *);
%}

%define api.value.type union /* Generate YYSTYPE from these types: */
%token <double>  NUM     /* Double precision number. */
%token <symrec*> VAR FUN /* Symbol table pointer: variable/function. */
%nterm <double>  exp

%precedence '='
%left '-' '+'
%left '*' '/'
%precedence NEG /* negation--unary minus */
%right '^'      /* exponentiation */

The above grammar introduces only two new features of the Bison language. These features allow semantic values to have various data types (see More Than One Value Type).

The special union value assigned to the %define variable api.value.type specifies that the symbols are defined with their data types. Bison will generate an appropriate definition of YYSTYPE to store these values.

Since values can now have various types, it is necessary to associate a type with each grammar symbol whose semantic value is used. These symbols are NUM, VAR, FUN, and exp. Their declarations are augmented with their data type (placed between angle brackets). For instance, values of NUM are stored in double.

The Bison construct %nterm is used for declaring nonterminal symbols, just as %token is used for declaring token kinds. Previously we did not use %nterm before because nonterminal symbols are normally declared implicitly by the rules that define them. But exp must be declared explicitly so we can specify its value type. See Nonterminal Symbols.

2.5.2 Grammar Rules for mfcalc

Here are the grammar rules for the multi-function calculator. Most of them are copied directly from calc; three rules, those which mention VAR or FUN, are new.

%% /* The grammar follows. */

input:
  %empty
| input line
;

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

exp:
  NUM
| VAR                { $$ = $1->value.var;              }
| VAR '=' exp        { $$ = $3; $1->value.var = $3;     }
| FUN '(' exp ')'    { $$ = $1->value.fun ($3);         }
| exp '+' exp        { $$ = $1 + $3;                    }
| exp '-' exp        { $$ = $1 - $3;                    }
| exp '*' exp        { $$ = $1 * $3;                    }
| exp '/' exp        { $$ = $1 / $3;                    }
| '-' exp  %prec NEG { $$ = -$2;                        }
| exp '^' exp        { $$ = pow ($1, $3);               }
| '(' exp ')'        { $$ = $2;                         }
;

/* End of grammar. */
%%

2.5.3 The mfcalc Symbol Table

The multi-function calculator requires a symbol table to keep track of the names and meanings of variables and functions. This doesn’t affect the grammar rules (except for the actions) or the Bison declarations, but it requires some additional C functions for support.

The symbol table itself consists of a linked list of records. Its definition, which is kept in the header calc.h, is as follows. It provides for either functions or variables to be placed in the table.

/* Function type. */
typedef double (func_t) (double);

/* Data type for links in the chain of symbols. */
struct symrec
{
  char *name;  /* name of symbol */
  int type;    /* type of symbol: either VAR or FUN */
  union
  {
    double var;    /* value of a VAR */
    func_t *fun;   /* value of a FUN */
  } value;
  struct symrec *next;  /* link field */
};

typedef struct symrec symrec;

/* The symbol table: a chain of 'struct symrec'. */
extern symrec *sym_table;

symrec *putsym (char const *name, int sym_type);
symrec *getsym (char const *name);

The new version of main will call init_table to initialize the symbol table:

struct init
{
  char const *name;
  func_t *fun;
};

struct init const funs[] =
{
  { "atan", atan },
  { "cos",  cos  },
  { "exp",  exp  },
  { "ln",   log  },
  { "sin",  sin  },
  { "sqrt", sqrt },
  { 0, 0 },
};

/* The symbol table: a chain of 'struct symrec'. */
symrec *sym_table;

/* Put functions in table. */
static void
init_table (void)

{
  for (int i = 0; funs[i].name; i++)
    {
      symrec *ptr = putsym (funs[i].name, FUN);
      ptr->value.fun = funs[i].fun;
    }
}

By simply editing the initialization list and adding the necessary include files, you can add additional functions to the calculator.

Two important functions allow look-up and installation of symbols in the symbol table. The function putsym is passed a name and the kind (VAR or FUN) of the object to be installed. The object is linked to the front of the list, and a pointer to the object is returned. The function getsym is passed the name of the symbol to look up. If found, a pointer to that symbol is returned; otherwise zero is returned.

/* The mfcalc code assumes that malloc and realloc
   always succeed, and that integer calculations
   never overflow.  Production-quality code should
   not make these assumptions.  */
#include <assert.h>
#include <stdlib.h> /* malloc, realloc. */
#include <string.h> /* strlen. */

symrec *
putsym (char const *name, int sym_type)
{
  symrec *res = (symrec *) malloc (sizeof (symrec));
  res->name = strdup (name);
  res->type = sym_type;
  res->value.var = 0; /* Set value to 0 even if fun. */
  res->next = sym_table;
  sym_table = res;
  return res;
}

symrec *
getsym (char const *name)
{
  for (symrec *p = sym_table; p; p = p->next)
    if (strcmp (p->name, name) == 0)
      return p;
  return NULL;
}

2.5.4 The mfcalc Lexer

The function yylex must now recognize variables, numeric values, and the single-character arithmetic operators. Strings of alphanumeric characters with a leading letter are recognized as either variables or functions depending on what the symbol table says about them.

The string is passed to getsym for look up in the symbol table. If the name appears in the table, a pointer to its location and its type (VAR or FUN) is returned to yyparse. If it is not already in the table, then it is installed as a VAR using putsym. Again, a pointer and its type (which must be VAR) is returned to yyparse.

No change is needed in the handling of numeric values and arithmetic operators in yylex.

#include <ctype.h>
#include <stddef.h>

int
yylex (void)
{
  int c = getchar ();

  /* Ignore white space, get first nonwhite character. */
  while (c == ' ' || c == '\t')
    c = getchar ();

  if (c == EOF)
    return YYEOF;

  /* Char starts a number => parse the number. */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      if (scanf ("%lf", &yylval.NUM) != 1)
        abort ();
      return NUM;
    }

Bison generated a definition of YYSTYPE with a member named NUM to store value of NUM symbols.

  /* Char starts an identifier => read the name. */
  if (isalpha (c))
    {
      static ptrdiff_t bufsize = 0;
      static char *symbuf = 0;

      ptrdiff_t i = 0;
      do

        {
          /* If buffer is full, make it bigger. */
          if (bufsize <= i)
            {
              bufsize = 2 * bufsize + 40;
              symbuf = realloc (symbuf, (size_t) bufsize);
            }
          /* Add this character to the buffer. */
          symbuf[i++] = (char) c;
          /* Get another character. */
          c = getchar ();
        }

      while (isalnum (c));

      ungetc (c, stdin);
      symbuf[i] = '\0';

      symrec *s = getsym (symbuf);
      if (!s)
        s = putsym (symbuf, VAR);
      yylval.VAR = s; /* or yylval.FUN = s. */
      return s->type;
    }

  /* Any other character is a token by itself. */
  return c;
}

2.5.5 The mfcalc Main

The error reporting function is unchanged, and the new version of main includes a call to init_table and sets the yydebug on user demand (See Tracing Your Parser, for details):

/* Called by yyparse on error. */
void yyerror (char const *s)
{
  fprintf (stderr, "%s\n", s);
}

int main (int argc, char const* argv[])

{
  /* Enable parse traces on option -p. */
  if (argc == 2 && strcmp(argv[1], "-p") == 0)
    yydebug = 1;

  init_table ();
  return yyparse ();
}

This program is both powerful and flexible. You may easily add new functions, and it is a simple job to modify this code to install predefined variables such as pi or e as well.

3.1.1 The prologue

The Prologue section contains macro definitions and declarations of functions and variables that are used in the actions in the grammar rules. These are copied to the beginning of the parser implementation file so that they precede the definition of yyparse. You can use ‘#include’ to get the declarations from a header file. If you don’t need any C declarations, you may omit the ‘%{’ and ‘%}’ delimiters that bracket this section.

The Prologue section is terminated by the first occurrence of ‘%}’ that is outside a comment, a string literal, or a character constant.

You may have more than one Prologue section, intermixed with the Bison declarations. This allows you to have C and Bison declarations that refer to each other. For example, the %union declaration may use types defined in a header file, and you may wish to prototype functions that take arguments of type YYSTYPE. This can be done with two Prologue blocks, one before and one after the %union declaration.

%{
  #define _GNU_SOURCE
  #include <stdio.h>
  #include "ptypes.h"
%}

%union {
  long n;
  tree t;  /* tree is defined in ptypes.h. */
}

%{
  static void print_token (yytoken_kind_t token, YYSTYPE val);
%}

…

When in doubt, it is usually safer to put prologue code before all Bison declarations, rather than after. For example, any definitions of feature test macros like _GNU_SOURCE or _POSIX_C_SOURCE should appear before all Bison declarations, as feature test macros can affect the behavior of Bison-generated #include directives.

3.1.2 Prologue Alternatives

The functionality of Prologue sections can often be subtle and inflexible. As an alternative, Bison provides a %code directive with an explicit qualifier field, which identifies the purpose of the code and thus the location(s) where Bison should generate it. For C/C++, the qualifier can be omitted for the default location, or it can be one of requires, provides, top. See %code Summary.

Look again at the example of the previous section:

%{
  #define _GNU_SOURCE
  #include <stdio.h>
  #include "ptypes.h"
%}

%union {
  long n;
  tree t;  /* tree is defined in ptypes.h. */
}

%{
  static void print_token (yytoken_kind_t token, YYSTYPE val);
%}

…

Notice that there are two Prologue sections here, but there’s a subtle distinction between their functionality. For example, if you decide to override Bison’s default definition for YYLTYPE, in which Prologue section should you write your new definition?⁵ You should write it in the first since Bison will insert that code into the parser implementation file before the default YYLTYPE definition. In which Prologue section should you prototype an internal function, trace_token, that accepts YYLTYPE and yytoken_kind_t as arguments? You should prototype it in the second since Bison will insert that code after the YYLTYPE and yytoken_kind_t definitions.

This distinction in functionality between the two Prologue sections is established by the appearance of the %union between them. This behavior raises a few questions. First, why should the position of a %union affect definitions related to YYLTYPE and yytoken_kind_t? Second, what if there is no %union? In that case, the second kind of Prologue section is not available. This behavior is not intuitive.

To avoid this subtle %union dependency, rewrite the example using a %code top and an unqualified %code. Let’s go ahead and add the new YYLTYPE definition and the trace_token prototype at the same time:

%code top {
  #define _GNU_SOURCE
  #include <stdio.h>

  /* WARNING: The following code really belongs
   * in a '%code requires'; see below. */

  #include "ptypes.h"
  #define YYLTYPE YYLTYPE
  typedef struct YYLTYPE
  {
    int first_line;
    int first_column;
    int last_line;
    int last_column;
    char *filename;
  } YYLTYPE;
}

%union {
  long n;
  tree t;  /* tree is defined in ptypes.h. */
}

%code {
  static void print_token (yytoken_kind_t token, YYSTYPE val);
  static void trace_token (yytoken_kind_t token, YYLTYPE loc);
}

…

In this way, %code top and the unqualified %code achieve the same functionality as the two kinds of Prologue sections, but it’s always explicit which kind you intend. Moreover, both kinds are always available even in the absence of %union.

The %code top block above logically contains two parts. The first two lines before the warning need to appear near the top of the parser implementation file. The first line after the warning is required by YYSTYPE and thus also needs to appear in the parser implementation file. However, if you’ve instructed Bison to generate a parser header file (see Bison Declaration Summary), you probably want that line to appear before the YYSTYPE definition in that header file as well. The YYLTYPE definition should also appear in the parser header file to override the default YYLTYPE definition there.

In other words, in the %code top block above, all but the first two lines are dependency code required by the YYSTYPE and YYLTYPE definitions. Thus, they belong in one or more %code requires:

%code top {
  #define _GNU_SOURCE
  #include <stdio.h>
}

%code requires {
  #include "ptypes.h"
}

%union {
  long n;
  tree t;  /* tree is defined in ptypes.h. */
}

%code requires {
  #define YYLTYPE YYLTYPE
  typedef struct YYLTYPE
  {
    int first_line;
    int first_column;
    int last_line;
    int last_column;
    char *filename;
  } YYLTYPE;
}

%code {
  static void print_token (yytoken_kind_t token, YYSTYPE val);
  static void trace_token (yytoken_kind_t token, YYLTYPE loc);
}

…

Now Bison will insert #include "ptypes.h" and the new YYLTYPE definition before the Bison-generated YYSTYPE and YYLTYPE definitions in both the parser implementation file and the parser header file. (By the same reasoning, %code requires would also be the appropriate place to write your own definition for YYSTYPE.)

When you are writing dependency code for YYSTYPE and YYLTYPE, you should prefer %code requires over %code top regardless of whether you instruct Bison to generate a parser header file. When you are writing code that you need Bison to insert only into the parser implementation file and that has no special need to appear at the top of that file, you should prefer the unqualified %code over %code top. These practices will make the purpose of each block of your code explicit to Bison and to other developers reading your grammar file. Following these practices, we expect the unqualified %code and %code requires to be the most important of the four Prologue alternatives.

At some point while developing your parser, you might decide to provide trace_token to modules that are external to your parser. Thus, you might wish for Bison to insert the prototype into both the parser header file and the parser implementation file. Since this function is not a dependency required by YYSTYPE or YYLTYPE, it doesn’t make sense to move its prototype to a %code requires. More importantly, since it depends upon YYLTYPE and yytoken_kind_t, %code requires is not sufficient. Instead, move its prototype from the unqualified %code to a %code provides:

%code top {
  #define _GNU_SOURCE
  #include <stdio.h>
}

%code requires {
  #include "ptypes.h"
}

%union {
  long n;
  tree t;  /* tree is defined in ptypes.h. */
}

%code requires {
  #define YYLTYPE YYLTYPE
  typedef struct YYLTYPE
  {
    int first_line;
    int first_column;
    int last_line;
    int last_column;
    char *filename;
  } YYLTYPE;
}

%code provides {
  void trace_token (yytoken_kind_t token, YYLTYPE loc);
}

%code {
  static void print_token (FILE *file, int token, YYSTYPE val);
}

…

Bison will insert the trace_token prototype into both the parser header file and the parser implementation file after the definitions for yytoken_kind_t, YYLTYPE, and YYSTYPE.

The above examples are careful to write directives in an order that reflects the layout of the generated parser implementation and header files: %code top, %code requires, %code provides, and then %code. While your grammar files may generally be easier to read if you also follow this order, Bison does not require it. Instead, Bison lets you choose an organization that makes sense to you.

You may declare any of these directives multiple times in the grammar file. In that case, Bison concatenates the contained code in declaration order. This is the only way in which the position of one of these directives within the grammar file affects its functionality.

The result of the previous two properties is greater flexibility in how you may organize your grammar file. For example, you may organize semantic-type-related directives by semantic type:

%code requires { #include "type1.h" }
%union { type1 field1; }
%destructor { type1_free ($$); } <field1>
%printer { type1_print (yyo, $$); } <field1>

%code requires { #include "type2.h" }
%union { type2 field2; }
%destructor { type2_free ($$); } <field2>
%printer { type2_print (yyo, $$); } <field2>

You could even place each of the above directive groups in the rules section of the grammar file next to the set of rules that uses the associated semantic type. (In the rules section, you must terminate each of those directives with a semicolon.) And you don’t have to worry that some directive (like a %union) in the definitions section is going to adversely affect their functionality in some counter-intuitive manner just because it comes first. Such an organization is not possible using Prologue sections.

This section has been concerned with explaining the advantages of the four Prologue alternatives over the original Yacc Prologue. However, in most cases when using these directives, you shouldn’t need to think about all the low-level ordering issues discussed here. Instead, you should simply use these directives to label each block of your code according to its purpose and let Bison handle the ordering. %code is the most generic label. Move code to %code requires, %code provides, or %code top as needed.

3.1.3 The Bison Declarations Section

The Bison declarations section contains declarations that define terminal and nonterminal symbols, specify precedence, and so on. In some simple grammars you may not need any declarations. See Bison Declarations.

3.1.4 The Grammar Rules Section

The grammar rules section contains one or more Bison grammar rules, and nothing else. See Grammar Rules.

There must always be at least one grammar rule, and the first ‘%%’ (which precedes the grammar rules) may never be omitted even if it is the first thing in the file.

3.1.5 The epilogue

The Epilogue is copied verbatim to the end of the parser implementation file, just as the Prologue is copied to the beginning. This is the most convenient place to put anything that you want to have in the parser implementation file but which need not come before the definition of yyparse. For example, the definitions of yylex and yyerror often go here. Because C requires functions to be declared before being used, you often need to declare functions like yylex and yyerror in the Prologue, even if you define them in the Epilogue. See Parser C-Language Interface.

If the last section is empty, you may omit the ‘%%’ that separates it from the grammar rules.

The Bison parser itself contains many macros and identifiers whose names start with ‘yy’ or ‘YY’, so it is a good idea to avoid using any such names (except those documented in this manual) in the epilogue of the grammar file.

3.3.1 Syntax of Grammar Rules

A Bison grammar rule has the following general form:

result: components…;

where result is the nonterminal symbol that this rule describes, and components are various terminal and nonterminal symbols that are put together by this rule (see Symbols, Terminal and Nonterminal).

For example,

exp: exp '+' exp;

says that two groupings of type exp, with a ‘+’ token in between, can be combined into a larger grouping of type exp.

White space in rules is significant only to separate symbols. You can add extra white space as you wish.

Scattered among the components can be actions that determine the semantics of the rule. An action looks like this:

{C statements}

This is an example of braced code, that is, C code surrounded by braces, much like a compound statement in C. Braced code can contain any sequence of C tokens, so long as its braces are balanced. Bison does not check the braced code for correctness directly; it merely copies the code to the parser implementation file, where the C compiler can check it.

Within braced code, the balanced-brace count is not affected by braces within comments, string literals, or character constants, but it is affected by the C digraphs ‘<%’ and ‘%>’ that represent braces. At the top level braced code must be terminated by ‘}’ and not by a digraph. Bison does not look for trigraphs, so if braced code uses trigraphs you should ensure that they do not affect the nesting of braces or the boundaries of comments, string literals, or character constants.

Usually there is only one action and it follows the components. See Actions.

Multiple rules for the same result can be written separately or can be joined with the vertical-bar character ‘|’ as follows:

result:
  rule1-components…
| rule2-components…
…
;

They are still considered distinct rules even when joined in this way.

3.3.2 Empty Rules

A rule is said to be empty if its right-hand side (components) is empty. It means that result in the previous example can match the empty string. As another example, here is how to define an optional semicolon:

semicolon.opt: | ";";

It is easy not to see an empty rule, especially when | is used. The %empty directive allows to make explicit that a rule is empty on purpose:

semicolon.opt:
  %empty
| ";"
;

Flagging a non-empty rule with %empty is an error. If run with -Wempty-rule, bison will report empty rules without %empty. Using %empty enables this warning, unless -Wno-empty-rule was specified.

The %empty directive is a Bison extension, it does not work with Yacc. To remain compatible with POSIX Yacc, it is customary to write a comment ‘/* empty */’ in each rule with no components:

semicolon.opt:
  /* empty */
| ";"
;

3.3.3 Recursive Rules

A rule is called recursive when its result nonterminal appears also on its right hand side. Nearly all Bison grammars need to use recursion, because that is the only way to define a sequence of any number of a particular thing. Consider this recursive definition of a comma-separated sequence of one or more expressions:

expseq1:
  exp
| expseq1 ',' exp
;

Since the recursive use of expseq1 is the leftmost symbol in the right hand side, we call this left recursion. By contrast, here the same construct is defined using right recursion:

expseq1:
  exp
| exp ',' expseq1
;

Any kind of sequence can be defined using either left recursion or right recursion, but you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space. Right recursion uses up space on the Bison stack in proportion to the number of elements in the sequence, because all the elements must be shifted onto the stack before the rule can be applied even once. See The Bison Parser Algorithm, for further explanation of this.

Indirect or mutual recursion occurs when the result of the rule does not appear directly on its right hand side, but does appear in rules for other nonterminals which do appear on its right hand side.

For example:

expr:
  primary
| primary '+' primary
;

primary:
  constant
| '(' expr ')'
;

defines two mutually-recursive nonterminals, since each refers to the other.

3.4.1 Data Types of Semantic Values

In a simple program it may be sufficient to use the same data type for the semantic values of all language constructs. This was true in the RPN and infix calculator examples (see Reverse Polish Notation Calculator).

Bison normally uses the type int for semantic values if your program uses the same data type for all language constructs. To specify some other type, define the %define variable api.value.type like this:

%define api.value.type {double}

or

%define api.value.type {struct semantic_value_type}

The value of api.value.type should be a type name that does not contain parentheses or square brackets.

Alternatively in C, instead of relying of Bison’s %define support, you may rely on the C preprocessor and define YYSTYPE as a macro:

#define YYSTYPE double

This macro definition must go in the prologue of the grammar file (see Outline of a Bison Grammar). If compatibility with POSIX Yacc matters to you, use this. Note however that Bison cannot know YYSTYPE’s value, not even whether it is defined, so there are services it cannot provide. Besides this works only for C.

3.4.2 More Than One Value Type

In most programs, you will need different data types for different kinds of tokens and groupings. For example, a numeric constant may need type int or long, while a string constant needs type char *, and an identifier might need a pointer to an entry in the symbol table.

To use more than one data type for semantic values in one parser, Bison requires you to do two things:

• Specify the entire collection of possible data types. There are several options:
  • let Bison compute the union type from the tags you assign to symbols;
  • use the %union Bison declaration (see The Union Declaration);
  • define the %define variable api.value.type to be a union type whose members are the type tags (see Providing a Structured Semantic Value Type);
  • use a typedef or a #define to define YYSTYPE to be a union type whose member names are the type tags.
• Choose one of those types for each symbol (terminal or nonterminal) for which semantic values are used. This is done for tokens with the %token Bison declaration (see Token Kind Names) and for groupings with the %nterm/%type Bison declarations (see Nonterminal Symbols).

3.4.3 Generating the Semantic Value Type

The special value union of the %define variable api.value.type instructs Bison that the type tags (used with the %token, %nterm and %type directives) are genuine types, not names of members of YYSTYPE.

For example:

%define api.value.type union
%token <int> INT "integer"
%token <int> 'n'
%nterm <int> expr
%token <char const *> ID "identifier"

generates an appropriate value of YYSTYPE to support each symbol type. The name of the member of YYSTYPE for tokens than have a declared identifier id (such as INT and ID above, but not 'n') is id. The other symbols have unspecified names on which you should not depend; instead, relying on C casts to access the semantic value with the appropriate type:

/* For an "integer". */
yylval.INT = 42;
return INT;

/* For an 'n', also declared as int. */
*((int*)&yylval) = 42;
return 'n';

/* For an "identifier". */
yylval.ID = "42";
return ID;

If the %define variable api.token.prefix is defined (see %define Summary), then it is also used to prefix the union member names. For instance, with ‘%define api.token.prefix {TOK_}’:

/* For an "integer". */
yylval.TOK_INT = 42;
return TOK_INT;

This Bison extension cannot work if %yacc (or -y/--yacc) is enabled, as POSIX mandates that Yacc generate tokens as macros (e.g., ‘#define INT 258’, or ‘#define TOK_INT 258’).

A similar feature is provided for C++ that in addition overcomes C++ limitations (that forbid non-trivial objects to be part of a union): ‘%define api.value.type variant’, see C++ Variants.

3.4.4 The Union Declaration

The %union declaration specifies the entire collection of possible data types for semantic values. The keyword %union is followed by braced code containing the same thing that goes inside a union in C.

For example:

%union {
  double val;
  symrec *tptr;
}

This says that the two alternative types are double and symrec *. They are given names val and tptr; these names are used in the %token, %nterm and %type declarations to pick one of the types for a terminal or nonterminal symbol (see Nonterminal Symbols).

As an extension to POSIX, a tag is allowed after the %union. For example:

%union value {
  double val;
  symrec *tptr;
}

specifies the union tag value, so the corresponding C type is union value. If you do not specify a tag, it defaults to YYSTYPE (see %define Summary).

As another extension to POSIX, you may specify multiple %union declarations; their contents are concatenated. However, only the first %union declaration can specify a tag.

Note that, unlike making a union declaration in C, you need not write a semicolon after the closing brace.

3.4.5 Providing a Structured Semantic Value Type

Instead of %union, you can define and use your own union type YYSTYPE if your grammar contains at least one ‘<type>’ tag. For example, you can put the following into a header file parser.h:

union YYSTYPE {
  double val;
  symrec *tptr;
};

and then your grammar can use the following instead of %union:

%{
#include "parser.h"
%}
%define api.value.type {union YYSTYPE}
%nterm <val> expr
%token <tptr> ID

Actually, you may also provide a struct rather that a union, which may be handy if you want to track information for every symbol (such as preceding comments).

The type you provide may even be structured and include pointers, in which case the type tags you provide may be composite, with ‘.’ and ‘->’ operators.

3.4.6 Actions

An action accompanies a syntactic rule and contains C code to be executed each time an instance of that rule is recognized. The task of most actions is to compute a semantic value for the grouping built by the rule from the semantic values associated with tokens or smaller groupings.

An action consists of braced code containing C statements, and can be placed at any position in the rule; it is executed at that position. Most rules have just one action at the end of the rule, following all the components. Actions in the middle of a rule are tricky and used only for special purposes (see Actions in Midrule).

The C code in an action can refer to the semantic values of the components matched by the rule with the construct $n, which stands for the value of the nth component. The semantic value for the grouping being constructed is $$. In addition, the semantic values of symbols can be accessed with the named references construct $name or $[name]. Bison translates both of these constructs into expressions of the appropriate type when it copies the actions into the parser implementation file. $$ (or $name, when it stands for the current grouping) is translated to a modifiable lvalue, so it can be assigned to.

Here is a typical example:

exp:
…
| exp '+' exp     { $$ = $1 + $3; }

Or, in terms of named references:

exp[result]:
…
| exp[left] '+' exp[right]  { $result = $left + $right; }

This rule constructs an exp from two smaller exp groupings connected by a plus-sign token. In the action, $1 and $3 ($left and $right) refer to the semantic values of the two component exp groupings, which are the first and third symbols on the right hand side of the rule. The sum is stored into $$ ($result) so that it becomes the semantic value of the addition-expression just recognized by the rule. If there were a useful semantic value associated with the ‘+’ token, it could be referred to as $2.

See Named References, for more information about using the named references construct.

Note that the vertical-bar character ‘|’ is really a rule separator, and actions are attached to a single rule. This is a difference with tools like Flex, for which ‘|’ stands for either “or”, or “the same action as that of the next rule”. In the following example, the action is triggered only when ‘b’ is found:

a-or-b: 'a'|'b'   { a_or_b_found = 1; };

If you don’t specify an action for a rule, Bison supplies a default: $$ = $1. Thus, the value of the first symbol in the rule becomes the value of the whole rule. Of course, the default action is valid only if the two data types match. There is no meaningful default action for an empty rule; every empty rule must have an explicit action unless the rule’s value does not matter.

$n with n zero or negative is allowed for reference to tokens and groupings on the stack before those that match the current rule. This is a very risky practice, and to use it reliably you must be certain of the context in which the rule is applied. Here is a case in which you can use this reliably:

foo:
  expr bar '+' expr  { … }
| expr bar '-' expr  { … }
;

bar:
  %empty    { previous_expr = $0; }
;

As long as bar is used only in the fashion shown here, $0 always refers to the expr which precedes bar in the definition of foo.

It is also possible to access the semantic value of the lookahead token, if any, from a semantic action. This semantic value is stored in yylval. See Special Features for Use in Actions.

3.4.7 Data Types of Values in Actions

If you have chosen a single data type for semantic values, the $$ and $n constructs always have that data type.

If you have used %union to specify a variety of data types, then you must declare a choice among these types for each terminal or nonterminal symbol that can have a semantic value. Then each time you use $$ or $n, its data type is determined by which symbol it refers to in the rule. In this example,

exp:
  …
| exp '+' exp    { $$ = $1 + $3; }

$1 and $3 refer to instances of exp, so they all have the data type declared for the nonterminal symbol exp. If $2 were used, it would have the data type declared for the terminal symbol '+', whatever that might be.

Alternatively, you can specify the data type when you refer to the value, by inserting ‘<type>’ after the ‘$’ at the beginning of the reference. For example, if you have defined types as shown here:

%union {
  int itype;
  double dtype;
}

then you can write $<itype>1 to refer to the first subunit of the rule as an integer, or $<dtype>1 to refer to it as a double.

3.4.8 Actions in Midrule

Occasionally it is useful to put an action in the middle of a rule. These actions are written just like usual end-of-rule actions, but they are executed before the parser even recognizes the following components.

• Using Midrule Actions
• Typed Midrule Actions
• Midrule Action Translation
• Conflicts due to Midrule Actions

stmt:
  "let" '(' var ')'
    {
      $<context>$ = push_context ();
      declare_variable ($3);
    }
  stmt
    {
      $$ = $6;
      pop_context ($<context>5);
    }

stmt:
  "let" '(' var ')'
    {
      $<context>let = push_context ();
      declare_variable ($3);
    }[let]
  stmt
    {
      $$ = $6;
      pop_context ($<context>let);
    }

stmt:
  "let" '(' var ')'
    {
      $<context>$ = push_context (); // ***
      declare_variable ($3);
    }
  stmt
    {
      $$ = $6;
      pop_context ($<context>5);     // ***
    }

stmt:
  "let" '(' var ')'
    <context>{                       // ***
      $$ = push_context ();          // ***
      declare_variable ($3);
    }
  stmt
    {
      $$ = $6;
      pop_context ($5);              // ***
    }

exp: { a(); } "b" { c(); } { d(); } "e" { f(); };

$@1: %empty { a(); };
$@2: %empty { c(); };
$@3: %empty { d(); };
exp: $@1 "b" $@2 $@3 "e" { f(); };

exp: { a(); } "b" { $$ = c(); } { d(); } "e" { f = $1; };

@1: %empty { a(); };
@2: %empty { $$ = c(); };
$@3: %empty { d(); };
exp: @1 "b" @2 $@3 "e" { f = $1; }

$ bison -Wmidrule-value mid.y

mid.y:2.6-13: warning: unset value: $$
    2 | exp: { a(); } "b" { $$ = c(); } { d(); } "e" { f = $1; };
      |      ^~~~~~~~

mid.y:2.19-31: warning: unused value: $3
    2 | exp: { a(); } "b" { $$ = c(); } { d(); } "e" { f = $1; };
      |                   ^~~~~~~~~~~~~

%nterm <context> let
%destructor { pop_context ($$); } let
%printer { print_context (yyo, $$); } let

%%

stmt:
  let stmt
    {
      $$ = $2;
      pop_context ($let);
    };

let:
  "let" '(' var ')'
    {
      $let = push_context ();
      declare_variable ($var);
    };

compound:
  '{' declarations statements '}'
| '{' statements '}'
;

compound:
  { prepare_for_local_variables (); }
     '{' declarations statements '}'

|    '{' statements '}'
;

compound:
  { prepare_for_local_variables (); }
    '{' declarations statements '}'
| { prepare_for_local_variables (); }
    '{' statements '}'
;

compound:
  '{' { prepare_for_local_variables (); }
    declarations statements '}'
| '{' statements '}'
;

subroutine:
  %empty  { prepare_for_local_variables (); }
;

compound:
  subroutine '{' declarations statements '}'
| subroutine '{' statements '}'
;

3.5.1 Data Type of Locations

Defining a data type for locations is much simpler than for semantic values, since all tokens and groupings always use the same type. The location type is specified using ‘%define api.location.type’:

%define api.location.type {location_t}

This defines, in the C generated code, the YYLTYPE type name. When YYLTYPE is not defined, Bison uses a default structure type with four members:

typedef struct YYLTYPE
{
  int first_line;
  int first_column;
  int last_line;
  int last_column;
} YYLTYPE;

In C, you may also specify the type of locations by defining a macro called YYLTYPE, just as you can specify the semantic value type by defining a YYSTYPE macro (see Data Types of Semantic Values). However, rather than using macros, we recommend the api.value.type and api.location.type %define variables.

Default locations represent a range in the source file(s), but this is not a requirement. It could be a single point or just a line number, or even more complex structures.

When the default location type is used, Bison initializes all these fields to 1 for yylloc at the beginning of the parsing. To initialize yylloc with a custom location type (or to chose a different initialization), use the %initial-action directive. See Performing Actions before Parsing.

3.5.2 Actions and Locations

Actions are not only useful for defining language semantics, but also for describing the behavior of the output parser with locations.

The most obvious way for building locations of syntactic groupings is very similar to the way semantic values are computed. In a given rule, several constructs can be used to access the locations of the elements being matched. The location of the nth component of the right hand side is @n, while the location of the left hand side grouping is @$.

In addition, the named references construct @name and @[name] may also be used to address the symbol locations. See Named References, for more information about using the named references construct.

Here is a basic example using the default data type for locations:

exp:
  …
| exp '/' exp
    {
      @$.first_column = @1.first_column;
      @$.first_line = @1.first_line;
      @$.last_column = @3.last_column;
      @$.last_line = @3.last_line;
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

As for semantic values, there is a default action for locations that is run each time a rule is matched. It sets the beginning of @$ to the beginning of the first symbol, and the end of @$ to the end of the last symbol.

With this default action, the location tracking can be fully automatic. The example above simply rewrites this way:

exp:
  …
| exp '/' exp
    {
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

It is also possible to access the location of the lookahead token, if any, from a semantic action. This location is stored in yylloc. See Special Features for Use in Actions.

3.5.3 Printing Locations

When using the default location type, the debug traces report the symbols’ location. The generated parser does so using the YYLOCATION_PRINT macro.

Macro: YYLOCATION_PRINT (file, loc); ¶

When traces are enabled, print loc (of type ‘YYLTYPE const *’) on file (of type ‘FILE *’). Do nothing when traces are disabled, or if the location type is user defined.

To get locations in the debug traces with your user-defined location types, define the YYLOCATION_PRINT macro. For instance:

#define YYLOCATION_PRINT   location_print

3.5.4 Default Action for Locations

Actually, actions are not the best place to compute locations. Since locations are much more general than semantic values, there is room in the output parser to redefine the default action to take for each rule. The YYLLOC_DEFAULT macro is invoked each time a rule is matched, before the associated action is run. It is also invoked while processing a syntax error, to compute the error’s location. Before reporting an unresolvable syntactic ambiguity, a GLR parser invokes YYLLOC_DEFAULT recursively to compute the location of that ambiguity.

Most of the time, this macro is general enough to suppress location dedicated code from semantic actions.

The YYLLOC_DEFAULT macro takes three parameters. The first one is the location of the grouping (the result of the computation). When a rule is matched, the second parameter identifies locations of all right hand side elements of the rule being matched, and the third parameter is the size of the rule’s right hand side. When a GLR parser reports an ambiguity, which of multiple candidate right hand sides it passes to YYLLOC_DEFAULT is undefined. When processing a syntax error, the second parameter identifies locations of the symbols that were discarded during error processing, and the third parameter is the number of discarded symbols.

By default, YYLLOC_DEFAULT is defined this way:

# define YYLLOC_DEFAULT(Cur, Rhs, N)                      \
do                                                        \
  if (N)                                                  \
    {                                                     \
      (Cur).first_line   = YYRHSLOC(Rhs, 1).first_line;   \
      (Cur).first_column = YYRHSLOC(Rhs, 1).first_column; \
      (Cur).last_line    = YYRHSLOC(Rhs, N).last_line;    \
      (Cur).last_column  = YYRHSLOC(Rhs, N).last_column;  \
    }                                                     \
  else                                                    \
    {                                                     \
      (Cur).first_line   = (Cur).last_line   =            \
        YYRHSLOC(Rhs, 0).last_line;                       \
      (Cur).first_column = (Cur).last_column =            \
        YYRHSLOC(Rhs, 0).last_column;                     \
    }                                                     \
while (0)

where YYRHSLOC (rhs, k) is the location of the kth symbol in rhs when k is positive, and the location of the symbol just before the reduction when k and n are both zero.

When defining YYLLOC_DEFAULT, you should consider that:

• All arguments are free of side-effects. However, only the first one (the result) should be modified by YYLLOC_DEFAULT.
• For consistency with semantic actions, valid indexes within the right hand side range from 1 to n. When n is zero, only 0 is a valid index, and it refers to the symbol just before the reduction. During error processing n is always positive.
• Your macro should parenthesize its arguments, if need be, since the actual arguments may not be surrounded by parentheses. Also, your macro should expand to something that can be used as a single statement when it is followed by a semicolon.

3.7.1 Require a Version of Bison

You may require the minimum version of Bison to process the grammar. If the requirement is not met, bison exits with an error (exit status 63).

%require "version"

Some deprecated behaviors are disabled for some required version:

"3.2" (or better)

The C++ deprecated files position.hh and stack.hh are no longer generated.

3.7.2 Token Kind Names

The basic way to declare a token kind name (terminal symbol) is as follows:

%token name

Bison will convert this into a definition in the parser, so that the function yylex (if it is in this file) can use the name name to stand for this token kind’s code.

Alternatively, you can use %left, %right, %precedence, or %nonassoc instead of %token, if you wish to specify associativity and precedence. See Operator Precedence. However, for clarity, we recommend to use these directives only to declare associativity and precedence, and not to add string aliases, semantic types, etc.

You can explicitly specify the numeric code for a token kind by appending a nonnegative decimal or hexadecimal integer value in the field immediately following the token name:

%token NUM 300
%token XNUM 0x12d // a GNU extension

It is generally best, however, to let Bison choose the numeric codes for all token kinds. Bison will automatically select codes that don’t conflict with each other or with normal characters.

In the event that the stack type is a union, you must augment the %token or other token declaration to include the data type alternative delimited by angle-brackets (see More Than One Value Type).

For example:

%union {              /* define stack type */
  double val;
  symrec *tptr;
}
%token <val> NUM      /* define token NUM and its type */

You can associate a literal string token with a token kind name by writing the literal string at the end of a %token declaration which declares the name. For example:

%token ARROW "=>"

For example, a grammar for the C language might specify these names with equivalent literal string tokens:

%token  <operator>  OR      "||"
%token  <operator>  LE 134  "<="
%left  OR  "<="

Once you equate the literal string and the token kind name, you can use them interchangeably in further declarations or the grammar rules. The yylex function can use the token name or the literal string to obtain the token kind code (see Calling Convention for yylex).

String aliases allow for better error messages using the literal strings instead of the token names, such as ‘syntax error, unexpected ||, expecting number or (’ rather than ‘syntax error, unexpected OR, expecting NUM or LPAREN’.

String aliases may also be marked for internationalization (see Token Internationalization):

%token
    OR     "||"
    LPAREN "("
    RPAREN ")"
    '\n'   _("end of line")
  <double>
    NUM    _("number")

would produce in French ‘erreur de syntaxe, || inattendu, attendait nombre ou (’ rather than ‘erreur de syntaxe, || inattendu, attendait number ou (’.

3.7.3 Operator Precedence

Use the %left, %right, %nonassoc, or %precedence declaration to declare a token and specify its precedence and associativity, all at once. These are called precedence declarations. See Operator Precedence, for general information on operator precedence.

The syntax of a precedence declaration is nearly the same as that of %token: either

%left symbols…

or

%left <type> symbols…

And indeed any of these declarations serves the purposes of %token. But in addition, they specify the associativity and relative precedence for all the symbols:

• The associativity of an operator op determines how repeated uses of the operator nest: whether ‘x op y op z’ is parsed by grouping x with y first or by grouping y with z first. %left specifies left-associativity (grouping x with y first) and %right specifies right-associativity (grouping y with z first). %nonassoc specifies no associativity, which means that ‘x op y op z’ is considered a syntax error.

  %precedence gives only precedence to the symbols, and defines no associativity at all. Use this to define precedence only, and leave any potential conflict due to associativity enabled.

• The precedence of an operator determines how it nests with other operators. All the tokens declared in a single precedence declaration have equal precedence and nest together according to their associativity. When two tokens declared in different precedence declarations associate, the one declared later has the higher precedence and is grouped first.

For backward compatibility, there is a confusing difference between the argument lists of %token and precedence declarations. Only a %token can associate a literal string with a token kind name. A precedence declaration always interprets a literal string as a reference to a separate token. For example:

%left  OR "<="         // Does not declare an alias.
%left  OR 134 "<=" 135 // Declares 134 for OR and 135 for "<=".

3.7.4 Nonterminal Symbols

When you use %union to specify multiple value types, you must declare the value type of each nonterminal symbol for which values are used. This is done with a %type declaration, like this:

%type <type> nonterminal…

Here nonterminal is the name of a nonterminal symbol, and type is the name given in the %union to the alternative that you want (see The Union Declaration). You can give any number of nonterminal symbols in the same %type declaration, if they have the same value type. Use spaces to separate the symbol names.

While POSIX Yacc allows %type only for nonterminals, Bison accepts that this directive be also applied to terminal symbols. To declare exclusively nonterminal symbols, use the safer %nterm:

%nterm <type> nonterminal…

3.7.5 Syntax of Symbol Declarations

The syntax of the various directives to declare symbols is as follows.

%token tag? ( id number? string? )+ ( tag ( id number? string? )+ )*
%left  tag? ( id number?)+ ( tag ( id number? )+ )*
%type  tag? ( id | char | string )+ ( tag ( id | char | string )+ )*
%nterm tag? id+ ( tag id+ )*

where tag denotes a type tag such as ‘<ival>’, id denotes an identifier such as ‘NUM’, number a decimal or hexadecimal integer such as ‘300’ or ‘0x12d’, char a character literal such as ‘'+'’, and string a string literal such as ‘"number"’. The postfix quantifiers are ‘?’ (zero or one), ‘*’ (zero or more) and ‘+’ (one or more).

The directives %precedence, %right and %nonassoc behave like %left.

3.7.6 Performing Actions before Parsing

Sometimes your parser needs to perform some initializations before parsing. The %initial-action directive allows for such arbitrary code.

Directive: %initial-action { code } ¶

Declare that the braced code must be invoked before parsing each time yyparse is called. The code may use $$ (or $<tag>$) and @$ — initial value and location of the lookahead — and the %parse-param.

For instance, if your locations use a file name, you may use

%parse-param { char const *file_name };
%initial-action
{
  @$.initialize (file_name);
};

3.7.7 Freeing Discarded Symbols

During error recovery (see Error Recovery), symbols already pushed on the stack and tokens coming from the rest of the file are discarded until the parser falls on its feet. If the parser runs out of memory, or if it returns via YYABORT, YYACCEPT or YYNOMEM, all the symbols on the stack must be discarded. Even if the parser succeeds, it must discard the start symbol.

When discarded symbols convey heap based information, this memory is lost. While this behavior can be tolerable for batch parsers, such as in traditional compilers, it is unacceptable for programs like shells or protocol implementations that may parse and execute indefinitely.

The %destructor directive defines code that is called when a symbol is automatically discarded.

Directive: %destructor { code } symbols ¶

Invoke the braced code whenever the parser discards one of the symbols. Within code, $$ (or $<tag>$) designates the semantic value associated with the discarded symbol, and @$ designates its location. The additional parser parameters are also available (see The Parser Function yyparse).

When a symbol is listed among symbols, its %destructor is called a per-symbol %destructor. You may also define a per-type %destructor by listing a semantic type tag among symbols. In that case, the parser will invoke this code whenever it discards any grammar symbol that has that semantic type tag unless that symbol has its own per-symbol %destructor.

Finally, you can define two different kinds of default %destructors. You can place each of <*> and <> in the symbols list of exactly one %destructor declaration in your grammar file. The parser will invoke the code associated with one of these whenever it discards any user-defined grammar symbol that has no per-symbol and no per-type %destructor. The parser uses the code for <*> in the case of such a grammar symbol for which you have formally declared a semantic type tag (%token, %nterm, and %type count as such a declaration, but $<tag>$ does not). The parser uses the code for <> in the case of such a grammar symbol that has no declared semantic type tag.

For example:

%union { char *string; }
%token <string> STRING1 STRING2
%nterm <string> string1 string2
%union { char character; }
%token <character> CHR
%nterm <character> chr
%token TAGLESS

%destructor { } <character>
%destructor { free ($$); } <*>
%destructor { free ($$); printf ("%d", @$.first_line); } STRING1 string1
%destructor { printf ("Discarding tagless symbol.\n"); } <>

guarantees that, when the parser discards any user-defined symbol that has a semantic type tag other than <character>, it passes its semantic value to free by default. However, when the parser discards a STRING1 or a string1, it uses the third %destructor, which frees it and prints its line number to stdout (free is invoked only once). Finally, the parser merely prints a message whenever it discards any symbol, such as TAGLESS, that has no semantic type tag.

A Bison-generated parser invokes the default %destructors only for user-defined as opposed to Bison-defined symbols. For example, the parser will not invoke either kind of default %destructor for the special Bison-defined symbols $accept, $undefined, or $end (see Bison Symbols), none of which you can reference in your grammar. It also will not invoke either for the error token (see Bison Symbols), which is always defined by Bison regardless of whether you reference it in your grammar. However, it may invoke one of them for the end token (token 0) if you redefine it from $end to, for example, END:

%token END 0

Finally, Bison will never invoke a %destructor for an unreferenced midrule semantic value (see Actions in Midrule). That is, Bison does not consider a midrule to have a semantic value if you do not reference $$ in the midrule’s action or $n (where n is the right-hand side symbol position of the midrule) in any later action in that rule. However, if you do reference either, the Bison-generated parser will invoke the <> %destructor whenever it discards the midrule symbol.

Discarded symbols are the following:

• stacked symbols popped during the first phase of error recovery,
• incoming terminals during the second phase of error recovery,
• the current lookahead and the entire stack (except the current right-hand side symbols) when the parser returns immediately, and
• the current lookahead and the entire stack (including the current right-hand side symbols) when the C++ parser (lalr1.cc) catches an exception in parse,
• the start symbol, when the parser succeeds.

The parser can return immediately because of an explicit call to YYABORT, YYACCEPT or YYNOMEM, or failed error recovery, or memory exhaustion.

Right-hand side symbols of a rule that explicitly triggers a syntax error via YYERROR are not discarded automatically. As a rule of thumb, destructors are invoked only when user actions cannot manage the memory.

3.7.8 Printing Semantic Values

When run-time traces are enabled (see Tracing Your Parser), the parser reports its actions, such as reductions. When a symbol involved in an action is reported, only its kind is displayed, as the parser cannot know how semantic values should be formatted.

The %printer directive defines code that is called when a symbol is reported. Its syntax is the same as %destructor (see Freeing Discarded Symbols).

Directive: %printer { code } symbols ¶

Invoke the braced code whenever the parser displays one of the symbols. Within code, yyo denotes the output stream (a FILE* in C, an std::ostream& in C++, and stdout in D), $$ (or $<tag>$) designates the semantic value associated with the symbol, and @$ its location. The additional parser parameters are also available (see The Parser Function yyparse).

The symbols are defined as for %destructor (see Freeing Discarded Symbols.): they can be per-type (e.g., ‘<ival>’), per-symbol (e.g., ‘exp’, ‘NUM’, ‘"float"’), typed per-default (i.e., ‘<*>’, or untyped per-default (i.e., ‘<>’).

For example:

%union { char *string; }
%token <string> STRING1 STRING2
%nterm <string> string1 string2
%union { char character; }
%token <character> CHR
%nterm <character> chr
%token TAGLESS

%printer { fprintf (yyo, "'%c'", $$); } <character>
%printer { fprintf (yyo, "&%p", $$); } <*>
%printer { fprintf (yyo, "\"%s\"", $$); } STRING1 string1
%printer { fprintf (yyo, "<>"); } <>

guarantees that, when the parser print any symbol that has a semantic type tag other than <character>, it display the address of the semantic value by default. However, when the parser displays a STRING1 or a string1, it formats it as a string in double quotes. It performs only the second %printer in this case, so it prints only once. Finally, the parser print ‘<>’ for any symbol, such as TAGLESS, that has no semantic type tag. See Enabling Debug Traces for mfcalc, for a complete example.

3.7.9 Suppressing Conflict Warnings

Bison normally warns if there are any conflicts in the grammar (see Shift/Reduce Conflicts), but most real grammars have harmless shift/reduce conflicts which are resolved in a predictable way and would be difficult to eliminate. It is desirable to suppress the warning about these conflicts unless the number of conflicts changes. You can do this with the %expect declaration.

The declaration looks like this:

%expect n

Here n is a decimal integer. The declaration says there should be n shift/reduce conflicts and no reduce/reduce conflicts. Bison reports an error if the number of shift/reduce conflicts differs from n, or if there are any reduce/reduce conflicts.

For deterministic parsers, reduce/reduce conflicts are more serious, and should be eliminated entirely. Bison will always report reduce/reduce conflicts for these parsers. With GLR parsers, however, both kinds of conflicts are routine; otherwise, there would be no need to use GLR parsing. Therefore, it is also possible to specify an expected number of reduce/reduce conflicts in GLR parsers, using the declaration:

%expect-rr n

You may wish to be more specific in your specification of expected conflicts. To this end, you can also attach %expect and %expect-rr modifiers to individual rules. The interpretation of these modifiers differs from their use as declarations. When attached to rules, they indicate the number of states in which the rule is involved in a conflict. You will need to consult the output resulting from -v to determine appropriate numbers to use. For example, for the following grammar fragment, the first rule for empty_dims appears in two states in which the ‘[’ token is a lookahead. Having determined that, you can document this fact with an %expect modifier as follows:

dims:
  empty_dims
| '[' expr ']' dims
;

empty_dims:
  %empty   %expect 2
| empty_dims '[' ']'
;

Mid-rule actions generate implicit rules that are also subject to conflicts (see Conflicts due to Midrule Actions). To attach an %expect or %expect-rr annotation to an implicit mid-rule action’s rule, put it before the action. For example,

%glr-parser
%expect-rr 1

%%

clause:
  "condition" %expect-rr 1 { value_mode(); } '(' exprs ')'
| "condition" %expect-rr 1 { class_mode(); } '(' types ')'
;

Here, the appropriate mid-rule action will not be determined until after the ‘(’ token is shifted. Thus, the two actions will clash with each other, and we should expect one reduce/reduce conflict for each.

In general, using %expect involves these steps:

• Compile your grammar without %expect. Use the -v option to get a verbose list of where the conflicts occur. Bison will also print the number of conflicts.
• Check each of the conflicts to make sure that Bison’s default resolution is what you really want. If not, rewrite the grammar and go back to the beginning.
• Add an %expect declaration, copying the number n from the number that Bison printed. With GLR parsers, add an %expect-rr declaration as well.
• Optionally, count up the number of states in which one or more conflicted reductions for particular rules appear and add these numbers to the affected rules as %expect-rr or %expect modifiers as appropriate. Rules that are in conflict appear in the output listing surrounded by square brackets or, in the case of reduce/reduce conflicts, as reductions having the same lookahead symbol as a square-bracketed reduction in the same state.

Now Bison will report an error if you introduce an unexpected conflict, but will keep silent otherwise.

3.7.10 The Start-Symbol

Bison assumes by default that the start symbol for the grammar is the first nonterminal specified in the grammar specification section. The programmer may override this restriction with the %start declaration as follows:

%start symbol

3.7.11 A Pure (Reentrant) Parser

A reentrant program is one which does not alter in the course of execution; in other words, it consists entirely of pure (read-only) code. Reentrancy is important whenever asynchronous execution is possible; for example, a nonreentrant program may not be safe to call from a signal handler. In systems with multiple threads of control, a nonreentrant program must be called only within interlocks.

Normally, Bison generates a parser which is not reentrant. This is suitable for most uses, and it permits compatibility with Yacc. (The standard Yacc interfaces are inherently nonreentrant, because they use statically allocated variables for communication with yylex, including yylval and yylloc.)

Alternatively, you can generate a pure, reentrant parser. The Bison declaration ‘%define api.pure’ says that you want the parser to be reentrant. It looks like this:

%define api.pure full

The result is that the communication variables yylval and yylloc become local variables in yyparse, and a different calling convention is used for the lexical analyzer function yylex. See Calling Conventions for Pure Parsers, for the details of this. The variable yynerrs becomes local in yyparse in pull mode but it becomes a member of yypstate in push mode. (see The Error Reporting Function yyerror). The convention for calling yyparse itself is unchanged.

Whether the parser is pure has nothing to do with the grammar rules. You can generate either a pure parser or a nonreentrant parser from any valid grammar.

3.7.12 A Push Parser

A pull parser is called once and it takes control until all its input is completely parsed. A push parser, on the other hand, is called each time a new token is made available.

A push parser is typically useful when the parser is part of a main event loop in the client’s application. This is typically a requirement of a GUI, when the main event loop needs to be triggered within a certain time period.

Normally, Bison generates a pull parser. The following Bison declaration says that you want the parser to be a push parser (see %define Summary):

%define api.push-pull push

In almost all cases, you want to ensure that your push parser is also a pure parser (see A Pure (Reentrant) Parser). The only time you should create an impure push parser is to have backwards compatibility with the impure Yacc pull mode interface. Unless you know what you are doing, your declarations should look like this:

%define api.pure full
%define api.push-pull push

There is a major notable functional difference between the pure push parser and the impure push parser. It is acceptable for a pure push parser to have many parser instances, of the same type of parser, in memory at the same time. An impure push parser should only use one parser at a time.

When a push parser is selected, Bison will generate some new symbols in the generated parser. yypstate is a structure that the generated parser uses to store the parser’s state. yypstate_new is the function that will create a new parser instance. yypstate_delete will free the resources associated with the corresponding parser instance. Finally, yypush_parse is the function that should be called whenever a token is available to provide the parser. A trivial example of using a pure push parser would look like this:

int status;
yypstate *ps = yypstate_new ();
do {
  status = yypush_parse (ps, yylex (), NULL);
} while (status == YYPUSH_MORE);
yypstate_delete (ps);

If the user decided to use an impure push parser, a few things about the generated parser will change. The yychar variable becomes a global variable instead of a local one in the yypush_parse function. For this reason, the signature of the yypush_parse function is changed to remove the token as a parameter. A nonreentrant push parser example would thus look like this:

extern int yychar;
int status;
yypstate *ps = yypstate_new ();
do {
  yychar = yylex ();
  status = yypush_parse (ps);
} while (status == YYPUSH_MORE);
yypstate_delete (ps);

That’s it. Notice the next token is put into the global variable yychar for use by the next invocation of the yypush_parse function.

Bison also supports both the push parser interface along with the pull parser interface in the same generated parser. In order to get this functionality, you should replace the ‘%define api.push-pull push’ declaration with the ‘%define api.push-pull both’ declaration. Doing this will create all of the symbols mentioned earlier along with the two extra symbols, yyparse and yypull_parse. yyparse can be used exactly as it normally would be used. However, the user should note that it is implemented in the generated parser by calling yypull_parse. This makes the yyparse function that is generated with the ‘%define api.push-pull both’ declaration slower than the normal yyparse function. If the user calls the yypull_parse function it will parse the rest of the input stream. It is possible to yypush_parse tokens to select a subgrammar and then yypull_parse the rest of the input stream. If you would like to switch back and forth between between parsing styles, you would have to write your own yypull_parse function that knows when to quit looking for input. An example of using the yypull_parse function would look like this:

yypstate *ps = yypstate_new ();
yypull_parse (ps); /* Will call the lexer */
yypstate_delete (ps);

Adding the ‘%define api.pure’ declaration does exactly the same thing to the generated parser with ‘%define api.push-pull both’ as it did for ‘%define api.push-pull push’.

3.7.13 Bison Declaration Summary

Here is a summary of the declarations used to define a grammar:

Directive: %union ¶

Declare the collection of data types that semantic values may have (see The Union Declaration).

Directive: %token ¶

Declare a terminal symbol (token kind name) with no precedence or associativity specified (see Token Kind Names).

Directive: %right ¶

Declare a terminal symbol (token kind name) that is right-associative (see Operator Precedence).

Directive: %left ¶

Declare a terminal symbol (token kind name) that is left-associative (see Operator Precedence).

Directive: %nonassoc ¶

Declare a terminal symbol (token kind name) that is nonassociative (see Operator Precedence). Using it in a way that would be associative is a syntax error.

Directive: %nterm ¶

Declare the type of semantic values for a nonterminal symbol (see Nonterminal Symbols).

Directive: %type ¶

Declare the type of semantic values for a symbol (see Nonterminal Symbols).

Directive: %start ¶

Specify the grammar’s start symbol (see The Start-Symbol).

Directive: %expect ¶

Declare the expected number of shift/reduce conflicts, either overall or for a given rule (see Suppressing Conflict Warnings).

Directive: %expect-rr ¶

Declare the expected number of reduce/reduce conflicts, either overall or for a given rule (see Suppressing Conflict Warnings).

In order to change the behavior of bison, use the following directives:

Directive: %code {code} ¶

Directive: %code qualifier {code} ¶

Insert code verbatim into the output parser source at the default location or at the location specified by qualifier. See %code Summary.

Directive: %debug ¶

Instrument the parser for traces. Obsoleted by ‘%define parse.trace’. See Tracing Your Parser.

Directive: %define variable ¶

Directive: %define variable value ¶

Directive: %define variable {value} ¶

Directive: %define variable "value" ¶

Define a variable to adjust Bison’s behavior. See %define Summary.

Directive: %defines ¶

Directive: %defines defines-file ¶

Historical name for %header. See %header.

Directive: %destructor ¶

Specify how the parser should reclaim the memory associated to discarded symbols. See Freeing Discarded Symbols.

Directive: %file-prefix "prefix" ¶

Specify a prefix to use for all Bison output file names. The names are chosen as if the grammar file were named prefix.y.

Directive: %header ¶

Write a parser header file containing definitions for the token kind names defined in the grammar as well as a few other declarations. If the parser implementation file is named name.c then the parser header file is named name.h.

For C parsers, the parser header file declares YYSTYPE unless YYSTYPE is already defined as a macro or you have used a <type> tag without using %union. Therefore, if you are using a %union (see More Than One Value Type) with components that require other definitions, or if you have defined a YYSTYPE macro or type definition (see Data Types of Semantic Values), you need to arrange for these definitions to be propagated to all modules, e.g., by putting them in a prerequisite header that is included both by your parser and by any other module that needs YYSTYPE.

Unless your parser is pure, the parser header file declares yylval as an external variable. See A Pure (Reentrant) Parser.

If you have also used locations, the parser header file declares YYLTYPE and yylloc using a protocol similar to that of the YYSTYPE macro and yylval. See Tracking Locations.

This parser header file is normally essential if you wish to put the definition of yylex in a separate source file, because yylex typically needs to be able to refer to the above-mentioned declarations and to the token kind codes. See Semantic Values of Tokens.

If you have declared %code requires or %code provides, the output header also contains their code. See %code Summary.

The generated header is protected against multiple inclusions with a C preprocessor guard: ‘YY_PREFIX_FILE_INCLUDED’, where PREFIX and FILE are the prefix (see Multiple Parsers in the Same Program) and generated file name turned uppercase, with each series of non alphanumerical characters converted to a single underscore.

For instance with ‘%define api.prefix {calc}’ and ‘%header "lib/parse.h"’, the header will be guarded as follows.

#ifndef YY_CALC_LIB_PARSE_H_INCLUDED
# define YY_CALC_LIB_PARSE_H_INCLUDED
...
#endif /* ! YY_CALC_LIB_PARSE_H_INCLUDED */

Introduced in Bison 3.8.

Directive: %header header-file ¶

Same as above, but save in the file header-file.

Directive: %language "language" ¶

Specify the programming language for the generated parser. Currently supported languages include C, C++, D and Java. language is case-insensitive.

Directive: %locations ¶

Generate the code processing the locations (see Special Features for Use in Actions). This mode is enabled as soon as the grammar uses the special ‘@n’ tokens, but if your grammar does not use it, using ‘%locations’ allows for more accurate syntax error messages.

Directive: %name-prefix "prefix" ¶

Obsoleted by ‘%define api.prefix {prefix}’. See Multiple Parsers in the Same Program. For C++ parsers, see the ‘%define api.namespace’ documentation in this section.

Rename the external symbols used in the parser so that they start with prefix instead of ‘yy’. The precise list of symbols renamed in C parsers is yyparse, yylex, yyerror, yynerrs, yylval, yychar, yydebug, and (if locations are used) yylloc. If you use a push parser, yypush_parse, yypull_parse, yypstate, yypstate_new and yypstate_delete will also be renamed. For example, if you use ‘%name-prefix "c_"’, the names become c_parse, c_lex, and so on.

Contrary to defining api.prefix, some symbols are not renamed by %name-prefix, for instance YYDEBUG, YYTOKENTYPE, yytoken_kind_t, YYSTYPE, YYLTYPE.

Directive: %no-lines ¶

Don’t generate any #line preprocessor commands in the parser implementation file. Ordinarily Bison writes these commands in the parser implementation file so that the C compiler and debuggers will associate errors and object code with your source file (the grammar file). This directive causes them to associate errors with the parser implementation file, treating it as an independent source file in its own right.

Directive: %output "file" ¶

Generate the parser implementation in file.

Directive: %pure-parser ¶

Deprecated version of ‘%define api.pure’ (see %define Summary), for which Bison is more careful to warn about unreasonable usage.

Directive: %require "version" ¶

Require version version or higher of Bison. See Require a Version of Bison.

Directive: %skeleton "file" ¶

Specify the skeleton to use.

If file does not contain a /, file is the name of a skeleton file in the Bison installation directory. If it does, file is an absolute file name or a file name relative to the directory of the grammar file. This is similar to how most shells resolve commands.

Directive: %token-table ¶

This feature is obsolescent, avoid it in new projects.

Generate an array of token names in the parser implementation file. The name of the array is yytname; yytname[i] is the name of the token whose internal Bison token code is i. The first three elements of yytname correspond to the predefined tokens "$end", "error", and "$undefined"; after these come the symbols defined in the grammar file.

The name in the table includes all the characters needed to represent the token in Bison. For single-character literals and literal strings, this includes the surrounding quoting characters and any escape sequences. For example, the Bison single-character literal '+' corresponds to a three-character name, represented in C as "'+'"; and the Bison two-character literal string "\\/" corresponds to a five-character name, represented in C as "\"\\\\/\"".

When you specify %token-table, Bison also generates macro definitions for macros YYNTOKENS, YYNNTS, and YYNRULES, and YYNSTATES:

YYNTOKENS

The number of terminal symbols, i.e., the highest token code, plus one.

YYNNTS

The number of nonterminal symbols.

YYNRULES

The number of grammar rules,

YYNSTATES

The number of parser states (see Parser States).

Here’s code for looking up a multicharacter token in yytname, assuming that the characters of the token are stored in token_buffer, and assuming that the token does not contain any characters like ‘"’ that require escaping.

for (int i = 0; i < YYNTOKENS; i++)
  if (yytname[i]
      && yytname[i][0] == '"'
      && ! strncmp (yytname[i] + 1, token_buffer,
                    strlen (token_buffer))
      && yytname[i][strlen (token_buffer) + 1] == '"'
      && yytname[i][strlen (token_buffer) + 2] == 0)
    break;

This method is discouraged: the primary purpose of string aliases is forging good error messages, not describing the spelling of keywords. In addition, looking for the token kind at runtime incurs a (small but noticeable) cost.

Finally, %token-table is incompatible with the custom and detailed values of the parse.error %define variable.

Directive: %verbose ¶

Write an extra output file containing verbose descriptions of the parser states and what is done for each type of lookahead token in that state. See Understanding Your Parser, for more information.

Directive: %yacc ¶

Pretend the option --yacc was given (see --yacc), i.e., imitate Yacc, including its naming conventions. Only makes sense with the yacc.c skeleton. See Tuning the Parser, for more.

Of course, being a Bison extension, %yacc is somewhat self-contradictory…

3.7.14 %define Summary

There are many features of Bison’s behavior that can be controlled by assigning the feature a single value. For historical reasons, some such features are assigned values by dedicated directives, such as %start, which assigns the start symbol. However, newer such features are associated with variables, which are assigned by the %define directive:

Directive: %define variable ¶

Directive: %define variable value ¶

Directive: %define variable {value} ¶

Directive: %define variable "value" ¶

Define variable to value.

The type of the values depend on the syntax. Braces denote value in the target language (e.g., a namespace, a type, etc.). Keyword values (no delimiters) denote finite choice (e.g., a variation of a feature). String values denote remaining cases (e.g., a file name).

It is an error if a variable is defined by %define multiple times, but see -D name[=value].

The rest of this section summarizes variables and values that %define accepts.

Some variables take Boolean values. In this case, Bison will complain if the variable definition does not meet one of the following four conditions:

1. value is true
2. value is omitted (or "" is specified). This is equivalent to true.
3. value is false.
4. variable is never defined. In this case, Bison selects a default value.

What variables are accepted, as well as their meanings and default values, depend on the selected target language and/or the parser skeleton (see Bison Declaration Summary, see Bison Declaration Summary). Unaccepted variables produce an error. Some of the accepted variables are described below.

Directive: %define api.filename.type {type} ¶

• Language(s): C++
• Purpose: Define the type of file names in Bison’s default location and position types. See Exposing the Location Classes.
• Accepted Values: Any type that is printable (via streams) and comparable (with == and !=).
• Default Value: const std::string.
• History: Introduced in Bison 2.0 as filename_type (with std::string as default), renamed as api.filename.type in Bison 3.7 (with const std::string as default).

Directive: %define api.header.include {"header.h"} ¶

Directive: %define api.header.include {<header.h>} ¶

• Languages(s): C (yacc.c)
• Purpose: Specify how the generated parser should include the generated header.

  Historically, when option -d or --header was used, bison generated a header and pasted an exact copy of it into the generated parser implementation file. Since Bison 3.6, it is #included as ‘"basename.h"’, instead of duplicated, unless file is ‘y.tab’, see below.

  The api.header.include variable allows to control how the generated parser #includes the generated header. For instance:

  %define api.header.include {"parse.h"}
  

  or

  %define api.header.include {<parser/parse.h>}
  

  Using api.header.include does not change the name of the generated header, only how it is included.

  To work around limitations of Automake’s ylwrap (which runs bison with --yacc), api.header.include is not predefined when the output file is y.tab.c. Define it to avoid the duplication.

• Accepted Values: An argument for #include.
• Default Value: ‘"header-basename"’, unless the header file is y.tab.h, where header-basename is the name of the generated header, without directory part. For instance with ‘bison -d calc/parse.y’, api.header.include defaults to ‘"parse.h"’, not ‘"calc/parse.h"’.
• History: Introduced in Bison 3.4. Defaults to ‘"basename.h"’ since Bison 3.7, unless the header file is y.tab.h.

Directive: %define api.location.file "file" ¶

Directive: %define api.location.file none ¶

• Language(s): C++
• Purpose: Define the name of the file in which Bison’s default location and position types are generated. See Exposing the Location Classes.
• Accepted Values:

  none

  If locations are enabled, generate the definition of the position and location classes in the header file if %header, otherwise in the parser implementation.

  "file"

  Generate the definition of the position and location classes in file. This file name can be relative (to where the parser file is output) or absolute.

• Default Value: Not applicable if locations are not enabled, or if a user location type is specified (see api.location.type). Otherwise, Bison’s location is generated in location.hh (see C++ location).
• History: Introduced in Bison 3.2.

Directive: %define api.location.include {"file"} ¶

Directive: %define api.location.include {<file>} ¶

• Language(s): C++
• Purpose: Specify how the generated file that defines the position and location classes is included. This makes sense when the location class is exposed to the rest of your application/library in another directory. See Exposing the Location Classes.
• Accepted Values: Argument for #include.
• Default Value: ‘"dir/location.hh"’ where dir is the directory part of the output. For instance src/parse if --output=src/parse/parser.cc was given.
• History: Introduced in Bison 3.2.

Directive: %define api.location.type {type} ¶

• Language(s): C, C++, Java
• Purpose: Define the location type. See Data Type of Locations, and User Defined Location Type.
• Accepted Values: String
• Default Value: none
• History: Introduced in Bison 2.7 for C++ and Java, in Bison 3.4 for C. Was originally named location_type in Bison 2.5 and 2.6.

Directive: %define api.namespace {namespace} ¶

• Languages(s): C++
• Purpose: Specify the namespace for the parser class. For example, if you specify:

  %define api.namespace {foo::bar}
  

  Bison uses foo::bar verbatim in references such as:

  foo::bar::parser::value_type
  

  However, to open a namespace, Bison removes any leading :: and then splits on any remaining occurrences:

  namespace foo { namespace bar {
    class position;
    class location;
  } }
  

• Accepted Values: Any absolute or relative C++ namespace reference without a trailing "::". For example, "foo" or "::foo::bar".
• Default Value: yy, unless you used the obsolete ‘%name-prefix "prefix"’ directive.

Directive: %define api.parser.class {name} ¶

• Language(s): C++, Java, D
• Purpose: The name of the parser class.
• Accepted Values: Any valid identifier.
• Default Value: In C++, parser. In D and Java, YYParser or api.prefixParser (see Java Bison Interface).
• History: Introduced in Bison 3.3 to replace parser_class_name.

Directive: %define api.prefix {prefix} ¶

• Language(s): C, C++, Java
• Purpose: Rename exported symbols. See Multiple Parsers in the Same Program.
• Accepted Values: String
• Default Value: YY for Java, yy otherwise.
• History: introduced in Bison 2.6, with its argument in double quotes. Uses braces since Bison 3.0 (double quotes are still supported for backward compatibility).

Directive: %define api.pure purity ¶

• Language(s): C
• Purpose: Request a pure (reentrant) parser program. See A Pure (Reentrant) Parser.
• Accepted Values: true, false, full

  The value may be omitted: this is equivalent to specifying true, as is the case for Boolean values.

  When %define api.pure full is used, the parser is made reentrant. This changes the signature for yylex (see Calling Conventions for Pure Parsers), and also that of yyerror when the tracking of locations has been activated, as shown below.

  The true value is very similar to the full value, the only difference is in the signature of yyerror on Yacc parsers without %parse-param, for historical reasons.

  I.e., if ‘%locations %define api.pure’ is passed then the prototypes for yyerror are:

  void yyerror (char const *msg);                 // Yacc parsers.
  void yyerror (YYLTYPE *locp, char const *msg);  // GLR parsers.
  

  But if ‘%locations %define api.pure %parse-param {int *nastiness}’ is used, then both parsers have the same signature:

  void yyerror (YYLTYPE *llocp, int *nastiness, char const *msg);
  

  (see The Error Reporting Function yyerror)

• Default Value: false
• History: the full value was introduced in Bison 2.7

Directive: %define api.push-pull kind ¶

• Language(s): C (deterministic parsers only), D, Java
• Purpose: Request a pull parser, a push parser, or both. See A Push Parser.
• Accepted Values: pull, push, both
• Default Value: pull

Directive: %define api.symbol.prefix {prefix} ¶

• Languages(s): all
• Purpose: Add a prefix to the name of the symbol kinds. For instance

  %define api.symbol.prefix {S_}
  %token FILE for ERROR
  %%
  start: FILE for ERROR;
  

  generates this definition in C:

  /* Symbol kind.  */
  enum yysymbol_kind_t
  {
    S_YYEMPTY = -2,   /* No symbol.  */
    S_YYEOF = 0,      /* $end  */
    S_YYERROR = 1,    /* error  */
    S_YYUNDEF = 2,    /* $undefined  */
    S_FILE = 3,       /* FILE  */
    S_for = 4,        /* for  */
    S_ERROR = 5,      /* ERROR  */
    S_YYACCEPT = 6,   /* $accept  */
    S_start = 7       /* start  */
  };
  

• Accepted Values: Any non empty string. Must be a valid identifier in the target language (typically a non empty sequence of letters, underscores, and —not at the beginning— digits).

  The empty prefix is (generally) invalid:

  • in C it would create collision with the YYERROR macro, and potentially token kind definitions and symbol kind definitions would collide;
  • unnamed symbols (such as ‘'+'’) have a name which starts with a digit;
  • even in languages with scoped enumerations such as Java, an empty prefix is dangerous: symbol names may collide with the target language keywords, or with other members of the SymbolKind class.
• Default Value: YYSYMBOL_ in C, S_ in C++ and Java, empty in D.
• History: introduced in Bison 3.6.

Directive: %define api.token.constructor ¶

• Language(s): C++, D
• Purpose: Request that symbols be handled as a whole (type, value, and possibly location) in the scanner. In the case of C++, it works only when variant-based semantic values are enabled (see C++ Variants), see Complete Symbols, for details. In D, token constructors work with both ‘%union’ and ‘%define api.value.type union’.
• Accepted Values: Boolean.
• Default Value: false
• History: introduced in Bison 3.0.

Directive: %define api.token.prefix {prefix} ¶

• Languages(s): all
• Purpose: Add a prefix to the token names when generating their definition in the target language. For instance

  %define api.token.prefix {TOK_}
  %token FILE for ERROR
  %%
  start: FILE for ERROR;
  

  generates the definition of the symbols TOK_FILE, TOK_for, and TOK_ERROR in the generated source files. In particular, the scanner must use these prefixed token names, while the grammar itself may still use the short names (as in the sample rule given above). The generated informational files (*.output, *.xml, *.gv) are not modified by this prefix.

  Bison also prefixes the generated member names of the semantic value union. See Generating the Semantic Value Type, for more details.

  See Calc++ Parser and Calc++ Scanner, for a complete example.

• Accepted Values: Any string. Must be a valid identifier prefix in the target language (typically, a possibly empty sequence of letters, underscores, and —not at the beginning— digits).
• Default Value: empty
• History: introduced in Bison 3.0.

Directive: %define api.token.raw ¶

• Language(s): all
• Purpose: The output files normally define the enumeration of the token kinds with Yacc-compatible token codes: sequential numbers starting at 257 except for single character tokens which stand for themselves (e.g., in ASCII, ‘'a'’ is numbered 65). The parser however uses symbol kinds which are assigned numbers sequentially starting at 0. Therefore each time the scanner returns an (external) token kind, it must be mapped to the (internal) symbol kind.

  When api.token.raw is set, the code of the token kinds are forced to coincide with the symbol kind. This saves one table lookup per token to map them from the token kind to the symbol kind, and also saves the generation of the mapping table. The gain is typically moderate, but in extreme cases (very simple user actions), a 10% improvement can be observed.

  When api.token.raw is set, the grammar cannot use character literals (such as ‘'a'’).

• Accepted Values: Boolean.
• Default Value: true in D, false otherwise
• History: introduced in Bison 3.5. Was initially introduced in Bison 1.25 as ‘%raw’, but never worked and was removed in Bison 1.29.

Directive: %define api.value.automove ¶

• Language(s): C++
• Purpose: Let occurrences of semantic values of the right-hand sides of a rule be implicitly turned in rvalues. When enabled, a grammar such as:

  exp:
    "number"     { $$ = make_number ($1); }
  | exp "+" exp  { $$ = make_binary (add, $1, $3); }
  | "(" exp ")"  { $$ = $2; }
  

  is actually compiled as if you had written:

  exp:
    "number"     { $$ = make_number (std::move ($1)); }
  | exp "+" exp  { $$ = make_binary (add,
                                     std::move ($1),
                                     std::move ($3)); }
  | "(" exp ")"  { $$ = std::move ($2); }
  

  Using a value several times with automove enabled is typically an error. For instance, instead of:

  exp: "twice" exp  { $$ = make_binary (add, $2, $2); }
  

  write:

  exp: "twice" exp { auto v = $2; $$ = make_binary (add, v, v); }
  

  It is tempting to use std::move on one of the v, but the argument evaluation order in C++ is unspecified.

• Accepted Values: Boolean.
• Default Value: false
• History: introduced in Bison 3.2

Directive: %define api.value.type support ¶

Directive: %define api.value.type {type} ¶

• Language(s): all
• Purpose: The type for semantic values.
• Accepted Values:

  ‘{}’

  This grammar has no semantic value at all. This is not properly supported yet.

  ‘union-directive’ (C, C++, D)

  The type is defined thanks to the %union directive. You don’t have to define api.value.type in that case, using %union suffices. See The Union Declaration. For instance:

  %define api.value.type union-directive
  %union
  {
    int ival;
    char *sval;
  }
  %token <ival> INT "integer"
  %token <sval> STR "string"
  

  ‘union’ (C, C++)

  The symbols are defined with type names, from which Bison will generate a union. For instance:

  %define api.value.type union
  %token <int> INT "integer"
  %token <char *> STR "string"
  

  Most C++ objects cannot be stored in a union, use ‘variant’ instead.

  ‘variant’ (C++)

  This is similar to union, but special storage techniques are used to allow any kind of C++ object to be used. For instance:

  %define api.value.type variant
  %token <int> INT "integer"
  %token <std::string> STR "string"
  

  See C++ Variants.

  ‘{type}’

  Use this type as semantic value.

  %code requires
  {
    struct my_value
    {
      enum
      {
        is_int, is_str
      } kind;
      union
      {
        int ival;
        char *sval;
      } u;
    };
  }
  %define api.value.type {struct my_value}
  %token <u.ival> INT "integer"
  %token <u.sval> STR "string"
  

• Default Value:
  • - union-directive if %union is used, otherwise …
  • - int if type tags are used (i.e., ‘%token <type>…’ or ‘%nterm <type>…’ is used), otherwise …
  • - undefined.
• History: introduced in Bison 3.0. Was introduced for Java only in 2.3b as stype.

Directive: %define api.value.union.name name ¶

• Language(s): C
• Purpose: The tag of the generated union (not the name of the typedef). This variable is set to id when ‘%union id’ is used. There is no clear reason to give this union a name.
• Accepted Values: Any valid identifier.
• Default Value: YYSTYPE.
• History: Introduced in Bison 3.0.3.

Directive: %define lr.default-reduction when ¶

• Language(s): all
• Purpose: Specify the kind of states that are permitted to contain default reductions. See Default Reductions.
• Accepted Values: most, consistent, accepting
• Default Value:
  • accepting if lr.type is canonical-lr.
  • most otherwise.
• History: introduced as lr.default-reductions in 2.5, renamed as lr.default-reduction in 3.0.

Directive: %define lr.keep-unreachable-state ¶

• Language(s): all
• Purpose: Request that Bison allow unreachable parser states to remain in the parser tables. See Unreachable States.
• Accepted Values: Boolean
• Default Value: false
• History: introduced as lr.keep_unreachable_states in 2.3b, renamed as lr.keep-unreachable-states in 2.5, and as lr.keep-unreachable-state in 3.0.

Directive: %define lr.type type ¶

• Language(s): all
• Purpose: Specify the type of parser tables within the LR(1) family. See LR Table Construction.
• Accepted Values: lalr, ielr, canonical-lr
• Default Value: lalr

Directive: %define namespace {namespace} ¶

Obsoleted by api.namespace

Directive: %define parse.assert ¶

• Languages(s): C, C++
• Purpose: Issue runtime assertions to catch invalid uses. In C, some important invariants in the implementation of the parser are checked when this option is enabled.

  In C++, when variants are used (see C++ Variants), symbols must be constructed and destroyed properly. This option checks these constraints using runtime type information (RTTI). Therefore the generated code cannot be compiled with RTTI disabled (via compiler options such as -fno-rtti).

• Accepted Values: Boolean
• Default Value: false

Directive: %define parse.error verbosity ¶

• Languages(s): all
• Purpose: Control the generation of syntax error messages. See Error Reporting.
• Accepted Values:
  • simple Error messages passed to yyerror are simply "syntax error".
  • detailed Error messages report the unexpected token, and possibly the expected ones. However, this report can often be incorrect when LAC is not enabled (see LAC). Token name internationalization is supported.
  • verbose Similar (but inferior) to detailed. The D parser does not support this value.

    Error messages report the unexpected token, and possibly the expected ones. However, this report can often be incorrect when LAC is not enabled (see LAC).

    Does not support token internationalization. Using non-ASCII characters in token aliases is not portable.

  • custom The user is in charge of generating the syntax error message by defining the yyreport_syntax_error function. See The Syntax Error Reporting Function yyreport_syntax_error.
• Default Value: simple
• History: introduced in 3.0 with support for simple and verbose. Values custom and detailed were introduced in 3.6.

Directive: %define parse.lac when ¶

• Languages(s): C/C++ (deterministic parsers only), D and Java.
• Purpose: Enable LAC (lookahead correction) to improve syntax error handling. See LAC.
• Accepted Values: none, full
• Default Value: none

Directive: %define parse.trace ¶

• Languages(s): C, C++, D, Java
• Purpose: Require parser instrumentation for tracing. See Tracing Your Parser.

  In C/C++, define the macro YYDEBUG (or prefixDEBUG with ‘%define api.prefix {prefix}’), see Multiple Parsers in the Same Program) to 1 (if it is not already defined) so that the debugging facilities are compiled.

• Accepted Values: Boolean
• Default Value: false

Directive: %define parser_class_name {name} ¶

Obsoleted by api.parser.class

3.7.15 %code Summary

The %code directive inserts code verbatim into the output parser source at any of a predefined set of locations. It thus serves as a flexible and user-friendly alternative to the traditional Yacc prologue, %{code%}. This section summarizes the functionality of %code for the various target languages supported by Bison. For a detailed discussion of how to use %code in place of %{code%} for C/C++ and why it is advantageous to do so, see Prologue Alternatives.

Directive: %code {code} ¶

This is the unqualified form of the %code directive. It inserts code verbatim at a language-dependent default location in the parser implementation.

For C/C++, the default location is the parser implementation file after the usual contents of the parser header file. Thus, the unqualified form replaces %{code%} for most purposes.

For D and Java, the default location is inside the parser class.

Directive: %code qualifier {code} ¶

This is the qualified form of the %code directive. qualifier identifies the purpose of code and thus the location(s) where Bison should insert it. That is, if you need to specify location-sensitive code that does not belong at the default location selected by the unqualified %code form, use this form instead.

For any particular qualifier or for the unqualified form, if there are multiple occurrences of the %code directive, Bison concatenates the specified code in the order in which it appears in the grammar file.

Not all qualifiers are accepted for all target languages. Unaccepted qualifiers produce an error. Some of the accepted qualifiers are:

requires ¶

• Language(s): C, C++
• Purpose: This is the best place to write dependency code required for the value and location types (YYSTYPE and YYLTYPE in C). In other words, it’s the best place to define types referenced in %union directives. In C, if you use #define to override Bison’s default YYSTYPE and YYLTYPE definitions, then it is also the best place. However you should rather %define api.value.type and api.location.type.
• Location(s): The parser header file and the parser implementation file before the Bison-generated definitions of the value and location types (YYSTYPE and YYLTYPE in C).

provides ¶

• Language(s): C, C++
• Purpose: This is the best place to write additional definitions and declarations that should be provided to other modules.
• Location(s): The parser header file and the parser implementation file after the Bison-generated value and location types (YYSTYPE and YYLTYPE in C), and token definitions.

top ¶

• Language(s): C, C++
• Purpose: The unqualified %code or %code requires should usually be more appropriate than %code top. However, occasionally it is necessary to insert code much nearer the top of the parser implementation file. For example:

  %code top {
    #define _GNU_SOURCE
    #include <stdio.h>
  }
  

• Location(s): Near the top of the parser implementation file.

imports ¶

• Language(s): D, Java
• Purpose: This is the best place to write Java import directives. D syntax allows for import statements all throughout the code.
• Location(s): The parser Java file after any Java package directive and before any class definitions. The parser D file before any class definitions.

Though we say the insertion locations are language-dependent, they are technically skeleton-dependent. Writers of non-standard skeletons however should choose their locations consistently with the behavior of the standard Bison skeletons.

4.3.1 Calling Convention for yylex

The value that yylex returns must be the positive numeric code for the kind of token it has just found; a zero or negative value signifies end-of-input.

When a token kind is referred to in the grammar rules by a name, that name in the parser implementation file becomes an enumerator of the enum yytoken_kind_t whose definition is the proper numeric code for that token kind. So yylex should use the name to indicate that type. See Symbols, Terminal and Nonterminal.

When a token is referred to in the grammar rules by a character literal, the numeric code for that character is also the code for the token kind. So yylex can simply return that character code, possibly converted to unsigned char to avoid sign-extension. The null character must not be used this way, because its code is zero and that signifies end-of-input.

Here is an example showing these things:

int
yylex (void)
{
  …
  if (c == EOF)    /* Detect end-of-input. */
    return YYEOF;
  …
  else if (c == '+' || c == '-')
    return c;      /* Assume token kind for '+' is '+'. */
  …
  else
    return INT;    /* Return the kind of the token. */
  …
}

This interface has been designed so that the output from the lex utility can be used without change as the definition of yylex.

4.3.2 Special Tokens

In addition to the user defined tokens, Bison generates a few special tokens that yylex may return.

The YYEOF token denotes the end of file, and signals to the parser that there is nothing left afterwards. See Calling Convention for yylex, for an example.

Returning YYUNDEF tells the parser that some lexical error was found. It will emit an error message about an “invalid token”, and enter error-recovery (see Error Recovery). Returning an unknown token kind results in the exact same behavior.

Returning YYerror requires the parser to enter error-recovery without emitting an error message. This way the lexical analyzer can produce an accurate error messages about the invalid input (something the parser cannot do), and yet benefit from the error-recovery features of the parser.

int
yylex (void)
{
  …
  switch (c)
    {
      …
      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
        …
        return TOK_NUM;
      …
      case EOF:
        return YYEOF;
      default:
        yyerror ("syntax error: invalid character: %c", c);
        return YYerror;
    }
}

4.3.3 Finding Tokens by String Literals

If the grammar uses literal string tokens, there are two ways that yylex can determine the token kind codes for them:

• If the grammar defines symbolic token names as aliases for the literal string tokens, yylex can use these symbolic names like all others. In this case, the use of the literal string tokens in the grammar file has no effect on yylex.

  This is the preferred approach.

• yylex can search for the multicharacter token in the yytname table. This method is discouraged: the primary purpose of string aliases is forging good error messages, not describing the spelling of keywords. In addition, looking for the token kind at runtime incurs a (small but noticeable) cost.

  The yytname table is generated only if you use the %token-table declaration. See Bison Declaration Summary.

4.3.4 Semantic Values of Tokens

In an ordinary (nonreentrant) parser, the semantic value of the token must be stored into the global variable yylval. When you are using just one data type for semantic values, yylval has that type. Thus, if the type is int (the default), you might write this in yylex:

  …
  yylval = value;  /* Put value onto Bison stack. */
  return INT;      /* Return the kind of the token. */
  …

When you are using multiple data types, yylval’s type is a union made from the %union declaration (see The Union Declaration). So when you store a token’s value, you must use the proper member of the union. If the %union declaration looks like this:

%union {
  int intval;
  double val;
  symrec *tptr;
}

then the code in yylex might look like this:

  …
  yylval.intval = value; /* Put value onto Bison stack. */
  return INT;            /* Return the kind of the token. */
  …

4.3.5 Textual Locations of Tokens

If you are using the ‘@n’-feature (see Tracking Locations) in actions to keep track of the textual locations of tokens and groupings, then you must provide this information in yylex. The function yyparse expects to find the textual location of a token just parsed in the global variable yylloc. So yylex must store the proper data in that variable.

By default, the value of yylloc is a structure and you need only initialize the members that are going to be used by the actions. The four members are called first_line, first_column, last_line and last_column. Note that the use of this feature makes the parser noticeably slower.

The data type of yylloc has the name YYLTYPE.

4.3.6 Calling Conventions for Pure Parsers

When you use the Bison declaration %define api.pure full to request a pure, reentrant parser, the global communication variables yylval and yylloc cannot be used. (See A Pure (Reentrant) Parser.) In such parsers the two global variables are replaced by pointers passed as arguments to yylex. You must declare them as shown here, and pass the information back by storing it through those pointers.

int
yylex (YYSTYPE *lvalp, YYLTYPE *llocp)
{
  …
  *lvalp = value;  /* Put value onto Bison stack. */
  return INT;      /* Return the kind of the token. */
  …
}

If the grammar file does not use the ‘@’ constructs to refer to textual locations, then the type YYLTYPE will not be defined. In this case, omit the second argument; yylex will be called with only one argument.

If you wish to pass additional arguments to yylex, use %lex-param just like %parse-param (see The Parser Function yyparse). To pass additional arguments to both yylex and yyparse, use %param.

Directive: %lex-param {argument-declaration} … ¶

Specify that argument-declaration are additional yylex argument declarations. You may pass one or more such declarations, which is equivalent to repeating %lex-param.

Directive: %param {argument-declaration} … ¶

Specify that argument-declaration are additional yylex/yyparse argument declaration. This is equivalent to ‘%lex-param {argument-declaration} … %parse-param {argument-declaration} …’. You may pass one or more declarations, which is equivalent to repeating %param.

For instance:

%lex-param   {scanner_mode *mode}
%parse-param {parser_mode *mode}
%param       {environment_type *env}

results in the following signatures:

int yylex   (scanner_mode *mode, environment_type *env);
int yyparse (parser_mode *mode, environment_type *env);

If ‘%define api.pure full’ is added:

int yylex   (YYSTYPE *lvalp, scanner_mode *mode, environment_type *env);
int yyparse (parser_mode *mode, environment_type *env);

and finally, if both ‘%define api.pure full’ and %locations are used:

int yylex   (YYSTYPE *lvalp, YYLTYPE *llocp,
             scanner_mode *mode, environment_type *env);
int yyparse (parser_mode *mode, environment_type *env);

4.4.1 The Error Reporting Function yyerror

The Bison parser detects a syntax error (or parse error) whenever it reads a token which cannot satisfy any syntax rule. An action in the grammar can also explicitly proclaim an error, using the macro YYERROR (see Special Features for Use in Actions).

The Bison parser expects to report the error by calling an error reporting function named yyerror, which you must supply. It is called by yyparse whenever a syntax error is found, and it receives one argument. For a syntax error, the string is normally "syntax error".

If you invoke ‘%define parse.error detailed’ (or ‘custom’) in the Bison declarations section (see The Bison Declarations Section), then Bison provides a more verbose and specific error message string instead of just plain "syntax error". However, that message sometimes contains incorrect information if LAC is not enabled (see LAC).

The parser can detect one other kind of error: memory exhaustion. This can happen when the input contains constructions that are very deeply nested. It isn’t likely you will encounter this, since the Bison parser normally extends its stack automatically up to a very large limit. But if memory is exhausted, yyparse calls yyerror in the usual fashion, except that the argument string is "memory exhausted".

In some cases diagnostics like "syntax error" are translated automatically from English to some other language before they are passed to yyerror. See Parser Internationalization.

The following definition suffices in simple programs:

void
yyerror (char const *s)
{

  fprintf (stderr, "%s\n", s);
}

After yyerror returns to yyparse, the latter will attempt error recovery if you have written suitable error recovery grammar rules (see Error Recovery). If recovery is impossible, yyparse will immediately return 1.

Obviously, in location tracking pure parsers, yyerror should have an access to the current location. With %define api.pure, this is indeed the case for the GLR parsers, but not for the Yacc parser, for historical reasons, and this is the why %define api.pure full should be preferred over %define api.pure.

When %locations %define api.pure full is used, yyerror has the following signature:

void yyerror (YYLTYPE *locp, char const *msg);

The prototypes are only indications of how the code produced by Bison uses yyerror. Bison-generated code always ignores the returned value, so yyerror can return any type, including void. Also, yyerror can be a variadic function; that is why the message is always passed last.

Traditionally yyerror returns an int that is always ignored, but this is purely for historical reasons, and void is preferable since it more accurately describes the return type for yyerror.

The variable yynerrs contains the number of syntax errors reported so far. Normally this variable is global; but if you request a pure parser (see A Pure (Reentrant) Parser) then it is a local variable which only the actions can access.

4.4.2 The Syntax Error Reporting Function yyreport_syntax_error

If you invoke ‘%define parse.error custom’ (see The Bison Declarations Section), then the parser no longer passes syntax error messages to yyerror, rather it delegates that task to the user by calling the yyreport_syntax_error function.

The following functions and types are “static”: they are defined in the implementation file (*.c) and available only from there. They are meant to be used from the grammar’s epilogue.

Function: static int yyreport_syntax_error (const yypcontext_t *ctx) ¶

Report a syntax error to the user. Return 0 on success, YYENOMEM on memory exhaustion. Whether it uses yyerror is up to the user.

Use the following types and functions to build the error message.

Type: yypcontext_t ¶

An opaque type that captures the circumstances of the syntax error.

Type: yysymbol_kind_t ¶

An enum of all the grammar symbols, tokens and nonterminals. Its enumerators are forged from the symbol names:

enum yysymbol_kind_t
{
  YYSYMBOL_YYEMPTY = -2,      /* No symbol.  */
  YYSYMBOL_YYEOF = 0,         /* "end of file"  */
  YYSYMBOL_YYerror = 1,       /* error  */
  YYSYMBOL_YYUNDEF = 2,       /* "invalid token"  */
  YYSYMBOL_PLUS = 3,          /* "+"  */
  YYSYMBOL_MINUS = 4,         /* "-"  */
  [...]
  YYSYMBOL_VAR = 14,          /* "variable"  */
  YYSYMBOL_NEG = 15,          /* NEG  */
  YYSYMBOL_YYACCEPT = 16,     /* $accept  */
  YYSYMBOL_exp = 17,          /* exp  */
  YYSYMBOL_input = 18         /* input  */
};
typedef enum yysymbol_kind_t yysymbol_kind_t;

Function: static yysymbol_kind_t yypcontext_token (const yypcontext_t *ctx) ¶

The “unexpected” token: the symbol kind of the lookahead token that caused the syntax error. Returns YYSYMBOL_YYEMPTY if there is no lookahead.

Function: static YYLTYPE * yypcontext_location (const yypcontext_t *ctx) ¶

The location of the syntax error (that of the unexpected token).

Function: static int yypcontext_expected_tokens (const yypcontext_t *ctx, yysymbol_kind_t argv[], int argc) ¶

Fill argv with the expected tokens, which never includes YYSYMBOL_YYEMPTY, YYSYMBOL_YYerror, or YYSYMBOL_YYUNDEF.

Never put more than argc elements into argv, and on success return the number of tokens stored in argv. If there are more expected tokens than argc, fill argv up to argc and return 0. If there are no expected tokens, also return 0, but set argv[0] to YYSYMBOL_YYEMPTY.

When LAC is enabled, may return a negative number on errors, such as YYENOMEM on memory exhaustion.

If argv is null, return the size needed to store all the possible values, which is always less than YYNTOKENS.

Function: static const char * yysymbol_name (symbol_kind_t symbol) ¶

The name of the symbol whose kind is symbol, possibly translated.

A custom syntax error function looks as follows. This implementation is inappropriate for internationalization, see the c/bistromathic example for a better alternative.

static int
yyreport_syntax_error (const yypcontext_t *ctx)
{
  int res = 0;
  YYLOCATION_PRINT (stderr, *yypcontext_location (ctx));
  fprintf (stderr, ": syntax error");
  // Report the tokens expected at this point.
  {
    enum { TOKENMAX = 5 };
    yysymbol_kind_t expected[TOKENMAX];
    int n = yypcontext_expected_tokens (ctx, expected, TOKENMAX);
    if (n < 0)
      // Forward errors to yyparse.
      res = n;
    else
      for (int i = 0; i < n; ++i)
        fprintf (stderr, "%s %s",
                 i == 0 ? ": expected" : " or", yysymbol_name (expected[i]));
  }
  // Report the unexpected token.
  {
    yysymbol_kind_t lookahead = yypcontext_token (ctx);
    if (lookahead != YYSYMBOL_YYEMPTY)
      fprintf (stderr, " before %s", yysymbol_name (lookahead));
  }
  fprintf (stderr, "\n");
  return res;
}

You still must provide a yyerror function, used for instance to report memory exhaustion.

4.6.1 Enabling Internationalization

The maintainer of a package that uses a Bison-generated parser enables the internationalization of the parser’s output through the following steps. Here we assume a package that uses GNU Autoconf and GNU Automake.

1. Into the directory containing the GNU Autoconf macros used by the package —often called m4— copy the bison-i18n.m4 file installed by Bison under ‘share/aclocal/bison-i18n.m4’ in Bison’s installation directory. For example:

   cp /usr/local/share/aclocal/bison-i18n.m4 m4/bison-i18n.m4
   

2. In the top-level configure.ac, after the AM_GNU_GETTEXT invocation, add an invocation of BISON_I18N. This macro is defined in the file bison-i18n.m4 that you copied earlier. It causes configure to find the value of the BISON_LOCALEDIR variable, and it defines the source-language symbol YYENABLE_NLS to enable translations in the Bison-generated parser.
3. In the main function of your program, designate the directory containing Bison’s runtime message catalog, through a call to ‘bindtextdomain’ with domain name ‘bison-runtime’. For example:

   bindtextdomain ("bison-runtime", BISON_LOCALEDIR);
   

   Typically this appears after any other call bindtextdomain (PACKAGE, LOCALEDIR) that your package already has. Here we rely on ‘BISON_LOCALEDIR’ to be defined as a string through the Makefile.

4. In the Makefile.am that controls the compilation of the main function, make ‘BISON_LOCALEDIR’ available as a C preprocessor macro, either in ‘DEFS’ or in ‘AM_CPPFLAGS’. For example:

   DEFS = @DEFS@ -DBISON_LOCALEDIR='"$(BISON_LOCALEDIR)"'
   

   or:

   AM_CPPFLAGS = -DBISON_LOCALEDIR='"$(BISON_LOCALEDIR)"'
   

5. Finally, invoke the command autoreconf to generate the build infrastructure.

4.6.2 Token Internationalization

When the %define variable parse.error is set to custom or detailed, token aliases can be internationalized:

%token
    '\n'   _("end of line")
  <double>
    NUM    _("number")
  <symrec*>
    FUN    _("function")
    VAR    _("variable")

The remainder of the grammar may freely use either the token symbol (FUN) or its alias ("function"), but not with the internationalization marker (_("function")).

If at least one token alias is internationalized, then the generated parser will use both N_ and _, that must be defined (see The Programmer’s View in GNU gettext utilities). They are used only on string aliases marked for translation. In other words, even if your catalog features a translation for “function”, then with

%token
  <symrec*>
    FUN      "function"
    VAR    _("variable")

“function” will appear untranslated in debug traces and error messages.

Unless defined by the user, the end-of-file token, YYEOF, is provided “end of file” as an alias. It is also internationalized if the user internationalized tokens. To map it to another string, use:

%token END 0 _("end of input")

5.3.1 When Precedence is Needed

Consider the following ambiguous grammar fragment (ambiguous because the input ‘1 - 2 * 3’ can be parsed in two different ways):

expr:
  expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
…
;

Suppose the parser has seen the tokens ‘1’, ‘-’ and ‘2’; should it reduce them via the rule for the subtraction operator? It depends on the next token. Of course, if the next token is ‘)’, we must reduce; shifting is invalid because no single rule can reduce the token sequence ‘- 2 )’ or anything starting with that. But if the next token is ‘*’ or ‘<’, we have a choice: either shifting or reduction would allow the parse to complete, but with different results.

To decide which one Bison should do, we must consider the results. If the next operator token op is shifted, then it must be reduced first in order to permit another opportunity to reduce the difference. The result is (in effect) ‘1 - (2 op 3)’. On the other hand, if the subtraction is reduced before shifting op, the result is ‘(1 - 2) op 3’. Clearly, then, the choice of shift or reduce should depend on the relative precedence of the operators ‘-’ and op: ‘*’ should be shifted first, but not ‘<’.

What about input such as ‘1 - 2 - 5’; should this be ‘(1 - 2) - 5’ or should it be ‘1 - (2 - 5)’? For most operators we prefer the former, which is called left association. The latter alternative, right association, is desirable for assignment operators. The choice of left or right association is a matter of whether the parser chooses to shift or reduce when the stack contains ‘1 - 2’ and the lookahead token is ‘-’: shifting makes right-associativity.

5.3.2 Specifying Operator Precedence

Bison allows you to specify these choices with the operator precedence declarations %left and %right. Each such declaration contains a list of tokens, which are operators whose precedence and associativity is being declared. The %left declaration makes all those operators left-associative and the %right declaration makes them right-associative. A third alternative is %nonassoc, which declares that it is a syntax error to find the same operator twice “in a row”. The last alternative, %precedence, allows to define only precedence and no associativity at all. As a result, any associativity-related conflict that remains will be reported as an compile-time error. The directive %nonassoc creates run-time error: using the operator in a associative way is a syntax error. The directive %precedence creates compile-time errors: an operator can be involved in an associativity-related conflict, contrary to what expected the grammar author.

The relative precedence of different operators is controlled by the order in which they are declared. The first precedence/associativity declaration in the file declares the operators whose precedence is lowest, the next such declaration declares the operators whose precedence is a little higher, and so on.

5.3.3 Specifying Precedence Only

Since POSIX Yacc defines only %left, %right, and %nonassoc, which all defines precedence and associativity, little attention is paid to the fact that precedence cannot be defined without defining associativity. Yet, sometimes, when trying to solve a conflict, precedence suffices. In such a case, using %left, %right, or %nonassoc might hide future (associativity related) conflicts that would remain hidden.

The dangling else ambiguity (see Shift/Reduce Conflicts) can be solved explicitly. This shift/reduce conflicts occurs in the following situation, where the period denotes the current parsing state:

if e1 then if  e2 then s1 • else s2

The conflict involves the reduction of the rule ‘IF expr THEN stmt’, which precedence is by default that of its last token (THEN), and the shifting of the token ELSE. The usual disambiguation (attach the else to the closest if), shifting must be preferred, i.e., the precedence of ELSE must be higher than that of THEN. But neither is expected to be involved in an associativity related conflict, which can be specified as follows.

%precedence THEN
%precedence ELSE

The unary-minus is another typical example where associativity is usually over-specified, see Infix Notation Calculator: calc. The %left directive is traditionally used to declare the precedence of NEG, which is more than needed since it also defines its associativity. While this is harmless in the traditional example, who knows how NEG might be used in future evolutions of the grammar…

5.3.4 Precedence Examples

In our example, we would want the following declarations:

%left '<'
%left '-'
%left '*'

In a more complete example, which supports other operators as well, we would declare them in groups of equal precedence. For example, '+' is declared with '-':

%left '<' '>' '=' "!=" "<=" ">="
%left '+' '-'
%left '*' '/'

5.3.5 How Precedence Works

The first effect of the precedence declarations is to assign precedence levels to the terminal symbols declared. The second effect is to assign precedence levels to certain rules: each rule gets its precedence from the last terminal symbol mentioned in the components. (You can also specify explicitly the precedence of a rule. See Context-Dependent Precedence.)

Finally, the resolution of conflicts works by comparing the precedence of the rule being considered with that of the lookahead token. If the token’s precedence is higher, the choice is to shift. If the rule’s precedence is higher, the choice is to reduce. If they have equal precedence, the choice is made based on the associativity of that precedence level. The verbose output file made by -v (see Invoking Bison) says how each conflict was resolved.

Not all rules and not all tokens have precedence. If either the rule or the lookahead token has no precedence, then the default is to shift.

5.3.6 Using Precedence For Non Operators

Using properly precedence and associativity directives can help fixing shift/reduce conflicts that do not involve arithmetic-like operators. For instance, the “dangling else” problem (see Shift/Reduce Conflicts) can be solved elegantly in two different ways.

In the present case, the conflict is between the token "else" willing to be shifted, and the rule ‘if_stmt: "if" expr "then" stmt’, asking for reduction. By default, the precedence of a rule is that of its last token, here "then", so the conflict will be solved appropriately by giving "else" a precedence higher than that of "then", for instance as follows:

%precedence "then"
%precedence "else"

Alternatively, you may give both tokens the same precedence, in which case associativity is used to solve the conflict. To preserve the shift action, use right associativity:

%right "then" "else"

Neither solution is perfect however. Since Bison does not provide, so far, “scoped” precedence, both force you to declare the precedence of these keywords with respect to the other operators your grammar. Therefore, instead of being warned about new conflicts you would be unaware of (e.g., a shift/reduce conflict due to ‘if test then 1 else 2 + 3’ being ambiguous: ‘if test then 1 else (2 + 3)’ or ‘(if test then 1 else 2) + 3’?), the conflict will be already “fixed”.

5.8.1 LR Table Construction

For historical reasons, Bison constructs LALR(1) parser tables by default. However, LALR does not possess the full language-recognition power of LR. As a result, the behavior of parsers employing LALR parser tables is often mysterious. We presented a simple example of this effect in Mysterious Conflicts.

As we also demonstrated in that example, the traditional approach to eliminating such mysterious behavior is to restructure the grammar. Unfortunately, doing so correctly is often difficult. Moreover, merely discovering that LALR causes mysterious behavior in your parser can be difficult as well.

Fortunately, Bison provides an easy way to eliminate the possibility of such mysterious behavior altogether. You simply need to activate a more powerful parser table construction algorithm by using the %define lr.type directive.

Directive: %define lr.type type ¶

Specify the type of parser tables within the LR(1) family. The accepted values for type are:

• lalr (default)
• ielr
• canonical-lr

For example, to activate IELR, you might add the following directive to you grammar file:

%define lr.type ielr

For the example in Mysterious Conflicts, the mysterious conflict is then eliminated, so there is no need to invest time in comprehending the conflict or restructuring the grammar to fix it. If, during future development, the grammar evolves such that all mysterious behavior would have disappeared using just LALR, you need not fear that continuing to use IELR will result in unnecessarily large parser tables. That is, IELR generates LALR tables when LALR (using a deterministic parsing algorithm) is sufficient to support the full language-recognition power of LR. Thus, by enabling IELR at the start of grammar development, you can safely and completely eliminate the need to consider LALR’s shortcomings.

While IELR is almost always preferable, there are circumstances where LALR or the canonical LR parser tables described by Knuth (see Knuth 1965) can be useful. Here we summarize the relative advantages of each parser table construction algorithm within Bison:

• LALR

  There are at least two scenarios where LALR can be worthwhile:

  • GLR without static conflict resolution.

    When employing GLR parsers (see Writing GLR Parsers), if you do not resolve any conflicts statically (for example, with %left or %precedence), then the parser explores all potential parses of any given input. In this case, the choice of parser table construction algorithm is guaranteed not to alter the language accepted by the parser. LALR parser tables are the smallest parser tables Bison can currently construct, so they may then be preferable. Nevertheless, once you begin to resolve conflicts statically, GLR behaves more like a deterministic parser in the syntactic contexts where those conflicts appear, and so either IELR or canonical LR can then be helpful to avoid LALR’s mysterious behavior.

  • Malformed grammars.

    Occasionally during development, an especially malformed grammar with a major recurring flaw may severely impede the IELR or canonical LR parser table construction algorithm. LALR can be a quick way to construct parser tables in order to investigate such problems while ignoring the more subtle differences from IELR and canonical LR.

• IELR

  IELR (Inadequacy Elimination LR) is a minimal LR algorithm. That is, given any grammar (LR or non-LR), parsers using IELR or canonical LR parser tables always accept exactly the same set of sentences. However, like LALR, IELR merges parser states during parser table construction so that the number of parser states is often an order of magnitude less than for canonical LR. More importantly, because canonical LR’s extra parser states may contain duplicate conflicts in the case of non-LR grammars, the number of conflicts for IELR is often an order of magnitude less as well. This effect can significantly reduce the complexity of developing a grammar.

• Canonical LR

  While inefficient, canonical LR parser tables can be an interesting means to explore a grammar because they possess a property that IELR and LALR tables do not. That is, if %nonassoc is not used and default reductions are left disabled (see Default Reductions), then, for every left context of every canonical LR state, the set of tokens accepted by that state is guaranteed to be the exact set of tokens that is syntactically acceptable in that left context. It might then seem that an advantage of canonical LR parsers in production is that, under the above constraints, they are guaranteed to detect a syntax error as soon as possible without performing any unnecessary reductions. However, IELR parsers that use LAC are also able to achieve this behavior without sacrificing %nonassoc or default reductions. For details and a few caveats of LAC, see LAC.

For a more detailed exposition of the mysterious behavior in LALR parsers and the benefits of IELR, see Denny 2008, and Denny 2010 November.

5.8.2 Default Reductions

After parser table construction, Bison identifies the reduction with the largest lookahead set in each parser state. To reduce the size of the parser state, traditional Bison behavior is to remove that lookahead set and to assign that reduction to be the default parser action. Such a reduction is known as a default reduction.

Default reductions affect more than the size of the parser tables. They also affect the behavior of the parser:

• Delayed yylex invocations.

  A consistent state is a state that has only one possible parser action. If that action is a reduction and is encoded as a default reduction, then that consistent state is called a defaulted state. Upon reaching a defaulted state, a Bison-generated parser does not bother to invoke yylex to fetch the next token before performing the reduction. In other words, whether default reductions are enabled in consistent states determines how soon a Bison-generated parser invokes yylex for a token: immediately when it reaches that token in the input or when it eventually needs that token as a lookahead to determine the next parser action. Traditionally, default reductions are enabled, and so the parser exhibits the latter behavior.

  The presence of defaulted states is an important consideration when designing yylex and the grammar file. That is, if the behavior of yylex can influence or be influenced by the semantic actions associated with the reductions in defaulted states, then the delay of the next yylex invocation until after those reductions is significant. For example, the semantic actions might pop a scope stack that yylex uses to determine what token to return. Thus, the delay might be necessary to ensure that yylex does not look up the next token in a scope that should already be considered closed.

• Delayed syntax error detection.

  When the parser fetches a new token by invoking yylex, it checks whether there is an action for that token in the current parser state. The parser detects a syntax error if and only if either (1) there is no action for that token or (2) the action for that token is the error action (due to the use of %nonassoc). However, if there is a default reduction in that state (which might or might not be a defaulted state), then it is impossible for condition 1 to exist. That is, all tokens have an action. Thus, the parser sometimes fails to detect the syntax error until it reaches a later state.

  While default reductions never cause the parser to accept syntactically incorrect sentences, the delay of syntax error detection can have unexpected effects on the behavior of the parser. However, the delay can be caused anyway by parser state merging and the use of %nonassoc, and it can be fixed by another Bison feature, LAC. We discuss the effects of delayed syntax error detection and LAC more in the next section (see LAC).

For canonical LR, the only default reduction that Bison enables by default is the accept action, which appears only in the accepting state, which has no other action and is thus a defaulted state. However, the default accept action does not delay any yylex invocation or syntax error detection because the accept action ends the parse.

For LALR and IELR, Bison enables default reductions in nearly all states by default. There are only two exceptions. First, states that have a shift action on the error token do not have default reductions because delayed syntax error detection could then prevent the error token from ever being shifted in that state. However, parser state merging can cause the same effect anyway, and LAC fixes it in both cases, so future versions of Bison might drop this exception when LAC is activated. Second, GLR parsers do not record the default reduction as the action on a lookahead token for which there is a conflict. The correct action in this case is to split the parse instead.

To adjust which states have default reductions enabled, use the %define lr.default-reduction directive.

Directive: %define lr.default-reduction where ¶

Specify the kind of states that are permitted to contain default reductions. The accepted values of where are:

• most (default for LALR and IELR)
• consistent
• accepting (default for canonical LR)

5.8.3 LAC

Canonical LR, IELR, and LALR can suffer from a couple of problems upon encountering a syntax error. First, the parser might perform additional parser stack reductions before discovering the syntax error. Such reductions can perform user semantic actions that are unexpected because they are based on an invalid token, and they cause error recovery to begin in a different syntactic context than the one in which the invalid token was encountered. Second, when verbose error messages are enabled (see Error Reporting), the expected token list in the syntax error message can both contain invalid tokens and omit valid tokens.

The culprits for the above problems are %nonassoc, default reductions in inconsistent states (see Default Reductions), and parser state merging. Because IELR and LALR merge parser states, they suffer the most. Canonical LR can suffer only if %nonassoc is used or if default reductions are enabled for inconsistent states.

LAC (Lookahead Correction) is a new mechanism within the parsing algorithm that solves these problems for canonical LR, IELR, and LALR without sacrificing %nonassoc, default reductions, or state merging. You can enable LAC with the %define parse.lac directive.

Directive: %define parse.lac value ¶

Enable LAC to improve syntax error handling.

• none (default)
• full

This feature is currently only available for deterministic parsers in C and C++.

Conceptually, the LAC mechanism is straight-forward. Whenever the parser fetches a new token from the scanner so that it can determine the next parser action, it immediately suspends normal parsing and performs an exploratory parse using a temporary copy of the normal parser state stack. During this exploratory parse, the parser does not perform user semantic actions. If the exploratory parse reaches a shift action, normal parsing then resumes on the normal parser stacks. If the exploratory parse reaches an error instead, the parser reports a syntax error. If verbose syntax error messages are enabled, the parser must then discover the list of expected tokens, so it performs a separate exploratory parse for each token in the grammar.

There is one subtlety about the use of LAC. That is, when in a consistent parser state with a default reduction, the parser will not attempt to fetch a token from the scanner because no lookahead is needed to determine the next parser action. Thus, whether default reductions are enabled in consistent states (see Default Reductions) affects how soon the parser detects a syntax error: immediately when it reaches an erroneous token or when it eventually needs that token as a lookahead to determine the next parser action. The latter behavior is probably more intuitive, so Bison currently provides no way to achieve the former behavior while default reductions are enabled in consistent states.

Thus, when LAC is in use, for some fixed decision of whether to enable default reductions in consistent states, canonical LR and IELR behave almost exactly the same for both syntactically acceptable and syntactically unacceptable input. While LALR still does not support the full language-recognition power of canonical LR and IELR, LAC at least enables LALR’s syntax error handling to correctly reflect LALR’s language-recognition power.

There are a few caveats to consider when using LAC:

• Infinite parsing loops.

  IELR plus LAC does have one shortcoming relative to canonical LR. Some parsers generated by Bison can loop infinitely. LAC does not fix infinite parsing loops that occur between encountering a syntax error and detecting it, but enabling canonical LR or disabling default reductions sometimes does.

• Verbose error message limitations.

  Because of internationalization considerations, Bison-generated parsers limit the size of the expected token list they are willing to report in a verbose syntax error message. If the number of expected tokens exceeds that limit, the list is simply dropped from the message. Enabling LAC can increase the size of the list and thus cause the parser to drop it. Of course, dropping the list is better than reporting an incorrect list.

• Performance.

  Because LAC requires many parse actions to be performed twice, it can have a performance penalty. However, not all parse actions must be performed twice. Specifically, during a series of default reductions in consistent states and shift actions, the parser never has to initiate an exploratory parse. Moreover, the most time-consuming tasks in a parse are often the file I/O, the lexical analysis performed by the scanner, and the user’s semantic actions, but none of these are performed during the exploratory parse. Finally, the base of the temporary stack used during an exploratory parse is a pointer into the normal parser state stack so that the stack is never physically copied. In our experience, the performance penalty of LAC has proved insignificant for practical grammars.

While the LAC algorithm shares techniques that have been recognized in the parser community for years, for the publication that introduces LAC, see Denny 2010 May.

5.8.4 Unreachable States

If there exists no sequence of transitions from the parser’s start state to some state s, then Bison considers s to be an unreachable state. A state can become unreachable during conflict resolution if Bison disables a shift action leading to it from a predecessor state.

By default, Bison removes unreachable states from the parser after conflict resolution because they are useless in the generated parser. However, keeping unreachable states is sometimes useful when trying to understand the relationship between the parser and the grammar.

Directive: %define lr.keep-unreachable-state value ¶

Request that Bison allow unreachable states to remain in the parser tables. value must be a Boolean. The default is false.

There are a few caveats to consider:

• Missing or extraneous warnings.

  Unreachable states may contain conflicts and may use rules not used in any other state. Thus, keeping unreachable states may induce warnings that are irrelevant to your parser’s behavior, and it may eliminate warnings that are relevant. Of course, the change in warnings may actually be relevant to a parser table analysis that wants to keep unreachable states, so this behavior will likely remain in future Bison releases.

• Other useless states.

  While Bison is able to remove unreachable states, it is not guaranteed to remove other kinds of useless states. Specifically, when Bison disables reduce actions during conflict resolution, some goto actions may become useless, and thus some additional states may become useless. If Bison were to compute which goto actions were useless and then disable those actions, it could identify such states as unreachable and then remove those states. However, Bison does not compute which goto actions are useless.