[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] Add %precedence support.
|
From: |
Akim Demaille |
|
Subject: |
[PATCH] Add %precedence support. |
|
Date: |
Mon, 10 Nov 2008 09:51:40 -0000 |
Unfortunately it is not possible to reuse the %prec directive. This
is because to please POSIX, we do not require to end the rules with a
semicolon. As a result,
foo: bar %prec baz
is ambiguous: either a rule which precedence is that of baz, or a rule,
and then a declaration of the precedence of the token baz.
* doc/bison.texinfo: Document %precedence.
(Precedence Only): New.
* src/assoc.h, src/assoc.c (precedence_assoc): New.
* src/conflicts.c (resolve_sr_conflict): Support it.
* src/scan-gram.l, src/parse-gram.y (%precedence): New token.
Parse it.
* tests/calc.at: Use %precedence for NEG.
* tests/conflicts.at (%precedence does not suffice)
(%precedence suffices): New tests.
---
ChangeLog | 22 +++++++++++
doc/bison.texinfo | 105 ++++++++++++++++++++++++++++++++++++++++++----------
src/assoc.c | 5 ++-
src/assoc.h | 11 +++--
src/conflicts.c | 17 +++++---
src/parse-gram.y | 8 ++-
src/scan-gram.l | 1 +
tests/calc.at | 6 +-
tests/conflicts.at | 60 ++++++++++++++++++++++++++++-
9 files changed, 195 insertions(+), 40 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index be1ab02..757e1fd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,25 @@
+2008-11-10 Akim Demaille <address@hidden>
+
+ Add %precedence support.
+ Unfortunately it is not possible to reuse the %prec directive. This
+ is because to please POSIX, we do not require to end the rules with a
+ semicolon. As a result,
+
+ foo: bar %prec baz
+
+ is ambiguous: either a rule which precedence is that of baz, or a rule,
+ and then a declaration of the precedence of the token baz.
+
+ * doc/bison.texinfo: Document %precedence.
+ (Precedence Only): New.
+ * src/assoc.h, src/assoc.c (precedence_assoc): New.
+ * src/conflicts.c (resolve_sr_conflict): Support it.
+ * src/scan-gram.l, src/parse-gram.y (%precedence): New token.
+ Parse it.
+ * tests/calc.at: Use %precedence for NEG.
+ * tests/conflicts.at (%precedence does not suffice)
+ (%precedence suffices): New tests.
+
2008-11-09 Akim Demaille <address@hidden>
Make benches in a sub dirs.
diff --git a/doc/bison.texinfo b/doc/bison.texinfo
index 09ca7ab..ebb37ca 100644
--- a/doc/bison.texinfo
+++ b/doc/bison.texinfo
@@ -264,7 +264,8 @@ The Bison Parser Algorithm
Operator Precedence
* Why Precedence:: An example showing why precedence is needed.
-* Using Precedence:: How to specify precedence in Bison grammars.
+* Using Precedence:: How to specify precedence and associativity.
+* Precedence Only:: How to specify precedence only.
* Precedence Examples:: How these features are used in the previous example.
* How Precedence:: How they work.
@@ -1858,8 +1859,8 @@ parentheses nested to arbitrary depth. Here is the Bison
code for
%token NUM
%left '-' '+'
%left '*' '/'
-%left NEG /* negation--unary minus */
-%right '^' /* exponentiation */
+%precedence NEG /* negation--unary minus */
+%right '^' /* exponentiation */
%% /* The grammar follows. */
input: /* empty */
@@ -1892,15 +1893,16 @@ In the second section (Bison declarations),
@code{%left} declares token
types and says they are left-associative operators. The declarations
@code{%left} and @code{%right} (right associativity) take the place of
@code{%token} which is used to declare a token type name without
-associativity. (These tokens are single-character literals, which
+associativity/precedence. (These tokens are single-character literals, which
ordinarily don't need to be declared. We declare them here to specify
-the associativity.)
+the associativity/precedence.)
Operator precedence is determined by the line ordering of the
declarations; the higher the line number of the declaration (lower on
the page or screen), the higher the precedence. Hence, exponentiation
has the highest precedence, unary minus (@code{NEG}) is next, followed
-by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator
+by @samp{*} and @samp{/}, and so on. Unary minus is not associative,
+only precedence matters (@code{%precedence}. @xref{Precedence, ,Operator
Precedence}.
The other important new feature is the @code{%prec} in the grammar
@@ -2003,7 +2005,7 @@ the same as the declarations for the infix notation
calculator.
%left '-' '+'
%left '*' '/'
-%left NEG
+%precedence NEG
%right '^'
%% /* The grammar follows. */
@@ -2251,8 +2253,8 @@ Here are the C and Bison declarations for the
multi-function calculator.
%right '='
%left '-' '+'
%left '*' '/'
-%left NEG /* negation--unary minus */
-%right '^' /* exponentiation */
+%precedence NEG /* negation--unary minus */
+%right '^' /* exponentiation */
@end group
%% /* The grammar follows. */
@end smallexample
@@ -4019,7 +4021,8 @@ Bison will convert this into a @code{#define} directive in
the parser, so that the function @code{yylex} (if it is in this file)
can use the name @var{name} to stand for this token type's code.
-Alternatively, you can use @code{%left}, @code{%right}, or
+Alternatively, you can use @code{%left}, @code{%right},
address@hidden, or
@code{%nonassoc} instead of @code{%token}, if you wish to specify
associativity and precedence. @xref{Precedence Decl, ,Operator
Precedence}.
@@ -4095,7 +4098,8 @@ of ``$end'':
@cindex declaring operator precedence
@cindex operator precedence, declaring
-Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
+Use the @code{%left}, @code{%right}, @code{%nonassoc}, or
address@hidden declaration to
declare a token and specify its precedence and associativity, all at
once. These are called @dfn{precedence declarations}.
@xref{Precedence, ,Operator Precedence}, for general information on
@@ -4131,6 +4135,10 @@ left-associativity (grouping @var{x} with @var{y} first)
and
means that @address@hidden @var{op} @var{y} @var{op} @var{z}} is
considered a syntax error.
address@hidden gives only precedence to the @var{symbols}, and
+defines no associativity at all. Use this to define precedence only,
+and leave any potential conflict due to associativity enabled.
+
@item
The precedence of an operator determines how it nests with other operators.
All the tokens declared in a single precedence declaration have equal
@@ -6221,7 +6229,8 @@ shift and when to reduce.
@menu
* Why Precedence:: An example showing why precedence is needed.
-* Using Precedence:: How to specify precedence in Bison grammars.
+* Using Precedence:: How to specify precedence and associativity.
+* Precedence Only:: How to specify precedence only.
* Precedence Examples:: How these features are used in the previous example.
* How Precedence:: How they work.
@end menu
@@ -6276,8 +6285,9 @@ makes right-associativity.
@node Using Precedence
@subsection Specifying Operator Precedence
@findex %left
address@hidden %right
@findex %nonassoc
address@hidden %precedence
address@hidden %right
Bison allows you to specify these choices with the operator precedence
declarations @code{%left} and @code{%right}. Each such declaration
@@ -6287,13 +6297,63 @@ those operators left-associative and the @code{%right}
declaration makes
them right-associative. A third alternative is @code{%nonassoc}, which
declares that it is a syntax error to find the same operator twice ``in a
row''.
+The last alternative, @code{%precedence}, allows to define only
+precedence and no associativity at all. As a result, any
+associativity-related conflict that remains will be reported as an
+compile-time error. The directive @code{%nonassoc} creates run-time
+error: using the operator in a associative way is a syntax error. The
+directive @code{%precedence} creates compile-time errors: an operator
address@hidden be involved in an associativity-related conflict, contrary to
+what expected the grammar author.
The relative precedence of different operators is controlled by the
-order in which they are declared. The first @code{%left} or
address@hidden declaration in the file declares the operators whose
+order in which they are declared. The first precedence/associativity
+declaration in the file declares the operators whose
precedence is lowest, the next such declaration declares the operators
whose precedence is a little higher, and so on.
address@hidden Precedence Only
address@hidden Specifying Precedence Only
address@hidden %precedence
+
+Since @acronym{POSIX} Yacc defines only @code{%left}, @code{%right}, and
address@hidden, which all defines precedence and associativity, little
+attention is paid to the fact that precedence cannot be defined without
+defining associativity. Yet, sometimes, when trying to solve a
+conflict, precedence suffices. In such a case, using @code{%left},
address@hidden, or @code{%nonassoc} might hide future (associativity
+related) conflicts that would remain hidden.
+
+The dangling @code{else} ambiguity (@pxref{Shift/Reduce, , Shift/Reduce
+Conflicts}) can be solved explictly. This shift/reduce conflicts occurs
+in the following situation, where the period denotes the current parsing
+state:
+
address@hidden
+if @var{e1} then if @var{e2} then @var{s1} . else @var{s2}
address@hidden example
+
+The conflict involves the reduction of the rule @samp{IF expr THEN
+stmt}, which precedence is by default that of its last token
+(@code{THEN}), and the shifting of the token @code{ELSE}. The usual
+disambiguation (attach the @code{else} to the closest @code{if}),
+shifting must be preferred, i.e., the precedence of @code{ELSE} must be
+higher than that of @code{THEN}. But neither is expected to be involved
+in an associativity related conflict, which can be specified as follows.
+
address@hidden
+%precedence THEN
+%precedence ELSE
address@hidden example
+
+The unary-minus is another typical example where associativity is
+usually over-specified, see @ref{Infix Calc, , Infix Notation
+Calculator: @code{calc}}. The @code{%left} directive is traditionaly
+used to declare the precedence of @code{NEG}, which is more than needed
+since it also defines its associativity. While this is harmless in the
+traditional example, who knows how @code{NEG} might be used in future
+evolutions of the address@hidden
+
@node Precedence Examples
@subsection Precedence Examples
@@ -6355,8 +6415,8 @@ outlandish at first, but it is really very common. For
example, a minus
sign typically has a very high precedence as a unary operator, and a
somewhat lower precedence (lower than multiplication) as a binary operator.
-The Bison precedence declarations, @code{%left}, @code{%right} and
address@hidden, can only be used once for a given token; so a token has
+The Bison precedence declarations
+can only be used once for a given token; so a token has
only one precedence declared in this way. For context-dependent
precedence, you need to use an additional mechanism: the @code{%prec}
modifier for rules.
@@ -9865,7 +9925,7 @@ Specify the programming language for the generated parser.
@end deffn
@deffn {Directive} %left
-Bison declaration to assign left associativity to token(s).
+Bison declaration to assign precedence and left associativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
@@ -9900,7 +9960,7 @@ parser file. @xref{Decl Summary}.
@end deffn
@deffn {Directive} %nonassoc
-Bison declaration to assign nonassociativity to token(s).
+Bison declaration to assign precedence and nonassociativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
@@ -9920,6 +9980,11 @@ Bison declaration to assign a precedence to a specific
rule.
@xref{Contextual Precedence, ,Context-Dependent Precedence}.
@end deffn
address@hidden {Directive} %precedence
+Bison declaration to assign precedence to token(s), but no associativity
address@hidden Decl, ,Operator Precedence}.
address@hidden deffn
+
@deffn {Directive} %pure-parser
Deprecated version of @code{%define api.pure} (@pxref{Decl Summary, ,%define}),
for which Bison is more careful to warn about unreasonable usage.
@@ -9931,7 +9996,7 @@ Require a Version of Bison}.
@end deffn
@deffn {Directive} %right
-Bison declaration to assign right associativity to token(s).
+Bison declaration to assign precedence and right associativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
diff --git a/src/assoc.c b/src/assoc.c
index 2ce16f0..3ab3579 100644
--- a/src/assoc.c
+++ b/src/assoc.c
@@ -1,5 +1,5 @@
/* Associativity information.
- Copyright (C) 2002, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2005, 2006, 2008 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -41,5 +41,8 @@ assoc_to_string (assoc a)
case non_assoc:
return "%nonassoc";
+
+ case precedence_assoc:
+ return "%precedence";
}
}
diff --git a/src/assoc.h b/src/assoc.h
index d900caf..e65586f 100644
--- a/src/assoc.h
+++ b/src/assoc.h
@@ -1,5 +1,5 @@
/* Associativity information.
- Copyright (C) 2002, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2006, 2008 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -22,10 +22,11 @@
/* Associativity values for tokens and rules. */
typedef enum
{
- undef_assoc,
- right_assoc,
- left_assoc,
- non_assoc
+ undef_assoc, /** Not defined. */
+ right_assoc, /** %right */
+ left_assoc, /** %left */
+ non_assoc, /** %nonassoc */
+ precedence_assoc /** %precedence */
} assoc;
char const *assoc_to_string (assoc a);
diff --git a/src/conflicts.c b/src/conflicts.c
index 7a9f3c2..05545b2 100644
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -1,7 +1,7 @@
/* Find and resolve or report lookahead conflicts for bison,
Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
- 2007 Free Software Foundation, Inc.
+ 2007, 2008 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -285,16 +285,21 @@ resolve_sr_conflict (state *s, int ruleno, symbol
**errors, int *nerrs)
flush_reduce (lookahead_tokens, i);
}
else
- /* Matching precedence levels.
- For left association, keep only the reduction.
- For right association, keep only the shift.
- For nonassociation, keep neither. */
+ /* Matching precedence levels.
+ For non-defined associativity, keep both: unexpected
+ associativity conflict.
+ For left associativity, keep only the reduction.
+ For right associativity, keep only the shift.
+ For nonassociativity, keep neither. */
switch (symbols[i]->assoc)
{
- default:
+ case undef_assoc:
abort ();
+ case precedence_assoc:
+ break;
+
case right_assoc:
log_resolution (redrule, i, right_resolution);
flush_reduce (lookahead_tokens, i);
diff --git a/src/parse-gram.y b/src/parse-gram.y
index cae4fb7..8e3b732 100644
--- a/src/parse-gram.y
+++ b/src/parse-gram.y
@@ -115,6 +115,7 @@ static int current_prec = 0;
%token PERCENT_LEFT "%left"
%token PERCENT_RIGHT "%right"
%token PERCENT_NONASSOC "%nonassoc"
+%token PERCENT_PRECEDENCE "%precedence"
%token PERCENT_PREC "%prec"
%token PERCENT_DPREC "%dprec"
@@ -412,9 +413,10 @@ precedence_declaration:
;
precedence_declarator:
- "%left" { $$ = left_assoc; }
-| "%right" { $$ = right_assoc; }
-| "%nonassoc" { $$ = non_assoc; }
+ "%left" { $$ = left_assoc; }
+| "%right" { $$ = right_assoc; }
+| "%nonassoc" { $$ = non_assoc; }
+| "%precedence" { $$ = precedence_assoc; }
;
type.opt:
diff --git a/src/scan-gram.l b/src/scan-gram.l
index 25fac40..7e4c1f1 100644
--- a/src/scan-gram.l
+++ b/src/scan-gram.l
@@ -183,6 +183,7 @@ splice (\\[ \f\t\v]*\n)*
"%output" return PERCENT_OUTPUT;
"%parse-param" return PERCENT_PARSE_PARAM;
"%prec" return PERCENT_PREC;
+ "%precedence" return PERCENT_PRECEDENCE;
"%printer" return PERCENT_PRINTER;
"%pure"[-_]"parser" return PERCENT_PURE_PARSER;
"%require" return PERCENT_REQUIRE;
diff --git a/tests/calc.at b/tests/calc.at
index 2624908..03c8238 100644
--- a/tests/calc.at
+++ b/tests/calc.at
@@ -106,11 +106,11 @@ static void unget_char (]AT_LEX_PRE_FORMALS[ int c);
%token <ival> NUM "number"
%type <ival> exp
-%nonassoc '=' /* comparison */
+%nonassoc '=' /* comparison */
%left '-' '+'
%left '*' '/'
-%left NEG /* negation--unary minus */
-%right '^' /* exponentiation */
+%precedence NEG /* negation--unary minus */
+%right '^' /* exponentiation */
/* Grammar follows */
%%
diff --git a/tests/conflicts.at b/tests/conflicts.at
index 866b944..28a1c82 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -1,6 +1,6 @@
# Exercising Bison on conflicts. -*- Autotest -*-
-# Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
+# Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
Inc.
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -326,6 +326,62 @@ state 5
AT_CLEANUP
+## ---------------------- ##
+## %precedence suffices. ##
+## ---------------------- ##
+
+AT_SETUP([%precedence suffices])
+
+AT_DATA([input.y],
+[[%precedence "then"
+%precedence "else"
+%%
+stmt:
+ "if" cond "then" stmt
+| "if" cond "then" stmt "else" stmt
+| "stmt"
+;
+
+cond:
+ "exp"
+;
+]])
+
+AT_BISON_CHECK([-o input.c input.y])
+
+AT_CLEANUP
+
+
+## ------------------------------ ##
+## %precedence does not suffice. ##
+## ------------------------------ ##
+
+AT_SETUP([%precedence does not suffice])
+
+AT_DATA([input.y],
+[[%precedence "then"
+%precedence "else"
+%%
+stmt:
+ "if" cond "then" stmt
+| "if" cond "then" stmt "else" stmt
+| "stmt"
+;
+
+cond:
+ "exp"
+| cond "then" cond
+;
+]])
+
+AT_BISON_CHECK([-o input.c input.y], 0, [],
+[[input.y: conflicts: 1 shift/reduce
+input.y:12.3-18: warning: rule useless in parser due to conflicts: cond: cond
"then" cond
+]])
+
+AT_CLEANUP
+
+
## -------------------------------- ##
## Defaulted Conflicted Reduction. ##
## -------------------------------- ##
@@ -878,7 +934,7 @@ AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state
1$/p']], 0,
13 empty_c3: . ['c']
'b' shift, and go to state 1
-
+
'c' reduce using rule 13 (empty_c3)
$default reduce using rule 9 (empty_a)
--
1.6.0.2.588.g3102
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [PATCH] Add %precedence support.,
Akim Demaille <=