1. The Concepts of Bison

This chapter introduces many of the basic concepts without which the details of Bison will not make sense. If you do not already know how to use Bison or Yacc, we suggest you start by reading this chapter carefully.

1.1 Languages and Context-Free Grammars

In order for Bison to parse a language, it must be described by a context-free grammar. This means that you specify one or more syntactic groupings and give rules for constructing them from their parts. For example, in the C language, one kind of grouping is called an ‘expression’. One rule for making an expression might be, “An expression can be made of a minus sign and another expression”. Another would be, “An expression can be an integer”. As you can see, rules are often recursive, but there must be at least one rule which leads out of the recursion.

The most common formal system for presenting such rules for humans to read is Backus-Naur Form or “BNF”, which was developed in order to specify the language Algol 60. Any grammar expressed in BNF is a context-free grammar. The input to Bison is essentially machine-readable BNF.

There are various important subclasses of context-free grammars. Although it can handle almost all context-free grammars, Bison is optimized for what are called LR(1) grammars. In brief, in these grammars, it must be possible to tell how to parse any portion of an input string with just a single token of lookahead. For historical reasons, Bison by default is limited by the additional restrictions of LALR(1), which is hard to explain simply. See section Mysterious Conflicts, for more information on this. As an experimental feature, you can escape these additional restrictions by requesting IELR(1) or canonical LR(1) parser tables. See section LR Table Construction, to learn how.

Parsers for LR(1) grammars are deterministic, meaning roughly that the next grammar rule to apply at any point in the input is uniquely determined by the preceding input and a fixed, finite portion (called a lookahead) of the remaining input. A context-free grammar can be ambiguous, meaning that there are multiple ways to apply the grammar rules to get the same inputs. Even unambiguous grammars can be nondeterministic, meaning that no fixed lookahead always suffices to determine the next grammar rule to apply. With the proper declarations, Bison is also able to parse these more general context-free grammars, using a technique known as GLR parsing (for Generalized LR). Bison’s GLR parsers are able to handle any context-free grammar for which the number of possible parses of any given string is finite.

In the formal grammatical rules for a language, each kind of syntactic unit or grouping is named by a symbol. Those which are built by grouping smaller constructs according to grammatical rules are called nonterminal symbols; those which can’t be subdivided are called terminal symbols or token types. We call a piece of input corresponding to a single terminal symbol a token, and a piece corresponding to a single nonterminal symbol a grouping.

We can use the C language as an example of what symbols, terminal and nonterminal, mean. The tokens of C are identifiers, constants (numeric and string), and the various keywords, arithmetic operators and punctuation marks. So the terminal symbols of a grammar for C include ‘identifier’, ‘number’, ‘string’, plus one symbol for each keyword, operator or punctuation mark: ‘if’, ‘return’, ‘const’, ‘static’, ‘int’, ‘char’, ‘plus-sign’, ‘open-brace’, ‘close-brace’, ‘comma’ and many more. (These tokens can be subdivided into characters, but that is a matter of lexicography, not grammar.)

Here is a simple C function subdivided into tokens:

int             /* keyword `int' */
square (int x)  /* identifier, open-paren, keyword `int',
                   identifier, close-paren */
{               /* open-brace */
  return x * x; /* keyword `return', identifier, asterisk,
                   identifier, semicolon */
}               /* close-brace */

The syntactic groupings of C include the expression, the statement, the declaration, and the function definition. These are represented in the grammar of C by nonterminal symbols ‘expression’, ‘statement’, ‘declaration’ and ‘function definition’. The full grammar uses dozens of additional language constructs, each with its own nonterminal symbol, in order to express the meanings of these four. The example above is a function definition; it contains one declaration, and one statement. In the statement, each ‘x’ is an expression and so is ‘x * x’.

Each nonterminal symbol must have grammatical rules showing how it is made out of simpler constructs. For example, one kind of C statement is the return statement; this would be described with a grammar rule which reads informally as follows:

A ‘statement’ can be made of a ‘return’ keyword, an ‘expression’ and a ‘semicolon’.

There would be many other rules for ‘statement’, one for each kind of statement in C.

One nonterminal symbol must be distinguished as the special one which defines a complete utterance in the language. It is called the start symbol. In a compiler, this means a complete input program. In the C language, the nonterminal symbol ‘sequence of definitions and declarations’ plays this role.

For example, ‘1 + 2’ is a valid C expression—a valid part of a C program—but it is not valid as an entire C program. In the context-free grammar of C, this follows from the fact that ‘expression’ is not the start symbol.

The Bison parser reads a sequence of tokens as its input, and groups the tokens using the grammar rules. If the input is valid, the end result is that the entire token sequence reduces to a single grouping whose symbol is the grammar’s start symbol. If we use a grammar for C, the entire input must be a ‘sequence of definitions and declarations’. If not, the parser reports a syntax error.

1.2 From Formal Rules to Bison Input

A formal grammar is a mathematical construct. To define the language for Bison, you must write a file expressing the grammar in Bison syntax: a Bison grammar file. See section Bison Grammar Files.

A nonterminal symbol in the formal grammar is represented in Bison input as an identifier, like an identifier in C. By convention, it should be in lower case, such as expr, stmt or declaration.

The Bison representation for a terminal symbol is also called a token type. Token types as well can be represented as C-like identifiers. By convention, these identifiers should be upper case to distinguish them from nonterminals: for example, INTEGER, IDENTIFIER, IF or RETURN. A terminal symbol that stands for a particular keyword in the language should be named after that keyword converted to upper case. The terminal symbol error is reserved for error recovery. See section Symbols, Terminal and Nonterminal.

A terminal symbol can also be represented as a character literal, just like a C character constant. You should do this whenever a token is just a single character (parenthesis, plus-sign, etc.): use that same character in a literal as the terminal symbol for that token.

A third way to represent a terminal symbol is with a C string constant containing several characters. See section Symbols, Terminal and Nonterminal, for more information.

The grammar rules also have an expression in Bison syntax. For example, here is the Bison rule for a C return statement. The semicolon in quotes is a literal character token, representing part of the C syntax for the statement; the naked semicolon, and the colon, are Bison punctuation used in every rule.

stmt: RETURN expr ';' ;

See section Syntax of Grammar Rules.

1.3 Semantic Values

A formal grammar selects tokens only by their classifications: for example, if a rule mentions the terminal symbol ‘integer constant’, it means that any integer constant is grammatically valid in that position. The precise value of the constant is irrelevant to how to parse the input: if ‘x+4’ is grammatical then ‘x+1’ or ‘x+3989’ is equally grammatical.

But the precise value is very important for what the input means once it is parsed. A compiler is useless if it fails to distinguish between 4, 1 and 3989 as constants in the program! Therefore, each token in a Bison grammar has both a token type and a semantic value. See section Defining Language Semantics, for details.

The token type is a terminal symbol defined in the grammar, such as INTEGER, IDENTIFIER or ','. It tells everything you need to know to decide where the token may validly appear and how to group it with other tokens. The grammar rules know nothing about tokens except their types.

The semantic value has all the rest of the information about the meaning of the token, such as the value of an integer, or the name of an identifier. (A token such as ',' which is just punctuation doesn’t need to have any semantic value.)

For example, an input token might be classified as token type INTEGER and have the semantic value 4. Another input token might have the same token type INTEGER but value 3989. When a grammar rule says that INTEGER is allowed, either of these tokens is acceptable because each is an INTEGER. When the parser accepts the token, it keeps track of the token’s semantic value.

Each grouping can also have a semantic value as well as its nonterminal symbol. For example, in a calculator, an expression typically has a semantic value that is a number. In a compiler for a programming language, an expression typically has a semantic value that is a tree structure describing the meaning of the expression.

1.4 Semantic Actions

In order to be useful, a program must do more than parse input; it must also produce some output based on the input. In a Bison grammar, a grammar rule can have an action made up of C statements. Each time the parser recognizes a match for that rule, the action is executed. See section Actions.

Most of the time, the purpose of an action is to compute the semantic value of the whole construct from the semantic values of its parts. For example, suppose we have a rule which says an expression can be the sum of two expressions. When the parser recognizes such a sum, each of the subexpressions has a semantic value which describes how it was built up. The action for this rule should create a similar sort of value for the newly recognized larger expression.

For example, here is a rule that says an expression can be the sum of two subexpressions:

expr: expr '+' expr   { $$ = $1 + $3; } ;

The action says how to produce the semantic value of the sum expression from the values of the two subexpressions.

1.5 Writing GLR Parsers

In some grammars, Bison’s deterministic LR(1) parsing algorithm cannot decide whether to apply a certain grammar rule at a given point. That is, it may not be able to decide (on the basis of the input read so far) which of two possible reductions (applications of a grammar rule) applies, or whether to apply a reduction or read more of the input and apply a reduction later in the input. These are known respectively as reduce/reduce conflicts (see section Reduce/Reduce Conflicts), and shift/reduce conflicts (see section Shift/Reduce Conflicts).

To use a grammar that is not easily modified to be LR(1), a more general parsing algorithm is sometimes necessary. If you include %glr-parser among the Bison declarations in your file (see section Outline of a Bison Grammar), the result is a Generalized LR (GLR) parser. These parsers handle Bison grammars that contain no unresolved conflicts (i.e., after applying precedence declarations) identically to deterministic parsers. However, when faced with unresolved shift/reduce and reduce/reduce conflicts, GLR parsers use the simple expedient of doing both, effectively cloning the parser to follow both possibilities. Each of the resulting parsers can again split, so that at any given time, there can be any number of possible parses being explored. The parsers proceed in lockstep; that is, all of them consume (shift) a given input symbol before any of them proceed to the next. Each of the cloned parsers eventually meets one of two possible fates: either it runs into a parsing error, in which case it simply vanishes, or it merges with another parser, because the two of them have reduced the input to an identical set of symbols.

During the time that there are multiple parsers, semantic actions are recorded, but not performed. When a parser disappears, its recorded semantic actions disappear as well, and are never performed. When a reduction makes two parsers identical, causing them to merge, Bison records both sets of semantic actions. Whenever the last two parsers merge, reverting to the single-parser case, Bison resolves all the outstanding actions either by precedences given to the grammar rules involved, or by performing both actions, and then calling a designated user-defined function on the resulting values to produce an arbitrary merged result.

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 section Semantic Info in Token Types) 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>
  #define YYSTYPE char const *
  int yylex (void);
  void yyerror (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 section 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 section 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 <stmtMerge>
| decl      %merge <stmtMerge>
;

and define the stmtMerge function as:

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

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

%{
  #define YYSTYPE char const *
  static YYSTYPE stmtMerge (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.

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.

1.5.3.1 Deferred semantic actions

By definition, a deferred semantic action is not performed at the same time as the associated reduction. This raises caveats for several Bison features you might use in a semantic action in a GLR parser.

In any semantic action, you can examine yychar to determine the type of the lookahead token present at the time of the associated reduction. After checking that yychar is not set to YYEMPTY or YYEOF, you can then examine yylval and yylloc to determine the lookahead token’s semantic value and location, if any. In a nondeferred semantic action, you can also modify any of these variables to influence syntax analysis. See section Lookahead Tokens.

In a deferred semantic action, it’s too late to influence syntax analysis. In this case, yychar, yylval, and yylloc are set to shallow copies of the values they had at the time of the associated reduction. For this reason alone, modifying them is dangerous. Moreover, the result of modifying them is undefined and subject to change with future versions of Bison. For example, if a semantic action might be deferred, you should never write it to invoke yyclearin (see section Special Features for Use in Actions) or to attempt to free memory referenced by yylval.

1.5.3.2 YYERROR

Another Bison feature requiring special consideration is YYERROR (see section Special Features for Use in Actions), which you can invoke in a semantic action to initiate error recovery. During deterministic GLR operation, the effect of YYERROR is the same as its effect in a deterministic parser. The effect in a deferred action is similar, but the precise point of the error is undefined; instead, the parser reverts to deterministic operation, selecting an unspecified stack on which to continue with a syntax error. In a semantic predicate (see Controlling a Parse with Arbitrary Predicates) during nondeterministic parsing, YYERROR silently prunes the parse that invoked the test.

1.5.3.3 Restrictions on semantic values and locations

GLR parsers require that you use POD (Plain Old Data) types for semantic values and location types when using the generated parsers as C++ code.

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. (This feature is experimental and may evolve. We welcome user feedback.) 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 action, except that its text is treated 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 be 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 mid-rule 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.

1.5.5 Considerations when Compiling GLR Parsers

The GLR parsers require a compiler for ISO C89 or later. In addition, they use the inline keyword, which is not C89, but is C99 and is a common extension in pre-C99 compilers. It is up to the user of these parsers to handle portability issues. For instance, if using Autoconf and the Autoconf macro AC_C_INLINE, a mere

%{
  #include <config.h>
%}

will suffice. Otherwise, we suggest

%{
  #if (__STDC_VERSION__ < 199901 && ! defined __GNUC__ \
       && ! defined inline)
  # define inline
  #endif
%}

1.6 Locations

Many applications, like interpreters or compilers, have to produce verbose and useful error messages. To achieve this, one must be able to keep track of the textual location, or location, of each syntactic construct. Bison provides a mechanism for handling these locations.

Each token has a semantic value. In a similar fashion, each token has an associated location, but the type of locations is the same for all tokens and groupings. Moreover, the output parser is equipped with a default data structure for storing locations (see section Tracking Locations, for more details).

Like semantic values, locations can be reached in actions using a dedicated set of constructs. In the example above, the location of the whole grouping is @$, while the locations of the subexpressions are @1 and @3.

When a rule is matched, a default action is used to compute the semantic value of its left hand side (see section Actions). In the same way, another default action is used for locations. However, the action for locations is general enough for most cases, meaning there is usually no need to describe for each rule how @$ should be formed. When building a new location for a given grouping, the default behavior of the output parser is to take the beginning of the first symbol, and the end of the last symbol.

1.7 Bison Output: the Parser Implementation File

When you run Bison, you give it a Bison grammar file as input. The most important output is a C source file that implements a parser for the language described by the grammar. This parser is called a Bison parser, and this file is called a Bison parser implementation file. Keep in mind that the Bison utility and the Bison parser are two distinct programs: the Bison utility is a program whose output is the Bison parser implementation file that becomes part of your program.

The job of the Bison parser is to group tokens into groupings according to the grammar rules—for example, to build identifiers and operators into expressions. As it does this, it runs the actions for the grammar rules it uses.

The tokens come from a function called the lexical analyzer that you must supply in some fashion (such as by writing it in C). The Bison parser calls the lexical analyzer each time it wants a new token. It doesn’t know what is “inside” the tokens (though their semantic values may reflect this). Typically the lexical analyzer makes the tokens by parsing characters of text, but Bison does not depend on this. See section The Lexical Analyzer Function yylex.

The Bison parser implementation file is C code which defines a function named yyparse which implements that grammar. This function does not make a complete C program: you must supply some additional functions. One is the lexical analyzer. Another is an error-reporting function which the parser calls to report an error. In addition, a complete C program must start with a function called main; you have to provide this, and arrange for it to call yyparse or the parser will never run. See section Parser C-Language Interface.

Aside from the token type names and the symbols in the actions you write, all symbols defined in the Bison parser implementation file itself begin with ‘yy’ or ‘YY’. This includes interface functions such as the lexical analyzer function yylex, the error reporting function yyerror and the parser function yyparse itself. This also includes numerous identifiers used for internal purposes. Therefore, you should avoid using C identifiers starting with ‘yy’ or ‘YY’ in the Bison grammar file except for the ones defined in this manual. Also, you should avoid using the C identifiers ‘malloc’ and ‘free’ for anything other than their usual meanings.

In some cases the Bison parser implementation file includes system headers, and in those cases your code should respect the identifiers reserved by those headers. On some non-GNU hosts, <alloca.h>, <malloc.h>, <stddef.h>, and <stdlib.h> are included as needed to declare memory allocators and related types. <libintl.h> is included if message translation is in use (see section Parser Internationalization). Other system headers may be included if you define YYDEBUG to a nonzero value (see section Tracing Your Parser).

1.8 Stages in Using Bison

The actual language-design process using Bison, from grammar specification to a working compiler or interpreter, has these parts:

1. Formally specify the grammar in a form recognized by Bison (see section Bison Grammar Files). For each grammatical rule in the language, describe the action that is to be taken when an instance of that rule is recognized. The action is described by a sequence of C statements.
2. Write a lexical analyzer to process input and pass tokens to the parser. The lexical analyzer may be written by hand in C (see section The Lexical Analyzer Function yylex). It could also be produced using Lex, but the use of Lex is not discussed in this manual.
3. Write a controlling function that calls the Bison-produced parser.
4. Write error-reporting routines.

To turn this source code as written into a runnable program, you must follow these steps:

1. Run Bison on the grammar to produce the parser.
2. Compile the code output by Bison, as well as any other source files.
3. Link the object files to produce the finished product.

1.9 The Overall Layout of a Bison Grammar

The input file for the Bison utility is a Bison grammar file. The general form of a Bison grammar file is as follows:

%{
Prologue
%}

Bison declarations

%%
Grammar rules
%%
Epilogue

The ‘%%’, ‘%{’ and ‘%}’ are punctuation that appears in every Bison grammar file to separate the sections.

The prologue may define types and variables used in the actions. You can also use preprocessor commands to define macros used there, and use #include to include header files that do any of these things. You need to declare the lexical analyzer yylex and the error printer yyerror here, along with any other global identifiers used by the actions in the grammar rules.

The Bison declarations declare the names of the terminal and nonterminal symbols, and may also describe operator precedence and the data types of semantic values of various symbols.

The grammar rules define how to construct each nonterminal symbol from its parts.

The epilogue can contain any code you want to use. Often the definitions of functions declared in the prologue go here. In a simple program, all the rest of the program can go here.

This document was generated by Rick Perry on December 29, 2013 using texi2html 1.82.