+@noindent
+This is another example of using @acronym{GLR} to parse an unambiguous
+construct, as shown in the previous section (@pxref{Simple GLR Parsers}).
+Here, there is no ambiguity (this cannot be parsed as a declaration).
+However, at the time the Bison parser encounters @code{x}, it does not
+have enough information to resolve the reduce/reduce conflict (again,
+between @code{x} as an @code{expr} or a @code{declarator}). In this
+case, no precedence declaration is used. Again, the parser splits
+into two, one assuming that @code{x} is an @code{expr}, and the other
+assuming @code{x} is a @code{declarator}. The second of these parsers
+then vanishes when it sees @code{+}, and the parser prints
+
+@example
+x T <cast> y +
+@end example
+
+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 @code{stmt} as
+follows:
+
+@example
+stmt : expr ';' %merge <stmtMerge>
+ | decl %merge <stmtMerge>
+ ;
+@end example
+
+@noindent
+and define the @code{stmtMerge} function as:
+
+@example
+static YYSTYPE
+stmtMerge (YYSTYPE x0, YYSTYPE x1)
+@{
+ printf ("<OR> ");
+ return "";
+@}
+@end example
+
+@noindent
+with an accompanying forward declaration
+in the C declarations at the beginning of the file:
+
+@example
+%@{
+ #define YYSTYPE char const *
+ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);
+%@}
+@end example
+
+@noindent
+With these declarations, the resulting parser parses the first example
+as both an @code{expr} and a @code{decl}, and prints
+
+@example
+"x" y z + T <init-declare> x T <cast> y z + = <OR>
+@end example
+
+Bison requires that all of the
+productions that participate in any particular merge have identical
+@samp{%merge} clauses. Otherwise, the ambiguity would be unresolvable,
+and the parser will report an error during any parse that results in
+the offending merge.
+
+@node GLR Semantic Actions
+@subsection GLR Semantic Actions
+
+@cindex 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 @acronym{GLR} parser.
+
+@vindex yychar
+@cindex @acronym{GLR} parsers and @code{yychar}
+@vindex yylval
+@cindex @acronym{GLR} parsers and @code{yylval}
+@vindex yylloc
+@cindex @acronym{GLR} parsers and @code{yylloc}
+In any semantic action, you can examine @code{yychar} to determine the type of
+the look-ahead token present at the time of the associated reduction.
+After checking that @code{yychar} is not set to @code{YYEMPTY} or @code{YYEOF},
+you can then examine @code{yylval} and @code{yylloc} to determine the
+look-ahead 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.
+@xref{Look-Ahead, ,Look-Ahead Tokens}.
+
+@findex yyclearin
+@cindex @acronym{GLR} parsers and @code{yyclearin}
+In a deferred semantic action, it's too late to influence syntax analysis.
+In this case, @code{yychar}, @code{yylval}, and @code{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 @code{yyclearin} (@pxref{Action Features}) or to attempt to free
+memory referenced by @code{yylval}.
+
+@findex YYERROR
+@cindex @acronym{GLR} parsers and @code{YYERROR}
+Another Bison feature requiring special consideration is @code{YYERROR}
+(@pxref{Action Features}), which you can invoke in a semantic action to
+initiate error recovery.
+During deterministic @acronym{GLR} operation, the effect of @code{YYERROR} is
+the same as its effect in an @acronym{LALR}(1) parser.
+In a deferred semantic action, its effect is undefined.
+@c The effect is probably a syntax error at the split point.
+
+Also, see @ref{Location Default Action, ,Default Action for Locations}, which
+describes a special usage of @code{YYLLOC_DEFAULT} in @acronym{GLR} parsers.
+
+@node Compiler Requirements
+@subsection Considerations when Compiling @acronym{GLR} Parsers
+@cindex @code{inline}
+@cindex @acronym{GLR} parsers and @code{inline}
+
+The @acronym{GLR} parsers require a compiler for @acronym{ISO} C89 or
+later. In addition, they use the @code{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 @code{AC_C_INLINE}, a mere
+
+@example
+%@{
+ #include <config.h>
+%@}
+@end example
+
+@noindent
+will suffice. Otherwise, we suggest
+
+@example
+%@{
+ #if __STDC_VERSION__ < 199901 && ! defined __GNUC__ && ! defined inline
+ #define inline
+ #endif
+%@}
+@end example
+
+@node Locations Overview
+@section Locations
+@cindex location
+@cindex textual location
+@cindex location, textual
+
+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 @dfn{textual location}, or @dfn{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 (@pxref{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 @code{@@$}, while the locations of the subexpressions are @code{@@1} and
+@code{@@3}.
+
+When a rule is matched, a default action is used to compute the semantic value
+of its left hand side (@pxref{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 @code{@@$} 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.
+
+@node Bison Parser
+@section Bison Output: the Parser File
+@cindex Bison parser
+@cindex Bison utility
+@cindex lexical analyzer, purpose
+@cindex parser
+
+When you run Bison, you give it a Bison grammar file as input. The output
+is a C source file that parses the language described by the grammar.
+This file is called a @dfn{Bison parser}. 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 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 @dfn{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.
+@xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
+
+The Bison parser file is C code which defines a function named
+@code{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 @code{main}; you have to provide this, and
+arrange for it to call @code{yyparse} or the parser will never run.
+@xref{Interface, ,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 file itself
+begin with @samp{yy} or @samp{YY}. This includes interface functions
+such as the lexical analyzer function @code{yylex}, the error reporting
+function @code{yyerror} and the parser function @code{yyparse} itself.
+This also includes numerous identifiers used for internal purposes.
+Therefore, you should avoid using C identifiers starting with @samp{yy}
+or @samp{YY} in the Bison grammar file except for the ones defined in
+this manual. Also, you should avoid using the C identifiers
+@samp{malloc} and @samp{free} for anything other than their usual
+meanings.
+
+In some cases the Bison parser file includes system headers, and in
+those cases your code should respect the identifiers reserved by those
+headers. On some non-@acronym{GNU} hosts, @code{<alloca.h>}, @code{<malloc.h>},
+@code{<stddef.h>}, and @code{<stdlib.h>} are included as needed to
+declare memory allocators and related types. @code{<libintl.h>} is
+included if message translation is in use
+(@pxref{Internationalization}). Other system headers may
+be included if you define @code{YYDEBUG} to a nonzero value
+(@pxref{Tracing, ,Tracing Your Parser}).
+
+@node Stages
+@section Stages in Using Bison
+@cindex stages in using Bison
+@cindex using Bison
+
+The actual language-design process using Bison, from grammar specification
+to a working compiler or interpreter, has these parts:
+
+@enumerate
+@item
+Formally specify the grammar in a form recognized by Bison
+(@pxref{Grammar File, ,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.
+
+@item
+Write a lexical analyzer to process input and pass tokens to the parser.
+The lexical analyzer may be written by hand in C (@pxref{Lexical, ,The
+Lexical Analyzer Function @code{yylex}}). It could also be produced
+using Lex, but the use of Lex is not discussed in this manual.
+
+@item
+Write a controlling function that calls the Bison-produced parser.
+
+@item
+Write error-reporting routines.
+@end enumerate
+
+To turn this source code as written into a runnable program, you
+must follow these steps:
+
+@enumerate
+@item
+Run Bison on the grammar to produce the parser.
+
+@item
+Compile the code output by Bison, as well as any other source files.
+
+@item
+Link the object files to produce the finished product.
+@end enumerate
+
+@node Grammar Layout
+@section The Overall Layout of a Bison Grammar
+@cindex grammar file
+@cindex file format
+@cindex format of grammar file
+@cindex layout of Bison grammar
+
+The input file for the Bison utility is a @dfn{Bison grammar file}. The
+general form of a Bison grammar file is as follows:
+
+@example
+%@{
+@var{Prologue}
+%@}
+
+@var{Bison declarations}
+
+%%
+@var{Grammar rules}
+%%
+@var{Epilogue}
+@end example
+
+@noindent
+The @samp{%%}, @samp{%@{} and @samp{%@}} 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
+@code{#include} to include header files that do any of these things.
+You need to declare the lexical analyzer @code{yylex} and the error
+printer @code{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.
+
+@node Examples
+@chapter Examples
+@cindex simple examples
+@cindex examples, simple
+
+Now we show and explain three sample programs written using Bison: a
+reverse polish notation calculator, an algebraic (infix) notation
+calculator, and a multi-function calculator. All three have been tested
+under BSD Unix 4.3; each produces a usable, though limited, interactive
projects / bison.git / blobdiff