@value{UPDATED}), the @acronym{GNU} parser generator.
Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
-1999, 2000, 2001, 2002 Free Software Foundation, Inc.
+1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
@quotation
Permission is granted to copy, distribute and/or modify this document
* Copying This Manual:: License for copying this manual.
* Index:: Cross-references to the text.
-@detailmenu --- The Detailed Node Listing ---
+@detailmenu
+ --- The Detailed Node Listing ---
The Concepts of Bison
a semantic value (the value of an integer,
the name of an identifier, etc.).
* Semantic Actions:: Each rule can have an action containing C code.
+* GLR Parsers:: Writing parsers for general context-free languages
+* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
* Stages:: Stages in writing and running Bison grammars.
Operator precedence is introduced.
* Simple Error Recovery:: Continuing after syntax errors.
* Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
-* Multi-function Calc:: Calculator with memory and trig functions.
- It uses multiple data-types for semantic values.
+* Multi-function Calc:: Calculator with memory and trig functions.
+ It uses multiple data-types for semantic values.
* Exercises:: Ideas for improving the multi-function calculator.
Reverse Polish Notation Calculator
* Rules:: How to write grammar rules.
* Recursion:: Writing recursive rules.
* Semantics:: Semantic values and actions.
+* Locations:: Locations and actions.
* Declarations:: All kinds of Bison declarations are described here.
* Multiple Parsers:: Putting more than one Bison parser in one program.
Outline of a Bison Grammar
-* Prologue:: Syntax and usage of the prologue (declarations section).
+* Prologue:: Syntax and usage of the prologue.
* Bison Declarations:: Syntax and usage of the Bison declarations section.
* Grammar Rules:: Syntax and usage of the grammar rules section.
-* Epilogue:: Syntax and usage of the epilogue (additional code section).
+* Epilogue:: Syntax and usage of the epilogue.
Defining Language Semantics
This says when, why and how to use the exceptional
action in the middle of a rule.
+Tracking Locations
+
+* Location Type:: Specifying a data type for locations.
+* Actions and Locations:: Using locations in actions.
+* Location Default Action:: Defining a general way to compute locations.
+
Bison Declarations
* Token Decl:: Declaring terminal symbols.
of the token it has read.
* Token Positions:: How @code{yylex} must return the text position
(line number, etc.) of the token, if the
- actions want that.
+ actions want that.
* Pure Calling:: How the calling convention differs
in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
* Tie-in Recovery:: Lexical tie-ins have implications for how
error recovery rules must be written.
-Understanding or Debugging Your Parser
+Debugging Your Parser
* Understanding:: Understanding the structure of your parser.
* Tracing:: Tracing the execution of your parser.
* Bison Options:: All the options described in detail,
in alphabetical order by short options.
* Option Cross Key:: Alphabetical list of long options.
+* Yacc Library:: Yacc-compatible @code{yylex} and @code{main}.
Frequently Asked Questions
four members:
@example
-struct
+typedef struct YYLTYPE
@{
int first_line;
int first_column;
int last_line;
int last_column;
-@}
+@} YYLTYPE;
@end example
@node Actions and Locations
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 @code{YYLLOC_DEFAULT} macro is invoked each time a rule is
-matched, before the associated action is run.
+matched, before the associated action is run. It is also invoked
+while processing a syntax error, to compute the error's location.
Most of the time, this macro is general enough to suppress location
dedicated code from semantic actions.
The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is
-the location of the grouping (the result of the computation). The second one
-is an array holding locations of all right hand side elements of the rule
-being matched. The last one is the size of the right hand side rule.
+the location of the grouping (the result of the computation). When a
+rule is matched, the second parameter is an array holding 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 processing
+a syntax error, the second parameter is an array holding locations of
+the symbols that were discarded during error processing, and the third
+parameter is the number of discarded symbols.
-By default, it is defined this way for simple @acronym{LALR}(1) parsers:
+By default, @code{YYLLOC_DEFAULT} is defined this way for simple
+@acronym{LALR}(1) parsers:
@example
@group
in the @code{%token} and @code{%type} declarations to pick one of the types
for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
-Note that, unlike making a @code{union} declaration in C, you do not write
+As an extension to @acronym{POSIX}, a tag is allowed after the
+@code{union}. For example:
+
+@example
+@group
+%union value @{
+ double val;
+ symrec *tptr;
+@}
+@end group
+@end example
+
+specifies the union tag @code{value}, so the corresponding C type is
+@code{union value}. If you do not specify a tag, it defaults to
+@code{YYSTYPE}.
+
+Note that, unlike making a @code{union} declaration in C, you need not write
a semicolon after the closing brace.
@node Type Decl
(@pxref{Parser Function, , The Parser Function @code{yyparse}}).
@strong{Warning:} as of Bison 1.875, this feature is still considered as
-experimental, as there was not enough users feedback. In particular,
+experimental, as there was not enough user feedback. In particular,
the syntax might still change.
@end deffn
Here @var{n} is a decimal integer. The declaration says there should be
no warning if there are @var{n} shift/reduce conflicts and no
-reduce/reduce conflicts. An error, instead of the usual warning, is
+reduce/reduce conflicts. The usual warning is
given if there are either more or fewer conflicts, or if there are any
reduce/reduce conflicts.
number which Bison printed.
@end itemize
-Now Bison will stop annoying you about the conflicts you have checked, but
-it will warn you again if changes in the grammar result in additional
-conflicts.
+Now Bison will stop annoying you if you do not change the number of
+conflicts, but it will warn you again if changes in the grammar result
+in more or fewer conflicts.
@node Start Decl
@subsection The Start-Symbol
Generate an array of token names in the parser file. The name of the
array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
token whose internal Bison token code number is @var{i}. The first
-three elements of @code{yytname} are always @code{"$end"},
+three elements of @code{yytname} correspond to the predefined tokens
+@code{"$end"},
@code{"error"}, and @code{"$undefined"}; after these come the symbols
defined in the grammar file.
Return immediately with value 1 (to report failure).
@end defmac
+@c For now, do not document %lex-param and %parse-param, since it's
+@c not clear that the current behavior is stable enough. For example,
+@c we may need to add %error-param.
+@clear documentparam
+
+@ifset documentparam
If you use a reentrant parser, you can optionally pass additional
parameter information to it in a reentrant way. To do so, use the
declaration @code{%parse-param}:
@deffn {Directive} %parse-param @{@var{argument-declaration}@}
@findex %parse-param
Declare that an argument declared by @code{argument-declaration} is an
-additional @code{yyparse} argument. This argument is also passed to
-@code{yyerror}. The @var{argument-declaration} is used when declaring
+additional @code{yyparse} argument.
+The @var{argument-declaration} is used when declaring
functions or prototypes. The last identifier in
@var{argument-declaration} must be the argument name.
@end deffn
@example
exp: @dots{} @{ @dots{}; *randomness += 1; @dots{} @}
@end example
+@end ifset
@node Lexical
only one argument.
+@ifset documentparam
If you wish to pass the additional parameter data to @code{yylex}, use
@code{%lex-param} just like @code{%parse-param} (@pxref{Parser
Function}).
int yylex (YYSTYPE *lvalp, YYLTYPE *llocp, int *nastiness);
int yyparse (int *nastiness, int *randomness);
@end example
+@end ifset
@node Error Reporting
@section The Error Reporting Function @code{yyerror}
void yyerror (YYLTYPE *locp, char const *msg); /* GLR parsers. */
@end example
+@ifset documentparam
If @samp{%parse-param @{int *nastiness@}} is used, then:
@example
-void yyerror (int *randomness, char const *msg); /* Yacc parsers. */
-void yyerror (int *randomness, char const *msg); /* GLR parsers. */
+void yyerror (int *nastiness, char const *msg); /* Yacc parsers. */
+void yyerror (int *nastiness, char const *msg); /* GLR parsers. */
@end example
Finally, GLR and Yacc parsers share the same @code{yyerror} calling
int *nastiness, int *randomness,
char const *msg);
@end example
+@end ifset
@noindent
The prototypes are only indications of how the code produced by Bison
grammar, in particular, it is only slightly slower than with the default
Bison parser.
+For a more detailed exposition of GLR parsers, please see: Elizabeth
+Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style
+Generalised @acronym{LR} Parsers, Royal Holloway, University of
+London, Department of Computer Science, TR-00-12,
+@uref{http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps},
+(2000-12-24).
+
@node Stack Overflow
@section Stack Overflow, and How to Avoid It
@cindex stack overflow
@example
calc.y: warning: 1 useless nonterminal and 1 useless rule
calc.y:11.1-7: warning: useless nonterminal: useless
-calc.y:11.8-12: warning: useless rule: useless: STR
-calc.y contains 7 shift/reduce conflicts.
+calc.y:11.10-12: warning: useless rule: useless: STR
+calc.y: conflicts: 7 shift/reduce
@end example
When given @option{--report=state}, in addition to @file{calc.tab.c}, it
The next section lists states that still have conflicts.
@example
-State 8 contains 1 shift/reduce conflict.
-State 9 contains 1 shift/reduce conflict.
-State 10 contains 1 shift/reduce conflict.
-State 11 contains 4 shift/reduce conflicts.
+State 8 conflicts: 1 shift/reduce
+State 9 conflicts: 1 shift/reduce
+State 10 conflicts: 1 shift/reduce
+State 11 conflicts: 4 shift/reduce
@end example
@noindent
exp go to state 11
@end example
-As was announced in beginning of the report, @samp{State 8 contains 1
-shift/reduce conflict}:
+As was announced in beginning of the report, @samp{State 8 conflicts:
+1 shift/reduce}:
@example
state 8
@noindent
will produce @file{output.c++} and @file{outfile.h++}.
+For compatibility with @acronym{POSIX}, the standard Bison
+distribution also contains a shell script called @command{yacc} that
+invokes Bison with the @option{-y} option.
+
@menu
* Bison Options:: All the options described in detail,
in alphabetical order by short options.
* Option Cross Key:: Alphabetical list of long options.
+* Yacc Library:: Yacc-compatible @code{yylex} and @code{main}.
@end menu
@node Bison Options
@file{y.tab.c}, and the other outputs are called @file{y.output} and
@file{y.tab.h}. The purpose of this option is to imitate Yacc's output
file name conventions. Thus, the following shell script can substitute
-for Yacc:
+for Yacc, and the Bison distribution contains such a script for
+compatibility with @acronym{POSIX}:
@example
-bison -y $*
+#! /bin/sh
+bison -y "$@"
@end example
@end table
@end example
@end ifinfo
+@node Yacc Library
+@section Yacc Library
+
+The Yacc library contains default implementations of the
+@code{yyerror} and @code{main} functions. These default
+implementations are normally not useful, but @acronym{POSIX} requires
+them. To use the Yacc library, link your program with the
+@option{-ly} option. Note that Bison's implementation of the Yacc
+library is distributed under the terms of the @acronym{GNU} General
+Public License (@pxref{Copying}).
+
+If you use the Yacc library's @code{yyerror} function, you should
+declare @code{yyerror} as follows:
+
+@example
+int yyerror (char const *);
+@end example
+
+Bison ignores the @code{int} value returned by this @code{yyerror}.
+If you use the Yacc library's @code{main} function, your
+@code{yyparse} function should have the following type signature:
+
+@example
+int yyparse (void);
+@end example
+
@c ================================================= Invoking Bison
@node FAQ
@end deffn
@deffn {Macro} YYERROR_VERBOSE
-An obsolete macro that you define with @code{#define} in the Bison
-declarations section to request verbose, specific error message strings
+An obsolete macro that you define with @code{#define} in the prologue
+to request verbose, specific error message strings
when @code{yyerror} is called. It doesn't matter what definition you
use for @code{YYERROR_VERBOSE}, just whether you define it. Using
@code{%error-verbose} is preferred.
@xref{Pure Calling,, Calling Conventions for Pure Parsers}.
@end deffn
-@deffn {Macro} YYLTYPE
-Macro for the data type of @code{yylloc}; a structure with four
+@deffn {Type} YYLTYPE
+Data type of @code{yylloc}; by default, a structure with four
members. @xref{Location Type, , Data Types of Locations}.
@end deffn
-@deffn {Type} yyltype
-Default value for YYLTYPE.
-@end deffn
-
@deffn {Macro} YYMAXDEPTH
Macro for specifying the maximum size of the parser stack. @xref{Stack
Overflow}.
to anything else.
@end deffn
-@deffn {Macro} YYSTYPE
-Macro for the data type of semantic values; @code{int} by default.
+@deffn {Type} YYSTYPE
+Data type of semantic values; @code{int} by default.
@xref{Value Type, ,Data Types of Semantic Values}.
@end deffn
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
+@ifset documentparam
@deffn {Directive} %lex-param @{@var{argument-declaration}@}
Bison declaration to specifying an additional parameter that
@code{yylex} should accept. @xref{Pure Calling,, Calling Conventions
for Pure Parsers}.
@end deffn
+@end ifset
@deffn {Directive} %merge
Bison declaration to assign a merging function to a rule. If there is a
Summary}.
@end deffn
+@ifset documentparam
@deffn {Directive} %parse-param @{@var{argument-declaration}@}
Bison declaration to specifying an additional parameter that
@code{yyparse} should accept. @xref{Parser Function,, The Parser
Function @code{yyparse}}.
@end deffn
+@end ifset
@deffn {Directive} %prec
Bison declaration to assign a precedence to a specific rule.
projects / bison.git / blobdiff