Hello everyone,
My name is Valentin Tolmer, and I'm a student at the EPITA (a computer
science school in Paris). I did an internship in January with Akim
Demaille, to work on the precedence and associativity in Bison. This led
to a small improvement : warnings for unused precedence and
associativity in grammars.
I also started (but haven't finished yet) working on a graph tool to
show in a clear way exactly what precedence relationships between tokens
are used. All of that in order to simplify the precedence declarations
and to detect unwanted conflict resolutions.
I am now working in a Google Summer of Code with the same objective, but
this time with a bigger goal : introducing a new syntax for the
precedence/associativity declaration part allowing for partial orders.
The final idea is to be able to specify only the relationships used, to
make the grammar clearer and to encourage reflexion about each
relationship and the conflicts it solves.
So far, my work with Akim Demaille has led me to these considerations :
- We need to be able to prioritize one rule over another, not only one
token over another
- We need to be able to give associativity specifically to a rule, not
only to tokens
- We need to be able to declare partial order priorities
- And, of course, backwards compatibility
Please find attached an example of the new syntax (subject to further
modification, of course).
I'm happy to start working on Bison again, and hope to have a great time
with you!
Valentin Tolmer
/* Example grammar for the new syntax. */
%token NUM TRUE FALSE THEN
/* Regular declaration of operators, no precedence relations with other
* operators from the groups.
* Associativity declaration is kept for defaults, but we're moving to remove
* it completely. */
%left IF
%precedence ELSE
/* Declare a group of operators named arithmetics, inside which the order is
* total. */
%prec arithmetics {
%prec bin_ops {
%precedence { '+' '-' }
%precedence '*' '/'
%prececedence '^'
}
%precedence UNARY
}
/* Declare another group of operators, no links with the first one */
%prec bool_ops {
%precedence OR
%precedence AND
%precedence NOT
}
%prec dummy {
%left DUMMY
}
%precedence A
%precedence B
%precedence C
%precedence D
%precedence E
/* Declare extra precedence relations to resolve conflicts. */
%prec AND > '+' /* non transitive operator */
%prec IF > AND
%prec IF > AND > '+' /* equivalent */
%prec ELSE >> arithmetics /* transitive operator */
%prec arithmetics >> dummy
%prec A >> B > C >> D >> E
/* Examples of what is declared:
- '+' == '-' Usual same-line declaration
- '+' < '*' Transitivity inside a group
- IF < ELSE Transitivity for general declarations (retro-compatible)
- AND > '+' Extra precedence declarations
- ELSE > '+' Development of the group precedence relation between ELSE and
arithmetics
- '+' > dummy Development of the group precedence relation between dummy
and arithmetics
- ELSE > dummy Transitivity for operator >>
- C > E Idem
Examples of what is not:
- '+' <> OR No links between groups
- IF <> UNARY No links between a group and the general declarations
- IF <> '+' No transitivity of the order relation If > AND > '+'
(operator >)
- B <> D Rupture of the transitivity chain with the operator >
*/
%%
stmt:
exp
| IF bool THEN exp
| IF bool THEN exp ELSE exp
;
exp:
NUM
| exp '+' exp
| exp '-' exp %left /* not necessary, as a default is present */
| exp '*' exp
| exp '/' exp %right /* change associativity for this rule */
| exp '^' exp
| '-' exp %right %prec UNARY
;
bool:
TRUE
| FALSE
| bool AND bool %left /* necessary, as it is not specified at the declaration
level */
| bool OR bool %left
| NOT bool
;
