@c @clear shorttitlepage-enabled
@c @set shorttitlepage-enabled
+@c Set following if you want to document %default-prec and %no-default-prec.
+@c This feature is experimental and may change in future Bison versions.
+@c @set defaultprec
+
@c ISPELL CHECK: done, 14 Jan 1993 --bob
@c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo
This manual is for @acronym{GNU} Bison (version @value{VERSION},
@value{UPDATED}), the @acronym{GNU} parser generator.
-Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 2003,
-1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
+Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
+1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
@quotation
Permission is granted to copy, distribute and/or modify this document
* Union Decl:: Declaring the set of all semantic value types.
* Type Decl:: Declaring the choice of type for a nonterminal symbol.
* Destructor Decl:: Declaring how symbols are freed.
-* Expect Decl:: Suppressing warnings about shift/reduce conflicts.
+* Expect Decl:: Suppressing warnings about parsing conflicts.
* Start Decl:: Specifying the start symbol.
* Pure Decl:: Requesting a reentrant parser.
* Decl Summary:: Table of all Bison declarations.
Frequently Asked Questions
* Parser Stack Overflow:: Breaking the Stack Limits
-* How Can I Reset @code{yyparse}:: @code{yyparse} Keeps some State
+* How Can I Reset the Parser:: @code{yyparse} Keeps some State
* Strings are Destroyed:: @code{yylval} Loses Track of Strings
+* C++ Parsers:: Compiling Parsers with C++ Compilers
+* Implementing Loops:: Control Flow in the Calculator
Copying This Manual
practical conditions for using Bison match the practical conditions for
using the other @acronym{GNU} tools.
-This exception applies only when Bison is generating C code for a
+This exception applies only when Bison is generating C code for an
@acronym{LALR}(1) parser; otherwise, the @acronym{GPL} terms operate
as usual. You can
tell whether the exception applies to your @samp{.c} output file by
void
yyerror (char const *s)
@{
- printf ("%s\n", s);
+ fprintf (stderr, "%s\n", s);
@}
@end group
@end example
%@}
%union @{
- long n;
+ long int n;
tree t; /* @r{@code{tree} is defined in @file{ptypes.h}.} */
@}
read your program will be confused.
All the escape sequences used in string literals in C can be used in
-Bison as well. However, unlike Standard C, trigraphs have no special
+Bison as well, except that you must not use a null character within a
+string literal. Also, unlike Standard C, trigraphs have no special
meaning in Bison string literals, nor is backslash-newline allowed. A
literal string token must contain two or more characters; for a token
containing just one character, use a character token (see above).
In most programs, you will need different data types for different kinds
of tokens and groupings. For example, a numeric constant may need type
-@code{int} or @code{long}, while a string constant needs type @code{char *},
+@code{int} or @code{long int}, while a string constant needs type @code{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
The C code in an action can refer to the semantic values of the components
matched by the rule with the construct @code{$@var{n}}, which stands for
the value of the @var{n}th component. The semantic value for the grouping
-being constructed is @code{$$}. (Bison translates both of these constructs
-into array element references when it copies the actions into the parser
-file.)
+being constructed is @code{$$}. Bison translates both of these
+constructs into expressions of the appropriate type when it copies the
+actions into the parser file. @code{$$} is translated to a modifiable
+lvalue, so it can be assigned to.
Here is a typical example:
functional parser, it can be useful to process some additional information,
especially symbol locations.
-@c (terminal or not) ?
-
The way locations are handled is defined by providing a data type, and
actions to take when rules are matched.
else
@{
$$ = 1;
- printf("Division by zero, l%d,c%d-l%d,c%d",
- @@3.first_line, @@3.first_column,
- @@3.last_line, @@3.last_column);
+ fprintf (stderr,
+ "Division by zero, l%d,c%d-l%d,c%d",
+ @@3.first_line, @@3.first_column,
+ @@3.last_line, @@3.last_column);
@}
@}
@end group
else
@{
$$ = 1;
- printf("Division by zero, l%d,c%d-l%d,c%d",
- @@3.first_line, @@3.first_column,
- @@3.last_line, @@3.last_column);
+ fprintf (stderr,
+ "Division by zero, l%d,c%d-l%d,c%d",
+ @@3.first_line, @@3.first_column,
+ @@3.last_line, @@3.last_column);
@}
@}
@end group
@example
@group
-#define YYLLOC_DEFAULT(Current, Rhs, N) \
- Current.first_line = Rhs[1].first_line; \
- Current.first_column = Rhs[1].first_column; \
- Current.last_line = Rhs[N].last_line; \
- Current.last_column = Rhs[N].last_column;
+# define YYLLOC_DEFAULT(Current, Rhs, N) \
+ ((Current).first_line = (Rhs)[1].first_line, \
+ (Current).first_column = (Rhs)[1].first_column, \
+ (Current).last_line = (Rhs)[N].last_line, \
+ (Current).last_column = (Rhs)[N].last_column)
@end group
@end example
@example
@group
-#define YYLLOC_DEFAULT(Current, Rhs, N) \
- Current.first_line = YYRHSLOC(Rhs,1).first_line; \
- Current.first_column = YYRHSLOC(Rhs,1).first_column; \
- Current.last_line = YYRHSLOC(Rhs,N).last_line; \
- Current.last_column = YYRHSLOC(Rhs,N).last_column;
+# define YYLLOC_DEFAULT(yyCurrent, yyRhs, YYN) \
+ ((yyCurrent).first_line = YYRHSLOC(yyRhs, 1).first_line, \
+ (yyCurrent).first_column = YYRHSLOC(yyRhs, 1).first_column, \
+ (yyCurrent).last_line = YYRHSLOC(yyRhs, YYN).last_line, \
+ (yyCurrent).last_column = YYRHSLOC(yyRhs, YYN).last_column)
@end group
@end example
@item
For consistency with semantic actions, valid indexes for the location
array range from 1 to @var{n}.
+
+@item
+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.
@end itemize
@node Declarations
* Union Decl:: Declaring the set of all semantic value types.
* Type Decl:: Declaring the choice of type for a nonterminal symbol.
* Destructor Decl:: Declaring how symbols are freed.
-* Expect Decl:: Suppressing warnings about shift/reduce conflicts.
+* Expect Decl:: Suppressing warnings about parsing conflicts.
* Start Decl:: Specifying the start symbol.
* Pure Decl:: Requesting a reentrant parser.
* Decl Summary:: Table of all Bison declarations.
Precedence}.
You can explicitly specify the numeric code for a token type by appending
-an integer value in the field immediately following the token name:
+a decimal or hexadecimal integer value in the field immediately
+following the token name:
@example
%token NUM 300
+%token XNUM 0x12d // a GNU extension
@end example
@noindent
Declare that the @var{code} must be invoked for each of the
@var{symbols} that will be discarded by the parser. The @var{code}
should use @code{$$} to designate the semantic value associated to the
-@var{symbols}. The additional parser parameters are also avaible
+@var{symbols}. The additional parser parameters are also available
(@pxref{Parser Function, , The Parser Function @code{yyparse}}).
@strong{Warning:} as of Bison 1.875, this feature is still considered as
@cindex warnings, preventing
@cindex conflicts, suppressing warnings of
@findex %expect
+@findex %expect-rr
Bison normally warns if there are any conflicts in the grammar
(@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars
given if there are either more or fewer conflicts, or if there are any
reduce/reduce conflicts.
+For normal LALR(1) 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 shift/reduce and reduce/reduce 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:
+
+@example
+%expect-rr @var{n}
+@end example
+
In general, using @code{%expect} involves these steps:
@itemize @bullet
@deffn {Directive} %nonassoc
Declare a terminal symbol (token type name) that is nonassociative
-(using it in a way that would be associative is a syntax error)
-@end deffn
(@pxref{Precedence Decl, ,Operator Precedence}).
+Using it in a way that would be associative is a syntax error.
+@end deffn
+
+@ifset defaultprec
+@deffn {Directive} %default-prec
+Assign a precedence to rules lacking an explicit @code{%prec} modifier
+(@pxref{Contextual Precedence, ,Context-Dependent Precedence}).
+@end deffn
+@end ifset
@deffn {Directive} %type
Declare the type of semantic values for a nonterminal symbol
Program}.
@end deffn
+@ifset defaultprec
+@deffn {Directive} %no-default-prec
+Do not assign a precedence to rules lacking an explicit @code{%prec}
+modifier (@pxref{Contextual Precedence, ,Context-Dependent
+Precedence}).
+@end deffn
+@end ifset
+
@deffn {Directive} %no-parser
Do not include any C code in the parser file; generate tables only. The
parser file contains just @code{#define} directives and static variable
@end group
@end example
+@ifset defaultprec
+If you forget to append @code{%prec UMINUS} to the rule for unary
+minus, Bison silently assumes that minus has its usual precedence.
+This kind of problem can be tricky to debug, since one typically
+discovers the mistake only by testing the code.
+
+The @code{%no-default-prec;} declaration makes it easier to discover
+this kind of problem systematically. It causes rules that lack a
+@code{%prec} modifier to have no precedence, even if the last terminal
+symbol mentioned in their components has a declared precedence.
+
+If @code{%no-default-prec;} is in effect, you must specify @code{%prec}
+for all rules that participate in precedence conflict resolution.
+Then you will see any shift/reduce conflict until you tell Bison how
+to resolve it, either by changing your grammar or by adding an
+explicit precedence. This will probably add declarations to the
+grammar, but it helps to protect against incorrect rule precedences.
+
+The effect of @code{%no-default-prec;} can be reversed by giving
+@code{%default-prec;}, which is the default.
+@end ifset
+
@node Parser States
@section Parser States
@cindex finite-state machine
@example
#! /bin/sh
-bison -y "$@"
+bison -y "$@@"
@end example
@end table
@menu
* Parser Stack Overflow:: Breaking the Stack Limits
-* How Can I Reset @code{yyparse}:: @code{yyparse} Keeps some State
+* How Can I Reset the Parser:: @code{yyparse} Keeps some State
* Strings are Destroyed:: @code{yylval} Loses Track of Strings
+* C++ Parsers:: Compiling Parsers with C++ Compilers
+* Implementing Loops:: Control Flow in the Calculator
@end menu
@node Parser Stack Overflow
This question is already addressed elsewhere, @xref{Recursion,
,Recursive Rules}.
-@node How Can I Reset @code{yyparse}
-@section How Can I Reset @code{yyparse}
+@node How Can I Reset the Parser
+@section How Can I Reset the Parser
-The following phenomenon gives raise to several incarnations,
-resulting in the following typical questions:
+The following phenomenon has several symptoms, resulting in the
+following typical questions:
@display
I invoke @code{yyparse} several times, and on correct input it works
properly; but when a parse error is found, all the other calls fail
-too. How can I reset @code{yyparse}'s error flag?
+too. How can I reset the error flag of @code{yyparse}?
@end display
@noindent
or
@display
-My parser includes support for a @samp{#include} like feature, in
+My parser includes support for an @samp{#include}-like feature, in
which case I run @code{yyparse} from @code{yyparse}. This fails
although I did specify I needed a @code{%pure-parser}.
@end display
-These problems are not related to Bison itself, but with the Lex
-generated scanners. Because these scanners use large buffers for
+These problems typically come not from Bison itself, but from
+Lex-generated scanners. Because these scanners use large buffers for
speed, they might not notice a change of input file. As a
demonstration, consider the following source file,
@file{first-line.l}:
.*\n ECHO; return 1;
%%
int
-yyparse (const char *file)
+yyparse (char const *file)
{
yyin = fopen (file, "r");
if (!yyin)
exit (2);
/* One token only. */
yylex ();
- if (!fclose (yyin))
+ if (fclose (yyin) != 0)
exit (3);
return 0;
}
int
-main ()
+main (void)
{
yyparse ("input");
yyparse ("input");
@end verbatim
@noindent
-then instead of getting twice the first line, you get:
+then instead of getting the first line twice, you get:
@example
$ @kbd{flex -ofirst-line.c first-line.l}
input:2: World!
@end example
-Therefore, whenever you change @code{yyin}, you must tell the Lex
-generated scanner to discard its current buffer, and to switch to the
-new one. This depends upon your implementation of Lex, see its
-documentation for more. For instance, in the case of Flex, a simple
-call @samp{yyrestart (yyin)} suffices after each change to
-@code{yyin}.
+Therefore, whenever you change @code{yyin}, you must tell the
+Lex-generated scanner to discard its current buffer and switch to the
+new one. This depends upon your implementation of Lex; see its
+documentation for more. For Flex, it suffices to call
+@samp{YY_FLUSH_BUFFER} after each change to @code{yyin}. If your
+Flex-generated scanner needs to read from several input streams to
+handle features like include files, you might consider using Flex
+functions like @samp{yy_switch_to_buffer} that manipulate multiple
+input buffers.
+
+If your Flex-generated scanner uses start conditions (@pxref{Start
+conditions, , Start conditions, flex, The Flex Manual}), you might
+also want to reset the scanner's state, i.e., go back to the initial
+start condition, through a call to @samp{BEGIN (0)}.
@node Strings are Destroyed
@section Strings are Destroyed
@end example
+@node C++ Parsers
+@section C++ Parsers
+
+@display
+How can I generate parsers in C++?
+@end display
+
+We are working on a C++ output for Bison, but unfortunately, for lack
+of time, the skeleton is not finished. It is functional, but in
+numerous respects, it will require additional work which @emph{might}
+break backward compatibility. Since the skeleton for C++ is not
+documented, we do not consider ourselves bound to this interface,
+nevertheless, as much as possible we will try to keep compatibility.
+
+Another possibility is to use the regular C parsers, and to compile
+them with a C++ compiler. This works properly, provided that you bear
+some simple C++ rules in mind, such as not including ``real classes''
+(i.e., structure with constructors) in unions. Therefore, in the
+@code{%union}, use pointers to classes, or better yet, a single
+pointer type to the root of your lexical/syntactic hierarchy.
+
+
+@node Implementing Loops
+@section Implementing Loops
+
+@display
+My simple calculator supports variables, assignments, and functions,
+but how can I implement loops?
+@end display
+
+Although very pedagogical, the examples included in the document blur
+the distinction to make between the parser---whose job is to recover
+the structure of a text and to transmit it to subsequent modules of
+the program---and the processing (such as the execution) of this
+structure. This works well with so called straight line programs,
+i.e., precisely those that have a straightforward execution model:
+execute simple instructions one after the others.
+
+@cindex abstract syntax tree
+@cindex @acronym{AST}
+If you want a richer model, you will probably need to use the parser
+to construct a tree that does represent the structure it has
+recovered; this tree is usually called the @dfn{abstract syntax tree},
+or @dfn{@acronym{AST}} for short. Then, walking through this tree,
+traversing it in various ways, will enable treatments such as its
+execution or its translation, which will result in an interpreter or a
+compiler.
+
+This topic is way beyond the scope of this manual, and the reader is
+invited to consult the dedicated literature.
+
+
+
@c ================================================= Table of Symbols
@node Table of Symbols
Equip the parser for debugging. @xref{Decl Summary}.
@end deffn
+@ifset defaultprec
+@deffn {Directive} %default-prec
+Assign a precedence to rules that lack an explicit @samp{%prec}
+modifier. @xref{Contextual Precedence, ,Context-Dependent
+Precedence}.
+@end deffn
+@end ifset
+
@deffn {Directive} %defines
Bison declaration to create a header file meant for the scanner.
@xref{Decl Summary}.
Bison declaration to rename the external symbols. @xref{Decl Summary}.
@end deffn
+@ifset defaultprec
+@deffn {Directive} %no-default-prec
+Do not assign a precedence to rules that lack an explicit @samp{%prec}
+modifier. @xref{Contextual Precedence, ,Context-Dependent
+Precedence}.
+@end deffn
+@end ifset
+
@deffn {Directive} %no-lines
Bison declaration to avoid generating @code{#line} directives in the
parser file. @xref{Decl Summary}.
@printindex cp
@bye
+
+@c LocalWords: texinfo setfilename settitle setchapternewpage finalout
+@c LocalWords: ifinfo smallbook shorttitlepage titlepage GPL FIXME iftex
+@c LocalWords: akim fn cp syncodeindex vr tp synindex dircategory direntry
+@c LocalWords: ifset vskip pt filll insertcopying sp ISBN Etienne Suvasa
+@c LocalWords: ifnottex yyparse detailmenu GLR RPN Calc var Decls Rpcalc
+@c LocalWords: rpcalc Lexer Gen Comp Expr ltcalc mfcalc Decl Symtab yylex
+@c LocalWords: yyerror pxref LR yylval cindex dfn LALR samp gpl BNF xref
+@c LocalWords: const int paren ifnotinfo AC noindent emph expr stmt findex
+@c LocalWords: glr YYSTYPE TYPENAME prog dprec printf decl init stmtMerge
+@c LocalWords: pre STDC GNUC endif yy YY alloca lf stddef stdlib YYDEBUG
+@c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit
+@c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok
+@c LocalWords: longjmp fprintf stderr preg yylloc YYLTYPE cos ln
+@c LocalWords: smallexample symrec val tptr FNCT fnctptr func struct sym
+@c LocalWords: fnct putsym getsym fname arith fncts atan ptr malloc sizeof
+@c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum
+@c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype
+@c LocalWords: Rhs YYRHSLOC LE nonassoc op deffn typeless typefull yynerrs
+@c LocalWords: yychar yydebug msg YYNTOKENS YYNNTS YYNRULES YYNSTATES
+@c LocalWords: cparse clex deftypefun NE defmac YYACCEPT YYABORT param
+@c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP
+@c LocalWords: YYEMPTY YYRECOVERING yyclearin GE def UMINUS maybeword
+@c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH
+@c LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm VCG notype
+@c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args
+@c LocalWords: YYPRINTF infile ypp yxx outfile itemx vcg tex leaderfill
+@c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll
+@c LocalWords: yyrestart nbar yytext fst snd osplit ntwo strdup AST
+@c LocalWords: YYSTACK DVI fdl printindex
projects / bison.git / blobdiff