* Precedence Only:: How to specify precedence only.
* Precedence Examples:: How these features are used in the previous example.
* How Precedence:: How they work.
+* Non Operators:: Using precedence for general conflicts.
Tuning LR
@end group
%%
-
-@group
type_decl: TYPE ID '=' type ';' ;
-@end group
@group
type:
@comment file: rpcalc.y
@example
-@group
#include <stdio.h>
-@end group
@group
/* Called by yyparse on error. */
@comment file: mfcalc.y: 3
@example
-@group
#include <ctype.h>
-@end group
@group
int
A Bison grammar rule has the following general form:
@example
-@group
@var{result}: @var{components}@dots{};
-@end group
@end example
@noindent
For example,
@example
-@group
exp: exp '+' exp;
-@end group
@end example
@noindent
following example, the action is triggered only when @samp{b} is found:
@example
-@group
a-or-b: 'a'|'b' @{ a_or_b_found = 1; @};
-@end group
@end example
@cindex default action
reentrant. It looks like this:
@example
-%define api.pure
+%define api.pure full
@end example
The result is that the communication variables @code{yylval} and
what you are doing, your declarations should look like this:
@example
-%define api.pure
+%define api.pure full
%define api.push-pull push
@end example
supported languages include C, C++, and Java.
@var{language} is case-insensitive.
-This directive is experimental and its effect may be modified in future
-releases.
@end deffn
@deffn {Directive} %locations
@item Purpose: Request a pure (reentrant) parser program.
@xref{Pure Decl, ,A Pure (Reentrant) Parser}.
-@item Accepted Values: Boolean
+@item Accepted Values: @code{true}, @code{false}, @code{full}
+
+The value may be omitted: this is equivalent to specifying @code{true}, as is
+the case for Boolean values.
+
+When @code{%define api.pure full} is used, the parser is made reentrant. This
+changes the signature for @code{yylex} (@pxref{Pure Calling}), and also that of
+@code{yyerror} when the tracking of locations has been activated, as shown
+below.
+
+The @code{true} value is very similar to the @code{full} value, the only
+difference is in the signature of @code{yyerror} on Yacc parsers without
+@code{%parse-param}, for historical reasons.
+
+I.e., if @samp{%locations %define api.pure} is passed then the prototypes for
+@code{yyerror} are:
+
+@example
+void yyerror (char const *msg); /* Yacc parsers. */
+void yyerror (YYLTYPE *locp, char const *msg); /* GLR parsers. */
+@end example
+
+But if @samp{%locations %define api.pure %parse-param @{int *nastiness@}} is
+used, then both parsers have the same signature:
+
+@example
+void yyerror (YYLTYPE *llocp, int *nastiness, char const *msg);
+@end example
+
+(@pxref{Error Reporting, ,The Error
+Reporting Function @code{yyerror}})
@item Default Value: @code{false}
+
+@item History: the @code{full} value was introduced in Bison 2.7
@end itemize
@c api.pure
@item Default Value: @code{false}
@end itemize
introduced as @code{lr.keep_unreachable_states} in 2.3b, renamed as
-@code{lr.keep-unreachable-state} in 2.5, and as
+@code{lr.keep-unreachable-states} in 2.5, and as
@code{lr.keep-unreachable-state} in 2.8.
@c lr.keep-unreachable-state
exp: @dots{} @{ @dots{}; *randomness += 1; @dots{} @}
@end example
+@noindent
+Using the following:
+@example
+%parse-param @{int *randomness@}
+@end example
+
+Results in these signatures:
+@example
+void yyerror (int *randomness, const char *msg);
+int yyparse (int *randomness);
+@end example
+
+@noindent
+Or, if both @code{%define api.pure full} (or just @code{%define api.pure})
+and @code{%locations} are used:
+
+@example
+void yyerror (YYLTYPE *llocp, int *randomness, const char *msg);
+int yyparse (int *randomness);
+@end example
+
@node Push Parser Function
@section The Push Parser Function @code{yypush_parse}
@findex yypush_parse
@node Pure Calling
@subsection Calling Conventions for Pure Parsers
-When you use the Bison declaration @samp{%define api.pure} to request a
+When you use the Bison declaration @code{%define api.pure full} to request a
pure, reentrant parser, the global communication variables @code{yylval}
and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
Parser}.) In such parsers the two global variables are replaced by
declarations, which is equivalent to repeating @code{%param}.
@end deffn
+@noindent
For instance:
@example
int yyparse (parser_mode *mode, environment_type *env);
@end example
-If @samp{%define api.pure} is added:
+If @samp{%define api.pure full} is added:
@example
int yylex (YYSTYPE *lvalp, scanner_mode *mode, environment_type *env);
@end example
@noindent
-and finally, if both @samp{%define api.pure} and @code{%locations} are used:
+and finally, if both @samp{%define api.pure full} and @code{%locations} are
+used:
@example
int yylex (YYSTYPE *lvalp, YYLTYPE *llocp,
immediately return 1.
Obviously, in location tracking pure parsers, @code{yyerror} should have
-an access to the current location.
-This is indeed the case for the GLR
-parsers, but not for the Yacc parser, for historical reasons. I.e., if
-@samp{%locations %define api.pure} is passed then the prototypes for
-@code{yyerror} are:
-
-@example
-void yyerror (char const *msg); /* Yacc parsers. */
-void yyerror (YYLTYPE *locp, char const *msg); /* GLR parsers. */
-@end example
+an access to the current location. With @code{%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 @code{%define api.pure full} should be
+prefered over @code{%define api.pure}.
-If @samp{%parse-param @{int *nastiness@}} is used, then:
+When @code{%locations %define api.pure full} is used, @code{yyerror} has the
+following signature:
@example
-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
-convention for absolutely pure parsers, i.e., when the calling
-convention of @code{yylex} @emph{and} the calling convention of
-@samp{%define api.pure} are pure.
-I.e.:
-
-@example
-/* Location tracking. */
-%locations
-/* Pure yylex. */
-%define api.pure
-%lex-param @{int *nastiness@}
-/* Pure yyparse. */
-%parse-param @{int *nastiness@}
-%parse-param @{int *randomness@}
-@end example
-
-@noindent
-results in the following signatures for all the parser kinds:
-
-@example
-int yylex (YYSTYPE *lvalp, YYLTYPE *llocp, int *nastiness);
-int yyparse (int *nastiness, int *randomness);
-void yyerror (YYLTYPE *locp,
- int *nastiness, int *randomness,
- char const *msg);
+void yyerror (YYLTYPE *locp, char const *msg);
@end example
@noindent
term:
'(' expr ')'
| term '!'
-| NUMBER
+| "number"
;
@end group
@end example
@example
@group
if_stmt:
- IF expr THEN stmt
-| IF expr THEN stmt ELSE stmt
+ "if" expr "then" stmt
+| "if" expr "then" stmt "else" stmt
;
@end group
@end example
@noindent
-Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
-terminal symbols for specific keyword tokens.
+Here @code{"if"}, @code{"then"} and @code{"else"} are terminal symbols for
+specific keyword tokens.
-When the @code{ELSE} token is read and becomes the lookahead token, the
+When the @code{"else"} token is read and becomes the lookahead token, the
contents of the stack (assuming the input is valid) are just right for
reduction by the first rule. But it is also legitimate to shift the
-@code{ELSE}, because that would lead to eventual reduction by the second
+@code{"else"}, because that would lead to eventual reduction by the second
rule.
This situation, where either a shift or a reduction would be valid, is
operator precedence declarations. To see the reason for this, let's
contrast it with the other alternative.
-Since the parser prefers to shift the @code{ELSE}, the result is to attach
+Since the parser prefers to shift the @code{"else"}, the result is to attach
the else-clause to the innermost if-statement, making these two inputs
equivalent:
@example
-if x then if y then win (); else lose;
+if x then if y then win; else lose;
-if x then do; if y then win (); else lose; end;
+if x then do; if y then win; else lose; end;
@end example
But if the parser chose to reduce when possible rather than shift, the
making these two inputs equivalent:
@example
-if x then if y then win (); else lose;
+if x then if y then win; else lose;
-if x then do; if y then win (); end; else lose;
+if x then do; if y then win; end; else lose;
@end example
The conflict exists because the grammar as written is ambiguous: either
Algol 60 and is called the ``dangling @code{else}'' ambiguity.
To avoid warnings from Bison about predictable, legitimate shift/reduce
-conflicts, use the @code{%expect @var{n}} declaration.
+conflicts, you can use the @code{%expect @var{n}} declaration.
There will be no warning as long as the number of shift/reduce conflicts
is exactly @var{n}, and Bison will report an error if there is a
different number.
-@xref{Expect Decl, ,Suppressing Conflict Warnings}.
+@xref{Expect Decl, ,Suppressing Conflict Warnings}. However, we don't
+recommend the use of @code{%expect} (except @samp{%expect 0}!), as an equal
+number of conflicts does not mean that they are the @emph{same}. When
+possible, you should rather use precedence directives to @emph{fix} the
+conflicts explicitly (@pxref{Non Operators,, Using Precedence For Non
+Operators}).
The definition of @code{if_stmt} above is solely to blame for the
conflict, but the conflict does not actually appear without additional
the conflict:
@example
-@group
-%token IF THEN ELSE variable
%%
-@end group
@group
stmt:
expr
@group
if_stmt:
- IF expr THEN stmt
-| IF expr THEN stmt ELSE stmt
+ "if" expr "then" stmt
+| "if" expr "then" stmt "else" stmt
;
@end group
expr:
- variable
+ "identifier"
;
@end example
* Precedence Only:: How to specify precedence only.
* Precedence Examples:: How these features are used in the previous example.
* How Precedence:: How they work.
+* Non Operators:: Using precedence for general conflicts.
@end menu
@node Why Precedence
declared with @code{'-'}:
@example
-%left '<' '>' '=' NE LE GE
+%left '<' '>' '=' "!=" "<=" ">="
%left '+' '-'
%left '*' '/'
@end example
-@noindent
-(Here @code{NE} and so on stand for the operators for ``not equal''
-and so on. We assume that these tokens are more than one character long
-and therefore are represented by names, not character literals.)
-
@node How Precedence
@subsection How Precedence Works
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.
+@node Non Operators
+@subsection Using Precedence For Non Operators
+
+Using properly precedence and associativity directives can help fixing
+shift/reduce conflicts that do not involve arithmetics-like operators. For
+instance, the ``dangling @code{else}'' problem (@pxref{Shift/Reduce, ,
+Shift/Reduce Conflicts}) can be solved elegantly in two different ways.
+
+In the present case, the conflict is between the token @code{"else"} willing
+to be shifted, and the rule @samp{if_stmt: "if" expr "then" stmt}, asking
+for reduction. By default, the precedence of a rule is that of its last
+token, here @code{"then"}, so the conflict will be solved appropriately
+by giving @code{"else"} a precedence higher than that of @code{"then"}, for
+instance as follows:
+
+@example
+@group
+%precedence "then"
+%precedence "else"
+@end group
+@end example
+
+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:
+
+@example
+%right "then" "else"
+@end example
+
+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 @samp{if test then 1 else 2 + 3}
+being ambiguous: @samp{if test then 1 else (2 + 3)} or @samp{(if test then 1
+else 2) + 3}?), the conflict will be already ``fixed''.
+
@node Contextual Precedence
@section Context-Dependent Precedence
@cindex context-dependent precedence
proper way to define @code{sequence}:
@example
+@group
sequence:
/* empty */ @{ printf ("empty sequence\n"); @}
| sequence word @{ printf ("added word %s\n", $2); @}
;
+@end group
@end example
Here is another common error that yields a reduce/reduce conflict:
@example
+@group
sequence:
/* empty */
| sequence words
| sequence redirects
;
+@end group
+@group
words:
/* empty */
| words word
;
+@end group
+@group
redirects:
/* empty */
| redirects redirect
;
+@end group
@end example
@noindent
@end group
@end example
+Yet this proposal introduces another kind of ambiguity! The input
+@samp{word word} can be parsed as a single @code{words} composed of two
+@samp{word}s, or as two one-@code{word} @code{words} (and likewise for
+@code{redirect}/@code{redirects}). However this ambiguity is now a
+shift/reduce conflict, and therefore it can now be addressed with precedence
+directives.
+
+To simplify the matter, we will proceed with @code{word} and @code{redirect}
+being tokens: @code{"word"} and @code{"redirect"}.
+
+To prefer the longest @code{words}, the conflict between the token
+@code{"word"} and the rule @samp{sequence: sequence words} must be resolved
+as a shift. To this end, we use the same techniques as exposed above, see
+@ref{Non Operators,, Using Precedence For Non Operators}. One solution
+relies on precedences: use @code{%prec} to give a lower precedence to the
+rule:
+
+@example
+%precedence "word"
+%precedence "sequence"
+%%
+@group
+sequence:
+ /* empty */
+| sequence word %prec "sequence"
+| sequence redirect %prec "sequence"
+;
+@end group
+
+@group
+words:
+ word
+| words "word"
+;
+@end group
+@end example
+
+Another solution relies on associativity: provide both the token and the
+rule with the same precedence, but make them right-associative:
+
+@example
+%right "word" "redirect"
+%%
+@group
+sequence:
+ /* empty */
+| sequence word %prec "word"
+| sequence redirect %prec "redirect"
+;
+@end group
+@end example
+
@node Mysterious Conflicts
@section Mysterious Conflicts
@cindex Mysterious Conflicts
@example
@group
-%token ID
-
%%
def: param_spec return_spec ',';
param_spec:
| name_list ':' type
;
@end group
+
@group
return_spec:
type
| name ':' type
;
@end group
+
+type: "id";
+
@group
-type: ID;
-@end group
-@group
-name: ID;
+name: "id";
name_list:
name
| name ',' name_list
@end group
@end example
-It would seem that this grammar can be parsed with only a single token
-of lookahead: when a @code{param_spec} is being read, an @code{ID} is
-a @code{name} if a comma or colon follows, or a @code{type} if another
-@code{ID} follows. In other words, this grammar is LR(1).
+It would seem that this grammar can be parsed with only a single token of
+lookahead: when a @code{param_spec} is being read, an @code{"id"} is a
+@code{name} if a comma or colon follows, or a @code{type} if another
+@code{"id"} follows. In other words, this grammar is LR(1).
@cindex LR
@cindex LALR
However, for historical reasons, Bison cannot by default handle all
LR(1) grammars.
-In this grammar, two contexts, that after an @code{ID} at the beginning
+In this grammar, two contexts, that after an @code{"id"} at the beginning
of a @code{param_spec} and likewise at the beginning of a
@code{return_spec}, are similar enough that Bison assumes they are the
same.
@example
@group
-%token BOGUS
-@dots{}
-%%
@dots{}
return_spec:
type
| name ':' type
-| ID BOGUS /* This rule is never used. */
+| "id" "bogus" /* This rule is never used. */
;
@end group
@end example
This corrects the problem because it introduces the possibility of an
-additional active rule in the context after the @code{ID} at the beginning of
+additional active rule in the context after the @code{"id"} at the beginning of
@code{return_spec}. This rule is not active in the corresponding context
in a @code{param_spec}, so the two contexts receive distinct parser states.
-As long as the token @code{BOGUS} is never generated by @code{yylex},
+As long as the token @code{"bogus"} is never generated by @code{yylex},
the added rule cannot alter the way actual input is parsed.
In this particular example, there is another way to solve the problem:
-rewrite the rule for @code{return_spec} to use @code{ID} directly
+rewrite the rule for @code{return_spec} to use @code{"id"} directly
instead of via @code{name}. This also causes the two confusing
contexts to have different sets of active rules, because the one for
@code{return_spec} activates the altered rule for @code{return_spec}
rather than the one for @code{name}.
@example
+@group
param_spec:
type
| name_list ':' type
;
+@end group
+
+@group
return_spec:
type
-| ID ':' type
+| "id" ':' type
;
+@end group
@end example
For a more detailed exposition of LALR(1) parsers and parser
parser table construction algorithm by using the @code{%define lr.type}
directive.
-@deffn {Directive} {%define lr.type @var{TYPE}}
+@deffn {Directive} {%define lr.type} @var{type}
Specify the type of parser tables within the LR(1) family. The accepted
-values for @var{TYPE} are:
+values for @var{type} are:
@itemize
@item @code{lalr} (default)
@cindex GLR with LALR
When employing GLR parsers (@pxref{GLR Parsers}), if you do not resolve any
-conflicts statically (for example, with @code{%left} or @code{%prec}), then
+conflicts statically (for example, with @code{%left} or @code{%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
To adjust which states have default reductions enabled, use the
@code{%define lr.default-reduction} directive.
-@deffn {Directive} {%define lr.default-reduction @var{WHERE}}
+@deffn {Directive} {%define lr.default-reduction} @var{where}
Specify the kind of states that are permitted to contain default reductions.
-The accepted values of @var{WHERE} are:
+The accepted values of @var{where} are:
@itemize
@item @code{most} (default for LALR and IELR)
@item @code{consistent}
sacrificing @code{%nonassoc}, default reductions, or state merging. You can
enable LAC with the @code{%define parse.lac} directive.
-@deffn {Directive} {%define parse.lac @var{VALUE}}
+@deffn {Directive} {%define parse.lac} @var{value}
Enable LAC to improve syntax error handling.
@itemize
@item @code{none} (default)
keeping unreachable states is sometimes useful when trying to understand the
relationship between the parser and the grammar.
-@deffn {Directive} {%define lr.keep-unreachable-state @var{VALUE}}
+@deffn {Directive} {%define lr.keep-unreachable-state} @var{value}
Request that Bison allow unreachable states to remain in the parser tables.
-@var{VALUE} must be a Boolean. The default is @code{false}.
+@var{value} must be a Boolean. The default is @code{false}.
@end deffn
There are a few caveats to consider:
Summary}). Currently supported languages include C, C++, and Java.
@var{language} is case-insensitive.
-This option is experimental and its effect may be modified in future
-releases.
-
@item --locations
Pretend that @code{%locations} was specified. @xref{Decl Summary}.
@node Split Symbols
@subsubsection Split Symbols
-Therefore the interface is as follows.
+The interface is as follows.
@deftypemethod {parser} {int} yylex (semantic_type* @var{yylval}, location_type* @var{yylloc}, @var{type1} @var{arg1}, ...)
@deftypemethodx {parser} {int} yylex (semantic_type* @var{yylval}, @var{type1} @var{arg1}, ...)
Contrary to C parsers, Java parsers do not use global variables; the
state of the parser is always local to an instance of the parser class.
Therefore, all Java parsers are ``pure'', and the @code{%pure-parser}
-and @samp{%define api.pure} directives does not do anything when used in
-Java.
+and @code{%define api.pure} directives do nothing when used in Java.
Push parsers are currently unsupported in Java and @code{%define
api.push-pull} have no effect.
@quotation
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 @samp{%define api.pure}.
+although I did specify @samp{%define api.pure full}.
@end quotation
These problems typically come not from Bison itself, but from
@c LocalWords: subdirectory Solaris nonassociativity perror schemas Malloy ints
@c LocalWords: Scannerless ispell american ChangeLog smallexample CSTYPE CLTYPE
@c LocalWords: clval CDEBUG cdebug deftypeopx yyterminate LocationType
-@c LocalWords: errorVerbose
+@c LocalWords: parsers parser's
+@c LocalWords: associativity subclasses precedences unresolvable runnable
+@c LocalWords: allocators subunit initializations unreferenced untyped
+@c LocalWords: errorVerbose subtype subtypes
@c Local Variables:
@c ispell-dictionary: "american"
projects / bison.git / blobdiff