This project is read-only.
2
Vote

Bug: Corner case in precedence handling in fsyacc

description

From FSBugs
 
 
Dear F#ers,
 
Is it possible that there is a bug in fsyacc (October 2008 CTP)?
 
The fixity directive
 
%nonassoc GT LT GE LE
 
in the attached NonAssocBug.fsy file seems to be ignored, and fsyacc reports shift/reduce conflicts as follows:
 
state 14: shift/reduce error on GT
state 14: shift/reduce error on LT
state 14: shift/reduce error on GE
state 14: shift/reduce error on LE
state 15: shift/reduce error on GT
state 15: shift/reduce error on LT
state 15: shift/reduce error on GE
state 15: shift/reduce error on LE
state 16: shift/reduce error on GT
state 16: shift/reduce error on LT
state 16: shift/reduce error on GE
state 16: shift/reduce error on LE
state 17: shift/reduce error on GT
state 17: shift/reduce error on LT
state 17: shift/reduce error on GE
state 17: shift/reduce error on LE
 
Here's an excerpt from the attached NonAssocBug.fsyacc.output file:
 
state 14:
items:
 Expr -> Expr . 'PLUS' Expr
 Expr -> Expr . 'MINUS' Expr
 ...
 Expr -> Expr . 'GT' Expr
 Expr -> Expr 'GT' Expr .
 Expr -> Expr . 'LT' Expr
 Expr -> Expr . 'GE' Expr
 Expr -> Expr . 'LE' Expr
 
actions:
 ...
 action 'GT' (explicit nonassoc 9997):   shift 25
 action 'LT' (explicit nonassoc 9997):   shift 26
 action 'GE' (explicit nonassoc 9997):   shift 27
 action 'LE' (explicit nonassoc 9997):   shift 28
 action 'PLUS' (explicit left 9998):   shift 18
 action 'MINUS' (explicit left 9998):   shift 19
 
which shows that fsyacc prefers a shift action on GT LT GE LE.
 
But really there should neither be shift nor reduce in those cases, only an error transition, because the point of %nonassoc is to disallow
 
e1 > e2 > e3   and   e1 > e2 < e3
 
and so on.
 
I faintly recall fixing similar associativity bugs in mosmlyac (based on a very old camlyacc) back in the 1990'es, but no details...
 
Best regard,
 
Peter

comments