From d78f0ac9d8c8830542faf9d00d0b6ef652dda45e Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Thu, 7 Aug 2008 23:15:34 +0200 Subject: [PATCH] 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. --- 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 be1ab02b..757e1fd0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,25 @@ +2008-11-10 Akim Demaille + + 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 Make benches in a sub dirs. diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 09ca7ab1..ebb37ca6 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}, +@code{%precedence}, 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 +@code{%precedence} 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 @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is considered a syntax error. +@code{%precedence} 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 -@findex %right @findex %nonassoc +@findex %precedence +@findex %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 +@emph{can} 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 -@code{%right} 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. +@node Precedence Only +@subsection Specifying Precedence Only +@findex %precedence + +Since @acronym{POSIX} Yacc defines only @code{%left}, @code{%right}, and +@code{%nonassoc}, 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}, +@code{%right}, 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: + +@example +if @var{e1} then if @var{e2} then @var{s1} . else @var{s2} +@end 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. + +@example +%precedence THEN +%precedence ELSE +@end 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 grammar@dots{} + @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 -@code{%nonassoc}, 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 +@deffn {Directive} %precedence +Bison declaration to assign precedence to token(s), but no associativity +@xref{Precedence Decl, ,Operator Precedence}. +@end 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 2ce16f0b..3ab3579f 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 d900caff..e65586ff 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 7a9f3c22..05545b20 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 cae4fb7b..8e3b7320 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 25fac402..7e4c1f10 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 26249088..03c8238f 100644 --- a/tests/calc.at +++ b/tests/calc.at @@ -106,11 +106,11 @@ static void unget_char (]AT_LEX_PRE_FORMALS[ int c); %token NUM "number" %type 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 866b9441..28a1c82c 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) -- 2.45.2